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ể.
Mục lục nội dung
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 ---
Tham khảo thêm
- pdf Luận văn ThS: Bài toán xác định vị trí của một điểm so với đa giác và ứng dụng trong bản đồ số
- pdf Luận văn ThS: Dự báo chuỗi thời gian mờ dựa trên đại số gia tử với mô hình ngữ nghĩa định lượng tối ưu và ứng dụng
- pdf Luận văn ThS: Nghiên cứu nhận dạng biển số xe ô tô Cộng hòa dân chủ nhân dân Lào
- pdf Luận văn ThS: Nghiên cứu một số kỹ thuật tạo chuyển động theo điểm điều khiển trong thực tại ảo
- pdf Luận văn ThS: Nghiên cứu mô hình người sử dụng mở trong các hệ thống gợi ý thông tin theo nhu cầu
- pdf Luận văn ThS: Phương pháp xây dựng cây quyết định dựa trên tập phụ thuộc hàm xấp xỉ
- pdf Luận văn ThS: Xác định vùng tìm kiếm trên hình ảnh địa hình và ứng dụng
- pdf Luận văn ThS: Hiển thị ảnh DICOM trong y tế theo thành phần
- pdf Luận văn ThS: Điều khiển dựa trên đại số gia tử với phép ngữ nghĩa hóa và giải nghĩa mở rộng
- pdf Luận văn ThS: Sử dụng công nghệ GIS để phân tích dữ liệu và dự báo sản lượng chè của tỉnh Thái Nguyên
- pdf Luận văn ThS: Nghiên cứu một số phương pháp bảo đảm an toàn thông tin trong mạng máy tính
- pdf Luận văn ThS: Nghiên cứu về dịch máy thống kê dựa vào cụm từ và ứng dụng dịch từ tiếng Việt sang tiếng Anh
- pdf Luận văn ThS: Tích hợp và dung hòa các ý kiến trong hệ trợ giúp quyết định đa tiêu chuẩn ngôn ngữ với thông tin trọng số không đầy đủ
- pdf Luận văn ThS: Nghiên cứu kỹ thuật Rainbow- Crack thám khóa mã RC4 và ứng dụng
- pdf Luận văn ThS: Cụm dữ liệu và ứng dụng trong phân tích lương của cán bộ trường Cao đẳng Nghề Hà Nam
- pdf Luận văn ThS: Kỹ thuật Datamining để khuyến nghị khách hàng trong hệ thống BI - Business Intelligence
- pdf Luận văn ThS: Tích hợp cơ sở dữ liệu quan hệ XML
- pdf Luận văn ThS: Kỹ thuật phân cụm dữ liệu trong phát hiện xâm nhập trái phép
- pdf Luận văn ThS: Phương pháp tối ưu đàn kiến dóng hàng hai đồ thị
- pdf Luận văn ThS: Nghiên cứu một số phương pháp cơ bản về nhận dạng mặt người trong ảnh và ứng dụng
- pdf Luận văn ThS: Xây dựng vùng đệm trong hệ thống thông tin địa lý sử dụng logic mờ
- pdf Luận văn ThS: Nghiên cứu sự ảnh hưởng của bộ tâm nội suy đến độ chính xác của xấp xỉ đạo hàm dựa trên nội suy hàm cơ sở bán kính
- pdf Luận văn ThS: Bảo vệ bản quyền ảnh màu kỹ thuật số bằng lược đồ thủy vân dựa vào phép biến đổi DFT kết hợp với phép biến đổi SIFT
- pdf Luận văn ThS: Nghiên cứu các phương pháp trích chọn thông tin và ứng dụng trích chọn thông tin du lịch trong văn bản tiếng Việt
- pdf Luận văn ThS: Phát hiện lỗi sản phẩm trên dây chuyền đóng chai nước bằng xử lý ảnh
- pdf Luận văn ThS: Khôi phục ảnh bằng tối ưu độ tương tự cục bộ
- pdf Luận văn ThS: Tối ưu bảng cụm từ để cải tiến dịch máy thống kê
- pdf Luận văn ThS: Giấu tin trong file âm thanh bằng các phép biến đổi rời rạc
- pdf Luận văn ThS: Một số thuật toán tìm core và ứng dụng trong phân tích mạng xã hội
- pdf Luận văn ThS: Nội suy ảnh trong hỗ trợ chẩn đoán hình ảnh
- pdf Luận văn ThS: Tối ưu hóa phân bổ và định giá đất đai theo thuật toan di truyền định hướng không gian
- pdf Luận văn ThS: Đề tài nhận dạng khuôn mặt trong hỗ trợ công tác quản lý tiếp dân
- pdf Luận văn ThS: Tìm hiểu khả năng an toàn của hệ mật mã RSA
- pdf Luận văn ThS: Tạo lập hệ luật mờ sử dụng phân cụm trừ mờ dữ liệu
- pdf Luận văn ThS: Giải pháp kết hợp công nghệ tính toán mềm với phương pháp lập luận mờ dựa trên đại số gia tử có tham số hiệu chỉnh
- pdf Luận văn ThS: Mạng Noron Wavelet và ứng dụng cho dự báo chứng khoán
- pdf Luận văn ThS: Phân đoạn từ tiếng Việt
- pdf Luận văn ThS: Xây dựng hệ thống truy vấn video nông nghiệp hướng ngữ nghĩa có sử dụng Ontology
- pdf Luận văn ThS: Tối ưu hoá truy vấn trong hệ cơ sở dữ liệu phân tán
- pdf Luận văn ThS: Xây dựng mô hình các chủ đề và công cụ tìm kiếm ngữ nghĩa
- pdf Luận văn ThS: Rút trích tri thức ngữ nghĩa từ tên thể loại Wikipedia
- pdf Luận văn ThS: Nghiên cứu mạng nơron nhân tạo và ứng dụng vào trao đổi khóa bí mật
- pdf Luận văn ThS: Xây dựng Ontology từ kho ngữ liệu dạng văn bản
- pdf Luận văn ThS: Ứng dụng GIS phục vụ công tác quản lý cầu tại TP Hồ Chí Minh
- pdf Luận văn ThS: Ứng dụng đồ thị euler tối ưu hóa bài toán tìm đường đi ngắn nhất
- pdf Luận văn ThS: Nghiên cứu về chuyển đổi lược đồ cơ sở dữ liệu quan hệ sang cơ sở dữ liệu NoSQL
- pdf Luận văn ThS: Trích chọn đặc trưng kết cấu màu cục bộ cho bài toán nhận dạng ảnh màu mặt người
- pdf Luận văn ThS: Thuật toán hiệu quả cho khai thác tăng trưởng các mô hình duyệt web
- pdf Luận văn ThS: Khai thác luật phân lớp kết hợp trên cơ sở dữ liệu bị sửa đổi
