Giới thiệu về cấu trúc dữ liệu và giải thuật

Tài liệu tham khảo về giới thiệu về cấu trúc dữ liệu và giải thuật - môn Khoa học máy tính
Nội dung trích xuất từ tài liệu:
Giới thiệu về cấu trúc dữ liệu và giải thuật Bài 1: Gi i thi u v c u trúc d li u và gi i thu t (Introduction to data structures and algorithms) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com C u trúc d li u (data structure)- C u trúc d li u là gì? C u trúc d li u là cách t ch c lưu gi d li u trong sao cho hi u qu nh t- Th nào là hi u qu ? 1. “Chính xác” 2. Dùng ít b nh 3. Kh năng tìm ki m/truy xu t 4. Kh năng c p nh t, thêm b t (modification, insertion / deletion) 5. ðơn gi n, d hi u- Các ki u c u trúc d li u cơ b n • B n ghi (struct) • Danh sách (array) • Danh sách liên k t (list) • Cây (tree) • B ng băm (hash table) Thu t toán (algorithm)• Thu t toán là gì? Thu t toán là m t phương pháp bao g m m t dãy các bư c tính toán ñ gi i quy t m t bài toán. Thu t toán có th ñư c di n t dư i d ng ngôn ng t nhiên (ti ng Vi t, ti ng Anh…) hay ngôn ng l p trình (C++, Java…)• Th nào là m t thu t toán t t? 1. “ðúng ñ n” 2. Nhanh 3. Ít b nh 4. ðơn gi n, d hi u Ví d 1: S p x p danh sách tuy n sinhNăm 2008, ð i h c Công Ngh có N thí sinh tham gia tuy n sinh, hãy vi t chương trình s p x p các thí sinh theo th t gi m d n c a t ng ñi m thi ba mônVí d :Stt H tên Toán Lý Hóa T ng1 Tr n Anh Tu n 7 8 7 222 Bùi Ng c Thăng 10 10 9 293 Lê S Vinh 10 8 8 264 Nguy n Th Ánh 8 10 9 27 S p x p n i b t (bubble sort)Ý tư ng: L n lư t duy t qua danh sách thí sinh, n u hai thí sinh không ñúng th t , ñ i ch hai thí sinh. L p l i quá trình trên cho ñ n khi danh sách ñư c s p x p Step 0 Step 1 Step 31. (Tu n, 22) 1. (Thăng, 29) 1. (Thăng, 29)2. (Thăng , 29) 2. (Tu n, 22) 2. (Vinh, 26)3. (Vinh, 26) 3. (Vinh, 26) 3. (Tu n, 22)4. (Ánh , 27) 4. (Ánh, 27) 4. (Ánh, 27) Step 4 Step 51. (Thăng, 29) 1. (Thăng, 29)2. (Vinh, 26) 2. (Ánh, 27)3. (Ánh, 27) 3. (Vinh, 26)4. (Tu n, 22) 4. (Tu n, 22) S p x p n i b t (bubble sort)Function bubbleSort (A : danh sách thí sinh) { swapped := false; do swapped := false; for each i = 1 to N – 1 do if A[i].diem < A[i + 1]. diem then { swap (A[i], A[i+1]); swapped := true; } done; while (swapped = true)} Ví d 1’: S p x p danh sách website (google search)Google có danh sách N website. Website x có m t ñ ưu tiên là f(x). Hãy s p x p các website trên theo ñ ưu tiên gi m d nCâu h i: Có th dùng bubble sort không?Tr l i: ðư c, nhưng không hi u qu Ví d 2: Danh b ñi n tho iVi t m t chương trình qu n lý danh b ñi n tho i c a toàn b thành ph Hà N i, sao cho các thao tác sau ñư c hi u qu nh t:1. Ki m tra m t s ñi n tho i2. Thêm m t s ñi n tho i3. Xóa m t s ñi n tho i Ví d 3: Tìm ñư ng ñi t t nh t• Xây d ng h th ng ph n m m ch ñư ng ñi t t nh t cho ngư i dùng 1. ðư ng ñi ng n nh t 2. ðư ng ñi qua ít ñèn xanh – ñèn ñ nh t 3. ðư ng ñi ít t c nh tVí d 3: Tìm ñư ng ñi t t nh t (google map)Ví d 3: Tìm ñư ng ñi t t nh t (google map) Ví d 4: Xây d ng h th ng t ñi nVi t chương trình t ñi n Anh – Vi t, cho phép th c hi n các thao tác sau: 1. Tìm m t t 2. Thêm m t t 3. Xóa m t t 4. S a m t t 5. Tìm t ñ ng nghĩa Ví d 5: Ngư i bán hàng traveling salesman problem (TSP)M t ngư i bán hàng c n ñ n thăm N khách hàng N ñ a ñi m khác nhau. Tìmm t hành trình cho ngư i bán hàng trên sao cho: 1. M i ñ a ñi m thăm ñúng 1 l n, sau ñó quay v ñi m xu t phát 2. T ng chi phí ñi l i là ít nh t Ngư i bán hàngThu t toán: Thăm ñ a ñi m g n nh t (nearest neighbor tour) T ñi m xu t phát, l n lư t ñi thăm các ñi m theo quy t c: “ð n thăm ñi m chưa ñư c thăm g n v i ñi m hi n t i nh t” Ngư i bán hàngNearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1ðương ñi t i ưu: 1→2 →3→4 →5 →6 →8→7→X→9→1Các ví d khác (10’) Th nào là m t chương trình t t?1. ðúng ñ n2. Hi u qu3. D hi u4. D tìm l i5. D thay ñ i và nâng c p“Thu t toán + C u trúc d li u = Chương trình” N. Wirth D li u• D li u là nh ng thông tin mà máy tính có th x lý: s nguyên, s th c, xâu kí t , và các d li u ph c t p ñư c t o t nhi u thành ph n• Trong b nh máy tính, d li u ñư c ...