Giáo trình một số vấn đề về thuật toán

Hiện tại sách khoa học về tin học bằng tiếng 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 trình cũng chủ yếu 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á O-lớn hoặc a-nhỏ, phương trình 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áo 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ừ đơn giản đến phức tạp, mỗi khái niệm mới đều được định nghĩa trước khi vào bài tập. Xương sống trong lí luận của 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.
Chương 1 của cuốn sách hoàn toàn mang tính công cụ toán học. Những bài tập trong chương này rất hay về mặt toán học và nó còn tạo đà cho các chương sau chuyên về tin học. Chương 2 nói về tính đúng đắn của thuật toán và cách chứng minh tính đúng đắn đó cho các thuật toán quen thuộc. Những chương còn lại chỉ ra độ phức tạp tính toán của các thuật toán kết hợp với phương pháp thiết kế chúng như phương pháp chia để trị, phương pháp quy hoạch động, phương pháp tham, phương pháp quy lui, …. Việc chỉ ra độ phức tạp tính toán của các thuật toán còn cho ta hướng phân tích và thiết kế thuật toán một cách tối ưu nhất. Các thuật toán được thể hiện bằng ngôn ngữ giả mã gần như ngôn ngữ lập trình Pascal mà nhiều người đã quen thuộc. Các bước của mỗi thuật toán được đánh số theo dòng, những giải thích và lập luận đều dựa trên các số dòng này. Mỗi mục đều có những bài giải mẫu và sau đó là những bài tập. Những bài tập có thể có lời giải hoặc gợi ý hoặc bạn đọc phải suy ngẫm dựa trên các ví dụ đã giải..
Do thời gian biên soạn cuốn sách bị eo hẹp nên có thể còn vài sai sót, mong bạn đọc góp ý. Hơn nữa, còn nhiều vấn đề về thuật toán liên quan đến độ phức tạp tính toán của chúng không được trình bày ở đây. Xin hẹn trong một tài liệu khác, chúng tôi sẽ giới thiệu về các chuyên đề như thuật toán sắp xếp, tìm kiếm, thuật toán số học, các thuật toán trong lí thuyết đồ thị, … cùng các hàm thời gian tính toán của chúng và các chủ đề tính toán với thuật toán có độ phức tạp P, NP, NP đầy đủ,…Trình bày và biên soạn cuốn sách bằng chương trình LATEX có cài dấu tiếng Việt do tác giả thực hiện.

Nguồn: https://www.thuvienpdf.com