Luận văn ThS: Một số thuật toán chọn lọc và ứng dụng trong tin học phổ thông

Luận văn Một số thuật toán chọn lọc và ứng dụng trong tin học phổ thông trình bày tổng quan về các khái niệm cơ bản về thuật toán và độ phức tạp của thuật toán, vấn đề phân lớp các bài toán trên cơ sở đánh giá độ phức tạp của thuật toán; trình bày tổng quan về thuật toán đệ quy, thuật toán tham lam, thuật toán xấp xỉ và một số thuật toán trên mô hình đồ thị; cài đặt chương trình cho một số bài toán cụ thể.

Luận văn ThS: Một số thuật toán chọn lọc và ứng dụng trong tin học phổ thông

1. Mở đầu

Ở Việt Nam môn Tin học được đưa vào giảng dạy chính thức ở trường phổ thông từ năm học 2006 - 2007 tuy nhiên trong thực tế môn Tin học đã được đưa vào tham gia thi học sinh giỏi cấp tỉnh, cấp quốc gia từ rất lâu: Hội thi Tin học trẻ không chuyên toàn quốc được tổ chức lần đầu vào năm 1995, kỳ thi học sinh giỏi Tin học quốc gia được tổ chức vào năm 1995 và đặc biệt kỳ thi Olympic Tin học quốc tế (IOI) tổ chức lần đầu vào năm 1989. Từ đó đến nay các kỳ thi học sinh giỏi, Olympic Tin học ngày một nhiều và đòi hỏi kiến thức rất cao. Chúng ta biết rằng để có kết quả cao trong kỳ thi chọn học sinh giỏi môn Tin học nói chung thì học sinh phải có vốn kiến thức về thuật toán để giải được các bài toán khó (đặc biệt là các thuật toán nâng cao), sau đó học sinh sẽ sử dụng ngôn ngữ lập trình nào đó để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo yêu cầu. Chương trình giảng dạy ở sách giáo khoa của môn Tin học hiện hành trong trường phổ thông có lượng kiến thức rất hạn chế và đơn giản, không đủ cơ sở để học sinh có thể dựa vào vốn kiến thức đó để tham gia một kỳ thi học sinh giỏi cấp thành phố hay cấp cao hơn

2. Nội dung

2.1 Các khái niệm về thuật toán

Khái niệm cơ bản về thuật toán

  • Khái niệm bài toán Tin học
  • Khái niệm thuật toán

Yêu cầu của thuật toán

Thể hiện thuật toán

Độ phức tạp của thuật toán

  • Chi phí phải trả cho một quá trình tính toán
  • Phân tích thời gian thực hiện giải thuật
  • Độ phức tạp của thuật toán
  • Các qui tắc xác định độ phức tạp tính toán của giải thuật

Phân lớp các bài toán dựa trên độ phức tạp của thuật toán

  • Lớp P
  • Lớp NP
  • Lớp NPC

2.2 Một số thuật toán chọn lọc và ứng dụng

Thuật toán đệ quy

  • Khái niệm đệ quy
  • Giải thuật đệ quy và thủ tục đệ quy
  • Cấu trúc và đặc điểm của đệ quy
  • Một số bài toán thường gặp trong đệ quy

Thuật toán tham lam

  • Tổng quan về thuật toán tham lam
  • Vấn đề thiết kế thuật toán
  • Một số bài toán áp dụng thuật toán tham lam

Thuật toán xấp xỉ (Heuristic)

Một số thuật toán trên đồ thị

  • Khái niệm cơ bản
  • Phân loại đồ thị
  • Một số khái niệm
  • Biểu diễn đồ thị trên máy tính
  • Một số thuật toán chọn lọc trên mô hình đồ thị

2.3 Một số ứng dụng thực tế

Bài toán gia công (trình tự gia công ngắn nhất)

Bài toán xếp việc

Bài toán đường đi ngắn nhất

Bài toán mắc dây điện

Bài toán quân cờ Domino

Bài toán mạng giao thông

3. Kết luận

Thuật toán là một mảng rất rộng, nếu đi hầu hết tất cả vấn đề của thuật toán đó là một khối lượng kiến thức khổng lồ, các vấn đề ứng dụng của thuật toán cũng rất nhiều, phong phú và đa dạng. Trong luận văn đã tập trung nghiên cứu, trình bày những kiến thức cơ bản về thuật toán và ứng dụng của thuật toán vào việc giải một số bài toán tin học, đề thi học sinh giỏi, đề thi olympic. Qua đó luận văn đã đạt được một số kết quả như sau:

  • Về lý thuyết: Luận văn tập trung nghiên cứu các kiến thức chung nhất về thuật toán và độ phức tạp của thuật toán, một số thuật toán trên mô hình đồ thị. Luận văn đã phân tích kỹ về các thuật toán của các bài toán ứng dụng.
  • Về ứng dụng: Luận văn đã phân tích và cài đặt các thuật toán của các bài toán ứng dụng trong thi học sinh giỏi, Olympic Tin học.
  • Phạm vi và khả năng áp dụng: Luận văn là một tài liệu tham khảo tốt cho giáo viên và học sinh trong các trường phổ thông.

4. Tài liệu tham khảo

Nguyễn Thanh Bình (2007), Giáo trình - bài giảng thuật toán nâng cao, trường Đại học Bách khoa - Đại học Đà Nẵng.

Hồ Sĩ Đàm (2009), Tài liệu giáo khoa chuyên tin, Nxb Giáo dục.

Nguyễn Hữu Điển (2002), Một số vấn đề về thuật toán, Nxb Giáo dục.

Đỗ Đức Giáo (1998), Toán rời rạc, Nxb Đại học Quốc gia Hà Nội.

Nguyễn Xuân Huy (2011), Sáng tạo trong thuật toán và lập trình, Tập 1, 2, 3, Nxb Thông tin và truyền thông.....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn Thạc sĩ trên ---

Ngày:28/08/2020 Chia sẻ bởi:Nguyễn Minh Duy

CÓ THỂ BẠN QUAN TÂM