Báo Cáo Nghiên cứu về Toán rời rạc

TÊN ĐỀ TÀI: Nghiên cứu về Toán rời rạc​

Information

YÊU CẦU CỦA ĐỀ TÀI:

Thuật toán đệ quy và cách khử đệ quy:

1. Trình bày hiểu biết về thuật toán đệ quy, ưu nhược điểm của đệ quy.

2. Các phương pháp xây dựng chương trình con đệ quy, cách thực hiện chương trình đệ quy, cơ chế cấp phát và quản lý bộ nhớ cho chương trình đệ quy.

3. Vấn đề khử đệ quy và một số phương pháp khử đệ quy, có ví dụ minh họa.

4. Cài đặt thuật toán Selectionsort thực hiện việc sắp xếp một dãy n số nguyên theo chiều tăng dần bằng phương pháp đệ quy sau đó khử đệ quy.










LỜI MỞ ĐẦU

Toán rời rạc là một lĩnh vực của toán học nghiên cứu các đối tượng rời rạc.Chúng ta sẽ sử dụng công cụ rời rạc khi phải đếm các đối tượng, khi nghiên cứu quan hệ giữa các tập rời rạc, khi phân tích các quá trình hữu hạn.Đồng thời tầm quan trọng của toán rời rạc được nâng cao là nhờ việc cất giữ và xử lý thông tin trên máy tính có bản chất là các quá trình rời rạc.Các quá trình rời rạc ấy được xử lý và biểu diễn thông qua các chương trình, các thuật toán cụ thể.Khi nói đến các thuật toán trong toán rời rạc ta không thể không nói đến đệ quy và giải thuật của đệ quy. Đệ quy không những giúp người lập trình giải quyết tốt các bài toán mà còn giúp nâng cao tư duy toán, rèn luyện kỹ thuật lập trình.Tuy rằng bên cạnh giải thuật đệ quy vẫn có những giải thuật lặp khá đơn giản và hữu hiệu,chẳng hạn như giải thuật lặp tính n!. nhưng đệ quy vẫn có vai trò xứng đáng của nó, có những bài toán việc nghĩ ra lời giải đệ quy thuận lợi hơn nhiều so với lời giải lặp và có những giải thuật đệ quy thật sự cũng có hiệu lực cao nữa. Một điều cần nói thêm về đệ quy là: Về mặt định nghĩa công cụ đệ quy đã cho phép xác định một tập vô hạn các đối tượng bằng một phát biểu hữu hạn. Chúng ta sẽ thấy rõ vai trò của công cụ này trong định nghĩa văn phạm, định nghĩa cú pháp ngôn ngữ, định nghĩa một số cấu trúc dữ liệu Nội dung của bài đề tài được trình bày sau đây sẽ phần nào giúp các bạn hiểu sâu sắc hơn về đệ quy và các giải thuật liên quan tới nó.Trong đề tài này chúng tôi trình bày gồm có 4 chương.Mỗi chương chúng tôi đã cố gắng trình bày ngắn gọn, trực tiếp vào bản chất của vấn đề, đồng thời sử dụng cài đặt tất cả các chương trình bằng ngôn ngữ lập trình pascal,hy vọng sẽ mang lại sự gần gũi, dễ hiểu cho các sinh viên,mong rằng nó sẽ thực sự giúp ích cho các bạn trong quá trình nghiên cứu về đệ quy.

Sinh viên nhóm 5 rất cảm ơn các thầy cô giáo trong bộ môn khoa học máy tính đã hướng dẫn chúng em trong quá trình thực hiện đề tài này.Mặc dù rất cố gắng nhưng không tránh khỏi những thiếu sót và hạn chế,rất mong được sự tham gia, đóng góp ý kiến bổ sung của thầy cô và các bạn cho đề tài này.

Chúng tôi xin chân thành cảm ơn!


Phần I:

GIỚI THIỆU

Toán học rời rạc là một trong những môn cơ sở được giảng dạy ở các khoa công nghệ thông tin hiện nay.Nhằm đáp ứng thêm nhu cầu đa dạng về kiến thức cho các bạn sinh viên về toán rời rạc,đề tài này chúng tôi nghiên cứu về đệ quy và cách khử đệ quy,đây là bài toán rất nhỏ được sử dụng trong toán rời rạc nhưng khi xét về vai trò thì nó là một phần không thể thiếu của toán rời rạc.Nội dung đề tài chúng tôi trình bày gồm bốn chương, mỗi chương chúng tôi cố gắng trình bày cô đọng các nội dung,cụ thể như:

ã Chương 1: Sơ lược về đệ quy,qua chương này các bạn sẽ nắm được những khái niệm cơ bản về đệ quy, và phần nào hiểu hơn về nó.

ã Chương 2: Chương trình con đệ quy và một số vấn đề liên quan đến nó,qua chương này các bạn sẽ hiểu thêm về cách xây dựng và sử dụng các hàm, cũng như các thủ tục của đệ quy.

ã Chương 3: Chương này chúng tôi trình bày cách khử đệ quy, khử đệ quy ở đây được hiểu là một phương pháp làm mất đi tính đệ quy của một chương trình đệ quy.Giải thuật này cũng mang một ý nghĩa hết sức quan trọng trong quá trình giải các bài toán liên quan.

ã Chương 4: Chương này chúng tôi cài đăt một bài toán ví dụ giúp các bạn hiểu thêm một cách sâu sắc hơn về những gì chúng tôi đã nêu ở trên.


Nói một cách tổng quát, qua bài đề này chúng tôi mong giúp cho mọi người hiểu một cách sâu sắc hơn về đệ quy, và từ đó áp dụng thành thạo nó trong việc giải quyết các bài toán có liên quan.




*****



KẾT LUẬN:

Trên đây là toàn bộ nội dung chúng tôi muốn gửi tới các bạn,những vấn đề cơ bản về đệ quy,chúng tôi mong rằng đây sẽ là tài liệu hữu ích cho các bạn khi tìm hiểu về đệ quy. Chúng tôi đã đưa ra một cách khái quát và khá chi tiết những hiểu biết về đệ qui,cũng như đưa ra khái niệm, thuật toán đệ quy, bên cạnh đó để các bạn có thể hiểu hơn về đệ quy, đồng thời đề tài cũng đưa ra những ví dụ cụ thể để các bạn có thể hiểu một cách sâu sắc về những khái niệm mang tính chất trừu tượng như đệ quy.Chúng tôi cũng đã trình bày khá chi tiết về khử đệ quy,đây là một giải thuật làm mất tính đệ quy của một chương trình đệ quy. Mặc dù đã rất cẩn thận trong quá trình thực hiện đề tài song vẫn không tránh khỏi những thiếu sót rất mong những ý kiến đóng góp của các thầy cô và các bạn.








TÀI LIỆU THAM KHẢO

1. Giaó trình toán rời rạc - Bộ môn khoa học máy tính.

2. Giáo trình kĩ thuật lập trình nâng cao - Trần Hoàng Thọ (Trường Đại học Đà Lạt 2002).

3. Kỹ thuật lập trình C cơ sở và nâng cao – Phạm Văn Ất.

4. Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi,NXB Khoa học kỹ thuật ( 1998).