Bài giảng Cấu trúc dữ liệu và giải thuật - Chương mở đầu - Dương Thành Phết

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương mở đầu - Dương Thành Phết

1. Trường Đại Học Kinh Tế Kỹ Thuật Bình Dương Khoa Kỹ Thuật - Công Nghệ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giảng viên: Dương Thành Phết Email: phetcm@gmail.com Website: 1 Tel: 0918158670 – 08.3.7900261
2. Lời Nói Đầu ✓ Cấu trúc DL & GT là 1 trong những môn học cơ bản, quan trong nhất cho sinh viên ngành CNTT Chương trình = Cấu trúc dữ liệu + Giải thuật ✓ Cấu trúc dữ liệu: Là phương pháp tổ chức lưu trữ và sử dụng dữ liệu trong máy tính một cách hiệu quả nhất. ✓ Giải thuật (thuật toán): Cách thức để xử lý và khai thác dữ liệu ✓ Cấu trúc dữ liệu và giải thuật là 2 yếu tố có quan hệ chặt chẽ và không thể tách rời. 2 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
3. Mục tiêu Sau khi kết thúc học phần, sinh viên có khả năng: ✓ Mô tả được vai trò của cấu trúc dữ liệu và giải thuật ✓ Đánh giá, so sánh được độ phức tạp của các giải thuật ✓ Trình bày được tư tưởng và minh họa các giải thuật tìm kiếm, sắp xếp trên mảng một chiều ✓ Trình bày được các khái niệm, thao tác trên các cấu trúc dữ liệu như: danh sách liên kết đơn, hàng đợi, ngăn xếp, cây nhị phân tìm kiếm ✓ Kỹ năng thực hành cài đặt được các giải thuật và các thao tác trên các cấu trúc dữ liệu bằng ngôn ngữ C/ C++ 3 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
4. Điều kiện ✓ Đã học qua môn Tin học đại cương ✓ Đã học qua môn kỹ thuật lập trình C Thời lượng Tổng số: 45 tiết lý thuyết: 45 tiết Tự học: 90 giờ 4 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
5. Đánh giá kết quả học tập ❖ Tham gia học tập trên lớp (đi học đầy đủ, chuẩn bị bài tốt, tích cực thảo luận và phát biểu, ): 10% ❖ Kiểm tra giữa kỳ: 20% (Tự luận) ❖ Thuyết trình: 20%(Thực hiện theo nhóm) ❖ Kiểm tra cuối kỳ : 50% (Tự luận, thời gian 60’, không sử dụng tài liệu) 5 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
6. Nhiệm vụ của sinh viên ❖ Xem bài giảng và tài liệu tham khảo trước mỗi buổi lên lớp. ❖ Tích cực tham gia phát biểu, đóng góp ý kiến xây dựng bài. ❖ Chia nhóm để làm bài tập và báo cáo do giảng viên giao. ❖ Tự giác tìm tài liệu, nghiên cứu và thảo luận nhóm khi ở nhà. ❖ Nghiêm túc làm tất cả các bài tập trong giờ thực hành. 6 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
7. Phần mềm thực hành ✓ Microsoft Visual C++ 6.0 hoặc ✓ Microsoft Visual .Net 2005 Viết ứng dụng dạng Console 7 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
8. Tài liệu học tập & Tài liệu tham khảo [1] Dương Thành Phết, Bài giảng Cấu Trúc Dữ Liệu & Giải thuật, Khoa CNTT Trường ĐH KTKT Bình Dương(2010). [2] Dương Thành Phết, Bài tập Cấu Trúc Dữ Liệu & Giải thuật, Khoa CNTT Trường ĐH KTKT Bình Dương(2010 [3]. Trần Hạnh Nhi – Dương Anh Đức, Cấu trúc dữ liệu, Khoa CNTT, Trường ĐHKHTN – ĐHQG TP.HCM [4]. Nguyễn Trung Trực, Cấu trúc dữ liệu, Khoa CNTT, trường ĐHBK TP.HCM [5]. Nguyễn Xuân Huy. Thuật toán. Nhà xuất bản Thống kê, 1988 [6]. Algorithms + Data Structure = Programs (Sách dịch) - N.Wirth. NXB Thống kê, 1981. [7]. Programs and Data Structures in C - Leendert Ammeraal. John Willey & Sons Press. 8 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
9. NỘI DỤNG ✓ Chương 1: Tổng quan về cấu trúc dữ liệu và thuật toán ✓ Chương 2: Tìm kiếm và sắp xếp ✓ Chương 3: Cấu trúc dữ liệu động ✓ Chương 4: Cấu trúc cây 9 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
10. Chương 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & THUẬT TOÁN 1.1. Khái niệm về cấu trúc dữ liệu và giải thuật 1.1.1. Cấu trúc dữ liệu 1.1.2. Giải thuật 1.1.3. Sự liên hệ giữa giải thuật và cấu trúc dữ liệu 1.2. Phân tích giải thuật 1.2.1. Phân tích thời gian thực hiện giải thuật 1.2.2. Độ phức tạp tính toán của giải thuật 1.2.3. Xác định độ phức tạp tính toán 1.3. Bài tập 10 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
11. Chương 2 TÌM KiẾM & SẮP XẾP 2.1. Các giải thuật tìm kiếm 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 2.2. Các giải thuật sắp xếp 2.2.1. Bài toán sắp xếp 2.2.2 Giải thuật đổi chổ trực tiếp –Interchange Sort 2.2.3 Giải thuật chọn trực tiếp-Selection Sort 2.2.4 Giải thuật chèn trực tiếp-Insert Sort 2.2.5 Giải thuật nổi bọt – Bubble Sort 2.2.6 Giải thuật nhanh – Quick Sort 11 2.3. Bài tập © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
12. Chương 3: CẤU TRÚC DỮ LIỆU ĐỘNG 3.1. Kiểu dữ liệu con trỏ 3.2. Danh sách liên kết (link list) 3.3. Danh sách liên kết đơn 3.4. Sắp xếp danh sách 3.5. Các cấu trúc đặc biệt của danh sách liên kết đơn 3.5.1. Stack 3.5.2. Hàng đợi (Queue) 3.6. Bài tập 12 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
13. Chương 4 CẤU TRÚC CÂY 4.1. Cấu trúc cây 4.1.1. Định nghĩa 4.1.2. Một số khái niệm cơ bản 4.2. Cây nhị phân 4.2.1. Định nghĩa 4.2.2. Một số tính chất của cây nhị phân 4.2.3. Biểu diễn cây nhị phân 4.3. Cây nhị phân tìm kiếm 4.3.1. Cây nhị phân tìm kiếm 4.3.2. Các thao tác trên cây nhị phân tìm kiếm 4.4. Bài tập 13 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
14. Nội dung thi cuối kỳ ✓ Giải thuật tìm kiếm ✓ Giải thuật sắp xếp ✓ Danh sách liên kết ✓ Cây nhị phân tìm kiếm 14 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương