Xây dựng video bài giảng môn học cấu trúc dữ liệu và giải thuật

THUYET MINH DE TAT KHOA HOC VA CONG NGHE CAP TRUONG NAM 2022 Khoa học Khoa học Kỹ thuật CỮU | Tu nhién và Công nghệ Cơ Ứng Triển Khoa học Khoa học _ Nông bản dụng khai VY VY; dược Aen,

; ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP

Chủ nhiệm đề tài: ThS Nguyễn Thị Hương

THÁI NGUYÊN, NĂM 2022

THUYET MINH DE TAT

KHOA HOC VA CONG NGHE CAP TRUONG NAM 2022

Khoa học Khoa học Kỹ thuật CỮU |

Tu nhién và Công nghệ Cơ Ứng Triển Khoa học Khoa học _ Nông bản dụng khai

VY VY; dược Aen, nhiên nghiệp

Don-vi công tác và Nội dung

1 Họ và tên nghiên cứu cụ

Chữ ký lĩnh vực chuyên môn | thể qược giao

Nội dung phối hợp nghiên cứu Họ và tên người

đại diện đơn vị

9 TONG QUAN TINH HINH NGHIÊN CỨU THUOC LINH VUC CUA DE TÀI Ở TRONG VÀ NGOÀI NƯỚC

9.1 Trong nước: Hiện tại trên youtube, mạng xã hội có rất nhiều video bài giảng liên quan _— | đến học phần Cấu trúc dữ liệu và giải thuật Tuy nhiên, các video này thường không đầy đủ

bày về các nội dung chính của bài học theo đề cương chương trình giảng dạy là v6 cing can

thiếtcho sinh viên đặc biệt là trong giai đoạn giảng dạy onlime:

+ của đề t tài trên thể

dẫn khi đánh giá tổng quan)

†9-3: Đanh mục các công trình đã-công bố thuộc lĩnh-vực của đề tài-của-chú-nhiệm-và những:

- hành viên tham gia nghiên cứu (họ và tên tác giả; bài -báo;- ấm phẩm; -các yếu tố về xuất | —-

11 MUC TIEU BE TAI

Đề tài xây dựng 24 video bài giảng tương ứng với 45 tiết học của sinh viên Mỗi tiết học được cô đọng giảng dạy để sinh viên có thể năm được tống thể nội dung của bài học và

chuẩn bị bài trước khi đến lớp

13 CÁCH TIẾP CẬN, PHƯƠNG PHÁP NGHIÊN CỨU

13.1 Cách tiếp cận: Video sẽ bám sát vào để cương, bài giảng học phần

13.2.Phương pháp nghiên cứu: Quay video và giảng trên phần mềm Power Point

An quy kaos „| Bản thuyết minh và

¡ | Xâ dựng thuyết minh để Í (tự toán kinh phí của Si,

tài đề tài 04/2022 Nguyên Thị Hương

2 wi _— _ File trình chiếu [05/2022 —) vấn Thị Hươn

E6 Powerpoint |06/2022 guych VN L0WGHệ

Powerpoint cho môn học

Ghi hình các bài giảng a 07/2022 — x x

3 chương 1,2 Video 08/2022 Nguyễn Thị Hương

Ghi hình các bài giảng 09/2022 — * sar

4 chương 3.4 Video 10/2022 Nguyên Thị Hương Ghi hình các bài giảng x :

5 chương 5,6 Video 11/2022 Nguyễn Thị Hương

ø | Ghỉ hình các bài giảng Video 12/2022 | Nguyễn Thị Hương

Yéu cau chat trong san pham

- - (mô tả chỉ tiết chất lượng vân

Stt Tén san pham SỐ lượng phẩm đạt được như nội dung,

- 7U SƠ 1UUQHE VIdcCO

Í- Bài giảng bám sát Đề cương chỉ

21 Video bai giảng học phần cầu 24 video tết học phân Câu trúc đỡ liệu và

trúc dữ liệu và giải thuật giải thuật

- Chất lượng hình ảnh và âm thanh được đảm bảo

16.1 Phương thức chuyển giao: Bộ video bài giảng sẽ được chuyển giao cho Bộ môn Tin

học Công Nghiệp, Khoa Điện tử, trường Đại học Kỹ thuật Công nghiệp

16.2 Địa chỉ ứng dụng:-Trường Đại học Kỹ thuật Công nghiệp

17 TÁC ĐỌNG VÀ LỢI ÍCH MANG LẠI CỦA KÉT QUÁ NGHIÊN CỨU

17.1 Đối với lĩnh vực giáo dục và đào tạo:

- Có thể sử dụng như các bài giảng trong Đào tạo trực tuyến, từ xa

- Sinh viên có thể học trên các video theo thời gian chủ động và không giới hạn số lần Do đó sinh viên có thê xem trước bài giảng và đến giờ học trao đối, thảo luận sâu hơn

với giáo viên

_17.2 Đối với lĩnh vực.khoa học và công nghệ có liên quan

-17:3: Đối với phát triển kinh tế-xã hội

17.4 Déi với tổ chức chủ trì và các cơ sở ứng dụng kết quả nghiên cứu

————}—_ Cé thể khai thác; sử dụng phục vụ cho công tác Đào tạo từ Xâ ———————

- Góp phan xây dựng, hoàn thiện bộ học liệu phục vụ giảng dạy / học tập trong Nhà trường

- Đảm bảo và nâng cao chất lượng đào tạo trong Nhà trường trong bối cảnh dịch bệnh Covid-19

MÔN CAU TRÚC ĐỮ LIỆU VÀ GIẢI THUẬT

Xác nhận của tô chức chủ trì Chủ nhiệm đề tài

THÔNG TIN KÉT QUẢ NGHIÊN CỨU

1 Thông tin chung:

- Tên đề tài: Xây dựng video bài giảng môn Cấu trúc dữ liệu và giải thuật

>t

_- Co quan cht tri: Truong Dai hoc Ky thuat Cong nghigp——

_ - Thời gian thực hién: Thang 3/2022— /2023

2 Mục tiêu: Đề tài xây dựng 24 video bài giảng Mỗi video được cô đọng giáng

_——— dạy từ 8~20.phút, tùy nội-dung cần trình bày để sinh viên có thể nắm được tông

—~—— thể nội dung của bài hợc và chuẩn bị bài trước khi déntép ——— -~ ~ —~-

3 Kết quả nghiên cứu: 24 video

GIỚI THIỆU

1 Lý do chọn đề tài

Học phần Cấu trúc dữ liệu và giải thuật là học phần cơ sở được giảng dạy cho ——— sinh viên khối ngành kỹ thuật Đây là học phần sinh viên cần học tập, làm bài tập, xây

dựng phần mềm trên máy tính vì vậy việc xây đựng viđeo trực quan, sinh động, giúp

" sinh viên hiểu bài là rất cần thiết, giúp sinh viên có thể chủ động chuẩn bị bài học ở

viên

Bên cạnh đó, giảng viên có thể giảm thời gian trình bày lý thuyết, tăng cường,

hướng dẫn thực hành, mở rộng số lượng bài tập cho sinh viên, giúp sinh viên hiểu bài =

hơn

2 Mục tiêu của đề tài

Mục tiêu của đề tài là xây dựng video bài giảng cho học phần Cấu trúc dữ liệu

và giải thuật

322 IDiễn giải và bảo vệ các kết quả thực hiện bải tập nộp, 4

~~ bài kiểm tra một cách khoa học, chuyên nghiệp

Xây dựng chương trình từ thuật toán

M3 4.1.3 Phat trién chương trình phần mềm i

—_ - Mô Tả tón tat hoe phar

ô chức và những thao tác cơ sở trên từng cầu trúc đữ liệu, kết hợp với việc phát triển tư duy giải thuật để hình thành nên chương

trình máy tính, Công cụ được sử sử dụng là các ngôn ngữ lập trình cấp cao như: Pascal, ——————]

C Crt ; Các khái niệm: câu trúc dit liệu, giải thuật, Các phương pháp thiết kế giải

Chương 1 Mở đầu (3, 0, 6) (ghi chi: số tiết học trên Giảng, Thảo

lóp/số tiết thí nghiệm, thực hành/số tiết tự học) luận, Hướng

dẫn bài tập

l4 Nội dung giảng dạy - học tập [1].{21.13]

Nội dung giảng day:

E Giải thuật và câu trúc đữ liệu

- Cầu trúc dữ liệu và các vẫn đề liên

quan

12 [ Ngôn ngữ diễn đạt giải thuật 1.2.1 Các câu hình tô hợp đơn giản

INội dung học tập ở nhà:

- Học lại kiến thức đã được học

- Tìm hiểu thêm các thuật toán

IB Noi dung thực hành, thí nghiệm: (nếu Giảng lkhông có ghỉ ` “không `) Không -

Chương 2 Phân tích và thiết kế (3, 0, 6) (ghi chil; số

tiết học trên lóp/số tiễt thí nghiệm, thực hành/Số tiết tự hoc)

- Học lại kiến thức đã được học

12.1 2.1.1 1-2

INới “hing giảng day:

Các khái niệm cơ bản về cây

- Cây tổng quát, cây nhị phân: —

A Nội dung giảng dạy - học tập [2151 Giảng

VOI đụng học tập ởnhà”

IB Noi dung thực hành, thí nghiệm: (néu

Nội dung học tập ở nhà:

Học lạt: kiến thức đã được học

A Nội dung giảng dạy - học tập

- Định nghĩa và các khái niệm về đồ

2.1.1 2.1.2 1.2.1 7]

L Học lại kiến thức đã được học hông có ghỉ “không ”) Không

A Nội dung giảng dạy - học tập

- Một sô phương pháp sắp xếp đơn giản

- Sắp xếp kiéu phan doan (Quick sort)

b Sắp: xếp 'kiêu vun đống (Heap sort) ~

IB Nội dung thực hành, thí nghiệm: (néu

1.21

2.11 2.1.2

thận xét và đưzra kêt luận về hiệu quả; độ phức tạp

của các thuật toán và chương trình 10

3 IĐánh giá

Sángtạo ‘Dé xuất thuật toán cải tiên chơ bài toán cụ thé 5

Ghỉ chú: Nội đụng này nhằm phục vụ xây đựng, cẩu hoi kiém tra qua Trình, Ngân hang câu hỏi thì, đề thị kết thúc học phần và đánh giá kết quả kiểm tra hoặc thị

- Bộ môn: Tin học Công nghiệp

- Giảng viên giáng dạy chính:(Yêu cầu mỗi HP phải bỗ trí tỗi thiểu từ 02 giảng

viên giảng dạy chính)

1 ThS Nguyễn Thi Huong Email:huongktpm@tnut.edu.vn

3 Thể » Ping Thị Hiên °n BmaildangtiiMlendjimuicd.vn

5 ThS Tran Thi Thanh Email:tranthithanh@tnut.edu.vn

6 ThS Đỗ Duy Cốp Email:duycop@tnut.edu.vn

1.2 Đối tượng sử dụng

Video bài giảng sẽ được sử dụng làm tài liệu giảng dạy cho các Thầy, cô

của bộ môn và làm tài liệu học tập cho toàn bộ sinh-viên khối-ngành kỹ thuật

CHƯƠNG 2: TRIÊN KHAI THỰC HIỆN

2.1 Phương pháp triển khai

e Số lượng video: Đối với học phần Cấu trúc dữ liệu và giải thuật, việc Xây

———dựng video được _ bám sát theo yêu cầu của đề cương môn học Tuy nhiên, mỗi

_— —— — video không xây đựng theo toàn bộ tiết học, mà lựa chọn những nội đưng trọng

tâm nhất để xây dựng video Số lượng video của học phần này là 24 video có độ

đài từ 08 — 20 phút

e Bố cục video: Mỗi video sẽ diễn giải về một nội dung riéng trong Ứng với

_ chinh:

> _ Lý thuyết: : Giảng viên giảng bai trén file PowerPomt

> Bai tập về nhà: bên cạnh việc › hiểu được lý thuyết, biết cách viết mã _ lệnh theo hướng dẫn của giảng viên, sinh viên còn cần biết ứng đụng các nội

dung đã học dé lam bai tap Cac bài tập về nha được đưa1a sát với nội dung học;

giúp sinh viên hiểu hơn về những nội dung đã học

e Nội dung video: Bam sát đề cương môn học

Nội dung | Tén video BG ~ _ NOi.dung video Thời lượng | Đánh |

chỉ tiết

Chương 1 | Bai giang Chương I: MỞ ĐẦU 10p

MỞ ĐẦU | Video _Chuongl CTDL&G | 1 Giải thuật và cầu trúc

T_Nguyen Thi Huong dữ liệu

— Chương 2—† Bai-giang Chương II: THIET KE 7-15 phut —

THIẾT | Video - Chuong2 1 CTDL | VÀ PHÂN TÍCH mỗi viđeo

KÉVÀ | &GT Nguyen Thi Huong 1 Tir bai toán đến PHAN Bai giang chuong trinh

10

Bai giang Video_Chuong6.5_CTDL

&GT_ Nguyen Thi Huong

Chuong 7 | Bai giang Chương VIE LY | 8-20 pit

LY Video_Chuong71_CTDL | T HUYET DO THI moi-video THUVET | &GT_Neuyen Thi Huong |1 Định nghĩa và các

DO THI | Bải giang khái niệm về đồ thị

Video Chuong?7.2 CTDL †2 Đồ thị vô hướng, đồ

&GT_Nguyen Thi Huong thị có hướng Bai giang 3 Đường đi, chu trình

Videe_Chueng7.3_CTDL Đề thị liên thông

&GT_ Nguyen Thi Huong |4 Cây và cây khung của _— -HBaigiang ——-————|_-đềti_ _ | |

¬ Video_Chuong7.4_CTDL } —_. . _| _._ —

&GT Nguyen Thi Huong

Chương 8 | Bai giang video chuong | Chuong VIII: SAP XEP | 8-20 phit

Thi Huong

Bai giang video_chuong

8.2_CTDL&GT_Nguyen Thi Huong

Bai giang video_chuong

8.3_CTDL&GT_Nguyen Thi Huong

Chuong 9 | Bai giang Chương IX: TIM KIEM 10p

TÌM Video _Chuong9_CTDL&G 1 Dat van dé KIEM T_Nguyen Thi Huong 2 Tim kiém tuan tự

CHUONG 4: KET LUAN

4.1 Kết luận

se———— Đề tài xây dựng video bài giảng cho học phần Cấu trúc dữ liệu là một đề

—————— tài triển khai-theo đặt hàng của nhà

x teed DA th nha ak tah af à trường- Đề- tải này-có-tính-ứng-dụng-cao; là

‘

Az 4 +44 sà: 1 A h +: an +h ¬ nh : ws cn một tài liệu học tập tốt cho sinh viên Giúp nâng cao tính tự giác; tự nghiên cứu

của sinh viên

Hoàn thiện, chỉnh sửa chất lượng video cho tốt hơn Bồ sung thêm các nội

1.2 Các tính chất của thuật toán

+ Nhập (input): Các thuật giải có các giá trị nhập (input - -

values) từ một tập hợp nhất định nào đó

- Xuất (output): Từ mỗi tập hợp các giá trị được nhập một

thuật toán thường tạo ra những giá trị xuất (output

values) thuộc một tập hợp nhất định nào đó thể hiện lời

giải cho bài toán

_ ®-Tính xác định (definiteness): Các bước trong thuật toán phải

_ Giải thuật timMax(1, n)

Input: Mang A, som n sỐ nguyên _

A a Ue Nate eee Wik 12-

Diễn đạt giải thuật

Các nút biểu diễn giải thuật bằng sơ đồ khối

3 esle if delta = 0 then

Xuất kết quả: phương trình có nghiệm kép là -b /

(2*a)

4 else { trường hợp delta < 0}

_ Xuất kết quả: phương trình vô nghiệm; _

KHOA ĐIỆN TỬ @

Module hoa Và VIỆC giải quyết bài toán _ —

“Cc

s Để thực hiện chiến thuật này, thường có

~~ hai cach thiết kế: — — TT

1.Từ trên xuống (Top-Down Design)

2.Tinh chỉnh từng bước —————————————]

Ví dụ: Bài toán sắp xêp một dãy n sô,

theo thu tu tang dan ~~ "

° Chọn sô bé nhât trong n sô đê vào vị trí thứ 1

s Chọn số bé nhất trong n-1 số còn lại

đề vào vị trí thứ 2

- Chọn số bé nhất trong 2 số còn lại để

PHÂN TÍCH GIẢI THUẬT

—“¬- ~ huật được xây + dựng, hàng loạt ———]

_* Yêu cầu về tính đúng dan cua giải thuật

5 Tính đơn giản của giải thuật -

‹ Yêu cầu về không gian :

PHAN TICH GIAI THUAT

Giải quyết bài toán

‹ Phải đứng trước việc lựa chọn giải thuật

nào 2

¢ Dwa trên cơ sở nào đê lựa chọn ?

KHOA ĐIỆN TỪ 8

—— Độ phức tạp của thuật toán

_— * Độ phức tạp của thuật toán được thể hiện qua khối lượng |

— thời gian và không gian để thực hiện thuậttoán —— _

_ việc đưc ưƯỢC:

“Trong phần nầy chúng ta chỉ đề cập đến độ phức tap —

về thời gian của thuật toán

Độ phức tạp của thuật toán

vào số lượng thao tác được sử dụng

trong thuật toán và số lượng thao tác nay

phụ thuộc vào cỡ (size) của dữ liệu nhập

¢Ta con gọi độ phức tạp thời gian của

KHOA ĐIỆN TỪ @à

DO PHUC TAP CUA THUAT TOÁN

—— _ Trong thuật toán - nếu ta xem - thời - gian -——

——— thực hiện thuật toán là số lần Thực hiện _ _— ‡

phép so sánh hay phép gán thì thời gian

thực hiện thuật toán trong trường hợp xâ

DO PHUC TAP CUA THUAT TOAN

Thời gian thực hiện thuật toán trong trường hợp tốt

nhất là:

T(n) = 1+(n-1) =n

Ký hiệu O

Ví dụ 2: Đánh giá độ phức tạp (thời gian) của thuật

toán tìm kiêm tuyên tính

_ —— Thời gian thực hiện thuật toán trong trường h tốt

_ nhât lã: O(1) _ 7 ° „

In 0 v00) 0 CÔNG nts HIỆ

KHOA ĐIỆN TỬ 8

Thiết kế giải thuật đệ quy

Ưu nhược điểm của đệ quy

- _—— Mộtsố dạng giải thuật đệ quy

THUẬT CÔNG NGHIỆP

CHUONG 3:DE QUI _„

VA GIAI THUAT DE QUI

lêu bài toán T được thự chỉ én Tt b

giải của bài toán T ˆ có dan ng gidng T là

- lời giải đệ quy - - |

Giải thuật tương ứng với lời giải như /

vậy gọi là giải thuật đệ quy

Giải thuật đệ quy

Ví dụ: Xét bài toán tìm một từ trong quyển từ điển:

If (từ điển là một trang)

tìm từ trong trang này

else {

Mở từ điển vào trang ' giữa"

fi Xác định xem nửa nào của từ điển chứa từ cần ìm;

if (từ đó nằm ở nửa trước)

a tìm từ đó ở nửa trước

_—_— else tìm từ đó ở nửa sau.

Vi dụ 1 : Ham Fact(n) tinh số hạng n của

_— đấyn†, định nghĩa như sau:

Ví dụ 2: Tính số hạng thứ n của dãy Fibonaci

được định nghĩa như sau:

Ưu điểm của dé quy

- Sáng sủa, dễ hiểu, nêu rõ bản chất van đề 3

° Tiết kiệm thời sian Tiện thực mã nguồn— —-

Nhược điểm của đệ quy

_=Tốn nhiêu bộ nhớ, thời gianthực thilâu -

———— Chuyển dian tir A sang C —

Chuyên (n-1) đĩa từ B sang C, À

làm trung gian 4:

sơ, CHƯƠNG 3; : DE QUT ^

KHOA ĐIỆN TỬ @%

Mỗi phần tử của mảng ngoài giá trị

biểu hiện thứ tự của nó trong mảng Có

mảng 1 chiều, 2, 3 chiều n chiều

thường xuyên tác động lên danh sách

—— Một danh sách mà quan hệ lân cận giữa

— 4.2 Cấu trúc lưu trữ của mảng

phân: t tử ah 1<= j<= n chiếm c từ máy

_ thì nó sẽ được lưu trữ trong cn tu

Sequential storange allocation)

LO: địa chỉ gốc (là địa chỉ của từ máy đầu

tiên trong miền nhớ kế tiếp dùng để lưu

trữ véc tơ ) Địa chỉ ai sẽ được tính bởi:

Loc(ai) =LO + c*(i-1)

trong pham vi hep

A rasƯ TT”

_ Ma trận biểu diễn nhiều phần tử 0 gây ra sự

“lang phí bộ nhớ Gọi là ma trận thưa

4.3 Lưu trữ kế tiếp của d/s tuyến tính

Do số phần tử của d/s tuyến tính thường biến

động nên việc lưu trữ chỉ đảm bảo được nếu

biết được m = max (n), (n- kích thước d/5)

Gây lãng phí bộ nhớ vì có hiện tượng “Giữ chỗ

Tgiảm 1: Khiloarbỏ-+phân n từ ra khỏi stack -

T=0: Khi stack rỗng TT ees

Stack=array[0 'MaxStack] of Item;

ử Stack bằng một véc tơ lưu phần tử nhớ kế tiếp

Top= MaxStack;

~~ Cae thao hccobintrén stack; —

—— *Stack: khởi tạo Stack rong —

- ets y_kiém tra Stack r6ng-?~—

-|sFull: kiêm tra Stack day ?

*Push: them 1 phan-tte-vao-dinh =~

Stack, có thể làm Stack day

return true; // Stack day

return false; // Stack chua day

Thêm một phần tử vào Stack

boolean Push(int newitem)

KHOA ĐIỆN TỬ @@À

Queue là 1 cấu trúc dữ liệu:

~~ Gồm nhiêu phân tử có t nue tu —

- Dùng † số nguyên (QMax) để lưu số phần tử tối đa trong hàng đợi

° Dùng 2 số nguyên (QFront, QRear) để

xác định vị trí Đâu, Cuối hàng đợi

° Dùng, 1 số nguyên (QNumltems) để

S Khai báo lớp Queue _

—— nguyên (nt)- ————

private int []QArray, ,

_privateintQMax, 7777

private int QFront;

Khai báo lớp Queue

/¡ Khởi tạo Queue chứa các phân tử

kiêu nguyên (int)

public Queue(int size) {

QArray = new int[size];

QMax = size;

QNumltems = 0; // chưa có phan tt pao-trong Queue 4

KÈỀỒ\ TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP KHOA ĐIỆN TỬ /@

Queue ra 1 phần tử ở dau Queue

boolean Take(int itemout)

{if (IsEmpty()) return false; // Queue rỗng, không lấy ra

được

itemout = QArray[QFront]; / láy phần tử đâu ra

QFront++;

QNumltems ;

" -if (QFront==QMax) // nếu đi hết mảng

— QFront= QRear = -1;// quay tro về đầu mảng _

return true; lấy thành công

Ầ J

_— Danh sách móc nội cũng gôm- nhiêu phan —

Khái niệm về danh sách móc nối

-Danh sách móc nối (linked list) là một cau

trúc dữ liệu bao gồm một nhóm các nút (nodes)

tao thành một chuỗi Thông thường moi nút

gôm đữ liệu (data) ở nút đó và tham chiếu

_ (reference) đ đến nút kế tiếp trong chuỗi