intTypePromotion=1
ADSENSE

Đề cương bài giảng Toán rời rạc - ĐH Sư Phạm Kỹ Thuật Hưng Yên

Chia sẻ: Le Thanh Hai | Ngày: | Loại File: PDF | Số trang:187

70
lượt xem
12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

(NB) Đề cương bài giảng Toán rời rạc cung cấp cho sinh viên những kiến thức cơ bản về yêu cầu môn học, nội dung cơ bản của môn học, ứng dụng của toán rời rạc trong ngôn ngữ lập trình,... Đây là một tài liệu hữu ích dành cho các bạn sinh viên các ngành Khoa học tự nhiên dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:
Lưu

Nội dung Text: Đề cương bài giảng Toán rời rạc - ĐH Sư Phạm Kỹ Thuật Hưng Yên

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN<br /> <br /> KHOA CÔNG NGHỆ THÔNG TIN<br /> <br /> ĐỀ CƯƠNG BÀI GIẢNG<br /> <br /> TOÁN RỜI RẠC<br /> <br /> Trình độ đào tạo: Đại học<br /> Hệ đào tạo:<br /> <br /> Chính qui<br /> <br /> Hưng Yên, Tháng 8 năm 2016<br /> <br /> TOÁN RỜI RẠC<br /> LỜI NÓI ĐẦU<br /> <br /> Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán<br /> học có đối tượng nghiên cứu là các tập hợp cấu trúc, đối tượng rời rạc, các ngành này được<br /> tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy<br /> tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán<br /> học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boolean.<br /> Một quan điểm rộng rãi hơn, gộp tất cả các ngành toán học làm việc với các tập hữu hạn<br /> hoặc đếm được vào toán học rời rạc như số học modulo m, lý thuyết nhóm hữu hạn, lý thuyết<br /> mật mã, ...<br /> Trong các cấu trúc, đối tường rời rạc không có một cấu trúc nào là cơ bản thực sự, bởi<br /> vì hầu hết cấu trúc có thể được định nghĩa thông qua hầu như bất kỳ các kiểu khác. Do vậy,<br /> trong modul này, nội dung sẽ trình bày những cấu trúc cơ bản và quan trọng nhất.<br /> Có thể nói toán học rời rạc là môn tiên quyết và hiệu quả nhất để người học nâng cao tư<br /> duy toán học trong phân tích, thiết kế thuật toán và rèn luyện kỹ năng lập trình với những<br /> thuật toán phức tạp. Không những thế nó còn là “cửa ngõ” để người học có thể tiếp cận với rất<br /> nhiều modul trong khoa học máy tính (như Chương trình dịch, lý thuyết tính toán, Trí tuệ<br /> nhân tạo, ...).<br /> Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránh khỏi<br /> những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả đọc giả và<br /> các bạn đồng nghiệp.<br /> Mọi góp xin gửi về: Khoa Công nghệ Thông tin – Trường ĐHSPKT Hưng Yên<br /> <br /> Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên<br /> <br /> Trang 1<br /> <br /> TOÁN RỜI RẠC<br /> <br /> Mục lục<br /> LỜI NÓI ĐẦU ................................................................................................................................ 0<br /> Mục lục ........................................................................................................................................... 2<br /> Danh mục các hình vẽ ..................................................................................................................... 6<br /> Bài 1 Tổng quan môn học ............................................................................................................... 8<br /> 1.1 Mở đầu................................................................................................................................... 8<br /> 1.2 Tại sao học toán rời rạc ......................................................................................................... 9<br /> 1.3 Toán học rời rạc nghiên cứu những gì ................................................................................ 10<br /> 1.4 Học toán rời rạc như thế nào ............................................................................................... 12<br /> 1.5. Toán rời rạc và ứng dụng ................................................................................................... 13<br /> BÀI 2: Logic mệnh đề (propositional logic) ................................................................................ 14<br /> 2.1. Mệnh đề .............................................................................................................................. 14<br /> 2.2. Các phép toán lôgic cơ bản ................................................................................................ 16<br /> 2.2.1. Phép phủ định .............................................................................................................. 16<br /> 2.2.2. Phép hội ....................................................................................................................... 16<br /> 2.2.3. Phép tuyển ................................................................................................................... 17<br /> 2.2.4. Phép kéo theo............................................................................................................... 18<br /> 2.2.5. Phép tương đương........................................................................................................ 19<br /> 2.3. Sự tương đương lôgic và luật ............................................................................................. 20<br /> 2.3.1. Giới thiệu ..................................................................................................................... 20<br /> 2.3.2. Sự tương đương lôgic .................................................................................................. 20<br /> 2.4. Bài tập................................................................................................................................. 23<br /> Bài 3 Logic vị từ (predicate logic)................................................................................................ 24<br /> 3.1. Vị từ .................................................................................................................................... 24<br /> 3.1.1. Định nghĩa ................................................................................................................... 24<br /> 3.1.1. Các phép toán vị từ ...................................................................................................... 24<br /> 3.2. Lượng từ ............................................................................................................................. 25<br /> 3.2.1. Mệnh đề tồn tại ............................................................................................................ 25<br /> 3.2.2. Mệnh đề tất cả.............................................................................................................. 26<br /> 3.2.3. Quy tắc phủ định mệnh đề có lượng từ........................................................................ 27<br /> 3.2.4 Một số lượng từ hai biến............................................................................................... 28<br /> 3.2.5 Một số quy tắc phổ dụng .............................................................................................. 28<br /> 3.3. Logic trong tìm kiếm trên mạng ........................................................................................ 29<br /> 3.4. Logic trong lập trình .......................................................................................................... 29<br /> 3.5. Logic trong đời sống .......................................................................................................... 29<br /> 3.6. Logic trong tính toán .......................................................................................................... 30<br /> 3.7. Logic trong suy luận ........................................................................................................... 30<br /> 3.8. Logic trong giải bài toán trong kĩ thuật .............................................................................. 31<br /> Bài 4 Thảo luận Logic ................................................................................................................... 34<br /> 4.1. Logic mệnh đề .................................................................................................................... 34<br /> 4.1.1 Logic trong suy luận ..................................................................................................... 34<br /> 4.1.2. Mạch logic số............................................................................................................... 34<br /> 4.2. Logic vị từ .......................................................................................................................... 34<br /> 4.2.1 Logic trong suy luận ..................................................................................................... 34<br /> 4.3. Logic mờ (*) ....................................................................................................................... 34<br /> 4.4. Thảo luận ............................................................................................................................ 34<br /> Bài 5 Một số phương pháp chứng minh........................................................................................ 35<br /> 5.1. Giới thiệu ............................................................................................................................ 35<br /> 5.1.1. Vai trò của chứng minh ............................................................................................... 35<br /> 5.1.2. Một số thuật ngữ .......................................................................................................... 35<br /> 5.2. Chứng minh nhờ luật suy diễn ........................................................................................... 36<br /> 5.2.1. Giới thiệu ..................................................................................................................... 36<br /> <br /> Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên<br /> <br /> Trang 2<br /> <br /> TOÁN RỜI RẠC<br /> <br /> 5.2.2. Một số ví dụ ................................................................................................................. 38<br /> 5.3. Các phương pháp chứng minh cho mệnh đề kéo theo ....................................................... 39<br /> 5.3.1. Chứng minh trực tiếp................................................................................................... 39<br /> 5.3.2. Chứng minh gián tiếp .................................................................................................. 40<br /> 5.3.3. Chứng minh bằng cách phân chia trường hợp............................................................. 41<br /> 5.3.4. Chứng minh vacuous ................................................................................................... 42<br /> 5.3.5. Chứng minh trivial ...................................................................................................... 42<br /> 5.4. Chứng minh bằng phản chứng ........................................................................................... 43<br /> 5.5. Chứng minh bằng quy nạp ................................................................................................. 44<br /> 5.6. Chứng minh bằng cách đưa ra phản ví dụ .......................................................................... 45<br /> 5.7. Một số ngộ nhận thường gặp ............................................................................................. 46<br /> Bài 6. Ứng dụng của phương pháp chứng minh nhờ luật suy diễn .............................................. 47<br /> 6.1. Ứng dụng............................................................................................................................ 47<br /> 6.2. Bài tập ................................................................................................................................ 47<br /> Bài 7 Số và Ma trận ...................................................................................................................... 49<br /> 7.1. Thuật toán .......................................................................................................................... 49<br /> 7.1.1. Giới thiệu ..................................................................................................................... 49<br /> 7.1.2. Định nghĩa ................................................................................................................... 49<br /> 7.1.3. Các đặc trưng của thuật toán: ...................................................................................... 50<br /> 7.2. Độ phức tạp của thuật toán ................................................................................................ 50<br /> 7.2.1. Khái niệm về độ phức tạp của một thuật toán ............................................................. 50<br /> 7.2.2. So sánh độ phức tạp của các thuật toán: ...................................................................... 52<br /> 7.3. Số nguyên và thuật toán ..................................................................................................... 55<br /> 7.3.1 Thuật toán Euclide........................................................................................................ 55<br /> 7.3.2 Biểu diễn các số nguyên ............................................................................................... 57<br /> 7.3.3 Thuật toán cho các phép tính số nguyên ...................................................................... 58<br /> 7.4. Số học đồng dư................................................................................................................... 60<br /> 7.5. Ma trận ............................................................................................................................... 62<br /> 7.5.1. Giới thiệu ma trận và ứng dụng của ma trận ............................................................... 62<br /> 7.5.2. Các phép toán trên ma trận .......................................................................................... 62<br /> 7.5.3. Các loại ma trận đặc biệt ............................................................................................. 63<br /> Bài 8 Số nguyên và ứng dụng ....................................................................................................... 65<br /> 8.1. Số học đồng dư và ứng dụng.............................................................................................. 65<br /> 8.1.1. Hàm băm ..................................................................................................................... 65<br /> 8.1.2. Các số giả ngẫu nhiên .................................................................................................. 65<br /> 8.1.3. Mật mã ......................................................................................................................... 65<br /> 8.2. Số nguyên tố và ứng dụng.................................................................................................. 66<br /> 8.2.1. Số nguyên tố ................................................................................................................ 66<br /> 8.2.2. Thuật toán sàng số nguyên tố ...................................................................................... 67<br /> 8.3. Giải thuật đệ quy ................................................................................................................ 69<br /> 8.3.1. Khái niệm đệ quy......................................................................................................... 69<br /> 8.3.2. Thuật toán đệ qui ......................................................................................................... 70<br /> 8.3.3. Đệ quy và lặp ............................................................................................................... 71<br /> BÀI 9 Kỹ thuật đếm cơ bản (Count technique) ............................................................................ 74<br /> 9.1. Định nghĩa .......................................................................................................................... 74<br /> 9.2. Nguyên lý cộng và nguyên lý nhân .................................................................................... 74<br /> 9.2.1. Nguyên lý cộng ........................................................................................................... 74<br /> 9.2.2. Nguyên lý nhân ........................................................................................................... 76<br /> 9.3. Nguyên lý bù trừ ................................................................................................................ 79<br /> 9.4. Nguyên lý Dirichlet ............................................................................................................ 80<br /> 9.4.1. Nguyên lý Dirichlet tổng quát ..................................................................................... 81<br /> 9.4.2. Một số ứng dụng của nguyên lý Dirichlet ................................................................... 81<br /> <br /> Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên<br /> <br /> Trang 3<br /> <br /> TOÁN RỜI RẠC<br /> <br /> 9.5. Hoán vị, tổ hợp, chỉnh hợp (*) ........................................................................................... 82<br /> 9.5.1. Chỉnh hợp .................................................................................................................... 82<br /> 9.5.2. Tổ hợp .......................................................................................................................... 83<br /> 9.5.3. Hoán vị ........................................................................................................................ 85<br /> 9.5.4. Hoán vị lặp................................................................................................................... 86<br /> 9.6. Bài tập................................................................................................................................. 87<br /> Bài 10 Quan hệ truy hồi (Recurrence Relations) .......................................................................... 88<br /> 10.1. Định nghĩa ........................................................................................................................ 88<br /> 10.2. Một số ví dụ...................................................................................................................... 88<br /> 10.3. Kỹ thuật giải phương trình truy hồi .................................................................................. 90<br /> 10.4. Bài tập............................................................................................................................... 90<br /> Bài 11. Thảo luận về kỹ thuật đếm ............................................................................................... 91<br /> 11.1. Nhắc lại lý thuyết ............................................................................................................. 91<br /> 11.2. Bài tập kỹ thuật đếm cơ bản ............................................................................................. 91<br /> 11.3. Bài tập kỹ thuật đếm nâng cao ......................................................................................... 92<br /> Bài 12 Các khái niệm cơ bản của Lý thuyết đồ thị .................................................................... 93<br /> 12.1 Định nghĩa cơ bản về đồ thị .............................................................................................. 93<br /> 12.2. Đường đi - chu trình - Đồ thị liên thông .......................................................................... 95<br /> 12.3. Phân loại đồ thị ................................................................................................................. 98<br /> 12.3.1. Đồ thị vô hướng liên thông ........................................................................................ 98<br /> 12.3.2. Đồ thị có hướng liên thông ........................................................................................ 99<br /> 12.4. Một số loại đồ thị đặc biệt .............................................................................................. 100<br /> Bài 13 Biểu diễn đồ thị trên máy tính ...................................................................................... 104<br /> 13.1. Ma trận kề - Ma trận trọng số ......................................................................................... 104<br /> 13.2. Danh sách cạnh (cung) ................................................................................................... 106<br /> 13.3. Danh sách kề .................................................................................................................. 107<br /> 13.4. Bài tập............................................................................................................................. 108<br /> Bài 14 Đồ thị Euler – Hamilton ............................................................................................... 109<br /> 14.1 Đồ thị Euler ..................................................................................................................... 109<br /> 14.1.1. Định nghĩa ............................................................................................................... 109<br /> 14.1.2. Các ví dụ .................................................................................................................. 109<br /> 14.1.3. Định lý Euler............................................................................................................ 110<br /> 14.1.4. Thuật toán Flor tìm đường đi chu trình Euler .......................................................... 113<br /> 14.1.5. Một số bài toán liên quan(*) .................................................................................... 113<br /> 14.2 Đồ thị Hamilton ............................................................................................................... 113<br /> 14.2.1 Định nghĩa ................................................................................................................ 114<br /> 14.2.2 Định lý Dirak ............................................................................................................ 114<br /> 14.2.3 Thuật toán liệt kê tất cả các chu trình Hamilton của đồ thị ...................................... 115<br /> Bài 15 Cài đặt đồ thị, thuật toán tìm chu trình Euler và liệt kê chu trình Hamilton ................ 118<br /> 15.1. Cài đặt biểu diễn đồ thị trên máy tính ............................................................................ 118<br /> 15.2. Cài đặt thuật toán liệt kê chu trình Euler ........................................................................ 118<br /> 15.3. Cài đặt thuật toán liệt kê chu trình Hamilton ................................................................. 119<br /> Bài 16 Thuật toán tìm kiếm trên đồ thị và ứng dụng ............................................................... 120<br /> 16.1. Duyệt đồ thị theo chiều rộng (BFS) ............................................................................... 120<br /> 16.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................. 123<br /> 16.3. Bài tập............................................................................................................................. 125<br /> 16.4. Ứng dụng ........................................................................................................................ 126<br /> Bài 17 Cây và cây khung ......................................................................................................... 128<br /> 17.1. Cây và cây khung ........................................................................................................... 128<br /> 17.1.1. Cây ........................................................................................................................... 128<br /> 17.1.2. Cây khung của đồ thị ............................................................................................... 129<br /> 17.2. Bài toán cây khung nhỏ nhất .......................................................................................... 131<br /> <br /> Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên<br /> <br /> Trang 4<br /> <br />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2