Chương 1: Công cụ để phân tích thuật toán và thiết kế thuật toán Thuật toán và các tính chất của nó Sử dụng thuật toán không phải chỉ bắt đầu từ khi xuất hiện máy tính. Loài người đã sử dụng thuật toán từ rất lâu để giải một cách hệ thống các bài toán. Một cách hình thức, một thuật toán có thể được mô tả như một dãy hữu hạn | NGUYỀN HỮU ĐIỂN Một số vấn để về THUẬT TOÁN CD NHÀ XUẤT BẢN GIÁO DỤC NGUYỄN HỮU ĐIÊN MỘT SÔ VẤN ĐỀ VÊ THUẬT TOÁN NHÀ XUẤT BẢN GIÁO DỤC LỜI NÓI ĐẨU Hiện tại sách khoa học về tín học bằng tiếhg Việt rất hiếm. Đa sô là các sách hướng dẫn sử dụng phần mềm kể cả việc dạy lập trinh cũng chủ yếii dựa trên cơ sỏ một phần mềm biên dịch nào đó. Tin học đã được phát triển dựa vào ngành Toán học tất cả những lí luận của ngành này rất chặt chẽ dựa vào những nguyên lí toán học. Tin học trong quá trình phát triển cũng nảy sinh đặc thù riêng và những lí luận riêng đáp ứng công nghệ thực tế của nó. Đặc biệt khái niệm về thuật toán thì bất cứ một người học tin học nào cũng cần phải nắm vững. Thuật toán đã được các nhà tin học phát triển và nghiên cứu khá kĩ thuật toán có mặt trong mọi lĩnh vực của công nghệ. Nhưng cách thức người ta phân tích và thiết kế một thuật toán như thế nào thì không phải ai cũng hiểu thâu đắo. Cuốn sách này giới thiệu các vân đề về thuật toán với độ phức tạp tính toán của nó. Để chứng minh và phân tích thuật toán một cách đúng đắn ta phải dùng một số công cụ toán học cơ bần như phương pháp chứng minh quy nạp toán học phương pháp dùng hàm đánh giá ỡ-lớn hoặc ỡ-nhồ phượng trinh hồi quy . và các kiến thức cơ bản của toán học rời rạc. Cuốn sách này được biên soạn nhàm phục vụ cho các bạn yêu thích toán học ứng dụng và tin học các bạn ồ lộp chuyên toán chuyên tin các thầy cổ giáo và những người quan tâm đến giáọ dục toán học tin học ỏ trường phổ thông cũng như đại học. Mỗi chương đều đi từ dơn giản đến phức tạp mỗi khái niệm mớị đều được định nghĩa trước khi vào bài tập. Xương sống trong lí luân cdaĩ cuốn sách này ngoài những định nghĩa cơ bản của các khái niệm là phương pháp lập luân theo quy nạp toán học mà bạn đọc có thể xem trong cuốn sách riêng về chuyên đề này 13
