Giáo trình Cấu trúc dữ liệu (Ngành: Hệ thống thông tin, thiết kế trang web, công nghệ thông tin) - CĐ Kinh tế Kỹ thuật TP.HCM

Chia sẻ: Solua999 Solua999 | Ngày: | Loại File: PDF | Số trang:96

Thêm vào BST

Báo xấu

38
lượt xem 6
download

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

Giáo trình Cấu trúc dữ liệu giúp người học trình bày được các bước phân tích, đánh giá độ phức tạp của thuật toán. Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương tứng trên các kiểu dữ liệu. Trình bày được các thuật toán tìm kiếm, sắp xếp.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu (Ngành: Hệ thống thông tin, thiết kế trang web, công nghệ thông tin) - CĐ Kinh tế Kỹ thuật TP.HCM

ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH  GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CÔNG NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM) TRÌNH ĐỘ: CAO ĐẲNG Thành phố Hồ Chí Minh, năm 2020
ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH  GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CÔNG NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM) TRÌNH ĐỘ: CAO ĐẲNG THÔNG TIN CHỦ NHIỆM ĐỀ TÀI Họ tên: Võ Đào Thị Hồng Tuyết Học vị: Thạc Sỹ Đơn vị: Khoa Công Nghệ Thông Tin Email: vodaothihongtuyet@hotec.edu.vn TRƯỞNG KHOA TRƯỞNG CHỦ NHIỆM BỘ MÔN ĐỀ TÀI HIỆU TRƯỞNG DUYỆT Thành phố Hồ Chí Minh, năm 2020
TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm.
GIỚI THIỆU Cấu trúc dữ liệu một trong những môn học cơ bản của sinh viên ngành Công Nghệ Thông Tin. Hiểu và vận dụng các cấu trúc dữ liệu và các giải thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các công cụ lập trình hiện đại. Cấu trúc dữ liệu có thể được xem như là 1 phương pháp lưu trữ dữ liệu trong máy tính nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệu một cách hiệu quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là 2 yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau. Việc lựa chọn một cấu trúc dữ liệu có thể sẽ ảnh hưởng lớn tới việc lựa chọn áp dụng giải thuật nào. Bài giảng “Cấu Trúc Dữ Liệu” bao gồm 4 chương, trình bày về các cấu trúc dữ liệu và các giải thuật cơ bản nhất trong tin học. Chương 1 trình bày về phân tích và thiết kế thuật toán. Đầu tiên là cách phân tích 1 vấn đề, từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng máy tính. Trình bày về đệ qui, một khái niệm rất cơ bản trong toán học. Việc sử dụng đệ qui có thể xây dựng được những chương trình giải quyết được các vấn đề rất phức tạp chỉ bằng một số ít câu lệnh, đặc biệt là các vấn đề mang bản chất đệ qui. Chương 2 trình bày về các thuật toán sắp xếp và tìm kiếm. Các thuật toán này cùng với các kỹ thuật được sử dụng trong đó được coi là các kỹ thuật cơ sở cho lập trình máy tính. Các thuật toán được xem xét bao gồm các lớp thuật toán đơn giản và cả các thuật toán cài đặt phức tạp nhưng có thời gian thực hiện tối ưu. Chương 3, 4 trình bày về các cấu trúc dữ liệu được sử dụng rất thông dụng như mảng và danh sách liên kết, ngăn xếp và hàng đợi, cây. Đó là các cấu trúc dữ liệu cũng rất gần gũi với các cấu trúc trong thực tiễn. Cuối mỗi phần đều có các câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm tra kiến thức của mình. Cuối tài liệu có các phụ lục hướng dẫn trả lời câu hỏi, mã nguồn tham khảo và tài liệu tham khảo. Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể được biểu diễn và cài đặt bằng bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có được các phân tích sâu sắc hơn và có kết quả thực tế hơn, tác giả đã sử dụng ngôn ngữ lập trình C để minh hoạ cho các cấu trúc dữ liệu và thuật toán. Do vậy, ngoài các kiến thức cơ bản về tin học, sinh viên cần có kiến thức về ngôn ngữ lập trình C. Cuối cùng, mặc dù đã hết sức cố gắng nhưng chắc chắn không tránh khỏi các thiếu sót. Tác giả rất mong nhận được sự góp ý của đồng nghiệp và sinh viên để tài liệu được hoàn thiện hơn.
MỤC LỤC CHƯƠNG 1: THIẾT KẾ GIẢI THUẬT - THUẬT GIẢI ĐỆ QUI 1 1. Thiết kế giải thuật 1 1.1. Giải thuật và ngôn ngữ diễn đạt giải thuật 1 1.2. Các bước cơ bản để giải quyết tập bài toán 2 2. Thuật giải đệ quy 4 2.1.Khái niệm về đệ qui 4 2.2.Thiết kế giải thuật đệ qui 5 2.3.Áp dụng thuật giải đệ qui 7 DANH MỤC HÌNH ẢNH CHƯƠNG 1 9 CÂU HỎI VÀ BÀI TẬP 10 CHƯƠNG 2: CÁC THUẬT GIẢI SẮP XẾP VÀ TÌM KIẾM 11 1. Một số phương pháp sắp xếp đơn giản 11 1.1. Đổi chỗ trực tiếp (Interchange Sort) 11 1.2. Nổi bọt (Bubble Sort) 14 1.3. Chèn trực tiếp (Insertion Sort) 17 1.4. Chọn trực tiếp (Selection Sort) 20 1.5. Phân hoạch (Quick Sort) 22 1.6. Nhận xét, đánh giá 25 2. Một số phương pháp tìm kiếm 27 2.1. Tìm kiếm tuần tự 27 2.2. Tìm kiếm nhị phân 29 2.3. Nhận xét, đánh giá: 32 DANH MỤC HÌNH ẢNH CHƯƠNG 2 34 CÂU HỎI VÀ BÀI TẬP 35 CHƯƠNG 3: CÁC CẤU TRÚC DỮ LIỆU 37 1. Danh sách liên kết đơn 37 2. Danh sách kiểu ngăn xếp (Stack) 42 2.1. Khái niệm 42 2.2. Cài đặt ngăn xếp bằng mảng 43 2.3. Cài đặt ngăn xếp bằng danh sách liên kết 45 3. Danh sách kiểu hàng đợi (Queue) 49 3.1. Khái niệm 49 3.2. Cài đặt hàng đợi bằng mảng 50 3.3 Cài đặt hàng đợi bằng danh sách liên kết 53 DANH MỤC HÌNH ẢNH CHƯƠNG 3 56 CÂU HỎI VÀ BÀI TẬP 57 CHƯƠNG 4: CÂY 58 1. Định nghĩa và khái niệm 58 2. Cây tổng quát 58
2.1. Biểu diễn 59 2.2. Phép duyệt 61 2.3.Cây nhị phân 63 DANH MỤC HÌNH ẢNH CHƯƠNG 4 70 CÂU HỎI VÀ BÀI TẬP 71 TÀI LIỆU THAM KHẢO 73
GIÁO TRÌNH MÔN HỌC Tên môn học: CẤU TRÚC DỮ LIỆU Mã môn học: MH3101302 Thời gian thực hiện môn học: 60 giờ; (Lý thuyết: 30 giờ; Thực hành: 28 giờ; Kiểm tra: 2 giờ) I. Vị trí, tính chất của môn học: - Vị trí: Môn học được bố trí sau khi người học học xong môn học kỹ thuật lập trình, học kỳ 1. - Tính chất: Là môn học đào tạo nghề bắt buộc. II. Mục tiêu môn học: - Về kiến thức: + Trình bày được các bước phân tích, đánh giá độ phức tạp của thuật toán + Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương tứng trên các kiểu dữ liệu. + Trình bày được các thuật toán tìm kiếm, sắp xếp - Về kỹ năng: + Vận dụng cấu trúc dữ liệu, các thao tác trên cấu trúc dữ liệu đã được sử dụng theo một bài toán cụ thể. + Vận dụng được các thuật toán tìm kiếm, sắp xếp và tự cài đặt theo một bài toán cụ thể. + Vận dụng các vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải thuật, phân tích thiết kế thuật toán. - Về năng lực tự chủ và trách nhiệm: + Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù hợp cho từng bài toán. KHOA CÔNG NGHỆ THÔNG TIN
III. Nội dung môn học: 1. Nội dung tổng quát và phân bổ thời gian: Số Thời gian (giờ) TT Tên chương, mục Bài tập, Tổng Lý Kiểm số thuyết thực hành Tra Chương 1: Thiết kế giải thuật - Thuật giải đệ qui 1. Thiết kế giải thuật 1.1. Giải thuật và ngôn ngữ diễn đạt giải thuật 1.2. Các bước cơ bản để giải 1 quyết tập bài toán 8 4 4 2. Thuật giải đệ quy 2.1. Khái niệm về đệ qui 2.2.Thiết kế giải thuật đệ qui 2.3. Áp dụng thuật giải đệ qui Chương 2: Các thuật giải sắp xếp và tìm kiếm 1. Một số phương pháp sắp xếp đơn giản 1.1. Đổi chỗ trực tiếp (Interchange Sort) 1.2. Nổi bọt (Bubble Sort) 2 16 8 7 1 1.3. Chèn trực tiếp (Insertion Sort) 1.4. Chọn trực tiếp (Selection Sort) 1.5. Phân hoạch (Quick Sort) 1.6 Nhận xét, đánh giá 2. Một số phương pháp tìm KHOA CÔNG NGHỆ THÔNG TIN
Số Thời gian (giờ) TT Tên chương, mục Bài tập, Tổng Lý Kiểm số thuyết thực hành Tra kiếm 2.1. Tìm kiếm tuần tự 2.2. Tìm kiếm nhị phân 2.3. Nhận xét, đánh giá Chương 3: Các cấu trúc dữ liệu 1.Danh sách liên kết đơn 3 2.Danh sách kiểu ngăn xếp 24 12 11 1 (Stack) 3.3.Danh sách kiểu hàng đợi (Queue) Chương 4: Cây 1. Định nghĩa và khái niệm 2. Cây tổng quát 4 12 6 6 2.1. Biểu diễn 2.2. Phép duyệt 2.3. Cây nhị phân Cộng 60 30 28 2 Nội dung chi tiết: Chương 1: Thiết kế giải thuật - Thuật giải đệ qui Thời gian: 8 giờ Mục tiêu: Trình bày được các bước cơ bản để giải quyết bài tập, và dần hình thành việc thiết kế giải thuật để giải quyết theo yêu cầu. Trình bày được khái niệm về giải thuật đệ quy, trình bày được các bước xây dựng thuật giải đệ quy. Qua đó đề xuất hướng áp dụng thuật giải đệ quy cho bài toán cụ thể. Nội dung: KHOA CÔNG NGHỆ THÔNG TIN
1. Thiết kế giải thuật 1.1.Giải thuật và ngôn ngữ diễn đạt giải thuật 1.2.Các bước cơ bản để giải quyết tập bài toán 2. Thuật giải đệ quy 2.1.Khái niệm về đệ qui 2.2.Thiết kế giải thuật đệ qui 2.3.Áp dụng thuật giải đệ qui Chương 2: Các thuật giải sắp xếp và tìm kiếm Thời gian: 16 giờ Mục tiêu: Tình bày được các giải thuật sắp xếp và tìm kiếm. Phân biệt được các thuật toán sắp xếp và tìm kiếm. Sinh viên có khả năng cài đặt được các thuật toán sắp xếp và tìm kiếm Nội dung: 1. Một số phương pháp sắp xếp đơn giản 1.1. Đổi chỗ trực tiếp (Interchange Sort) 1.2. Nổi bọt (Bubble Sort) 1.3. Chèn trực tiếp (Insertion Sort) 1.4. Chọn trực tiếp (Selection Sort) 1.5. Phân hoạch (Quick Sort) 1.6 Nhận xét, đánh giá 2. Một số phương pháp tìm kiếm 2.1. Tìm kiếm tuần tự 2.2. Tìm kiếm nhị phân 2.3. Nhận xét, đánh giá Chương 3: Các cấu trúc dữ liệu Thời gian: 24 giờ Mục tiêu: Trình bày được các cấu trúc dữ liệu cơ bản như ngăn xếp, hàng đợi, danh sách liên kết. Trình bày được các thao tác cơ bản trên cấu trúc dữ liệu. Vận dụng cấu trúc dữ liệu vào một bài toán cụ thể KHOA CÔNG NGHỆ THÔNG TIN
Nội dung: 1. Danh sách liên kết đơn 2. Danh sách kiểu ngăn xếp (Stack) 3. Danh sách kiểu hàng đợi (Queue) Chương 4: Cây Thời gian: 12 giờ Mục tiêu: Trình bày được định nghĩa, tính chất của cây. Trình bày được cấu trúc cơ bản của cây nhị phân, cây nhị phân tìm kiếm và các thao tác cơ bản trên cây nhị phân, cây nhị phân tìm kiếm. Nội dung: 1.Định nghĩa và khái niệm 2.Cây tổng quát 2.1. Biểu diễn 2.2. Phép duyệt 2.3.Cây nhị phân IV. Điều kiện thực hiện môn học: 1. Phòng học chuyên môn hóa/nhà xưởng: phòng máy 2. Trang thiết bị máy móc: máy chiếu, màn chiếu, hệ thống âm thanh 3. Học liệu, dụng cụ, nguyên vật liệu: bảng 4. Các điều kiện khác: không V. Nội dung và phương pháp, đánh giá: 1. Nội dung: - Chương 1: Phân tích, thiết kế giải thuật - Chương 2: Thuật giải đệ qui - Chương 2: Các thuật giải sắp xếp và tìm kiếm - Chương 3: Các cấu trúc dữ liệu - Chương 4: Cây - Kiến thức: KHOA CÔNG NGHỆ THÔNG TIN
+ Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương tứng trên các kiểu dữ liệu. + Trình bày được các thuật toán tìm kiếm, sắp xếp - Kỹ năng: + Vận dụng cấu trúc dữ liệu, các thao tác trên cấu trúc dữ liệu đã được sử dụng theo một bài toán cụ thể. + Vận dụng được các thuật toán tìm kiếm, sắp xếp và tự cài đặt theo một bài toán cụ thể. + Vận dụng các vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải thuật, phân tích thiết kế thuật toán. - Năng lực tự chủ và trách nhiệm: + Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù hợp cho từng bài toán. 2. Phương pháp: Số cột Thời STT Phương pháp Hình thức kiểm tra gian thi 01 Kiểm tra thường xuyên Viết 1 02 Kiểm tra định kỳ Viết 1 90’ 03 Thi kết thúc môn học Viết 90’ VI. Hướng dẫn thực hiện môn học: 1. Phạm vi áp dụng môn học: Áp dụng cho khóa học trình độ cao đẳng. 2. Hướng dẫn về phương pháp giảng dạy, học tập môn học: - Đối với giáo viên, giảng viên: + Giáo viên có thể vận dụng phương pháp thuyết trình, giảng giải kết hợp phương pháp gợi mở, phát vấn để người học nghề có thể tham gia tích cực vào bài giảng. + Phương tiện, dụng cụ giảng dạy: Ngoài phương tiện giảng dạy truyền thống giáo viên còn có thể sử dụng Máy chiếu Projector, Laptop, sơ đồ, tranh ảnh minh hoạ giúp làm rõ và sinh động nội dung bài học. + Trong điều kiện có thể kết hợp giảng dạy lý thuyết và thực hành trong cùng một phòng học chuyên môn hoá có máy tính được nối mạng LAN và mạng Internet, có sử dụng các phương tiện dạy học bằng ngôn ngữ lập trình. - Đối với người học: KHOA CÔNG NGHỆ THÔNG TIN
+ Thực hiện đầy đủ và nghiêm túc các qui định đối với môn học và của giáo viên. + Hoàn thành đầy đủ các bài thực hành và tham dự các buổi kiểm tra trên lớp. + Kết thúc khóa học, người học sẽ làm một bài kiểm tra để xác định việc họ có hoàn thành chương trình học hay không + Học sinh tham gia đầy đủ các buổi lên lớp (không nghỉ quá 30% thời lượng học) 3. Những trọng tâm cần chú ý: - Trình độ giáo viên: ít nhất phải có bằng cử nhân hoặc bằng cấp tương đương tính theo kinh nghiệm dạy học trước đó. Có chứng chỉ dạy nghề. - Nguồn lực đào tạo: Những nguồn lực sau đây được khuyến khích sử dụng để bổ trợ những phương pháp giảng dạy đề xuất. + Cuốn hướng dẫn dành cho giáo viên: được biên soạn và trình bày trong các khóa tập huấn đào tạo giáo viên. + Cơ sở vật chất, trang thiết bị giảng dạy: Lớp học có đầy đủ máy vi tính cho học sinh thực tập. + Sách, giáo trình và tài liệu tham khảo. + Kế hoạch giảng dạy và giáo án chi tiết của giáo viên đóng vai trò tài liệu chính được sử dụng trong quá trình giảng dạy. - Phương pháp đào tạo: Giáo viên kết hợp nhiều chiến lược giảng dạy để giúp tất cả người học thuộc mọi đối tượng có những tiến bộ nhất định nào đó. 4. Tài liệu tham khảo: Tên sách – giáo Năm TT Tên tác giả NXB trình XB PGS.TS. Hàn Viết Thuận Cấu trúc dữ liệu và Đại Học Kinh Tế 1 2018 ThS. Nguyễn Anh Phương giải thuật Quốc Dân Bản dịch tiếng 2 Robert Sedgewick Algorithms Việt, NXB Khoa 1994 học và Kỹ thuật, KHOA CÔNG NGHỆ THÔNG TIN
Chương 1: Thiết kế giải thuật – thuật giải đệ qui CHƯƠNG 1: THIẾT KẾ GIẢI THUẬT - THUẬT GIẢI ĐỆ QUI Mục tiêu: Trình bày được các bước cơ bản để giải quyết bài tập và dần hình thành việc thiết kế giải thuật để giải quyết theo yêu cầu. Trình bày được khái niệm về giải thuật đệ quy, trình bày được các bước xây dựng thuật giải đệ quy. Qua đó đề xuất hướng áp dụng thuật giải đệ quy cho bài toán cụ thể. 1. Thiết kế giải thuật 1.1. Giải thuật và ngôn ngữ diễn đạt giải thuật 1.1.1. Giải thuật Là một dãy các thao tác xác định trên một đối tượng, sao cho sau khi thực hiện một số hữu hạn các bước thì đạt được mục tiêu. Theo R.A.Kowalski thì bản chất của giải thuật: Giải thuật = Logic + Điều khiển Logic: Đây là phần khá quan trọng, nó trả lời câu hỏi "giải thuật làm gì, giải quyết vấn đề gì?", những yếu tố trong bài toán có quan hệ với nhau như thế nào v.v… Ở đây bao gồm những kiến thức chuyên môn mà bạn phải biết để có thể tiến hành giải bài toán. Ví dụ: để giải một bài toán tính diện tích hình cầu, mà bạn không còn nhớ công thức tính hình cầu thì bạn không thể viết chương trình cho máy để giải bài toán này được. Điều khiển: Thành phần này trả lời câu hỏi: giải thuật phải làm như thế nào? Chính là cách thức tiến hành áp dụng thành phần logic để giải quyết vấn đề. 1.1.2. Ngôn ngữ diễn đạt giải thuật Sau khi đã xây dựng được mô hình toán học cho vấn đề cần giải quyết, tiếp theo, ta có thể hình thành một thuật toán cho mô hình đó. Phiên bản đầu tiên của thuật toán thường được diễn tả dưới dạng các phát biểu tương đối tổng quát, và sau đó sẽ được tinh chỉnh dần từng bước thành chuỗi các lệnh cụ thể, rõ ràng hơn. Mối liên hệ giữa Cấu trúc dữ liệu và giải thuật Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên những đối tượng đó. Vì thế, để xây dựng một mô hình tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề : Tổ chức biểu diễn các đối tượng thực tế : Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựng những quan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ chức , xây dựng các cấu trúc thích hợp nhất sao cho vừa có thể phản ánh chính xác các KHOA CÔNG NGHỆ THÔNG TIN Trang 1
Chương 1: Thiết kế giải thuật – thuật giải đệ qui dữ liệu thực tế này, vừa có thể dễ dàng dùng máy tính để xử lý. Công việc này được gọi là xây dựng cấu trúc dữ liệu (Data structure) cho bài toán. Xây dựng các thao tác xử lý dữ liệu: Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thi hành để cho ra kết quả mong muốn, đây là bước xây dựng giải thuật (Algorithm) cho bài toán. Trong một đề án tin học, giải thuật và cấu trúc dữ liệu có mối quan hệ chặt chẽ với nhau, được thể hiện qua công thức : Cấu trúc dữ liệu + Giải thuật = Chương trình 1.2. Các bước cơ bản để giải quyết tập bài toán Chương trình (Program) Là một tập hợp các mô tả, các phát biểu, nằm trong một hệ thống qui ước về ý nghĩa và thứ tự thực hiện, nhằm điều khiển máy tính làm việc. Theo Niklaus Wirth thì: Chương trình = Thuật toán + Cấu trúc dữ liệu Các thuật toán và chương trình đều có cấu trúc dựa trên 3 cấu trúc điều khiển cơ bản: Tuần tự (Sequential): Các bước thực hiện tuần tự một cách chính xác từ trên xuống, mỗi bước chỉ thực hiện đúng một lần. Chọn lọc (Selection): Chọn 1 trong 2 hay nhiều thao tác để thực hiện. Lặp lại (Repetition): Một hay nhiều bước được thực hiện lặp lại một số lần. Ngôn ngữ lập trình (Programming language) Ngôn ngữ lập trình là hệ thống các ký hiệu tuân theo các qui ước về ngữ pháp và ngữ nghĩa, dùng để xây dựng thành các chương trình cho máy tính. Một chương trình được viết bằng một ngôn ngữ lập trình cụ thể (ví dụ Pascal, C…) gọi là chương trình nguồn, chương trình dịch làm nhiệm vụ dịch chương trình nguồn thành chương trình thực thi được trên máy tính. Các bước lập trình: Bước 1: Phân tích vấn đề và xác định các đặc điểm. (xác định I-P-O) Bước 2: Lập ra giải pháp. (đưa ra thuật giải) Bước 3: Cài đặt. (viết chương trình) Bước 4: Chạy thử chương trình. (dịch chương trình) KHOA CÔNG NGHỆ THÔNG TIN Trang 2
Chương 1: Thiết kế giải thuật – thuật giải đệ qui Bước 5: Kiểm chứng và hoàn thiện chương trình. (thử nghiệm bằng nhiều số liệu và đánh giá) Kỹ thuật lập trình I-P-O Cycle (Input-Pprocess-Output Cycle) (Quy trình nhập-xử lý-xuất) Quy trình xử lý cơ bản của máy tính gồm I-P-O. Input Output Process Hình 1. 1 Quy trình xử lý cơ bản của máy tính Ví dụ 1: Xác định Input, Process, Output của việc làm 1 ly nước chanh nóng Input : ly, đường, chanh, nước nóng, muỗng. Process : - cho hỗn hợp đường, chanh, nước nóng vào ly. - dùng muỗng khuấy đều. Output : ly chanh nóng đã sẵn sàng để dùng. Ví dụ 2: Xác định Input, Process, Output của chương trình tính tiền lương công nhân tháng 10/2002 biết rằng lương = lương căn bản * ngày công Input : lương căn bản, ngày công Process : nhân lương căn bản với ngày công Output : lương Ví dụ 3: Xác định Input, Process, Output của chương trình giải phương trình bậc nhất ax + b = 0 Input : hệ số a, b Process : chia – b cho a Output : nghiệm x Ví dụ 4: Xác định Input, Process, Output của chương trình tìm số lớn nhất của 2 số a và b. Input : a, b Process : Nếu a > b thì Output = a lớn nhất Ngược lại Output = b lớn nhất Với mỗi vấn đề cần giải quyết, ta có thể tìm ra nhiều thuật toán khác nhau. Có những thuật toán thiết kế đơn giản, dễ hiểu, dễ lập trình và sửa lỗi, tuy nhiên thời gian KHOA CÔNG NGHỆ THÔNG TIN Trang 3
Chương 1: Thiết kế giải thuật – thuật giải đệ qui thực hiện lớn và tiêu tốn nhiều tài nguyên máy tính. Ngược lại, có những thuật toán thiết kế và lập trình rất phức tạp, nhưng cho thời gian chạy nhanh hơn, sử dụng tài nguyên máy tính hiệu quả hơn. Khi đó, câu hỏi đặt ra là ta nên lựa chọn giải thuật nào để thực hiện? Đối với những chương trình chỉ được thực hiện một vài lần thì thời gian chạy không phải là tiêu chí quan trọng nhất. Đối với bài toán kiểu này, thời gian để lập trình viên xây dựng và hoàn thiện thuật toán đáng giá hơn thời gian chạy của chương trình và như vậy những giải thuật đơn giản về mặt thiết kế và xây dựng nên được lựa chọn. Đối với những chương trình được thực hiện nhiều lần thì thời gian chạy của chương trình đáng giá hơn rất nhiều so với thời gian được sử dụng để thiết kế và xây dựng nó. Khi đó, lựa chọn một giải thuật có thời gian chạy nhanh hơn (cho dù việc thiết kế và xây dựng phức tạp hơn) là một lựa chọn cần thiết. Trong thực tế, trong giai đoạn đầu của việc giải quyết vấn đề, một giải thuật đơn giản thường được thực hiện trước như là 1 nguyên mẫu (prototype), sau đó nó sẽ được phân tích, đánh giá, và cải tiến thành các phiên bản tốt hơn. 2. Thuật giải đệ quy 2.1.Khái niệm về đệ qui Khái niệm: Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. Ví dụ: Tổng S(n) được tính thông qua tổng S(n-1). Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)? Hình 1. 2 Mô tả các bước tính tổng S(n)=1+2+3+…+n với S(10) và S(11) KHOA CÔNG NGHỆ THÔNG TIN Trang 4
Chương 1: Thiết kế giải thuật – thuật giải đệ qui 2 điều kiện quan trọng: - Tồn tại bước đệ quy. - Điều kiện dừng. 2.2.Thiết kế giải thuật đệ qui 2.2.1.Hệ thức truy hồi Khái niệm: Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. Hình 1. 3 Mô tả hệ thức truy hồi Ví dụ 1: Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? Giải pháp - Gọi Vh là số vi trùng tại thời điểm h. - Ta có: • Vh = 2Vh-1 • V0 = 2 Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2 Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu? Giải pháp - Gọi Tn là số tiền có được sau n năm. - Ta có: • Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1 • V(0) = 1000 Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000 2.2.2.Chia để trị (divide & conquer) Khái niệm: - Chia bài toán thành nhiều bài toán con. KHOA CÔNG NGHỆ THÔNG TIN Trang 5
Chương 1: Thiết kế giải thuật – thuật giải đệ qui - Giải quyết từng bài toán con. - Tổng hợp kết quả từng bài toán con để ra lời giải. Thuật toán mô tả chia để trị: { if (P đủ nhỏ) Xử lý P else { Chia P  P1, P2, …, Pn for (int i=1;i
Chương 1: Thiết kế giải thuật – thuật giải đệ qui và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN Nhân 3 số nhỏ hơn (độ dài ½) đến khi có thể nhân được ngay. 2.2.3.Lần ngược (Backtracking) Khái niệm - Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp. - Nếu không thành công thì “lần ngược” chọn bước khác. - Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần ngược” để truy tìm lời giải mới. - Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã đi tuần. Hình 1. 4 Mô tả lần ngược (Backtracking) 2.3.Áp dụng thuật giải đệ qui Một số bài toán kinh điển Hình 1. 5 Một số bài toán kinh điển 2.3.1. Tháp Hà Nội Mô tả bài toán: Có 3 cột A, B và C và cột A hiện có N đĩa. Tìm cách chuyển N đĩa từ cột A sang cột C sao cho: - Một lần chuyển 1 đĩa - Đĩa lớn hơn phải nằm dưới. - Có thể sử dụng các cột A, B, C làm cột trung gian. KHOA CÔNG NGHỆ THÔNG TIN Trang 7