Chapter 0IntroductionDiscrete Struc

Chapter 0
Introduction
Discrete Structures for Computing on September 11, 2014
Huynh Tuong Nguyen, Tran Huong Lan
Faculty of Computer Science and Engineering
University of Technology - VNUHCMIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.2
Contents
1 Course description
Course outline
Document
2 Some applicationsIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.3
Context
Global
• 6 principal chapters on 45 hours for courses & exercises.
• 10 Labs (10%), 1 Assignment (10%)
• 2 evaluations: mid-exam (MCQ - 60 minutes - 40%) + final
exam (MCQ + writing - 120 minutes - 40%)
Aims
The content of this subject is mainly a great part of logic, set
theory and graph theory.
This is the mathematical base for many topics of Computational
ScienceIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.4
Subjects in general discrete mathematics course
☞ Logic
☞ Set theory
☞ Number theory
☞ Combinatorics: enumerative combinatorics, graph theory
☞ Algorithmics
☞ Information theory
☞ Complexity theory
☞ Probability theory
☞ Proof
☞ Counting and RelationsIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.5
Topics relational to the course
1 Theoretical computer science
2 Information theory
3 Logic
4 Set theory
5 Combinatorics
6 Graph theory
7 Probability
8 Number theory
9 Algebra
10 Calculus of finite differences, discrete calculus or discrete analysis
11 Geometry
12 Topology
13 Operations research: scheduling
14 Game theory, decision theory, utility theory, social choice theory
15 Discretization
16 Discrete analogues of continuous mathematics
17 . . .Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.6
Context
Course outline
• Proof methods
• modular arithmetic over integers.
• induction, contradiction.
• Set theory
• relations, functions, cardinalities, relation, equivalence equation, partial order
• combinatorics: counting, principles of sum, multiplication, division, inclusion
and exclusion.
• Graph theory
• directed, undirected, isomorphism
• weighted graphs, algorithm for finding shortest paths
• trees: features, binary trees, minimum spanning trees in connected and
weighted graphs
• flows network
• Probabilistics Modelling
• introductory random variables.Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.7
Document
Book
• Discrete mathematics and applications - Kenneth H. Rosen.
(Vietnamese translation - NXB KHKT 1997)
• Discrete mathematics - Richard Johnsonbaugh, Willey, 1997
• Discrete mathematics with algorithms - Micheal O. Albertson & Joan P.
Hutchinson, Willey, 1998Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.8
Application
• it concerns a wide range of disciplines in various areas: science, technology,
business and commerce.
• applied mathematicians are engaged in the creation, study and application of
advanced mathematical methods relevant to specific problems.
• applied mathematics has assumed a much broader meaning and embraces such
diverse fields as communication theory, optimization, game theory and numerical
analysis.
• today there is a remarkable variety of applications of mathematics in industry and
government, such as materials processing, design, medical diagnosis, development
of financial products, network management, weather prediction, etc.
Engineers use technology, mathematics and
scientific knowledge to solve practical
problems. (wikipedia.org)
Science
Technology
EngineeringIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.9
Computing of algorithm complexity
Know results
Size Approximating of computational time
n O(log n) O(n) O(n log n) O(n
2
) O(2n) O(n!)
10 3.10−9
s 10−8
s 3.10−8
s 10−7
s 10−6
s 3.10−3
s
102 7.10−9
s 10−7
s 7.10−7
s 10−5
s 4.1013y *
103 10−8
s 10−6
s 10−5
s 10−3
s * *
104 1, 3.10−8
s 10−5
s 10−4
s 10−1
s * *
105 1, 7.10−8
s 10−4
s 2.10−3
s 10s * *
106 2.10−8
s 10−3
s 2.10−2
s 17m * *Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.10
Mathematical model
Solver
• Simplex, GLPK
• CPLEX, MPL
• Excel, Mathlab, etc.Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.11
Mathematical model
Exercise
A bookseller A buys books from two publishers B, and C.
Publisher B offers a package of 5 mysteries and 5 romance novels
for $50, and publisher C offers a package of 5 mysteries and 10
romance novels for $150. The bookseller A wants to buy at least
2,500 mysteries and 3,500 romance novels, and he has promised C
(who has influence on the Senate Textbook Committee) that at
least 25% of the total number of books he purchases will come
from publisher C.
Question. How many packages should A order from each
publisher in order to minimize his cost and satisfy C ? What will
the novels cost him?Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.12
Mathematical model
Solution
Let x be the number of packages from Publisher B, and let y be
the number of packages from C.
Problem: Minimize C = 50x + 150y subject to
• 5x + 5y ≥ 2.500
• 5x + 10y ≥ 3.500
• x − 4.5y ≤ 0
• x ≥ 0, y ≥ 0
Answer: Buy 484 packages from Publisher B and 108 from C for a
total cost of $40.400.Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.13
Graph
• Shortest path problem
• Min cut and maximum flow
• Vehicle Routing ProblemIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.14
SchedulingIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.15
Scheduling
Exercise
Problem 1||Tmax.
Given 8 jobs with processing times and due dates as follows:
Job J1 J2 J3 J4 J5 J6 J7 J8
pi 1 2 2 3 3 4 4 3
di 25 16 19 7 18 22 27 8
Let Ci be completion time of job Ji and let Ti = max(0, Ci − di) its
tardiness.
Question. How to minimize Tmax = maxi Ti ? What is the minimum value of
Tmax ?Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.16
Timetabling
Example
In the bipartite graph below, the vertices P1, . . . , P6 represent workers and
edges J1, . . . , J6 of jobs. An edge connects a worker with a job if the worker
has the necessary qualifications to occupy this job. Here, all the edges have an
unit weight 1, mean that Pi has the skill(competence) to operate Jj if there is
an edge between Pi and Jj .
P1 P2 P3 P4 P5 P6
J1 J2 J3 J4 J5 J6Introduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.17
Game and simulation
Sally Salon GameIntroduction
Huynh Tuong Nguyen,
Tran Huong Lan
Contents
Course description
Course outline
Document
Some applications
0.18
Probabilistics Modelling
Calculating of Pi
Using a Monte-Carlo method to determine an approximate value
of π :
randomly draw a great number of points in a square of side 2, and
determine the ratio C/N where N is the total number of points,
and C the number of points whose distance to the center of the
square is ≤ 1).

Kết quả (Việt) 1:

Chương 0Giới thiệuCác cấu trúc rời rạc cho máy tính ngày 11 tháng 9 năm 2014Nguyễn Huỳnh tường, trần hương LanKhoa Khoa học máy tính và kỹ thuậtĐại học công nghệ - VNUHCMIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,2Nội dung1 Mô tả khóa họcĐề cương khóa họcTài liệu2 một số applicationsIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0.3Bối cảnhToàn cầu• 6 chính chương trên 45 giờ cho các khóa học và bài tập.• 10 labs (10%), 1 chuyển nhượng (10%)• 2 đánh giá: giữa kỳ thi (MCQ - 60 phút - 40%) + cuối cùngkỳ thi (MCQ + văn bản - 120 phút - 40%)Mục tiêuNội dung của chủ đề này là chủ yếu là một phần tuyệt vời của logic, đặtlý thuyết và lý thuyết đồ thị.Đây là cơ sở toán học cho nhiều đề tài của ComputationalScienceIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0.4Đối tượng nói chung khóa học toán học rời rạc☞ LogicLý thuyết tập hợp ☞Lý thuyết số ☞☞ toán học tổ hợp: enumerative toán học tổ hợp, lý thuyết đồ thị☞ Algorithmics☞ thông tin lý thuyếtLý thuyết độ phức tạp ☞Lý thuyết xác suất ☞☞ bằng chứng☞ Đếm và RelationsIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,5Các chủ đề quan hệ với khoá họcKhoa học lý thuyết máy tính 12 thông tin lý thuyết3 logic4 các lý thuyết tập hợpToán học tổ hợp 56 lý thuyết đồ thị7 xác suấtLý thuyết số 8Đại số 9Các tính toán 10 sự khác biệt hữu hạn, tính toán rời rạc hay phân tích rời rạc11 hình họcCấu trúc liên kết 1213 hoạt động nghiên cứu: lập kế hoạch14 lý thuyết trò chơi, lý thuyết quyết định, Tiện ích lý thuyết, lý thuyết xã hội lựa chọn15 discretization16 analogues liên tục toán học rời rạc17...Giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,6Bối cảnhĐề cương khóa học• Các phương pháp chứng minh• Mô-đun số học qua số nguyên.• cảm ứng, mâu thuẫn.• Lý thuyết tập hợp• quan hệ, chức năng, cardinalities, quan hệ, phương trình tương đương, một phần hàng• tổ hợp: đếm, các nguyên tắc của tổng hợp, nhân, chia, bao gồmvà loại trừ.• Lý thuyết đồ thị• đạo diễn, vô hướng, đẳng cấu• trọng đồ thị, các thuật toán cho việc tìm kiếm đường đi ngắn nhất• cây: tính năng, cây nhị phân, tối thiểu bao trùm cây trong kết nối vàtrọng đồ thị• chảy mạng• Probabilistics mô hình• giới thiệu biến ngẫu nhiên.Giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,7Tài liệuCuốn sách• Toán học rời rạc và ứng dụng - Kenneth H. Rosen.(Việt Nam dịch - NXB KHKT 1997)• Toán học rời rạc - Richard Johnsonbaugh, Willey, 1997• Các toán học rời rạc với các thuật toán - Michael O. Albertson & Joan P.Hutchinson, Willey, 1998IntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,8Ứng dụng• nó liên quan đến một loạt các ngành trong lĩnh vực khác nhau: khoa học, công nghệ,kinh doanh và thương mại.• áp dụng toán học đang tham gia vào việc tạo ra, nghiên cứu và ứng dụng củanâng cao phương pháp toán học vấn đề có liên quan đến cụ thể.• áp dụng toán học đã giả định một ý nghĩa rộng hơn nhiều và bao trùm như vậycác lĩnh vực đa dạng như lý thuyết giao tiếp, tối ưu hóa, lý thuyết trò chơi và sốphân tích.• hôm nay đó là một loạt đáng kể của các ứng dụng của toán học trong ngành công nghiệp vàchính phủ, chẳng hạn như chế biến vật liệu, thiết kế, chẩn đoán y tế, phát triểnsản phẩm tài chính, quản lý mạng, dự báo thời tiết, vv.Kỹ sư sử dụng công nghệ, toán học vàCác kiến thức khoa học để giải quyết thiết thựcvấn đề. (wikipedia.org)Khoa họcCông nghệEngineeringIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0.9Máy tính của thuật toán phức tạpBiết kết quảKích thước Approximating tính toán thời giann O(log n) O(n) O(n log n) O (n2) O(2n) O(n!)10 3.10−9s 10−8s 3.10−8s 10−7s 10−6s 3.10−3s102 7.10−9s 10−7s 7.10−7s 10−5s 4.1013y *103 10−8s 10−6s 10−5s 10−3s * *104 1, 3.10−8s 10−5s 10−4s 10−1s * *105 1, 7.10−8s 10−4s 2.10−3s 10s **106 2.10−8s 10−3s 2.10−2s 17m * * giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,10Mô hình toán họcNgười giải quyết• Simplex, GLPK• CPLEX, MPL• Excel, Mathlab, vv.Giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,11Mô hình toán họcTập thể dụcMột bookseller A mua sách từ nhà phát hành hai B, và C.Nhà xuất bản B cung cấp một gói của 5 bí ẩn và tiểu thuyết lãng mạn 5Đối với $50, và nhà xuất bản C cung cấp một gói bí ẩn 5 và 10tiểu thuyết lãng mạn cho $150. Bookseller A muốn mua ít2.500 bí ẩn và tiểu thuyết lãng mạn 3.500, và ông đã hứa hẹn C(những người có ảnh hưởng đến Ủy ban Thượng viện sách giáo khoa) mà lúcít nhất 25% của tổng số sách ông mua sẽ đếntừ nhà xuất bản C.Câu hỏi. Làm thế nào nhiều gói nên A đặt hàng từ mỗinhà xuất bản để giảm thiểu chi phí của mình và đáp ứng C? Điều gì sẽCác tiểu thuyết chi phí Anh ta?Giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,12Mô hình toán họcGiải phápCho x là số lượng các gói từ nhà xuất bản B, và cho ysố lượng các gói từ C.Vấn đề: Giảm thiểu C = 50 x + 150y chịu sự điều• 5 x + 5y ≥ 2,500• 5 x + 10y ≥ 3.500• x − 4.5y ≤ 0• x ≥ 0, y ≥ 0Trả lời: Mua 484 gói từ nhà xuất bản B và 108 từ C cho mộtTổng chi phí của $40.400.IntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,13Đồ thịBài toán đường đi ngắn nhất •• Min cắt và luồng cực đại• Xe định tuyến ProblemIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,14SchedulingIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,15Lập kế hoạchTập thể dụcVấn đề 1||Suspect.Cho các công việc 8 với thời gian chế biến và hạn như sau:Công việc J1 J2 J3 J4 J5 J6 J7 J8Pi 1 2 2 3 3 4 4 3di 25 16 19 7 18 22 27 8Hãy để Ci là thời gian hoàn thành công việc Ji và Ti = tối (0, Ci − di) của nótardiness.Câu hỏi. Làm thế nào để giảm thiểu suspect = maxi Ti? Giá trị tối thiểu của là gìSuspect?Giới thiệuHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,16TimetablingVí dụTrong đồ thị hai phía dưới, các đỉnh P1,..., P6 đại diện cho người lao động vàcạnh J1,..., J6 công ăn việc làm. Một cạnh kết nối một nhân viên với một công việc nếu các công nhâncó những yêu cầu cần thiết để chiếm công việc này. Ở đây, tất cả các cạnh có mộtđơn trọng 1, có nghĩa là Pi có skill(competence) hoạt động Jj nếu cómột cạnh giữa Pi và Jj.P1 P2 P3 P4 P5 P6J1 J2 J3 J4 J5 J6IntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,17Trò chơi và mô phỏngSally Salon GameIntroductionHuỳnh tường NguyễnTrần hương LanNội dungMô tả khóa họcĐề cương khóa họcTài liệuMột số ứng dụng0,18Probabilistics mô hìnhTính toán của PiBằng cách sử dụng một phương pháp Monte-Carlo để xác định một giá trị xấp xỉsố π:ngẫu nhiên rút ra một số lớn các điểm trong một hình vuông của bên 2, vàxác định tỷ lệ C/N N là tổng số điểm,và C số lượng chỉ có khoảng cách đến Trung tâm của cácvuông là ≤ 1).