Bài giảng Cơ sở toán học cho tin học

Bài giảng Cơ sở toán học cho tin học. Tập bài giảng gồm 5 chương có nội dung trình bày: tổng quan về thuật toán và phương pháp đếm; logic và ứng dụng; đại số Boole; lý thuyết đồ thị; cây và ứng dụng của cây;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở toán học cho tin học 21/07/20 CHƯƠNG I. TỔNG QUAN VỀ THUẬT TOÁN VÀ PHƯƠNG PHÁP ĐẾM CƠ SỞ TOÁN HỌC CHO TIN HỌC BM Công nghệ thông tin Bài giảng Cơ sở toán học cho tin học Nền tảng cơ bản cho các ứng dụng tin học BỘ MÔN CÔNG NGHỆ THÔNG TIN NỘI DUNG NỘI DUNG CHƯƠNG 1 • Chương 1. Tổng quan về thuật toán và phương 1.1. Tổng quan về thuật toán 1.1.1. Khái niệm thuật toán pháp đếm 1.1.2. Độ phức tạp của thuật toán • Chương 2. Logic và ứng dụng 1.1.3. Một số thuật cơ bản • Chương 3. Đại số Boole 1.2. Các phương pháp đếm 1.2.1. Các quy tắc đếm cơ bản • Chương 4. Lý thuyết đồ thị 1.2.2. Hoán vị, chỉnh hợp và tổ hợp • Chương 5. Cây và ứng dụng của cây 1.2.3. Hệ thức truy hồi 1.2.4. Quan hệ chia để trị Bài tập Chương 1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 2 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 5 TÀI LIỆU THAM KHẢO 1.1.1 KHÁI NIỆM THUẬT TOÁN • Đỗ Đức Giáo, Toán rời rạc ứng dụng trong tin học, NXB • Thuật toán là một bảng liệt kê các chỉ dẫn (hay Giáo dục, 2008 quy tắc) cần thực hiện theo từng bước xác định • Đỗ Đức Giáo, Hướng dẫn giải bài tập Toán rời rạc, NXB nhằm giải một bài toán đã cho. Giáo dục, 2006 • Có nhiều cách trình bày thuật toán: dùng ngôn • Kenneth H. Rosen, Discrete Mathematics and It’s ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn Applications, 7th Edition McGraw Hill, USA, 2019 ngữ lập trình • https://www.cis.upenn.edu/~jean/discmath-root-b.pdf • https://voer.edu.vn 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 3 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 6 1 21/07/20 Các đặc trưng của thuật toán Thuật toán tìm kiếm nhị phân • Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ. • Thuật toán này có thể được dùng khi bảng liệt kê • Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các có các số hạng được sắp theo thứ tự tăng dần. giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. • Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. Chẳng hạn, nếu các số hạng là các số thì chúng • Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. được sắp từ số nhỏ nhất đến số lớn nhất hoặc • Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi nếu chúng là các từ hay xâu ký tự thì chúng được đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. • Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp sắp theo thứ tự từ điển. Thuật toán thứ hai này gọi các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ là thuật toán tìm kiếm nhị phân liệu khác nhau trong một miền xác định. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 7 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 10 THUẬT TOÁN TÌM KIẾM Thuật toán tìm kiếm nhị phân procedure tìm kiếm nhị phân (x: integer, a1,a2,...,an: integers tăng dần) • Bài toán tìm kiếm: Xác định phần tử x ...