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)

Nội dung text: 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)

1. Bài 1 : Gii thiu v cu trúc d liu và gii thut (Introduction to data structures and algorithms) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Cu trúc d liu (data structure) Cu trúc d liu là gì? Cu trúc d liu là cách t chc lưu gi d liu trong sao cho hiu qu nht Th nào là hiu qu? 1. “Chính xác” 2. Dùng ít b nh 3. Kh năng tìm kim/truy xut 4. Kh năng cp nht, thêm bt (modification, insertion / deletion) 5. ðơn gin, d hiu Các kiu cu trúc d liu cơ bn • Bn ghi (struct) • Danh sách (array) • Danh sách liên kt (list) • Cây (tree) • Bng băm (hash table)
3. Thut tốn (algorithm) • Thut tốn là gì? Thut tốn là mt phương pháp bao gm mt dãy các bưc tính tốn đ gii quyt mt bài tốn. Thut tốn cĩ th đưc din t dưi dng ngơn ng t nhiên (ting Vit, ting Anh ) hay ngơn ng lp trình (C++, Java ) • Th nào là mt thut tốn tt? 1. “ðúng đn” 2. Nhanh 3. Ít b nh 4. ðơn gin, d hiu
4. Ví d 1: Sp xp danh sách tuyn sinh Năm 2008, ði hc Cơng Ngh cĩ N thí sinh tham gia tuyn sinh, hãy vit chương trình sp xp các thí sinh theo th t gim dn ca tng đim thi ba mơn Ví d: Stt H tên Tốn Lý Hĩa Tng 1 Trn Anh Tun 7 8 7 22 2 Bùi Ngc Thăng 10 10 9 29 3 Lê S Vinh 10 8 8 26 4 Nguyn Th Ánh 8 10 9 27
5. Sp xp ni bt (bubble sort) Ý tưng: Ln lưt duyt qua danh sách thí sinh, nu hai thí sinh khơng đúng th t, đi ch hai thí sinh. Lp li quá trình trên cho đn khi danh sách đưc sp xp Step 0 Step 1 Step 3 1. (Tun, 22) 1. (Thăng, 29) 1. (Thăng, 29) 2. (Thăng , 29) 2. (Tun, 22) 2. (Vinh, 26) 3. (Vinh, 26) 3. (Vinh, 26) 3. (Tun, 22) 4. (Ánh , 27) 4. (Ánh, 27) 4. (Ánh, 27) Step 4 Step 5 1. (Thăng, 29) 1. (Thăng, 29) 2. (Vinh, 26) 2. (Ánh, 27) 3. (Ánh, 27) 3. (Vinh, 26) 4. (Tun, 22) 4. (Tun, 22)
6. Sp xp ni bt (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) }
7. Ví d 1’: Sp xp danh sách website (google search) Google cĩ danh sách N website. Website x cĩ mt đ ưu tiên là f(x). Hãy sp xp các website trên theo đ ưu tiên gim dn Câu hi: Cĩ th dùng bubble sort khơng? Tr li: ðưc, nhưng khơng hiu qu
8. Ví d 2: Danh b đin thoi Vit mt chương trình qun lý danh b đin thoi ca tồn b thành ph Hà Ni, sao cho các thao tác sau đưc hiu qu nht: 1. Kim tra mt s đin thoi 2. Thêm mt s đin thoi 3. Xĩa mt s đin thoi
9. Ví d 3: Tìm đưng đi tt nht • Xây dng h thng phn mm ch đưng đi tt nht cho ngưi dùng 1. ðưng đi ngn nht 2. ðưng đi qua ít đèn xanh – đèn đ nht 3. ðưng đi ít tc nht
10. Ví d 3: Tìm đưng đi tt nht (google map)
11. Ví d 3: Tìm đưng đi tt nht (google map)
12. Ví d 4: Xây dng h thng t đin Vit chương trình t đin Anh – Vit, cho phép thc hin các thao tác sau: 1. Tìm mt t 2. Thêm mt t 3. Xĩa mt t 4. Sa mt t 5. Tìm t đng nghĩa
13. Ví d 5: Ngưi bán hàng traveling salesman problem (TSP) Mt ngưi bán hàng cn đn thăm N khách hàng N đa đim khác nhau. Tìm mt hành trình cho ngưi bán hàng trên sao cho: 1. Mi đa đim thăm đúng 1 ln, sau đĩ quay v đim xut phát 2. Tng chi phí đi li là ít nht
14. Ngưi bán hàng Thut tốn: Thăm đa đim gn nht (nearest neighbor tour) T đim xut phát, ln lưt đi thăm các đim theo quy tc: “ðn thăm đim chưa đưc thăm gn vi đim hin ti nht”
15. Ngưi bán hàng Nearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1 ðương đi ti ưu: 1 → 2 → 3 → 4 → 5 → 6 → 8 → 7 → X → 9 → 1
16. Các ví d khác (10’)
17. Th nào là mt chương trình tt? 1. ðúng đn 2. Hiu qu 3. D hiu 4. D tìm li 5. D thay đi và nâng cp “Thut tốn + Cu trúc d liu = Chương trình” N. Wirth
18. D liu • D liu là nhng thơng tin mà máy tính cĩ th x lý: s nguyên, s thc, xâu kí t, và các d liu phc tp đưc to t nhiu thành phn • Trong b nh máy tính, d liu đưc biu din dưi dng nh phân (dãy các kí t 0, 1) • Trong các ngơn ng lp trình bc cao (C++, Java ), d liu đưc biu din dưi dng tru tưng, xut phát t biu din tốn hc và d hiu cho con ngưi: – int age – double weight
19. Kiu d liu cơ bn Kiu d liu đưc xác đnh bi: 1. Phm vi giá tr 2. Các phép tốn Ví d trong C++ kiu phm vi phép tốn thưng dùng
    bool true / false and, or, not
    char 127 > 127 ‘ ’, ‘=’
    int 32,767 > 32,767 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
    float ~1E37 > ~1E+37 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
    double ~1.7E308 > ~1.7E+308 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
20. Kiu d liu cĩ cu trúc Câu hi: Làm sao đ biu din d liu v 1 đim trên mt phng? ðáp án: Ngơn ng lâp trình cung cp cho ta nhng lut đ xây dng kiu d liu mi T t nhng kiu d liu đã bit t1, t 2, ,t n. Ví d trong C++: struct T { t1 x1 t2 x2 tn xn }
21. Kiu d liu cĩ cu trúc • Xây dng cu trúc d liu đ biu din d liu ca 1 đim trên mt phng struct pointType { double x; double y; } • Xây dng cu trúc d liu đ biu din d liu ca 1 đon thng trên mt phng struct lineType { point Type start; pointType end; }
22. Kiu d liu cĩ cu trúc • Xây dng cu trúc d liu đ biu din 1 sinh viên (5’) struct studentType { char name[100]; int age; bool sex; } • Xây dng cu trúc d liu đ biu din danh sách 1 lp hc struct studentClassType{ char className[100]; int numberStudent; studentType studentArr[100]; }
23. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc Xét kiu d liu mi T đưc to t nhưng kiu d liu đã bit t1, t 2, ,t n, Ví d: struct complexType { double real; double image; } Phm vi: Xác đnh bi phm vi ca các kiu d liu thành phn – real: là s thc nm trong phm vi kiu ‘double’ – image: là s thc nm trong phm vi kiu ‘double’
24. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc Phép tốn: Do ngưi dùng đnh nghĩa Ví d: struct complexType { double real; double image; } complexType createComplex (double real, double image) { complexType c; c.real = real; c.image = image; return c; }
25. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc complexType add (complexType c1, complextType c2) { complexType c12; c12.real = c1.real + c2.real; c12.image = c1.image + c2.image; return c12; } complexType multiply (complexType c1, complextType c2) { complexType c12; c12.real = (c1.real * c2.real) – (c1.image * c2.image); c12.image = (c1.real * c2.image) + (c1.image * c2.real); return c12; }
26. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc complexType getReal (complexType c) { c.real } complexType getImage (complexType c) { c.image } void printComplex (complexType c) { cout << c.real << “ +i ” << c.image << “ \ n” ; }
27. Tru tưng hĩa d liu (abstraction data type) 1. ðc t đi tưng d liu (các thành phn d liu ca đi tưng) Ví d: đi tưng s phc (complex) – real – image 2. ðc t các phép tốn trên đi tưng d liu (operations) Ví d: ði tưng s phc (complex): – createComplex (real, image) – getReal (complexNumber) – getImage (complexNumber) – add (complexNumber1, complexNumber2) – multiply (complexNumber2, complexNumber2) – print (complexNumber)
28. Tru tưng hĩa d liu Tru tưng hĩa đi tưng sinh viên (student ) (5’) 1. ðc t đi tưng d liu name, age, sex, address 2. ðc t các phép tốn trên đi tưng d liu createStudent (name, age, sex, address) compare (student1, student2) getName (student) getAge (student) getSex (student) getAdd (student)
29. Tru tưng hĩa d liu • studentClass 1. ðc t đi tưng d liu className, numberStudent, studentArr, Address 2. ðc t các phép tốn trên đi tưng d liu addStudent (studentClass, student) findStudent (studentClass, student) deleteStudent (studentClass, student) getClassName (studentClass) getNumberStudent (studentClass) getStudentArr (studentClass) getStudentAddress (studentClass)
30. Lp trình hưng đi tưng Object oriented programming (OOP) • Lâp trình hưng đi tưng giúp chúng ta cài đt các mơ t tru tưng (đi tưng d liu và các phép tốn) thành các đon mã chương trình • Chương trình đưc thit k thành tng đon nh, mi đon mơ t v mt đi tưng (thuc tính d liu, các phép tốn trên d liu) • Hai thuc tính quan trng: đĩng gĩi (encapsulation) và tha k (inheritance)
31. OOP: Tính đĩng gĩi (encapsulation) Object: Biu din cho mt đi tưng c th ca mt lp complex c1; complex c2;
32. OOP: Tính đĩng gĩi (encapsulation) • Class : Cài đt mt lp đi tưng d liu tru tưng. Vic cài đt bao gm cài đt các thành phn d liu và các phép tốn trên d liu Ví d: class complex { • Liên kt cht ch gia d liu và private: double real; phép tốn double image; public: • Che du d liu void create (double newReal, double newImage) { real = newReal; image = newImage; • D dàng tìm li } double getReal () { return real; • Các đi tưng liên kt vi nhau } thơng qua các phép tốn void print { cout << real << “ +i ” << image << “ \ n” ; } };
33. Thit k chương trình • ðc t vn đ • Thit k cu trúc d liu và gii thut • Cài đt (C++, Java ) • Th nghim và sa li
34. Thit k chương trình: ðc t vn đ Chính xác hĩa vn đ cn gii quyt: Chúng ta đưc cho nhng gì? Chúng ta cn tìm ra cái gì? Mi quan h gia chúng là gì? ðc t vn đ trong khoa hc máy tính: Input: D liu vào, các rng buc, đnh dng Ouput: D liu ra, các rng buc, đnh dng
35. ðc t vn đ Ví d: Cho mt dãy s phc, hãy 1. Tính tng ca dãy s phc 2. Tính tích ca dãy s phc 3. Tìm s phc cĩ phn thc (real) ln nht 4. Tìm s phc cĩ phn o (image) ln nht ðc t vn đ: • Input: Mt dãy s phc, mi s phc đưc biu din bi 2 s thc mơ t phn thc (real) và phn o (image) • Output: – c1 (s phc biu din tng ca dãy s phc) – c2 (s phc biu din tích ca dãy s phc) – c3 (s phc cĩ phn thc ln nht) – c4 (s phc cĩ phn o ln nht)
36. Bài tp v nhà ðc t vn đ cho các bài tốn dưi đây 1. Sp xp danh sách website 2. H thng t đin 3. Tìm đưng đi tt nht 4. Ngưi bán hàng
37. Kiu d liu danh sách Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
38. Danh sách Danh sách là gì? Danh sách là cu trúc d liu tuyn tính, trong đĩ các phn t d liu đưc sp xp theo mt th t xác đnh Ví d: – Danh sách sinh viên – Danh sách đin thoi – Danh sách mơn hc – Danh sách bài hát – Danh sách cơng vic
39. Danh sách Tru tưng hĩa cu trúc danh sách 1. Mơ t d liu A = ( a0, a 1, , a n) trong đĩ ai là phn t th i ca danh sách A Ví d: A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tun’,. ‘Ánh’) 2. Mơ t các phép tốn trên cu trúc danh sách • empty (A): Kim tra danh sách cĩ rng hay khơng • length (A): Cho bit s phn t ca danh sách • element (A, i ) : Tr phn t v trí th i ca A. Ví d: A =(1,3,5) Element ( A, 0) → 1 Element (A, 2) → 5
40. Danh sách • insert (A, i, x ): Thêm phn t x vào danh sách A ti v trí i. A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a i1, x, a i, a n) Ví d: A = (1,3,5) insert ( A, 1, 4) → A = (1, 4, 3, 5) • append (A, x ): Thêm x vào đuơi danh sách A A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , x) Ví d: A = (1,3,5) append ( A, 8) → A = (1, 3, 5, 8) • delete (A, i ): Loi phn t v trí th i trong danh sách A A = (a 0, a 1, a i1, a i, a i+1 , a n) → A = (a 0,a 1, ,a i1, a i+1 , a n) Ví d: A = (1,3,5) delete ( A, 1) → A = (1, 5)
41. Cài đt danh sách bng mng Mng (array) • Tp hp các phn t (các bin) cĩ cùng mt kiu • Mt phn t c th trong mng s đưc xác đnh và truy cp bi mt ch s • Trong C/C++, các phn t ca mng đưc đt cnh nhau to thành mt khi liên tc. ða ch thp nht tương ng vi phn t đu tiên, đa ch cao nht tương ng vi phn t cui cùng • Mng thì cĩ th là mt chiu hoc nhiu chiu
42. Cài đt danh sách bng mng a . . . an a0 1 ↑ ↑ ↑ ↑ 0 1 N Max 1 Mng mt chiu: dataType arrayName [Max]; Ví d: int scoreArr[100]; student studentArr[100];
43. Danh sách Tĩm tt v tru tưng hĩa cu trúc danh sách • Mơ t d liu • A = ( a0, a 1, , a n) • Mơ t các phép tốn trên cu trúc danh sách • empty (A): Kim tra danh sách cĩ rng hay khơng • length (A): Cho bit s phn t ca danh sách • element (A, i ) : Tr phn t v trí th i ca A. • insert (A, i, x ): Thêm phn t x vào danh sách A ti v trí i. • append (A, x ): Thêm x vào đuơi danh sách A • delete (A, i ): Loi phn t v trí th i trong danh sách A Các phép tốn trên cu trúc danh sách khơng ph thuc vào kiu d liu ca các phn t trong danh sách!!!
44. Cài đt danh sách trong C++ Template 1. Generic function 2. Generic class ListArr project List.h List.cpp
45. Các phép tốn khác trên danh sách • Tìm phn t ln nht • ði ch hai phn t • Sp xp tăng dn
46. Con tr (pointer) • Là đim mnh nht, nhưng cũng nguy him nht ca C/ C++ • Cha đa ch ca mt t bào nh trong máy tính 1 2 3 1 4 6 5 Giá tr trong ơ nh 3 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ða ch ơ nh 10 11 12 13 14 15 16 17
47. Con tr (pointer) Khai báo con tr type * pointerVariable ví d: int *p Cp phát b nh (allocate memory) pointerVariable = new type (initializer) Ví d: p = new int (1) Gii phĩng b nh delete pointerVariable; ví d: delete p (xem ví d chương trình)
48. Con tr (pointer) Cp phát b nh cho mt đi tưng d liu pointerVariable = new objectDataType (xem ví d chương trình)
49. Con tr (pointer) Cp phát mng đng pointerVariable = new arrayType[size] ví d: int* p; p = new int[10] Gii phĩng mng đng delete [] pointerVariable ví d: delete [] p; (xem ví d chương trình)
50. Danh sách liên kt Mng -1 1 3 2 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 int listArr[4] = {-1, 1, 3, 2} Danh sách -1 1 3 2 liên kt ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 (-1, 15 ) → (1, 16 ) → (3, 21 ) → (2, NULL ) ↑ ↑ head tail
51. Cài đt danh sách liên kt Xem chương trình
52. Các phép tốn khác trên danh sách liên kt • Tìm phn t ln nht • ði ch hai phn t • Sp xp tăng dn
53. Mng và danh sách liên kt • Truy cp phn t • Thêm phn t • Xĩa phn t
54. ð phc tp thut tốn Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
55. Các vn đ liên quan đn thut tốn 1. Mt vn đ đưc gii quyt bi nhiu thut tốn khác nhau 2. ði vi mt thut tốn: – ð phc tp v khơng gian (dung lưng b nh s dng) – ð phc tp v thi gian chy 3. ð phc tp v thi gian chy – Kĩ năng lp trình – Chương trình dch – Tc đ thc hin các phép tốn trên máy tính – D liu vào “Thi gian chy chương trình : 10s” ???
56. ð phc tp thut tốn 1. Thi gian chy 1 thut tốn ph thuc vào c (size) ca d liu vào – Tìm xem 1 đi tưng cĩ trong danh sách N phn t hay khơng? – Sp xp tăng dn dãy s gm N s – Bài tốn ngưi bán hàng cn thăm N đa đim 2. Trong các d liu vào cùng mt c ( N), thi gian chy ca thut tốn cũng thay đi Ví d: Tìm xem 1 đi tưng cĩ trong danh sách N phn t hay khơng? – ði tưng nm đu danh sach – ði tưng nm gia danh sach – ði tưng nm cui danh sách
57. ð phc tp thut tốn 1. Thi gian chy trong trưng hp xu nht (worsecase running time) Thi gian chy ln nht ca thut tốn đĩ trên tt c các d liu cùng c 2. Thi gian chy trung bình Là trung bình cng thi gian chy trên tt c các b d liu cùng c. 3. Thi gian chy trong trưng hp tt nht (bestcase running time) Thi gian chy ít nht ca thut tốn đĩ trên tt c các d liu cùng c
58. ð phc tp thut tốn ðánh giá thi gian chy thut tốn: – T(n) = s lưng phép tốn sơ cp cn phi thc hin (phép tốn s hc, phép tốn logic, phép tốn so sánh). Mi phép tốn sơ cp đưc thc hin trong mt khong thi gian c đnh. – Quan tâm đn tc đ tăng ca hàm T(n) . – Ví d: T(n) = 2n 2 + 3n + 10
59. Biu din thi gian chy bi kí hiu O ðnh nghĩa . Gi s f(n) và g(n) là các hàm thc khơng âm ca đi s nguyên khơng âm n. Ta nĩi “f( n) là ơ ln ca g(n)” và vit là f(n) = O( g(n) ) nu tn ti các hng s dương c* và n 0 sao cho f(n) = n 0.
60. Biu din thi gian chy bi kí hiu O Ví d. Gi s f(n) = 5n 3 + 2n 2 + 13n + 6 , ta cĩ: f(n) = 5n 3 + 2n 2 + 13n + 6 <= 5n 3 + 2n 3 + 13n 3 + 6n 3 = 26n 3 f(n) = O(n 3) Tng quát nu f(n) là mt đa thc bc k ca n: k k1 k f(n) = a kn + a k1n + + a 1n + a 0 thì f(n) = O(n )
61. Biu din thi gian chy bi kí hiu O Ký hiu ơ ln Tên gi O(1) hng O(logn) logarit O(n) tuyn tính O(nlogn) nlogn O(n 2) bình phương O(n 3) lp phương O(2n) mũ
62. Thi gian chy ca các lnh 1. Lnh gán X = Thi gian chy ca lnh gán bng thi gian thc hin biu thc 2. Lnh la chon if (điu kin) → T0(n) lnh 1 → T1(n) else lnh 2 → T2(n) Thi gian: T 0(n) + max (T 1(n), T 2(n))
63. Thi gian chy ca các lnh 3. Lnh lp: for, while, dowhile Ví d: X (n) ∑()T0 ()()n +Ti n i=1 X(n): S vịng lp T0(n): ðiu kin lp Ti(n): Thi gian thc hin vịng lp th i
64. Thi gian chy ca các lnh 4. Phân tích các hàm đ quy
65. Ví d 2 Thut tốn to ra ma trn đơn v A cp n. (1) for (i = 0 ; i < n ; i++) (2) for (j = 0 ; j < n ; j++) (3) A[i][j] = 0; (4) for (i = 0 ; i < n ; i++) (5) A[i][i] = 1; ð phc tp:
66. Ví d 3 1) sum = 0; 2) for ( i = 0; i < n; i + +) 3) for ( j = i + 1; i < = n; j + +) 4) for ( k = 1; k < 10; k + +) 5) { sum = sum + i * j * k }; ð phc tp:
67. Ví d 4 Phân tích đ phc tp thut tốn ca tt c các phép tốn trên kiu danh d liu danh sách đưc cài đt bng mng và danh sách liên kt
68. Hàng đi và Ngăn xp (Queue and Stack) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
69. Hàng đi (Queue) Hàng đi là gì? Là mt danh sách nhưng các phép tốn ch đưc thc hin hai đnh ca danh sách. Mt đnh gi là đu hàng, đnh cịn li gi là cui hàng. Ví d: • Xp hàng mua vé tàu xe, giao dch vi ngân hàng Tính cht: Vào trưc ra trưc (First in First Out: FIFO)
70. Hàng đi Tru tưng hĩa cu trúc hàng đi 1. Mơ t d liu A = ( a0, a 1, , a n) trong đĩ: – ao: Phn t đu ca hàng đi A – an: Phn t cui ca hàng đi A Ví d: A = (‘Vinh’, ‘Tun’,. ‘Ánh’) trong đĩ: ‘Vinh’: ðu hàng đi ‘Ánh’: Cui hàng đi
71. Các phép tốn trên hàng đi • empty (A): Kim tra hàng đi cĩ rng hay khơng • length (A): Cho bit s phn t ca hàng đi • EnQueue (A, x ): Thêm phn t x cui hàng đi. x A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , ) Ví d: A = (1,3,5) EnQueue ( A, 4) → A = (1, 3, 5, 4) • DeQueue (A): Loi phn t đu hàng đi A = (a 0, a 1, , a n1, a n) → A = (a 1, ,a n) Ví d: A = (1,3,5) DeQueue ( A) → A = (3, 5) • GetHead (A): Ly phn t đu hàng đi A = (a 0, a 1, , a n1, a n) → getHead (A) → a 0 Ví d: A = (1,3,5) getHead ( A) → 1
72. Bài t p 1. Vit chương trình cài đt cu trúc hàng đi bng mng và danh sách liên kt 2. Tính đ phc tp cho cài đt câu 1 3. ðc và cài đt hàng đi bng màng trịn
73. Ngăn xp (stack) Ngăn xp là gì? Là mt danh sách nhưng các phép tốn ch đưc thc hin mt đnh ca danh sách. Ví d: – Ly hàng hĩa trong kho – Tìm các cp du ngoc tương ng Tính cht: Vào trưc ra sau (First In Last Out: FILO)
74. Ngăn xp Tru tưng hĩa cu trúc ngăn xp 1. Mơ t d liu A = ( a0, a 1, , a n) trong đĩ an là phn t đnh ca ngăn xp A Ví d: A = (1, 2, 3, 3, 4, 5) → 5: Phn t đnh ngăn xp A = (‘Vinh’, ‘Tun’,. ‘Ánh’) → Ánh: Phn t đnh ngăn xp 2. Mơ t các phép tốn trên cu trúc ngăn xp • empty (A): Kim tra ngăn xp cĩ rng hay khơng • length (A): Cho bit s phn t ca ngăn xp
75. Ngăn xp (stack) • push (A, x ): Thêm phn t x đnh ngăn xp. x A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , ) Ví d: A = (1,3,5) push ( A, 4) → A = (1, 3, 5, 4) • Pop (A): Loi phn t đnh ngăn xp A = (a 0, a 1, , a n1, a n) → A = (a 0,a 1, ,a n1) Ví d: A = (1,3,5) pop ( A) → A = (1, 3) • GetTop (A): Ly phn t đnh ngăn xp A = (a 0, a 1, , a n1, a n) → getTop (A) → a n Ví d: A = (1,3,5) getTop ( A) → 5
76. Bài t p 1. Vit chương trình cài đt cu trúc ngăn xp bng mng và danh sách liên kt 2. Vit chương trình tìm tt c các cp du ngoc tương ng trong mt chương trình C++ 3. Vi mi phép tốn, tính đ phc tp
77. Sp xp (sorting) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
78. Bài tốn sp xp Input: Danh sách các đi tưng A = (a 0, ,a n) Problem: ði ch các phn t đ thu đưc mt danh sách mi, trong đĩ các phn t đưc sp xp theo mt th t nào đĩ Output: A’ = (a’ 0, ,a’ n) | a’ i < a’ i+1 , i = 0 n 1 Ví d: A = (1 , 5, 0, 3) → (0, 1, 3, 5) A = (‘Vinh’, ‘Tuan’, ‘Anh’) → (‘Anh’, ‘Vinh’, ‘Tuan)
79. Sp xp ni bt Thut tốn: Ln lưt duyt qua danh sách, nu hai phn t lin k đng khơng đúng th t thì đi ch. Lp li quá trình trên cho đn khi danh sách đưc sp xp. Ví d: Sp tăng dn dãy s A = (9, 7, 6, 2) (9, 7, 6, 2 ) → (9, 7, 2 , 6) → ( 9, 2 , 7, 6) → (2, 9, 7, 6) (2, 9, 7, 6 ) → (2, 9, 6 , 7) → (2, 6, 9, 7) (2, 6, 9, 7 ) → (2, 6, 7, 9) Chương trình ð phc tp : O( n2)
80. Sp xp hịa nhp (Merge sort) Chia đ tr (Divide and conquer): Chia bài tốn ln thành nhng bài tốn nh hơn. Gii quyt nhng bài tốn nh sau đĩ gp li đ đưc li gii cho bài tốn ln. Ý tưng merge sort: ð sp xp mt mng A[start end ], ta chia mng A thành 2 mng con A1 và A2 . Sp xp A1 và A2 , sau đĩ hịa nhp chúng thành mt đ đưc mang A đã sp xp. Mơ t thut tốn: Bưc 1: – Mid = (start + end) / 2 – Sp xp hai na mng A[start mid ] và A[( mid + 1 ) end ]. Vic sp xp hai na mng đưc thc hin bng cách gi đ quy th tc sp xp hịa nhp Bưc 2: Hịa nhp hai na mng A[start mid ] và A[(mid + 1) end ] đ thu đưc mng A trong đĩ các phn t đã đưc sp xp. Ví d: A = (7, 3, 9, 1) Sp xp hai na mng: A = ( 3, 7, 1, 9) Hịa nhp hai na mng: A = (1, 3, 7, 9)
81. Image taken from Skiena’s lecture note at Stony brook
82. Sp xp hịa nhp (Merge sort) void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); } }
83. Hịa nhp hai mng tăng dn ↓ ↓ 3 7 1 9 1 ↓ ↓ 3 7 1 9 1 3 ↓ ↓ 3 7 1 9 1 3 7 ↓ ↓ 3 7 1 9 1 3 7 9
84. Sp xp hịa nhp Thut tốn merge: Xem chương trình ð phc tp thut tốn sp xp hịa nhp: O( n log n)
85. Ví d 0
86. Ví d Sp tăng dãy s 1. 9 8 7 6 5 4 3 2 1 2. C D A B G H I J K AB F E
87. Sp xp nhanh (Quick sort) Tư tưng ca Quick sort: Phân chia danh sách d liu cn sp xp ra thành hai phn “phn bên trái” và “phn bên phi” sao cho các phn t phn bên trái nh hơn hoc bng các phn t phn bên phi. Sau khi phân chia, tip tc thc hin “quick sort trên hai phn d liu trên. C th hơn, gi “pivot” là phn t trung tâm ca danh sách, các phn t nh hơn hoc bng “pivot” thi nm bên trái “pivot”, các phn t ln hơn hoc bng “pivot” thì nm bên phi “pivot”
88. Quick sort Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } }
89. Partition (A, start, end) Tư tưng phân chia: Danh sách gm ba phn: – Phn bên trái (các giá tr nh hơn pivot) – Phn bên phi (các giá tr ln hơn pivot) – Phn gia chưa đưc phân chia Duyt trên danh sách đ m rng dn phn bên trái và phn bên phi, đng thi thu hp phn chưa đưc phân chia, cho đn khi phn chưa đưc phân chia bng rng.
90. Partition (A, start, end) Khi to: Phn bên trái và phn bên bng rng. Phn chưa đưc phân chia t v trí start → end. Xác đnh pivot = A[start] Bưc 1: Duyt t trái sang phi ca phn chưa đưc phân chia, nu phn t hin ti nh hơn hoc bng pivot thì m rng phn bên trái và thu hp phn chưa đưc phân chia, nu khơng dng li. Bưc 2: Duyt t phi sang tri ca phn chưa đưc phân chia, nu phn t hin ti ln hơn hoc bng pivot thì m rng phn bên phi và thu hp phn chưa đưc phân chia, nu khơng dng li. Bưc 3: ði ch phn t bên trái nht và phn t bên phi nht ca phn chưa đưc phân chia. M rng phn bên trái và phn bên phi, đng thi thu hp hai đu ca phn chưa đưc phân chia. Bưc 4: Nu phn chưa đưc phân chia khác rng thì quay li Bưc 1. Bưc 5: Chuyn pivot vào đúng v trí
91. Ví d Sp xp dãy s sau bng quick sort • 3 1 4 5 9 2 6 8 7
92. Trưng hp tt nht T(n) = O( n log n)
93. Trưng hp ti nht T(n) = O( n2)
94. Nh n xét v quick sort Thi gian trung bình: O(n log n) Là mt thut tốn sp xp nhanh nht trong thc t
95. T đc • Heap sort
96. Tìm kim (searching) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
97. Các vn đ Tìm kim trên danh sách: Cĩ mt danh sách các đi tưng A, tìm xem mt đi tưng X cĩ thuc vào danh sách này hay khơng Ví d: – Tìm mt sinh viên – mt s đin thoi – Tìm 1 t trong t đin – Tìm 1 loi hàng hĩa
98. Các vn đ Tìm kim trên văn bn (text matching): Tim kim s xut hin ca mt đon văn bn (1 t, 1 câu, 1 đon ) trong mt văn bn ln. ðon văn bn cĩ th xut hin chính xác hoc gn chính xác trong văn bn ln. Ví d – Search and replace in editors – Search engine (yahoo, google )
99. Tìm kim trên danh sách Input: • Danh sách các đi tưng A = ( a0, ,a n) • ði tưng cn tìm X Output: • i: v trí xut hin ca tưng X trong A (i = 1 nu X khơng xut hin) Thut tốn: Duyt ln lưt trên danh sách A và so sánh xem X cĩ trong danh sách hay khơng. Nêu cĩ tr li v trí xut hin đu tiên, nu khơng tr li (1) ð phc tp: O(n)
100. Tìm kim trên danh sách đã đưc sp xp Input: • Danh sách các đi tưng đã đưc sp xp A = ( a0, ,a n) | ai ≤ ai+1 • ði tưng cn tìm X Output: i: v trí xut hin ca tưng X trong A (i = 1 nu X khơng xut hin) Tìm kim nh phân: So sánh X vi phn t gia danh sách , nu 1. Nu bng → X nm v trí gia danh sách 2. Nu nh hơn, Tìm kim X trên na đu ca danh sách 3. Nu ln hơn, Tìm kim X trên na cui ca danh sách ð phc tp: O (log 2 n)
101. ð th (Graph) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
102. Đ th (graph) • G = (V, E) – V: Tp đnh – E = { (u,v) | u, v ∈ V}: Tp cnh Ví d: Biu din bn đ đưng đi trong thành ph bng đ th G = (V, E) – V: Tp hp các đim trong thành ph – E: Tp hp các đưng đi trong thành ph, mi đưng đi ni hai đim
103. ð th cĩ hưng và khơng cĩ hưng (directed and undirected graph) G = (V, E) là đ th khơng cĩ hưng nu (u, v) ∈ E thì (v, u) ∈ E
104. ð th cĩ trng s và khơng cĩ trng s (weighted and unweighted graph) G = (V, E) là đ th cĩ trng s nu mi cnh (u, v) ∈ E đưc gán mt giá tr
105. ð th cĩ chu trình và khơng chu trình (cyclic and acyclic graph)
106. ð th khơng cĩ nhãn và đ th cĩ nhãn (unlabled and labled graph)
107. Friend graph
108. Bc ca đnh (vertex degree)
109. Biu din đ th G = (V, E); V = {0, 1, , n-1} • Biu din bng danh sách lin k A – A[u][v] = 1 nu cĩ cung (u,v) – A[u][v] = 0 nu khơng cĩ cung (u,v)
110. Biu din đ th G = (V, E); V = {0, 1, , n-1} • Biu din bng danh sách k
111. ði qua đ th • ði qua tt c các đnh, mi đnh mt ln 0, 1, 2, 3, 4 • ði qua tt c các cnh, mi cnh mt ln (0,1), (0, 2), (1, 2), (1, 4), (2, 3), (2, 4), (4, 3), (3, 0)
112. ði qua đ th theo chiu rng (Breadth first search) • ði qua tt c các đnh ca đ th, mi đnh đúng mt ln • Bt đu xut phát t mt đnh s, ln lưt thăm các đnh lin k vi s. Tip tc quá trình thăm các đnh theo nguyên tc: ðnh nào đưc thăm trưc thì các đnh lin k vi đnh đĩ s đưc thăm trưc • Xem ví d
113. ði qua đ th theo chiu rng (Breadth first search) //ði qua đ th theo b rng xut phát t v BreadthFirstSearch (v) { (1) Khi to hàng đi Q rng; (3) Xen v vào hàng đi Q; (2) ðánh du đnh v đã đưc thăm; (4) while (hàng đi Q khơng rng) { (5) Ly đnh w đu hàng đi Q; (6) for (mi đnh u k w) (7) if ( u chưa đưc thăm) { (8) Xen u vào đuơi hàng đi Q; (9) ðánh du u đã đưc thăm; } (10) Loi w ra khi hàng đi Q } // ht vịng lp while. }
114. ði qua đ th theo chiu rng (Breadth first search) // ði qua đ th G=( V, E) theo b rng BreadthFirstSearch_traversal (G) { (10) for (mi v ∈V) (11) ðánh du v chưa đưc thăm; (12) for (mi v ∈V) (13) if ( v chưa đưc thăm) (14) BreadthFirstSearch( v); }
115. ði qua đ th theo chiu sâu (Depth first search) //ði qua đ th theo chiu sâu xut phát t v DepthFirstSearch (v) { for (mi đnh u k vi v) if ( u chưa đưc thăm) { thăm u và đánh du u đã đưc thăm DepthFirstSearch ( u) } } Xem ví d
116. ði qua đ th theo chiu rng (Depth first search) // ði qua đ th G=( V, E) theo chiu sâu DepthFirstSearch_traversal (G) { (10) for (mi v ∈V) (11) ðánh du v chưa đưc thăm; (12) for (mi v ∈V) (13) if ( v chưa đưc thăm) (14) DepthFirstSearch( v); }
117. ð th (Graph) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
118. Đ th (graph) • G = (V, E) – V: Tp đnh – E = { (u,v) | u, v ∈ V}: Tp cnh Ví d: Biu din bn đ đưng đi trong thành ph bng đ th G = (V, E) – V: Tp hp các đim trong thành ph – E: Tp hp các đưng đi trong thành ph, mi đưng đi ni hai đim
119. ði qua đ th theo chiu rng (Breadth first search) • ði qua tt c các đnh ca đ th, mi đnh đúng mt ln • Bt đu xut phát t mt đnh s, ln lưt thăm các đnh lin k vi s. Tip tc quá trình thăm các đnh theo nguyên tc: ðnh nào đưc thăm trưc thì các đnh lin k vi đnh đĩ s đưc thăm trưc • Xem ví d
120. ði qua đ th theo chiu sâu (Depth first search) //ði qua đ th theo chiu sâu xut phát t v DepthFirstSearch (v) { for (mi đnh u k vi v) if ( u chưa đưc thăm) { thăm u và đánh du u đã đưc thăm DepthFirstSearch ( u) } } Xem ví d
121. Sp xp topo Cho đ th cĩ hưng nhưng khơng cĩ chu trình G = (V, E) (Directed acylic graph / DAG) Sp xp các đnh ca đ th G thành mt danh sách sao cho nu cĩ cung (u,v ) ∈ E, thì đ nh uuu ph i đ ng tr ư c đ nh vvv. G A B C F E D
122. Sp xp topo TopoSort (u) { ðánh du u đã thăm; for (mi đnh v k u) if ( v chưa thăm) TopoSort (v); Xen u vào đu danh sách T; } //Sp xp các đnh ca đ th đnh hưng //khơng cĩ chu trình G =(V,E) thành danh sách topo. TopoSortGraph (G) { for (mi đnh u ∈ V) ðánh du u chưa đưc thăm; Khi to danh sách topo T rng; for (mi đnh u ∈ V) if ( u chưa thăm) TopoSort (u); }
123. ðưng đi gia hai đim Cho đ th G = (V, E) Gia hai đnh ( x0, x k) cĩ đưng đi, nu tn ti (x 1, ,x k1 ) tha mãn (x i, x i+1 ) ∈ E, ∀i = 0 (k1)
124. ð th liên thơng (Connected graph) Cho đ th G = (V, E), G đưc gi là liên thơng nu tn ti đưng đi gia hai đnh bt kì ca đ th
125. Tìm tt c các thành phn liên thơng Cho đ th G = (V, E), tìm tt c các thành phn liên thơng ca đ th. ðnh i ca đ th đưc gán nhãn c i cho bit thuc min liên thơng c i.
126. Tìm các thành phn liên thơng //ði qua đ th theo b rng xut phát t v FindConnectedComponent (v, ci ) { (1) Khi to hàng đi Q rng; (2) Xen v vào hàng đi Q; (3) ðánh du đnh v đã đưc thăm, và gán nhãn v bng ci (4) while (hàng đi Q khơng rng) { (5) Ly đnh w đu hàng đi Q; (6) for (mi đnh u k w) (7) if ( u chưa đưc thăm) { (8) Xen u vào đuơi hàng đi Q; (9) ðánh du u đã đưc thăm, và gán nhãn u bng ci } (10) Loi w ra khi hàng đi Q } // ht vịng lp while. }
127. Tìm các thành phn liên thơng // Tìm các thành phn liên thơng ca đ th G=( V, E) FindAllConnectedComponent (G) { (10) for (mi v ∈V) (11) ðánh du v chưa đưc thăm; (12) ci = 0; (13) for (mi v ∈V) (14) if ( v chưa đưc thăm) { (15) FindConnectedComponent( v, ci ); (16) ci = ci + 1 } }
128. ðưng đi ngn nht Cho đ th G=(V, E), cnh ( u, v ) ∈ E cĩ đ dài weight ( u,v ) > 0. Tìm đưng đi ngn nht t đnh s đn đnh e Tư tưng thut tốn Dijkstra (thut tốn gán nhãn) dist[ v] = Khong cách đưng đi ngn nht t s đn v pre[ v] = u: ðnh lin phía trưc trên đưng đi ngn nht t s đn v Gán nhãn (sa nhãn): Nu dist[ u] + weight ( u, v ) < dist [ v] thì dist [ v] = dist[ u] + weight ( u, v ) pre[ v] = u s → → u → v
129. Thut tốn Dijkstra Known = {tp hp các đnh đã xác đnh đưc đưng đi ngn nht t s đn} Unknown = {tp hp các đnh chưa xác đnh đưc đưng đi ngn nht t s đn} Tin hành quá trình lp, ti bưc i tìm đnh u ∈ unknown cĩ kho ng cách nh nh t. if u = e then kt thúc else { known = known ∪ {u} unknown = unknown – {u} Dùng u đ sa nhãn cho các đnh thuc tp unknown tin hành bưc th (i + 1) }
130. Dijkstra Algorithm { Known = { s}; Unknown = {E} – {s} for v ∈ unknown { dist[ v] = weight [ s, v ]; pre[ v] = s; } u = s; // at the first step while ( u != e ){ chn u sao cho dist[ u] = min {dist[ x] | x ∈ unknown} Known = Known ∪ {u} Unknown = Unknown – {u} for v ∈ Unknown if dist[ u] + weight [ u, v ] < dist[ v] { //sa nhãn cho v t u dist[ v] = dist[ u] + weight[ u,v ]; pre[ v] = u; } } path = { e} while ( e != s) { e = pre[ e] path = { e} ∪ path } }
131. Cây (Tree) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
132. Khái nim cây • Cây là mt đ th đnh hưng tha mãn các tính cht sau: • Cĩ mt đnh đc bit đưc gi là gc cây • Mi đnh C bt kỳ khơng phi là gc, tn ti duy nht mt đnh P cĩ cung đi t P đn C. ðnh P đưc gi là cha ca đnh C, và C là con ca P • Cĩ đưng đi duy nht t gc ti mi đnh ca cây. Gc ðnh trong Lá
133. Cài đt cây bng mng con tr Template root class Node { Item data; List children; A } B C D Node * root; (Xem hình v) E F G
134. Cài đt cây bng hai con tr template root class Node { A Item data; Node * firstChild; Node* nextSibling; B C D }; Node * root; E F G
135. Duyt cây
136. Duyt cây theo th t trưc • Thăm gc r. • Duyt ln lưt các cây con T 1, , T k theo th t trưc A B E F C D G
137. Duyt cây theo th t trưc Template Preorder (Node* root) { visit (root); for each child r do Preorder ( r); }
138. Duyt cây theo th t sau • Duyt ln lưt các cây con T 1, , T k theo th t sau • Thăm gc r. E F B C G D A
139. Duyt cây theo th t sau Template Postorder (Node* root) { for each child r do Postorder ( r); visit (root); }
140. Cây nh phân template Class Node { Item data; // D liu cha trong mi đnh Node* left; Node* right; };
141. Các kiu cây nh phân Cây nh phân đy đ Cây nh phân cân bng: ð cao cây con bn trái và bên phi chênh nhau khơng quá mt
142. Problem Bài tốn: Cho mt danh sách các đi tưng, hãy t chc cu trúc d liu đ thc hin các phép tốn dưi đây mt cách hiu qu: • Tìm kim (search) • Thêm vào (insert) • Xĩa đi (delete) ðáp án: Dùng cu trúc cây tìm kim nh phân
143. Cây tìm kim nh phân • Cây nh phân rng là cây tìm kim nh phân • Cây nh phân khơng rng T là cây tìm kim nh phân nu: – Khĩa ca gc ln hơn khĩa ca tt c các đnh cây con trái T L và nh hơn khĩa ca tt c các đnh cây con phi TR – Cây con trái T L và cây con phi T R là các cây tìm kim nh phân.
144. Phép tốn tìm kim (search) binarySearchTree (Node* root, lookingData) { if (Root == NULL) return NULL; else if (root.data == lookingData) return root else if (root.data < lookingData) return binarySearchTree (root.right, lookingData) else return binarySearchTree (root.left, lookingData) }
145. Phép tốn tìm kim phn t nh nht ln nht //Root != NULL Min (Node* root) { if (Root .left == NULL) return root else return Min (root.left) } Max (Node* root) { if (Root .right == NULL) return root else return Max (root.right) }
146. Phép tốn thêm vào (insert) insert (Node* root, insertData) { if (Root == NULL) Root ← insertData else if (insertData < Root.data ) insert (root.left, insertData) else insert (root.right, insertData) }
147. Phép tốn thêm vào (insert) Thêm phn t 6 Thêm phn t 11
148. Phép tốn xĩa (delete)
149. Phép tốn xĩa (delete) 5 5 2 7 7 3 3 6 11 11 6 8 12 12 (b) 8 (a) 9 9 Xĩa đnh 2 5 2 8 3 6 11 (c) 9 12 Xĩa đnh 7
150. Phép tốn xĩa (delete) Delete (root, deleteData) { if (deleteData root.data) Delete (root.right, deleteData); // Loi cây con phi else if (root.left != NULL && root.right != NULL) { min ← Min (root.right); root ← min; Delete min; } else if (root.left == NULL) root = root.right else root = root.left }
151. Mt s vn đ khác trong đ th (T đc) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
152. Cây tìm kim nh phân cân bng AVL ( G.M. AdelsonVelsky and E.M. Landis )
153. ðưng đi ngn nht gia mi cp đnh Input: ð th G = (V, E) Output: Ma trn Dist[u,v] là đưng đi ngn nht gia hai đnh u và v Thut tốn Floyd: for ( u = 0 ; u < n ; u++) for ( v = 0 ; v < n ; v++) Dist[u][v] = weight[u][v]; for ( k = 0 ; k < n ; k++) for ( u = 0 ; u < n ; u++) for ( v = 0 ; v < n ; v++) if (Dist[u][k] + Dist[k][v] < Dist[u][v] ) Dist[u][v] = Dist[u][k] + Dist[k][v]
154. Cây bao trùm ngn nht (minimum spanning tree) • ð th khơng hưng G = (V, E), cây bao trùm T là đ th con ca G, liên thơng, khơng chu trình và ni tt c các đnh V ca G • Cây bao trùm ngn nht là cây cĩ tng đ dài các cnh ngn nht 4 0 3 1 4 0 4 9 3 1 6 3 5 7 3 6 5 8 8 5 5 2 1 2 2 1 2
155. Cây bao trùm ngn nht (minimum spanning tree) Prim(G,T) //Xây dng cây bao trùm ngn nht T ca đ th G { U = {s}; //Khi to tp U ch chưa mt đnh s T = ∅; // Khi to tp cnh T rng. while ( U ≠ V ) { chn (u,v) là cnh ngn nht vi u ∈ U và v ∈ V U; U = U ∪ {v}; T = T ∪ {(u,v}; } }
156. 0 4 4 9 4 3 1 0 4 9 3 1 7 3 6 5 8 8 7 3 6 5 5 8 8 1 2 2 5 (a) 1 2 2 4 (b) 0 4 9 3 1 4 0 4 9 3 1 7 3 6 5 8 8 7 3 6 5 5 8 8 5 1 2 2 (c) 1 2 2 (d) 4 0 4 9 4 3 1 0 4 9 3 1 7 3 6 5 7 3 6 5 8 8 8 8 5 5 1 2 2 1 2 2 (e) (f)
157. Thit k thut tốn Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
158. Chia đ tr (Divide and Conquer) • Chia bài tốn ln thành các bài tốn nh cùng dng vi bài tốn ln nhưng cĩ kích thưc nh hơn. • Gii quyt các bài tốn nh đc lp • Kt hp nghim ca nhng bài tốn nh đ thu đưc bài tốn ln
159. Ví d: Merge sort ð sp xp mt mng A[start end], ta chia mng A thành 2 mng con A1 và A2. Sp xp A1 và A2, sau đĩ hịa nhp chúng thành mt đ đưc mang A đã sp xp. void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); } }
160. Ví d: Quick sort Tư tưng ca Quick sort: Phân chia danh sách d liu cn sp xp ra thành hai phn “phn bên trái” và “phn bên phi” sao cho các phn t phn bên trái nh hơn hoc bng các phn t phn bên phi. Sau khi phân chia, tip tc thc hin “quick sort trên hai phn d liu trên. Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } }
161. Binary search BinarySearch (lookingData, items, start, end) { if (start > end) return (-1) else { mid = (start + end) / 2; if (items[mid] == lookingData) return mid else if (items[mid] > lookingData) BinarySearch (lookingData, items, start, mid -1) else BinarySearch (lookingData, items, mid + 1, end) } }
162. Tìm phn t ln nht trong danh sách findMax (int start, int end, items) { if (start == end) return items[start] else { int med = (start + end) / 2; Item max1 = findMax (start, med, items); Item max2 = findMax (med + 1, end, items); return Max (max1, max2); } }
163. Chin lưc vét cn (Backtracking) Ln lưt duyt qua tt c các trng thái cĩ th trong khơng gian tìm kim • A = (a 0, a 1, a n1): Là mt trng thái gm N thành phn, nu trng thái A tha mãn các yêu cu ca bài tốn thì gi là vector nghim. Trong đĩ a i ∈ S i • ð lit kê đưc tt c các trng thái A cĩ th, ta tin hành gi đ quy qua N vịng, ti bưc th i s ln lưt tin hành th tt c các ai ∈ S i
164. Chin lưc vét cn (Backtracking) Backtracking (A, i) { for ai ∈ Si { A = A ⋃ ai ; if (i < N) Backtracking (A, i+1) else CheckConfiguration (A); A = A – {ai} } }
165. Ví d: Lit kê tt c xâu nh phân đ dài N Void Binary (A, i) { for (int v = 0; v < 2; v ++) { A[i] = v; if (i < N) Binary (A, i+1) else A.print (); A[i] = -1; } }
166. Ví d: Lit kê tt c hốn v đ dài N Void Permutation (A, dd, i) { for (int v = 1; v <= N ; v ++) if (not dd[v]) { A[i] = v; dd[v] = true; if (i < N) Permutation(A, dd, i+1) else A.print (); A[i] = -1; dd[v] = false; } }
167. Tìm đưng đi ngn nht qua tt c các đnh ca đ th
168. Bài tốn cái ba lơ Cĩ N đ vt, đ vt i cĩ khi lưng wi và giá tr ti. Mt tên trm cĩ 1 chic ba lơ cĩ th mang đưc khơng qúa M kg. Hãy tìm cách mang mt s đ vt đ tng giá tr ly đưc là ln nht.
169. Thit k thut tốn Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
170. Chia ð Tr (Divide and Conquer) 1. Chia bài tốn ln thành các bài tốn cĩ kích thưc nh 2. Gii các bài tốn cĩ kích thưc nh 3. Kt hp nghim ca các bài tốn cĩ kích thưc nh đ gii bài tốn ln
171. Ví d: Dãy s Fibonacci Dãy Fibonacci: 0 1 2 3 5 8 13 f(0) = 0 f(1) = 1 f(k) = f(k1) + f(k2) Fibonacci_DAC (k) { if (k == 0) return 0 else if (k == 1) return 1 else return Fibonacci _DAC (k1) + fibonacci_DAC (k2) } Nhn xét: Các bài tốn nh đưc gii quyt da vào nhng bài tốn nh hơn ging nhau.
172. Quy hoch đng (Dynamic programming) • Ging phương pháp ‘chiađtr’ (divideandconquer) là gii quyt bài tốn ln da vào kt qu các bài tốn con. • ðim khác bit là quy hoch đng lưu li nghim ca tt c các bài tốn con, mi bài tốn con ch phi tính tốn 1 ln. • Quy hoach đng thưng đưc dùng đ gii quyt nhng bài tốn liên quan đn ti ưu hĩa (tìm nghim tt nht).
173. Ví d: Dãy s Fibonacci int fib[N]; for (int i = 0; i <= N; i ++) fib[i] = 1; fib[0] = 0; fib[1] = 1; int fibonacci (int k) { if (fib[k] == 1) fib[k] = fibonacci (k1) + fibonacci (k2); return fib[k]; }
174. Cu trúc chung ca phương pháp quy hoch đng 1. ðưa ra cách tính nghim ca các bài tốn con đơn gin 2. Tìm cơng thc xây dng nghim ca bài tốn thơng qua nghim ca các bài tốn con 3. Thit k bng đ lưu nghim ca các bài tốn 4. Tính nghim ca các bài tốn t nh đn ln 5. Xây dng nghim ca bài tốn cn tìm t bng
175. Ví d: Bài tốn cái ba lơ Cĩ N đ vt, đ vt i cĩ khi lưng wi và giá tr ti . Mt tên trm cĩ 1 chic ba lơ cĩ th mang đưc khơng qúa M kg. Hãy tìm cách mang mt s đ vt đ tng giá tr ly đưc là ln nht. Bit rng, wi nguyên dương nh hơn 101, M nguyên dương nh hơn 1001. Ví d N = 4, M = 10 i 1 2 3 4 wi 5 4 6 3 ti 1 4 3 5
176. Ví d: Dãy con chung Cho hai dãy s A = (a 1, ,a n) và B = ( b0, ,b m), tìm dãy s C = ( c0, ,c k) sao cho C là dãy con ca c A và B, và C dài nht cĩ th . Ví d: A = (3, 5, 1, 3, 5, 5, 3) B = (1, 5, 3, 5, 3, 1) C = (5, 3, 5, 3) hoc (1, 3, 5, 3) hoc (1, 5, 5, 3)
177. Ví d: Dãy con lin nhau tng ln nht Cho dãy s A = (a 1, ,a n), tìm dãy con lin nhau ( ai, a i+1 , ,a j1, a j) vi tng ln nht. Ví d: A = (3, 5, 4, 3, 2, 4, 1) Dãy con lin nhau tng ln nht: (5, 4, 3, 2)
178. Ví d: Chia ko Cĩ N gĩi ko, gĩi ko i cĩ ai cái. Hãy chia N gĩi ko trên thành 2 đng sao cho chênh lnh gia tng s ko ca hai đng là ít nht. Lưu ý là khơng đưc chia nh các gĩi ko ra. Ví d: N = 5 1 3 4 9 5 Chia thành: 1 9 và 3 4 5
179. Thiếtkt kế thuậtttốn tốn 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
180. Chiếnln lượccvétc vét cạn Tư tưởng: Duyệt tất cả các nghiệm cĩ thể trong khơng gian nghiệm để tìm ra nghiệm tốt nhất Ví d ụ: 1. Tìm đường đi ngắn nhất qua tất cả các đỉnh 2. Ba lơ 3. Chia k ẹo 4. 8 quân hậu
181. Chiến lược tham ăn (Gree ddy strategy) ) Ý tưởng: Quá trình xây dựng nghiệm được tiến hành qua N bước, tại mỗi bước thay vì xét tất cả các khả năng cĩ thể, ta chỉ xét một khả năng cho là tốt nhất. Nghiệm tìm được thường chỉ là nghiệm gần tối ưu Ví dụ: 1. Bài tốn người bán hàng 2. Bài tốn cái ba lơ 3. Bài tốn chia kẹo
182. Thuật tốn leo đồi (hill climbing) Ý tưởng: Từ một nghiệm ban đầu, cải tiến liên tục để thu được nghiệm tốt hơn cho đến khi khơng cải tiến được nữa. Ví d ụ: 1. Bài tốn chia kẹo 2. Bài tốn người bán hàng
183. Bảng b ăm 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
184. Dữ liệutu từ điển Ba phép tốn trên dữ liệu từ điển: 1. Tìm kiếm 2. Thêm vào 3. Xĩa đi Các cấu trúc: -Danháhh sách - Cây tìm kiếm nhị phân -Bảng băm
185. 0 1 Tính địa chỉ i Hàm băm Tập các giá tr ị khố SIZE-1 Mảng T
186. Các hàm băm • Phương pháp lấy phần dư h(k) = k % SIZE Size: S ố nguyên t ố cĩ d ạng 4K+3 (811) • Phương pháp nhân h(k) = ⎣(αk - ⎣αk⎦)S) . SIZE⎦ α: Là số thực dương (0,61803399) Ví dụ: SIZE = 1024, k = 1849970 h(k) = ⎣(α.1849970 - ⎣α.1849970⎦).1024⎦ =348
187. Hàm b ămmv với giá tr ị khĩa là xâu kí t ự • S = s0 sk 0 i k key(s) = s0 * 128 + si * 128 + + sk * 128 h(s) = key(s) % SIZE
188. Giải quy ếttvach va chạm • Phương pháp xác định địa chỉ mở T 13 388 14 926 130 • Phương pháp tạo dây chuyền Hàm băm h T
189. Tính hi ệuuqu quả củaab bảng b ăm Mức độ đầy: N α = SIZE Thời gian tìm kiếm trung bình trên bảng băm địa chỉ mở sử dụng thămdị tuyến tính: 1 ⎛ 1 ⎞ Thành cơng: ⎜1+ ⎟ 2 ⎝ 1−α ⎠ 1 ⎛ 1 ⎞ ⎜1+ ⎟ Thất bại: ⎜ 2 ⎟ 2 ⎝ (1−α ) ⎠
190. Gii thiu v mơn hc Cu trúc d liu và gii thut 2008 2009
191. Thơng tin giáo viên • Giáo viên chính: Ts. Lê S Vinh B mơn Khoa Hc Máy Tính Phịng 306, nhà E3 Email: vinhioi@yahoo.com • Tr ging: Ths. Bùi Ngc Thăng B mơn Khoa Hc Máy Tính Phịng 306, nhà E3 Email: thangbn@coltech.vnu.vn
192. Cách tính đim Tng thi gian hc: 15 tun Yêu cu: Bit v ngơn ng lp trình C++ Phân b đim: • Kim tra ln 1 (10%): Tun th 4 • Kim gia kì (20%): Tun th 8 • Kim tra ln 2 (10%): Tun th 12 • Thi ht mơn (60%) Thi ht mơn: ðim 3 ln kim tra là d1, d2, d3, điu kin cn đ đưc thi ht mơn d123 = ( d1 + d2 * 2 + d3) / 4 >= 5 Khuyn khích (<= 20%) : – Làm bài tp ln – Nghiên cu khoa hc – Tham gia trong bui hc
193. Tài liu tham kho • Cu trúc d liu và gii thut (PGS. ðinh Mnh Tưng) • Introduction to algorithms (Thomas H. Cormen, et al.) • Data structures and algorithms in C++ (Adam Drozdek) • Data structure and program design in C++ (Robert L. Kruse and Alexander J. Ryba) • The complete reference C++ (Herbert Schildt)