tài liệu giáo khoa chuyên tin (quyển 1)

tài liệu giáo khoa chuyên tin (quyển 1) trình bày các chuyên đề: thuật toán và phân tích thuật toán; các kiến thức cơ bản; sắp xếp; thiết kế giải thuật; các thuật toán trên đồ thị,... mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
tài liệu giáo khoa chuyên tin (quyển 1)Hå sÜ ®µm (Chñ biªn)®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïngtµi liÖu gi¸o khoachuyªn tinquyÓn 1Nhµ xuÊt b¶n gi¸o dôc viÖt namC«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc Hµ Néi - Nhµ xuÊt b¶n Gi¸o dôc ViÖt Namgi÷ quyÒn c«ng bè t¸c phÈm.349-2009/CXB/43-644/GD2M4 sè : 8I746H9LỜI NÓI ðẦUBộ Giáo dục và ðào tạo ñã ban hành chương trình chuyên tin học cho cáclớp chuyên 10, 11, 12. Dựa theo các chuyên ñề chuyên sâu trong chương trìnhnói trên, các tác giả biên soạn bộ sách chuyên tin học, bao gồm các vấn ñề cơbản nhất về cấu trúc dữ liệu, thuật toán và cài ñặt chương trình.Bộ sách gồm ba quyển, quyển 1, 2 và 3. Cấu trúc mỗi quyển bao gồm: phầnlí thuyết, giới thiệu các khái niệm cơ bản, cần thiết trực tiếp, thường dùng nhất;phần áp dụng, trình bày các bài toán thường gặp, cách giải và cài ñặt chươngtrình; cuối cùng là các bài tập. Các chuyên ñề trong bộ sách ñược lựa chọn mangtính hệ thống từ cơ bản ñến chuyên sâu.Với trải nghiệm nhiều năm tham gia giảng dạy, bồi dưỡng học sinh chuyên tinhọc của các trường chuyên có truyền thống và uy tín, các tác giả ñã lựa chọn,biên soạn các nội dung cơ bản, thiết yếu nhất mà mình ñã sử dụng ñể dạy họcvới mong muốn bộ sách phục vụ không chỉ cho giáo viên và học sinh chuyênPTTH mà cả cho giáo viên, học sinh chuyên tin học THCS làm tài liệu tham khảocho việc dạy và học của mình.Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham giacác kì thi học sinh giỏi Quốc gia, Quốc tế Hội thi Tin học trẻ Toàn quốc,Olympiad Sinh viên Tin học Toàn quốc, Kì thi lập trình viên Quốc tế khu vựcðông Nam Á, các tác giả ñã lựa chọn giới thiệu các bài tập, lời giải có ñịnhhướng phục vụ cho không chỉ học sinh mà cả sinh viên làm tài liệu tham khảokhi tham gia các kì thi trên.Lần ñầu tập sách ñược biên soạn, thời gian và trình ñộ có hạn chế nên chắcchắn còn nhiều thiếu sót, các tác giả mong nhận ñược ý kiến ñóng góp của bạnñọc, các ñồng nghiệp, sinh viên và học sinh ñể bộ sách ñược ngày càng hoànthiện hơn .Các tác giả34Chuyên ñề 1THUẬT TOÁNVÀ PHÂN TÍCH THUẬT TOÁN1. Thuật toánThuật toán là một trong những khái niệm quan trọng nhất trong tin học. Thuật ngữthuật toán xuất phát từ nhà khoa học Arập Abu Jafar Mohammed ibn Musa alKhowarizmi. Ta có thể hiểu thuật toán là dãy hữu hạn các bước, mỗi bước mô tảchính xác các phép toán hoặc hành ñộng cần thực hiện, ñể giải quyết một vấn ñề.ðể hiểu ñầy ñủ ý nghĩa của khái niệm thuật toán chúng ta xem xét 5 ñặc trưng saucủa thuật toán:•ðầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào ñó.•ðầu ra (Output): Với mỗi tập các dữ liệu ñầu vào, thuật toán ñưa ra cácdữ liệu tương ứng với lời giải của bài toán.•Chính xác: Các bước của thuật toán ñược mô tả chính xác.•Hữu hạn: Thuật toán cần phải ñưa ñược ñầu ra sau một số hữu hạn (cóthể rất lớn) bước với mọi ñầu vào.•ðơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán ñượcxác ñịnh một cách ñơn trị và chỉ phụ thuộc vào ñầu vào và các kết quảcủa các bước trước.•Tổng quát: Thuật toán có thể áp dụng ñể giải mọi bài toán có dạngñã cho.ðể biểu diễn thuật toán có thể biểu diễn bằng danh sách các bước, các bước ñượcdiễn ñạt bằng ngôn ngữ thông thường và các kí hiệu toán học; hoặc có thể biểudiễn thuật toán bằng sơ ñồ khối. Tuy nhiên, ñể ñảm bảo tính xác ñịnh của thuậttoán, thuật toán cần ñược viết bằng các ngôn ngữ lập trình. Một chương trình là sựbiểu diễn của một thuật toán trong ngôn ngữ lập trình ñã chọn. Trong tài liệu này,chúng ta sử dụng ngôn ngữ tựa Pascal ñể trình bày các thuật toán. Nói là tựaPascal, bởi vì nhiều trường hợp, ñể cho ngắn gọn, chúng ta không hoàn toàn tuân5