Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1b: Khởi động

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1b: Khởi động

1. Bài 1b: Khởi động Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính  Giải một bài toán tin học  Đặc tả vấn đề  Cấu trúc dữ liệu  Thuật toán 2 diepht@vnu
3. Ứng dụng từ điển Anh-Việt! 3 diepht@vnu
4. Tổ chức dữ liệu Tra từ Thêm từ Xóa từ 4 diepht@vnu
5. Giải một bài toán tin học  Đặc tả vấn đề  Thiết kế cấu trúc dữ liệu  Thiết kế giải thuật  Cài đặt (C++, Java )  Thử nghiệm và sửa lỗi  Tối ưu chương trình 5 diepht@vnu
6. Đặc tả vấn đề  Bài toán tin học khác với bài toán thuần tuý toán học  Ví dụ: cài đặt các hàm số phức tạp  Khai triển chuỗi vô hạn vs. Xấp xỉ 6 diepht@vnu
7.  Từ bài toán thực tế, phải phát biểu lại chính xác và chặt chẽ  Ví dụ:  Một dự án có n người tham gia thảo luận, họ muốn chia thành các nhóm và mỗi nhóm thảo luận riêng về một phần của dự án. Nhóm có bao nhiêu người thì được trình lên bấy nhiêu ý kiến. Nếu lấy ở mỗi nhóm một ý kiến đem ghép lại thì được một bộ ý kiến triển khai dự án. Hãy tìm cách chia để số bộ ý kiến cuối cùng thu được là lớn nhất. 7 diepht@vnu
8. Cấu trúc dữ liệu  Một cấu trúc dữ liệu là một dữ liệu phức hợp  gồm nhiều thành phần dữ liệu (cơ sở hoặc dựng sẵn)  liên kết các thành phần dữ liệu  mảng  cấu trúc  con trỏ 8 diepht@vnu
9. Các KDLTT quan trọng  Tập động – dynamic set KDLTT (kiểu dữ liệu trừu tượng): là kiểu  Từ điển – dictionary dữ liệu phức hợp  Danh sách – list bao gồm • các đối tượng và  Ngăn xếp – stack • các phép toán  Hàng đợi – queue trên các đối tượng  Cây – tree  Cây nhị phân – binary tree  Cây tìm kiếm nhị phân – binary search tree  Hàng ưu tiên – priority queue class trong C++: • data members,  Bảng băm – hash table • member  Đồ thị - graph functions 9 diepht@vnu
10. Thuật toán  Thuật toán là sự đặc tả chính xác một dãy các bước có thể thực hiện được một cách máy móc để giải quyết một vấn đề.  Ví dụ  Cộng 2 số tự nhiên có n chữ số  Tính UCLN của 2 số tự nhiên  Tính đúng đắn 10 diepht@vnu
11. Thuật toán  Các tiêu chí đánh giá thuật toán:  Đơn giản, dễ hiểu  Dễ cài đặt  Cần ít bộ nhớ Tính hiệu quả  Chạy nhanh  Biểu diễn thuật toán  Ngôn ngữ tự nhiên  Lưu đồ  Ngôn ngữ lập trình  Giả mã 11 diepht@vnu
12. Ví dụ  Tìm UCLN 1. (Input) Nhập a và b: Số tự nhiên 2. Nếu b ≠ 0 thì chuyển sang bước 3, nếu không thì bỏ qua bước 3, đi làm bước 4 3. Đặt r = a % b; Đặt a = b; Đặt b = r; Quay trở lại bước 2. 4. (Output) Kết luận ước số chung lớn nhất phải tìm là giá trị của a. Kết thúc thuật toán. 12 diepht@vnu
13. Biểu diễn thuật toán  Sơ đồ khối. Ví dụ: tìm UCLN 13 diepht@vnu
14. Biểu diễn thuật toán: Giả mã  Mô tả bậc cao của một thuật toán  Cấu trúc rõ ràng hơn văn xuôi  Không chi tiết như mã nguồn  Được ưa thích trong biểu diễn giải thuật  Ẩn đi các khía cạnh thiết kế chương trình 14 diepht@vnu
15. Cách viết giả mã  Luồng điều khiển  Gọi phương thức  if then [else ] var.method (arg [, arg ])  while do  Trả về giá trị  repeat until return biểu_thức  for do  Các biểu thức  Lùi đầu dòng thay thế các dấu  Gán ngoặc (= trong C++/Java)  Khai báo phương thức = So sánh bằng Algorithm method (arg [, arg ]) (== trong C++/Java) Input n2 Được sử dụng chỉ số trên và Output các ký hiệu toán học khác 15 diepht@vnu
16. Ví dụ thuật toán 16 diepht@vnu
17. Ví dụ 1: Sắp xếp nổi bọt (bubble sort) Ý tưởng: Lần lượt duyệt qua danh sách thí sinh từ cuối lên, 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. Bước 0 Bước 1 Bước 3 1. (Tuấn, 22) 1. (Tuấn, 22) 1. (Thăng, 29) 2. (Thăng , 29) 2. (Thăng, 29) 2. (Tuấn, 22) 3. (Vinh, 26) 3. (Ánh, 27) 3. (Ánh, 27) 4. (Ánh , 27) 4. (Vinh, 26) 4. (Vinh, 26) Bước 4 Bước 5 1. (Thăng, 29) 1. (Thăng, 29) 2. (Ánh, 27) 2. (Ánh, 27) 3. (Tuấn, 22) 3. (Vinh, 26) 4. (Vinh, 26) 4. (Tuấn, 22) 17 diepht@vnu
18. 18 diepht@vnu
19. Ví dụ 1’: Sắp xếp danh sách website (google search) Google có danh sách N website trả về cho truy vấn q. 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ả 19 diepht@vnu
20. 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. Tìm 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 20 diepht@vnu
21. 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 21 diepht@vnu
22. Ví dụ 3: Tìm đường đi tốt nhất (google map) 22 diepht@vnu
23. Ví dụ 3: Tìm đường đi tốt nhất (google map) 23 diepht@vnu
24. 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 24 diepht@vnu
25. 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 25 diepht@vnu
26. 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” 26 diepht@vnu
27. Người bán hàng Nearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1 27 Đương đi tối ưu: 1 → 2 → 3 → 4 → 5 → 6 → 8 → 7 → X → 9 → 1 diepht@vnu
28. Bài tập  Thực hiện bằng tay phép nhân: 1234 x 5678  Đếm xem bạn đã thực hiện bao nhiêu phép nhân 2 số có 1 chữ số?  Đếm xem bạn đã thực hiện bao nhiêu phép cộng 2 số có 1 chữ số?  Trả lời các câu hỏi trên với phép nhân 2 số tự nhiên n chữ số. 28 diepht@vnu
29. Chuẩn bị tuần tới  Thực hành: Ôn tập C++  Lý thuyết: Đọc chương 15 giáo trình 29 diepht@vnu