Phần 1: Toán rời rạc

Chia sẻ: Lan Lan | Ngày: | Loại File: PPT | Số trang:30

Thêm vào BST

Báo xấu

284
lượt xem 39
download

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

Trình bày các vấn đề của lý thuyết tổ hợp xoay quanh 4 bài toán cơ bản : Bài toán đêm, Bài toán tồn tại, Bài toán liệt kê và Bài toán tới ưu tổ hợp. Nội dung cảu phần I không những giúp nâng cao tư duy toán, mà còn làm quen với tư duy thuật toán trong việc giải quyết các vấn đề thực tế, đồng thời cũng rèn luyện kỹ thuật lập trình các bài toán tổ hợp

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phần 1: Toán rời rạc

TOÁN HỌC RỜI RẠC PHẦN 1 DISCRETE MATHEMATICS PART ONE
NỘI DUNG ÔN TẬP PHẦN 1 1. CƠ SỞ LOGIC a. Phép tính mệnh đề & vị từ b. Quy tắc suy luận. Quy nạp 2. ĐẠI SỐ BOOL a. Quan hệ thứ tự & tập hợp được sắp b. Dàn và đại số bool c. Hàm bool d. Phương trình bool & hệ phủ tối tiểu e. Công thức tối tiểu của hàm bool PHẦN 2 1. PHÉP ĐẾM a. Nguyên lý cộng, nhân & bù trừ b. Giải tích tổ hợp c. Nguyên lý Dirichlet d. Công thức đệ quy 2
NỘI DUNG ÔN TẬP (cont.) 2. LÝ THUYẾT ĐỒ THỊ a. Đại cương b. Đồ thị liên thông c. Đường đi ngắn nhất d. Cây khung trọng lượng tối tiểu e. Luồng cực đại 2. SỐ HỌC a. Lý thuyết chia hết b. Lý thuyết đồng dư 3
CƠ SỞ LOGIC (1) A. PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ Mệnh đề – Chân trị của mệnh đề: đúng, sai (true, false) – Các phép toán mệnh đề – Phép phủ định (NOT, ¬, …) • Phép hội (AND, ∧ ) • Phép tuyển: (OR, ∨ ) • Phép tuyển loại trừ (XOR, ⊕ ) • Phép toán trên bit • Phép kéo theo: → • Phép tương đương: ↔ • Biểu thức mệnh đề – Mệnh đề hệ quả & mệnh đề tương đương – Hằng đúng (tautology), hằng sai • Tiếp liên • Mệnh đề hệ quả: P → Q hằng đúng • Tương đương logic: P ↔ Q hằng đúng • 4
CƠ SỞ LOGIC (2) Các tương đương thường dùng (T=hằng đúng, F=hằng sai) P ∨T = T (P ∨Q) ∨R=P ∨(Q ∨R) = P ∨Q ∨R Domination laws Associative laws P ∧F = F (P ∧Q) ∧R = P ∧(Q ∧R) = P ∧Q ∧R P ∨F = P P ∨(Q ∧R)=(P∨ ∧(P∧ Identity laws Q) R) Distributive laws P ∧T = P P ∧(Q ∨R)=(P∧ ∨(P∧ Q) R) P ∨P = P ¬(P ∨Q) = ¬P ∧¬Q Idempotent laws De Morgan’s laws P ∧P = P ¬(P ∧Q) = ¬P ∨¬Q P ∨(P ∧Q) = P ¬(¬P)=P Double negation laws Absortion laws P ∨¬P = T P ∧(P ∨Q) = P Comlement laws P ∧¬P = F P → Q = ¬P ∨Q P ∨Q = Q ∨P Commutative laws P ∧Q = Q ∧P 5
CƠ SỞ LOGIC (3) Vị từ – Vị từ P: E → {0, 1} • Không gian của một vị từ: E = E1xE2x…xEn • Trọng lượng của một vị từ: n • Các phép toán vị từ: ¬, ∧ ∨ , , … • Các lượng tử • ¬ (∀ X: P(X)) = ∃ X: ¬P(X) – ¬ (∃ X: P(X)) = ∀ X: ¬P(X) – 6
CƠ SỞ LOGIC (4) B. QUY TẮC SUY LUẬN Các quy tắc suy luận: – Quy tắc Hằng đúng Tên P → (P ∨Q) Cộng P P∨Q P ∧Q → P P∧Q Rút gọn P (P ∧(P → Q)) → Q P, P → Q Modus ponens Q (¬Q ∧(P →Q)) → ¬P ¬Q , P → Q Modus tollens ¬P ((P →Q) ∧ → R)) → (P → R) Tam đoạn luận giả (Q P → Q, Q → R định P→R ¬P , P ∨ Q (¬P ∧(P ∨Q)) → Q Tam đoạn luận tuyển Q 7
CƠ SỞ LOGIC (5) Các phương pháp chứng minh: P → Q – Chứng minh rỗng (P = false) • Chứng minh tầm thường (Q = true) • Chứng minh trực tiếp (P = true kéo theo Q = true) • Chứng minh gián tiếp (Chứng minh ¬Q → ¬P đúng) • Chứng minh phản chứng (Chứng minh ¬Q ∧ → False) P • Chứng minh quy nạp • 8
ĐẠI SỐ BOOL (1) A. QUAN HỆ Quan hệ tương đương – Def: (phản xạ, đối xứng, bắc cầu) • Lớp tương đương • Tập thương • Quan hệ thứ tự – Def: (phản xạ, phản xứng, bắc cầu) (E, ≤ ) • Trội, trội trực tiếp, sơ đồ Hasse • Quan hệ thứ tự toàn phần, bộ phận • Phần tử • tối đại: M∈A ⊆ E, ∀x ∈A: M ≤ x ⇒ x=M – tối tiểu: m ∈A ⊆ E, ∀x ∈A: x ≤ m ⇒ x=M – phần tử lớn nhất: M∈A ⊆ E, ∀x ∈A: x ≤ M – phần tử nhỏ nhất: m∈A ⊆ E, ∀x ∈A: m ≤ x – 9
ĐẠI SỐ BOOL (2) B. DÀN (LATTICE) Cận trên: (E, ≤ ), x, y ∈ E, A={z| x ≤ z, y ≤ z}, nếu A có phần tử nhỏ – nhất thì phần tử nhỏ nhất đó được gọi là cận trên (đúng), ký hiệu sup(x, y) / x∨y cận dưới: (E, ≤ ), x, y ∈ E, A={z| z ≤ x, z ≤ y}, nếu A có phần tử lớn – nhất thì phần tử lớn nhất đó được gọi là cận dưới (đúng), ký hiệu inf(x, y) / x∧y / xy Dàn: (E, ≤ ), ∀x, y ∈ E, ∃ sup(x, y) = x∨y, inf(x, y)=x∧y – Các tính chất (giao hoán, kết hợp, phân phối) • Phần tử bù: (E, ≤ )dàn có phần tử lớn nhất ký hiệu 1, phần tử nhỏ nhất ký • hiệu 0, x ∈ E phần tử bù của x (trong E) là phần tử, ký hiệu sao cho x x ∨ x = 1   x ∧ x = 0  Dàn mà mọi phần tử đều có phần tử bù được gọi là dàn bị bù • 10
ĐẠI SỐ BOOL (3) ĐẠI SỐ BOOL • – Def1: dàn (E, ≤ ) có nhiều hơn một phần tử , là dàn phân phối và bị bù Def2: (E, ∨ ∧ ết hợp, giao hoán, phân phối, có phần tử trung , ) k hòa và phần tử bù – Định lý Stone • Atom: phần tử trội trực tiếp của phần tử nhỏ nhất • (E, ≤ ) là một đại số bool hữu hạn với phần tử nhỏ nhất ký hiệu là 0, ∀x ≠ 0∈ E, a1, a2, …, ak là tất cả các atom bị trội bởi x khi đó: x=a1 ∨ 2 ∨ ∨ k a … a cách viết này là duy nhất nếu không kể đến thự tự của các atom • Số phần tử của một đại số bool là lũy thừa của 2 • Đại số bool gồm 2n phần tử có n atom 11
HÀM BOOL (1) A. HÀM BOOL B=({0, 1}, ∨ ∧ à một đại số bool , ) l – f : Bn → B – ( x1 , x2 ,..., xn )  b f tương ứng với một dãy nhị phân độ dài 2n (dãy các giá trị của f trên các bộ biến 0…00, 0…01, 0…10, …) đánh chỉ số cho f bởi dãy nhị phân các giá trị của hàm f Fn = tập tất cả các hàm bool n biến – f, g ∈Fn , f ≤ g khi và chi khi ∀X ∈ Bn : f(X) ≤ g(X) – (Fn, ≤) là một đại số bool 12
HÀM BOOL (2) B. DẠNG CHUẨN TẮC TUYỂN Fn tập các hàm bool n biến – Từ tối tiểu (nguyên tửAtom): 00..010..0 – f là hàm bool, m1, m2, …, mk là tất cả các từ tối tiểu bị trội hơn – bởi f, ta có: f=m1∨ 2∨ ∨ k m …m xi , x i ( i = 1, 2,..., n) Literal: – ∀( b1 , b2 ,..., bn ) ∈ B n : xi ( b1 , b2 ,..., bn ) = bi xi ( b1 , b2 ,..., bn ) = bi Dạng chuẩn tắc tuyển của hàm bool f (n biến): – Lập bảng giá trị hàm f • Phân tích f thành tổng của các từ tối tiểu: f=m1 ∨ 2 ∨ ∨ k m … m • mi(b1, b2, …, bn) = 1, •  xi bi = 1 mi = y1 y2 ... yn ; y i =   x i bi = 0 13
HÀM BOOL (3) C. DẠNG CHUẨN TẮC HỘI Từ tối đại: 11…101…1 – M là từ tối đại, M(b1, b2, …, bn)=0 –  xi bi = 0 M = y1 ∨ y2 ∨ ... ∨ yn ; y i =   x i bi = 1 Dạng chuẩn tắc hội của hàm f (n biến): – Lập bảng giá trị của f • Phân tích f thành tích các từ tối đại: f=M1M2…Mk • Mi(b1, b2, …, bn)=0 •  xi bi = 0 M i = y1 ∨ y2 ∨ ... ∨ yn ; y i =   x i bi = 1 14
HÀM BOOL (4) HỆ PHƯƠNG TRÌNH BOOL & PHỦ TỐI TIỂU • HỆ PHƯƠNG TRÌNH BOOL: – G1, G2, …, Gk, D1, D2, …, Dk là 2n hàm bool n biến x1, x2, …, xn • Hệ phương trình bool • G1 ( x1 , x2 ,...xn ) = D1 ( x1 , x2 ,...xn )  ... G ( x , x ,...x ) = D ( x , x ,...x ) k 1 2 n k 1 2 n Phương pháp giải 1. Biến đổi mỗi phương trình về dạng tổng của các tích 2. Áp dụng biến đổi tương đương G=D ≅ 1=GD∨¬G¬D, biến đổi hệ về dạng 1 = G1 D1 ∨ ¬G1¬D1  ... 1 = G D ∨ ¬G ¬D  kk k k 3. Hệ tương đương với: 1=(G1D1∨¬G1¬D1)…(GkDk∨¬Gk¬Dk) 15
HÀM BOOL (5) 4. Biến đổi phương trình về dạng tổng của các tích: 1=h1 ∨ h2 ∨ … ∨ hm (hi là tích của các biến hoặc phủ định của biến 5. Phương trình tương đương với tuyển h1 = 1 ...  hm = 1  6. Do mỗi hi là tích các biến hoặc phủ định của biến, ta suy ra các nghiệm của hệ phương trình PHỦ TỐI TIỂU – Cho tập hợp E, e1, e2, …, en là các phần tử của E, A1, A2, …, Ap là các tập • con của E, ∪ { Ai | i=1,…, p} ⊇ {e1, e2, …, en}. Tìm họ con của họ {Ai} (phủ tối tiểu) sao cho: Hợp các tập của họ con này chứa {e1, e2, …, en} – Bỏ đi một tập bất kỳ của họ con thì hợp của các tập còn lại không còn chứa {e1, – e2, …, en} Phương pháp giải: • Đặt xi là biến sao cho nếu Ai được chọn ⇔ xi = 1 – ∀ ej / Aj1, Aj2, …, Ajq là tất cả các tập của họ chứa ej, ta xây dựng được – phương trình: xj1 ∨ xj2 ∨… ∨ xjq = 1 16 Giải hệ phương trình ta tìm được phủ tối tiểu –
ĐƠN GIẢN CÔNG THỨC (1) CÔNG THỨC TỐI TIỂU • Đơn thức: – tích của các literals khác 0 (nhân tử nguyên tố) • Đơn thức = 0 ⇔ tồn tại x bù của x trong đơn thức • Tồn tại duy nhất một cách viết đơn thức (sai khác thứ tự của các literals) • Tập Fn có 3n đơn thức • Ướ c – Đơn thức m là ước của đơn thức M (M chia hết cho m) nếu mỗi nhân tử • nguyên tố của m đều là nhân tử nguyên tố của M Đơn thức m là ước của M ⇔ M ≤ m • m là ước của M ⇔ m ∨ M = m • Công thức dạng đa thức: – f ∈ Fn , cách viết f dưới dạng tổng ( ∨ ủa các đơn thức được gọi là dạng ) c f = m1 ∨ m2 ∨ ... ∨ m m đa thức của f: , k k là các đơn thức Công thức dạng đa thức tối giản: – f = m1 ∨ m2 ∨ ... ∨ mk & ∀i ≠ j, mi không là ước của mj 17
ĐƠN GIẢN CÔNG THỨC (2) Quan hệ đơn giản hơn: – hai công thức tối giản của f: f=m1 ∨ 2 ∨ ∨ p m … m (1) f=M1 ∨ 2 ∨ ∨ q M … M (2) (1) được gọi là đơn giản hơn (2) khi và chỉ khi: p
ĐƠN GIẢN CÔNG THỨC (3) PHƯƠNG PHÁP KARNAUGH • Bảng Karnaugh – a a a a a a a a c c 1010 1110 0110 0010 101 111 011 001 d c d c 1011 1111 0111 0011 100 110 010 000 c d b 1001 1101 0101 0001 b b b c 1000 1100 0100 0000 d Sắp xếp các phần tử b b b b của B3 vào bảng karnaugh Sắp xếp các phần tử của B4 vào bảng karnaugh 19
ĐƠN GIẢN CÔNG THỨC (4) Sơ đồ karnaugh của hàm 3 hoặc 4 biến – B3 f B4 f 0000 0 000 0 0001 1 001 0 0010 0 1010 1110 0110 0010 010 1 101 111 011 001 0011 0 011 1 1011 1111 0111 0011 100 110 010 000 0100 1 100 0 1001 1101 0101 0001 0101 1 101 1 0110 0 1000 1100 0100 0000 110 1 0111 1 111 0 1000 0 1001 0 1010 0 Hàm bool 4 biến f hàm bool 3 biến f = =0100110100000011 00110110 1011 0 1100 0 1101 0 1110 1 1111 1 20