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

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST

Báo xấu

280
lượt xem 60
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’