Một số bài toán giải bằng phương pháp đệ quy cho ta lời giải rất gọn và có thể ra được lời giải. Những bài toán giải bằng đệ quy truyền thống như: THÁP HÀ-NỘI, bà toán 8-HẬU, bài toán MÃ ĐI TUẦN, ... Tuy nhiên phương pháp đệ quy khi áp dụng chỉ giải được những bài toán với cấu trúc dữ liệu nhỏ thường là với N<30 (hay NxN < 30x30). Vì vậy bài toán đặt ra là có thể giải quyết những bài toán như trên với dữ liệu lớn được hay không? Ví dụ như: bài toán MÃ ĐI TUẦN và THÁP HÀ-NỘI với bàn cờ cỡ 80x80 hay không? Xin trình bày một số phương pháp khử đệ quy để giải quyết những bài toán đệ quy truyền thống.

Bài toán Người du lịch (Travelling Salesman Problem) là một trong những bài toán kinh điển và khó trong tin học. Có rất nhiều cách tiếp cận giải bài toán này ngay từ khi nó mới ra đời, như sử dụng quy hoạch tuyến tính, nhánh và cận (đã được đăng trên Tin học và Nhà trường), nhưng mới chỉ dừng lại ở các bộ dữ liệu nhỏ. Gần đây các cách tiếp cận về tiến hóa, như thuật toán di truyền được áp dụng có những kết quả khả quan hơn.

Trong tin học, các bài toán liên quan đến số thực thường là các bài toán khá phức tạp trong việc xử lí và thao tác. Ví dụ: Nhân chia số thực chậm hơn rất nhiều so với số nguyên, rất khó kiểm soát điều kiện bằng nhau, hay lỗi thường gặp là chia cho 0.
Ví dụ bạn sẽ nhận được 1 vòng lặp vô hạn nếu bạn viết :

Duyệt từ 2 phía là 1 cách duyệt toàn bộ có tốc độ có thể chấp nhận được.

Duyệt từ 2 phía ứng dụng trong 1 số bài toán biến đổi, cho 2 trạng thái đầu và cuối và tập các biến đổi. Yêu cầu sử dụng các phép biến đổi đó để chuyển trạng thái đầu về trạng thái cuối.

Phạm Tuấn Hưng K49CA Đại học Công Nghệ-Đại học Quốc Gia Hà Nội

Các bạn thân mến!
Trong các kỳ thi Tin học lập trình, tỉ lệ xuất hiện bài toán về hình học là rất cao. Mà đó lại thường là những bài mà học sinh vấp váp, vì một trong các lý do sau đây:

Thầy Trần Thông Quế

Để các bạn học sinh và sinh viên mới bắt đầu nghiên cứu hoặc học “Lý thuyết đồ thị” dễ nhận thức hơn về thuật toán này tôi sẽ nói chi tiết về nó và cung cấp cho các bạn một cài đặt trực quan.

Nguyễn Khắc Vượng

Một trong những bài toán đầu tiên mà bất cứ học sinh Tin nào cũng phải vượt qua, đó là thực hiện những phép toán với 2 số lớn sử dụng mảng. Thực hiện cộng trừ hai số có n chữ số sẽ có độ phức tạp là O(n), nhân hai số có n chữ số sẽ có độ phức tạp là O(n2). Vậy thì cài đặt phép nhân như vậy đã là tối ưu chưa?

Sắp xếp thứ tự là một yêu cầu rất thường xuyên trong đời sống hàng ngày, trong tin học nó đặt nền móng cho nhiều tác vụ, thuật toán quan trọng. Bài toán sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng nào đó, theo một trật tự nhất định, chẳng hạn thứ tự tăng dần (hay giảm dần) đối với dãy số, thứ tự từ điển đối với các từ. Bài toán sắp xếp được nhiều nhà thiết kế thuật toán quan tâm nghiên cứu, có nhiều thuật toán hiệu quả đã được đề xuất. Ta có thể kể ra đây một danh sách không đầy đủ những thuật toán sắp xếp tiêu biểu: Insertion sort, Shell sort, Gnome sort, Bubble sort, Comb sort, Radix sort, Counting sort, Mergesort, Quicksort, Heap sort...Các thuật toán đơn giản như Bubble sort, Insertion Sort, Shell Sort có độ phức tạp thời gian là , các thuật toán phức tạp hơn là Quick Sort, Heap Sort... có độ phức tạp .

Đối với nhiều thuật toán nguyên lý “chia để trị” thường đóng vai trò chủ đạo trong việc thiết kế thuật toán: để giải quyết một bài toán lớn, chúng ta chia nó thành nhiều bài toán con có thể được giải quyết độc lập. Trong phương pháp quy hoạch động, việc thể hiện nguyên lý này được đẩy đến cực độ: khi không biết chắc cần giải quyết bài toán con nào, chúng ta giải quyết tất cả những bài toán con và lưu trữ những lời giải này với mục đích sử dụng lại chúng theo một sự phối hợp nào đó để giải quyết các bài toán tổng quát hơn.

Đề bài: Cho một đồ thị có trọng số, với mọi cặp đỉnh x, y hãy tìm đường đi từ x tới y sao cho đoạn đường đi là ngắn nhất?

(Đường đi từ đỉnh x tới đỉnh y trong một đồ thị là một danh sách các đỉnh mà hai đỉnh liên tiếp nhau trong danh sách đó được nối bởi một cạnh của đồ thị.)

Các trò chơi đối kháng giữa hai người chúng ta thường biết là những trò chơi như cờ tướng, cờ vua, cờ caro…đã được hình thành từ lâu. Và những người chơi luôn cố gắng tìm mọi cách để mình giành được phần thắng. Và bạn có biết rằng có thể đoán trước người thắng thua, hay hoà ? Điều này có nghĩa là nếu một trò chơi cho trước vị trí ban đầu thì kết quả tốt nhất mà người chơi đầu tiên đạt được đã được biết từ trước (giả thiết cả hai người chơi đều chơi tối ưu). Vấn đề là các trò chơi thường quá phức tạp nên không có một ai có thể đảm bảo rằng mọi nước đi của mình là tối ưu. Do vậy cho đến nay, chỉ một số lượng nhỏ bài toán đó đã được giải quyết.

Như chúng ta đã biết, QuickSort là một thuật toán sắp xếp được dùng rộng rãi nhất hơn bất kỳ thuật toán nào khác. QuickSort là phương pháp phổ biến vì khong có cài đặt. Là một trong những phương pháp sắp xếp cơ bản nhưng phương Quick Sort sắp xếp “hướng tổng quát” tốt vì nó làm việc tốt trong các tình huống khác nhau và trong nhiều trường hợp phương pháp này sử dụng ít tài nguyên hơn những phương pháp sắp xếp khác.

Chú gấu Mecho tìm thấy một kho báu nhỏ - một bầu mật ong dự trữ. Chú sung sướng ăn kho báu tìm thấy cho đến khi bỗng nhiên một chú ong trông thấy và phát tín hiệu báo động. Chú gấu hiểu rằng đàn ong ngay lập tức sẽ vây lấy bầu mật và lao vào đốt chú. Chú biết là phải rời khỏi bầu mật và co chân chạy về nhà thật nhanh, nhưng mật ông ngọt và thơm làm sao khiến Mecho không muốn bỏ đi quá sớm. Hãy giúp Mecho xác định thời điểm muộn nhất có thể phải bỏ đi.

Bãi đỗ xe có N chỗ đỗ xe, được đánh số từ 1 đến N. Buổi sáng, khi mở cửa chưa có xe nào trong bãi đỗ. Trong cả ngày, bãi đỗ được vận hành theo cách sau. Bất kì khi nào có một xe ô tô đến bãi đỗ, người gác sẽ kiểm tra xem có chỗ trống nào không. Nếu không có xê ô tô sẽ đợi cho đến khi có chỗ được phóng. Nếu có chỗ trống, hoặc ngay khi có một chỗ được giải phóng, xe sẽ được đưua vào chỗ đỗ trống này. Nếu có nhiều hơn một chỗ trống, xe sẽ được vào chỗ trống có hiệu số nhỏ nhất. Nếu có thêm xe ô tô đến trong khi có xe đang chờ, các xe sẽ xếp thành hàng đợi tại cửa bãi đỗ theo trình tự mà chúng đến. Sau đó, khi có chỗ đỗ được giải phóng, xe đầu tiên trong hàng đợi (nghĩa là xe đến sớm nhất) được đỗ vào chỗ trống này.

Bonny, nhà làm Sô cô la nổi tiếng của Plovdiv, cần cắt một thanh sô cô la trên bề mặt có nho khô. Thanh sô cô lo là một khối chữ nhật các ô vuông đơn vị (viết tắt là ô). Các ô được xếp liền nhau dọc theo cạnh của thanh sô cô la, tạo thành N dòng và M cột. Tổng cộng có N x M ô. Mỗi ô như vậy chứa một hay nhiều hạt nho khô, và không có hạt nho khô nào tranh ranh giới giữa hai ô.

Cuộc thi Olympic Tin học địa phương của vùng Plovdiv (POI) được tiến hành theo quy tắc đặc biệt như sau. Có N thí sinh và T bài toán. Mỗi bài được chấm bằng một test duy nhất. Vì vậy, với mỗi bài toán và với mỗi thí sinh chỉ có hai khả năng: hoặc là thí sinh giải được bài toán đó hoặc không giải được. Người ta không cho điểm từng phân với mỗi bài.

Bạn phải thuê nhân công để thực hiện một dự án xây dựng. Có N người ứng viên xin việc, được đánh số từ 1 đến N. Mỗi ứng viên k đòi hỏi, nếu chọn anh ta thì phải trả lương ít nhất là S_k đô la. Ngoài ra, người ta còn biết rằng ứng viên k có trình độ tay nghề là Q_k. Theo các quy định của ngành xây dựng, các công nhân phải được trả lương tỉ lệ thuận với trình độ tay nghề của họ. Ví dụ, nếu bạn thuê hai công nhân A và B và Q_A=3 * Q_B, thì bạn phải trả lương người A gấp 3 lần trả cho người B. Bạn được phép trả cho công nhân của mình một lượng tiền không biểu diễn bằng số nguyên. Thậm chí, tiền lương có thể là một số thập phân vô hạn, chẳng hạn như một phần ba (1/3) hoặc là một phần sau (1/6) đô la.

Một cuộc thi bắn cung được tổ chức theo các luật sau. Có N đích được xếp thành một hàng và được đánh số từ 1 đến N tương ứng với vị trí của nó trên hang (trái nhất là đích 1 và phải nhất là đích N). Có 2*N cung thủ. Tại mỗi thời điểm của cuộc thi có đúng 2 cung thủ đứng trước mỗi đích. Mỗi vòng thi đấu của cuộc thi được tổ chức như sau:

Bài toán: Một tên trộm sau khi đột nhập vào nhà thì thấy có N loại đồ vật có kích thước và giá trị khác nhau. Vật gì hắn ta cũng muốn mang đi, nhưng lại chỉ mang một chiếc túi có dung lượng M (có thể chứa được một số đồ vật sao cho tổng kích thước chỉ nhỏ hơn hay bằng M). Vấn đề đặt ra cho tên trộm là hắn phải chọn lựa một danh sách các đồ vật sẽ mang đi sao cho tổng giá trị lấy cắp là lớn nhất.

Hầu hết mọi người không lạ gì với bài toán 8-quân hậu vì tính dễ hiểu và có thể nó giống như một trò chơi vui, trí tuệ. Tuy nhiên không phải ai cũng viết nhiều vấn đề thú vị xung quanh nó (xét ở một góc độ nào đó nó giống như định lý Ferma: Định lý này đã làm hao mòn không biết bao bộ óc vĩ đại của các nhà toán học lừng danh trong gần 4 thế kỉ. Cuối cùng nó được chứng minh bởi Andrew Wiles năm 1993 sau gần 8 năm ròng nghiên cứu, phát triển chứng minh các giả thiết có liên quan[Fermat]).