Bài giảng Thuật toán

Tham khảo sách bài giảng thuật toán, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Bài giảng Thuật toán Bài giảngThuật toán MỤC LỤC1. THUẬT TOÁN2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN4.PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN5. THUẬT TOÁN ĐỆ QUY6.THUẬT GIẢI5.1.GIỚI THIỆU NGÔN NGỮ PASCAL5.2. CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL5.3. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH PASCAL5.4. SỬ DỤNG PHẦN MỀM TURBO PASCAL5.5 CÂU HỎI TRẮC NGHIỆM5.6. BÀI TẬP6.1. KHÁI NIỆM VỀ KIỂU DỮ LIỆU6.2. KIỂU SỐ NGUYÊN6.3. KIỂU SỐ THỰC6.4. KIỂU KÝ TỰ (CHAR)6.5. KIỂU LÔGIC (BOOLEAN)6.6. CHUỖI KÝ TỰ (STRING)6.7. CÂU HỎI TRẮC NGHIỆM7.1. HẰNG, BIẾN và BIỂU THỨC7.2. CÂU LỆNH và LỜI CHÚ GIẢI7.3.1. NHẬP DỮ LIỆU, THỦ TỤC “READLN”7.3.2. XUẤT DỮ LIỆU, THỦ TỤC “WRITE” và “WRITELN”7.4. KIỂU LIỆT KÊ và KIỂU ÐOẠN CON7.5. CÂU HỎI TRẮC NGHIỆM7.6. BÀI TẬP8.1. CÂU LỆNH IF8.2. CÂU LỆNH CASE8.3. CÂU HỎI TRẮC NGHIỆM8.4. BÀI TẬP9.1. CÂU LỆNH LẶP FOR9.2. CÂU LỆNH LẶP WHILE9.3. CÂU LỆNH LẶP REPEAT9.4. CÂU HỎI TRẮC NGHIỆM9.5. BÀI TẬP10.1. MẢNG MỘT CHIỀU10.2. MẢNG HAI CHIỀU (MA TRẬN)10.3. CÂU HỎI TRẮC NGHIỆM10.4. BÀI TẬP11.1. CÁC VÍ DỤ NÂNG CAO VỀ CÂU LỆNH LẶP11.2. CÁC VÍ DỤ NÂNG CAO VỀ MẢNG11.3. KIỂU CHUỖI KÝ TỰ11.4. CÂU HỎI TRẮC NGHIỆM11.5. BÀI TẬP12.1. KHÁI NIỆM VỀ CHƯƠNG TRÌNH CON12.2. HÀM (FUNCTION)12.3. THỦ TỤC (PROCEDURE)12.4. CÂU HỎI TRẮC NGHIỆM12.5. BÀI TẬP13.1. THAM SỐ TRỊ VÀ THAM SỐ BIẾN13.2. PHẠM VI TÁC DỤNG CỦA CÁC KHAI BÁO13.3. SỰ THAM KHẢO TRƯỚC và SỰ ÐỆ QUI13.4. CÂU HỎI TRẮC NGHIỆM13.5. BÀI TẬP14.1 KIỂU BẢN GHI14.2. CÁC VÍ DỤ VỀ BẢN GHI14.3. CÂU HỎI TRẮC NGHIỆM14.4 .BÀI TẬP15.1. KIỂU TẬP HỢP15.2. DỮ LIỆU KIỂU TẬP TIN15.3. CÂU HỎI TRẮC NGHIỆM15.4. BÀI TẬP 1. THUẬT TOÁN Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toánlà một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề- bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán cóthể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải củavấn đề - bài toán. Tại sao lại là Thuật toán ?Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allahibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học,trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này,phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toánhọc khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông. Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉgiải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặckhông rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toánđược định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trìnhhành động theo các bước này phải dừng và cho được kết quả như mong muốn. Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Sốbước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề- bài toán có vô số bước giải ? Tính không mập mờ và có thể thực thi được gọi chung là tính xácđịnh.Giả sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên chủ nhiệm chọn lớp trưởng mớitheo các bước sau : 1. Lập danh sách tất các học sinh trong lớp. 2. Sắp thứ tự danh sách học sinh. 3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng.Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu là trong danh sáchhọc sinh cần có những thông tin gì? Danh sách chỉ cần họ tên, hay cần thêm ngày tháng năm sinh?Có cần thêm điểm trung bình không? Yêu cầu 2 lại càng gây nhiều thắc mắc. Cần phải sắp xếp danhsách theo chiều tăng dần hoặc giảm dần ? Sắp theo chỉ tiêu gì ? Theo tên, theo ngày tháng năm sinhhay theo điểm trung bình chung, ...Giả sử sắp theo điểm trung bình thì nếu có hai học sinh cùngđiểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ sắp sau ? ...Hướng dẫn ở trên vi phạm tính chất không mập mờ của thuật toán. Nghĩa là, có quá nhiều thôngtin còn thiếu để làm cho các bước 1,2 được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu sửalại một chút ít thì hướng dẫn trên sẽ trở nên rõ ràng hơn rất nhiều và có thể gọi là một thuật toánchọn lớp trưởng ! 1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuốinăm. 2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Haihọc sinh có cùng điểm trung bình sẽ có cùng hạng. 3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng. Trường hợp cónhiều học sinh đồng hạng nhất thì chọn học sinh ...