MỞ ĐẦU 1. 1 Từ bài toán đên chương trình Để lập trình giải một bài toán bằng máy tính ta thường trải qua 2 giai đoạn giai đoạn 1: thiết kế - nhằm xác định bài toán cần giải quyết và xây dựng mô hình toán học cho bài toán. Mục đích của giai đoạn này là nhằm trả lời hai câu hỏi: Bài toán cho cái gì và yêu cầu làm những gì? sau đó trả lời câu hỏi “để thực hiện các yêu cầu của bài toán thì làm như thế nào”. Giai đoạn 2: Mã hóa - Sử dụng ngôn ngữ lập trình cụ thể để viết chương trình ứng với cách làm của giai đoạn trước nó 1.1 Xác định & mô hình hóa bài toán cần giải quyết Khi giải quyết 1 bài toán thực tế ta phải bắt đầu từ việc xác định bài toán, giai đoạn này cần nhiều thời gian và công sức bỏ ra để thực hiện.
Nó nhằm trả lời rõ ràng các câu hỏi: 1) bài toán yêu cầu ta "phải làm những công việc gì?"; 2) để thực hiện các công việc thì ta phải "làm như thế nào?". Thông thường, khi khởi đầu, hầu hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức tạp của bài toán thực tế, ta phải hình thức hóa nó, nghĩa là phát biểu lại bài toán thực tế thành một bài toán hình thức (hay còn gọi là mô hình toán). Có thể có rất nhiều bài toán thực tế có cùng một mô hình toán.
Ví dụ 1: Xét bài toán tô màu bản đồ thế giới. Ta cần phải tô màu cho các nước trên bản đồ thế giới. Trong đó mỗi nước đều được tô một màu và hai nước láng giềng (cùng biên giới) thì phải được tô bằng hai màu khác nhau. Hãy tìm một phương án tô màu sao cho số màu sử dụng là ít nhất.
Việc lựa chọn và xây dựng mô hình toán học cho bài toán diễn ra theo phân tích sau: Có thể xem mỗi nước trên bản đồ thế giới là một đỉnh của đồ thị, hai nước láng giềng của nhau thì hai đỉnh ứng với nó được nối với nhau bằng một cạnh. Bài toán lúc này trở thành bài toán tô màu cho đồ thị: Mỗi đỉnh đều phải được tô màu, Hai đỉnh có cạnh nối thì phải tô bằng hai màu khác nhau và ta cần tìm một phương án tô màu sao cho số màu được sử dụng là ít nhất. Mô hình toán học được sử dụng trong bài toán này là mô hình đồ thị. Ví dụ 2: Xét bài toán điều khiển đèn giao thông Cho một ngã năm như hình 1.1, trong đó C và E là các đường một chiều theo chiều mũi tên, các đường khác là hai chiều.
Hãy thiết kế một bảng đèn hiệu điều khiển giao thông tại ngã năm này một cách hợp lý, nghĩa là: phân chia các lối đi tại ngã năm này thành các nhóm, mỗi nhóm gồm các lối đi có thể cùng đi đồng thời nhưng không xảy ra tai nạn giao thông (các lối đi này có các hướng đi không cắt nhau), và số lượng nhóm chia là ít nhất có thể được.1 – Ngã năm giao thông với các lỗi rẽ Việc lựa chọn, xây dựng mô hình toán học cho bài toán được diễn ra theo phân tích sau: Có thể xem đầu vào của bài toán là tất cả các lối đi tại ngã năm này, đầu ra của bài toán là các nhóm lối đi có thể đi đồng thời mà không xảy ra tai nạn giao thông, mỗi nhóm sẽ tương ứng với một pha điều khiển của đèn hiệu, vì vậy ta phải tìm kiếm lời giải với số nhóm là ít nhất để giao thông không bị tắc nghẽn vì phải chờ đợi quá lâu. Trước hết ta nhận thấy rằng tại ngã năm này có 13 lối đi: AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED. Tất nhiên, để có thể giải được bài toán ta phải tìm một cách nào đó để thể hiện mối liên quan giữa các lối đi này. Lối nào với lối nào không thể đi đồng thời, lối nào và lối nào có thể đi đồng thời.
Ví dụ cặp AB và EC có thể đi đồng thời, nhưng AD và EB thì không, vì các hướng giao thông cắt nhau. Ở đây ta sẽ dùng một sơ đồ trực quan như sau: tên của 13 lối đi được viết lên mặt phẳng, hai lối đi nào nếu đi đồng thời sẽ xảy ra đụng nhau (tức là hai hướng đi cắt qua nhau) ta nối lại bằng một đoạn thẳng, hoặc cong, hoặc ngoằn ngoèo tuỳ thích. Ta sẽ có một sơ đồ như hình 1. Như vậy, trên sơ đồ này, hai lối đi có cạnh nối lại với nhau là hai lối đi không thể cho đi đồng thời.
AB AC AD BA BC BD DA DB DC EA EB EC ED Hình 1.2 – Đồ thị biểu diễn quan hệ giứa các lối đi 8 Với cách biểu diễn như vậy ta đã có một mô hình toán học đồ thị (Graph), trong đó mỗi lối đi trở thành một đỉnh của đồ thị, hai lối đi không thể cùng đi đồng thời được nối nhau bằng một đoạn ta gọi là cạnh của đồ thị. Bây giờ ta phải xác định các nhóm, với số nhóm ít nhất, mỗi nhóm gồm các lối đi có thể đi đồng thời, nó ứng với một pha của đèn hiệu điều khiển giao thông. Giả sử rằng, ta dùng màu để tô lên các đỉnh của đồ thị này sao cho: (1) Các lối đi cho phép cùng đi đồng thời sẽ có cùng một màu: Dễ dàng nhận thấy rằng hai đỉnh có cạnh nối nhau sẽ không được tô cùng màu. ( 2 ) Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là ít nhất.
Tóm lại, ta phải giải quyết bài toán sau: "Tô màu cho đồ thị ở hình 1.2 sao cho: Hai đỉnh có cạnh nối với nhau (hai còn gọi là hai đỉnh kề nhau) không cùng màu. Số màu được dùng là ít nhất." Trở về bài toán tương tự ví dụ trước Cả hai bài toán trên, ban đầu có vẻ rất khác nhau, nhưng sau khi phân tích để hình thức hóa thì chúng đều được đưa về mô hình toán học đồ thị, và áp dụng thuật toán tô mầu trên đồ thị để giải quyết các bài toán này. Một bài toán thực tế bất kỳ thường 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 đó, cho nên trong giai đoạn phân tích và thiết kế, khi xây dựng mô hình toán học cho bài toán cần chú trọng đến hai vấn đề : (1) Tổ chức biểu diễn các đối tượng dữ liệu của bài toán trong mô hình toán học như thế nào? mô hình này ta còn gọi là mô hình dữ liệu trong tin học ? (2) Xây dựng các thao tác xử lý trên các đối tượng của mô hình ra sao ? 1.2 Cài đặt chương trình cho bài toán cần giải quyết Khi cài đặt chương trình giải quyết bài toán tương ứng ta quan tâm đến hai vấn đề: 1) Biểu diễn mô hình dữ liệu/mô hình toán học của bài toán trên máy tính Ta phải chọn dạng biểu diễn nào để máy tính có thể hiểu và thực hiên các thao tác trên chúng. Giai đoạn này còn được gọi là xây dựng cấu trúc dữ liệu cho bài toán.
Ta có thể cài đặt một mô hình dữ liệu bởi nhiều cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, một số phép toán trên mô hình có thể được thực hiện thuận lơi, nhưng các phép toán khác có thể lại không thuận lợi 2) Mã hóa các giải thuật Với mỗi cấu trúc dữ liệu ta cần mã hóa các thao xử lý trên nó để giải quyết các yêu cầu đặt ra của bài toán Ta có thể sử dụng một ngôn ngữ lập trình cụ thể nào đó (Pascal,C,.) để cài đặt kết quả ở giai đoạn 1, ở bước này ta dùng các cấu trúc dữ liệu được cung cấp trong ngôn ngữ, ví dụ Array, Record,. để biểu diễn m ô h ì n h d ữ l i ệ u c ủ a b à i t o á n t r ê n m á y t í n h , và mã hóa giải thuật bởi các câu lệnh trong ngôn ngữ lập trình lựa chọn. Tóm lược các bước từ bài toán đến chương trình: 1) Về mặt dữ liệu 9 Theo quy trình từ: Mô hình dữ liệu -> Kiểu dữ liệu trừu tượng -> Cấu trúc dữ liệu.
Thật vậy: Trong quá trình phát triển chương trình, nhất là khi phát triển các hệ thống phần mềm lớn, ta cần đến hai dạng biểu diễn dữ liệu: Biếu diễn trừu tượng và biểu diễn cụ thể a) Trong giai đoạn xác định và mô hình hóa bài toán: ta cần sử dụng dạng biểu diễn trừu tượng: được xác định bởi mô hình dữ liệu – đó là mô hình toán học, ví dụ như: Mô hình cây, danh sách, tập hợp, đồ thị, mô hình ERA, …Khi ta dùng mô hình dữ liệu với một số xác định các phép toán nào đó, ta sẽ có một kiểu dữ liệu trừu tượng , ví dụ: Ngăn xếp, hàng đợi, bảng băm, …. => Dạng biểu diễn dữ liệu này không phụ thuộc vào ngôn ngữ lập trình cụ thể b) Trong giai đoạn cài đặt chương trình, ta cần sử dụng dạng biểu diễn cụ thể của dữ liệu: Là biểu diễn xác định cách lưu trữ vật lý của dữ liệu trong bộ nhớ máy tính. Biểu diễn cụ thể của dữ liệu được xác định bởi các cấu trúc dữ liệu. Các cấu trúc dữ liệu được mô tả trong ngôn ngữ lập trình cụ thể mà ta sử dụng.
=> Dạng biểu diễn này phụ thuộc vào ngôn ngữ lập trình cụ thể Từ biểu diễn trừu tượng, ta có thể chuyển dịch thành các biểu diễn cụ thể khác nhau, hay các cấu trúc dữ liệu khác nhau. Ví dụ, ta có thể biểu diễn danh sách bởi mảng hoặc bằng con trỏ, tương ứng ta thu được CTDL kế tiếp, CTDL danh sách liên kết đơn, đôi, vòng…. 2) Về mặt xử lý dữ liệu Theo quy trình từ: Giải thuật phi hình thức -> giải thuật bằng giả ngôn -> Giải thuật được mã hóa hoàn toàn bởi ngôn ngữ lập trình cụ thể. Thật vây: từ những yêu cầu xử lý của bài toán, ta xây dựng c á c giải thuật trên mô hình d ữ l i ệ u đ ã x â y d ự n g.
Giải thuật có thể mô tả một cách phi hình thức - nó chỉ nêu phương pháp giải hoặc các bước giải một cách tổng quát.