Bài giảng Giới thiệu về cấu trúc dữ liệu và giải thuật - Bài 1 - Lê Sỹ Vinh

Bài giảng Giới thiệu về cấu trúc dữ liệu và giải thuật - Bài 1 - Lê Sỹ Vinh giúp bạn nắm bắt cấu trúc dữ liệu, thuật toán, dữ liệu, kiểu dữ liệu cơ bản, kiểu dữ liệu có cấu trúc, trừu tượng hóa dữ liệu.
Nội dung trích xuất từ tài liệu:
Bài giảng Giới thiệu về cấu trúc dữ liệu và giải thuật - Bài 1 - Lê Sỹ Vinh 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 Nghe - Đ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. 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 sinh Nă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ôn Ví d : Stt H tên Toán Lý Hóa T ng 1 Tr n Anh Tu n 7 8 7 22 2 Bùi Ng c Thăng 10 10 9 29 3 Lê S Vinh 10 8 8 26 4 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 3 1. (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 5 1. (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 n Câ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 i Vi 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 i 2. Thêm m t s ñi n tho i 3. 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 t Ví 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 n Vi 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ìm m 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àng Thu 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àng Nearest 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→1 Các ví d khác (10’) Th nào là m t chương trình t t? 1. ðúng ñ n 2. Hi u qu 3. D hi u 4. D tìm l i 5. 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 bi u di n dư i d ng nh phân (dãy các kí t 0, 1) • Trong các ngôn ng l p trình b c cao (C++, Java..), d li u ñư c bi u di n dư i d ng tr u tư ng, xu t phát t bi u di n toán h c và d hi u cho con ngư i: – int age – double weight Ki u d li u cơ b n Ki u d li u ñư c xác ñ nh b i: 1. Ph m vi giá tr 2. Các phép toán Ví d trong C++ ki u ph m vi phép toán thư ng dùng bool true / false and, or, not char -127 -> 127 ‘’, ‘=’ int -32,767 -> 32,767 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ float ~1E-37 -> ~1E+37 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ double ~1.7E-308 -> ~1.7E+308 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ ...