Page

Toán rời rạc

1. Tên học phần: Toán rời rạc
                          (Discrete Mathematics)
2. Mã số học phần:  FMAT 1021
3. Số tín chỉ: 3                                   Tín chỉ học phí:
4. Điều kiện học phần:
                     -  Học phần tiên quyết:                                                Mã số:
  • Học phần trước:      
                                   Toán cao cấp 1                                                 Mã số: FMAT 0111
                                   Toán cao cấp 2                                               Mã số: FMAT 0211
                                   Lý thuyết xác suất và Thống kê Toán        Mã số: FMAT0511
                     -  Học phần song hành:                                               Mã số:
                     -  Điều kiện khác:
5. Đánh giá: (Theo quá trình)
                    - Điểm chuyên cần                                      10%
                    - Điểm thực hành                                              30%
                    - Điểm thi hết học phần                               60%
6. Thang điểm: 10
7.  Cán bộ giảng dạy học phần:
           
8. Mục tiêu của học phần:
       8.1. Mục tiêu chung: Cung cấp cho sinh viên những kiến thức cơ bản nhất về cơ sở toán của tin học. Cung cấp phương pháp tư duy lôgic và phương pháp suy luận trong chứng minh.
       8.2. Mục tiêu cụ thể :
            - Sinh viên cần nắm được những kiến thức về suy luận lôgic, về tập hợp đặc biệt là phép đếm các phần tử trong một tập hợp để áp dụng vào tin học.
            - Nắm được những cơ sở toán áp dụng vào tin học như Đại số Boole, Đồ thị, mạch tổ hợp và mô hình của máy tính.
            - Sau khi học xong học phần, sinh viªn cã cơ sở lý thuyết để nắm được các thuật toán và lập trình trong tin học.
9.  Mô tả v¾n t¾t nội dung học phần:
            Trang bị cho sinh viên nội dung cơ bản nhất và có hệ thống về cơ sở toán của tin học. Cung cấp cho sinh viên những phép suy luận lôgic, phép đếm các phần tử, mối quan hệ giữa các tập rời rạc và phân tích các quá trình hữu hạn.
            The Subject equips students with the most characterise and suystematic mathematical bases of informaties, provides students with the logical methods, operation on elements, relations between discret sets and analyse the finite process.
10. Tài liệu tham khảo:
       10.1. TLTK bắt buộc
            [1]. Đỗ Đức Giáo, Toán rời rạc, NXB Đại học Quốc Gia. Hà Nội 2004
            [2]. Kenneth.H. Rose, Toán học rời rạc và ứng dụng trong tin học, NXB Khoa học và Kỹ thuật Hà Nội 1998
            [3]. E. Goodaire, Discrete Mathematics with Graptheory, M Parment 1993
            [4]. Eric Gossett, Discrete Mathematics with proof , Pearson Education 2003
            [5]. Phạm Thế Long, Nguyễn Xuân Viên, Nguyễn Thiệu Luân, Nguyễn Đức Thiệu, Nguyễn Văn Xuất, Toán rời rạc, NXB Đại học Sư Phạm 2004.          
        10.2. TLTK khuyến khích
[6]. Nguyễn Đức Nghĩa, Nguyễn Đức Thành, Toán rời rạc, NXB Giáo Dục 1977
            [7]. Phan Đình Diệu, Lý thuyết Ôtômát và thuật toán, NXB Đại học 1977
            [8].  Đỗ Văn Nhơn. Giáo trình toán rời rạc. NXB thống kê 2003.
[9]. Lê Tự Hỷ. Toán rời rạc. NXB Giáo dục. 2005.
[10]. László Lovász and Katalin Vesztergombi. Discrete Mathematics, Yale University.
         Spring, 1999.
            [11]. Tạp chí  “Discrete Applied Mathematics” .
11. Đề cương chi tiết học phần:
Nội dung TLTK Ghi chú
 
Chương 1 : Những khái niệm cơ bản về lôgic, tập hợp
1.1.      Mệnh đề và lôgic.
   1.1.1.           Định nghĩa và thí dụ
   1.1.2.           Các phép toán trên mệnh đề
   1.1.3.           Biểu thức lôgic
   1.1.4.           Các luật lôgic
   1.1.5.           Các dạng chính tắc
1.2.  Tập hợp và các phép toán trên tập hợp
   1.2.1.           Các định nghĩa và thí dụ
   1.2.2.           Các hằng đẳng thức tập hợp
  1. Biểu diễn tập hợp trên máy tính   
1.3.  Lượng từ và vị từ
   1.3.1.           Hàm mệnh đề
   1.3.2.           Khái niệm về vị từ
   1.3.3.           Các phép toán trên các vị từ
   1.3.4.           Các lượng từ và mệnh đề có lượng từ
   1.3.5.           Quy tắc phủ định mệnh đề có lượng từ
1.4.  Quan hệ
   1.4.1.           Quan hệ hai ngôi và quan hệ trên một tập hợp
   1.4.2.           Các tính chất của quan hệ hai ngôi trên một tập hợp
   1.4.3.           Biểu diễn quan hệ hai ngôi dưới dạng ma trận
   1.4.4.           Quan hệ tương đương
  1. Quan hệ thứ tự         
1.5.  Các phương pháp chứng minh
   1.5.1.           Một số quy tắc suy luận trong lôgic mệnh đề
   1.5.2.           Các phương pháp chứng minh cơ bản
   1.5.3.           Phương pháp quy nạp
   1.5.4.           Đệ quy và ứng dụng
Chữa bài tập ôn chương     
 
[1
 
 
 
[1
 
 
 
[6]
 
 
 
 
 
 
 
 
[4]
 
 
 
[5]
 
 
[4]
[5]
 
LT
BT
 
 
LT
 
 
 
 
 
 
Đọc thêm
Chương 2.  Các phương pháp đếm
 2.1.  Các nguyên lý cơ bản của phép đếm
   2.1.1.           Mở đầu
   2.1.2.           Nguyên lý cộng
   2.1.3.           Nguyên lý nhân
  1. Một số phép đếm cơ bản
   2.2.1.           Tổ hợp, chỉnh hợp, hoán vị
  1. Tổ hợp lặp, chỉnh hợp lặp  
   2.2.3.           Hoán vị của tập hợp có số phần tử giống nhau
   2.2.4.           Ứng dụng vào phép đếm phần tử của tập hợp
2.3.  Nguyên lý Đirichlet
   2.3.1.           Nguyên lý chuồng bồ câu
   2.3.2.           Nguyên lý Đirichlet tổng quát
  1. Ứng dụng của nguyên lý    
2.4.  Nguyên lý bù trừ
   2.4.1.           Mở đầu
   2.4.2.           Nguyên lý bù trừ
   2.4.3.           ứng dụng của nguyên lý
Chữa bài tập ôn chương + Kiểm tra giữa kì
 
[4]
 
[1]
 
[1]
 
 
 
 
 
 
[2]
 
LT
 
LT
 
LT
 
 
 
 
 
 
BT
Chương 3 : Đồ thị và cây
3.1.  Các khái niệm cơ bản
   3.1.1.           Định nghĩa đồ thị và các thuật ngữ
  1. Đường đi, chu trình và đồ thị liên thông
   3.1.3.           Một số dạng đồ thị đặc biệt
3.2.  Biểu diễn đồ thị
   3.2.1.           Ma trận hệ, ma trận trọng số
   3.2.2.           Các tính chất của ma trận hệ số
   3.2.3.           Ma trận liên thuộc
  1. Sự đẳng cấu của các đồ thị            
3.3.  Đồ thị Euler và Hamilton
   3.3.1.           Đường đi Euler và chu trình Euler
   3.3.2.           Đường đi Hamilton và chu trình Hamilton
3.4.  Bài toán đường đi ngắn nhất
   3.4.1.           Đồ thì có trọng số
  1. Thuật toán tìm đường đi ngắn nhất           
3.5.  Cây
   3.5.1.           Định nghĩa và các tính chất cơ bản của cây
   3.5.2.           Cây khung của đồ thị
   3.5.3.           Cây phân cấp
   3.5.4.           Cây khung nhỏ nhất
Chữa bài tập ôn chương     
 
 
[2]
 
 
 
 
[1]
[5]
 
LT
 
LT
 
 
 
 
 
 
 
Đọc thêm
 
Đọc thêm
 
 
 
 
 
Đọc thêm
Đọc thêm
Chương 4.  Đại số Boole và ứng dụng trong mạch tổ hợp
4.1.  Hàm Boole và biểu thức Boole
    4.1.1.         Các phép toán Boole
   4.1.2.           Biểu thức Boole và hàm Boole
   4.1.3.           Các đồng nhất thức của đại số Boole
   4.1.4.           Quy tắc đối ngẫu.
4.2.  Biểu diễn các hàm Boole
   4.2.1.           Khai triển hàm Boole thành dạng tổng các tích
   4.2.2.           Khai triển hàm Boole thành dạng tích các tổng
  1. Tính đầy đủ của hệ hàm Boole     
4.3. Ứng dụng của đại số Boole trong lý thuyết mạch tổ hợp
   4.3.1.           Khái niệm về mạch tổ hợp
   4.3.2.           Mạch tổ hợp tương đương
   4.3.3.           Tổ hợp các cổng lôgic thực hiện một hàm Boole
  1. Bộ cộng
4.4. Cực tiểu hoá mạch tổ hợp
   4.4.1.           Bài toán cực tiểu hoá hàm Boole và mạch tổ hợp
   4.4.2.           Phương pháp biến đổi đại số
   4.4.3.           Phương pháp bảng Karnaugh
   4.4.4.           Phương pháp Quine – McCheskey
Chữa bài tập ôn chương                 
 
[1]
 
[4]
 
[1]
 
 
 
 
 
 
 
 
 
[1]
 
LT
 
LT
 
LT
 
 
 
 
 
 
 
 
Đọc thê
BT
Chương 5.  Ôtômát và mô hình của máy tính tuần tự
5.1.  Ôtômát hữu hạn trạng thái, có ra
   5.1.1.           Các khái niệm và định nghĩa
   5.1.2.           Các thí dụ
   5.1.3.           Bài toán rút gọn Ôtômát
5.2.  Ôtômát hữu hạn trạng thái, không có ra
   5.2.1.           Các khái niệm
  1. Ôtômát đa định
   5.2.3.           Biểu thức chính qui và định lý Kleene.
   5.2.4.           Bổ đề bơm và ngôn ngữ không chấp nhận được bởi ôtômát hữu hạn
5.3.  Máy Turing
   5.3.1.           Mô tả máy Turing
   5.3.2.           Hàm Turing thực hiện được
  1. Các thí dụ.
Chữa bài tập ôn chương + Kiểm tra cuối kì
 
[3]
 
[1]
 
[4]
 
[5]
 
 
 
 
 
[7]
 
LT
 
LT
 
LT
 
Đọc thêm
Đọc thêm
Đọc thêm
 
 
LT
Đọc thêm
Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây