Bài giảng Toán rời rạc - Chương 1: Cơ sở logic - Huỳnh Thị Thu Thủy

viên đó không tán khiển bởi nhiều công tắc. thành. –Các mạch cần được thiết kế sao cho khi ấn 1 –Tương tự: y, z cho thành viên thứ 2 và 3. công tắc bất kỳ , hệ thống đèn đang tắt sẽ bật và đang bật sẽ tắt. –Biểu thức Boole? – Hãy thiết kế 1 mạch thực hiện điều đó khi có 2 F = xy+xz+yz côtông tắc vààkhi khi c ó3ó 3 c ông tắc. Gv: Huỳnh Thị Thu Thủy 131 Gv: Huỳnh Thị Thu Thủy 132 33 5/10/2013 Ví dụ về các mạch (tt) Ví dụ về các mạch (tt) • Ví dụ 2 (tt): •Ví dụ 2 (tt): – Khi có 2 công tắc: – Chúng ta có thể chọn để đèn sáng •Giả sử: x=1: công tắc 1 đóng khi 2 công tắc đều đóng, tức là xyF • x=0: công tắc 1 mở F(1,1)=1. 111 • y=1: công tắc 2 đóng. – Khi 1 trong 2 công tắc mở đèn sẽ • y=0: công tắc 2 mở. tắt, tức là F(1,0)=F(0,1)=0. 100 – Khi công tắc còn lại cũng mở nốt • F(x,y)=1: khi đèn sáng 010 thì đèn sáng , tứclàF(00)=1c là F(0,0)=1. • F(x,y)=0: khi đèn tắt. –Mạch tổ hợp? 001 Gv: Huỳnh Thị Thu Thủy 133 Gv: Huỳnh Thị Thu Thủy 134 Ví dụ về các mạch (tt) Ví dụ về các mạch (tt) •Ví dụ 2 (tt): xyzF • Ví dụ 2 (tt): – Khi 1 công tắc mở đèn sẽ tắt, 111 1 – Khi có 3 công tắc: tứclà:c là: 1 1 0 0 •Giả sử: x,y,z đại diện cho 3 công tắc 1,2,3. F(1,1,0)=F(1,0,1)=F(0,1,1)=0. 1010 • Khi biến nào bằng 1: công tắc tương ứng với – Khi thêm 1 công tắc mở đèn sẽ biến đó đóng. sáng, tức là: 100 1 • Khi biến nào bằng 0: công tắc tương ứng với F(1,0,0)=F(0,1,0)=F(0,0,1)=1. 0110 biến đó mở. • F(x,y,z) =1 : khi đèáèn sáng – Khi cả 3 công tắc đềumu mở đèn lại 0 1 0 1 • F(x,y,z)=0: khi đèn tắt. tắt, tức là: F(0,0,0)=0. 001 1 –Mạch tổ hợp? 0000 Gv: Huỳnh Thị Thu Thủy 135 Gv: Huỳnh Thị Thu Thủy 136 34 5/10/2013 6- Bộ cộng 6- Bộ cộng (tt) •Mạch logic có thể được dùng để thực hiện •Bảng giá trị: xysc phép cộng 2 số nguyên dương từ các triển •Từ bảng giá trị ta khai nhị phân của chúng. thấy: 1101 –Xây dựng mạch tìm x+y với x,y là 2 bit c=x.y – Đầu vào mạch này là x,y Và s=xy+xy=(x+y)(x y) 1010 – Đầu ra là 2 biến s,c; trong đó s là tổng và c là bit nhớ. • Mạch bộ nửa 0110 –Mạch thiết kế được gọi là bộ nửa cộng vì nó cộng 2 cộng? bít mà không xét đến số nhớ từ phép cộng trước. 0000 Gv: Huỳnh Thị Thu Thủy 137 Gv: Huỳnh Thị Thu Thủy 138 6- Bộ cộng (tt) Đầu vào Đầu ra 6- Bộ cộng (tt) • Chúng ta sẽ dùng bộ cộng đầy đủ để tính bít xyci sci+1 tổng và bít nhớ khi 2 bít 111 1 1 •Hai đầu ra của bộ cộng đầy đủ được đượccc cộng cùng vớisi số biểu diễn: nhớ. 110 0 1 –s= xyc+ xyc + xyc + xyc • Đầu vào của bộ cộng 101 0 1 i i i i đầy đủ: x,y và số nhớ c –ci+1= xyci+ xyci+ xyci+ xyci i 100 1 0 • Đầu ra là bít tổng s và – Thay vì thiết kế bộ cộng đầy đủ, ta sẽ dùng bít nhớ mới ci+1 011 0 1 bộ nửa cộng: 010 1 0 001 1 0 000 0 0 Gv: Huỳnh Thị Thu Thủy 139 Gv: Huỳnh Thị Thu Thủy 140 35 5/10/2013 6- Bộ cộng (tt) 7- Tối tiểu hoá hàm Boole •Bản đồ Karnaugh – Biểu diễn biểu thức Boole dưới dạng bảnggg Karnaugh. c s i Bộ nửa  – Các ô có đánh dấu “1” kề nhau được ghép lại với cộng (x+y)(xy) nhau sao cho có được nhóm lớn nhất các ô vuông c –Chọn các nhóm và các ô vuông riêng lẻ (các ô x Bộ nửa  i+1 không được ghép với nhau) theo quy luật: y cộng số nhớ c =xy •Mỗi chữ số 1 được chứa ít nhất 1 lần trong các nhóm i đãchoã cho. •Số lượng nhóm được chọn sao cho phải là ít nhất. Gv: Huỳnh Thị Thu Thủy 141 Gv: Huỳnh Thị Thu Thủy 142 7- Tối tiểu hoá hàm Boole (tt) 7- Tối tiểu hoá hàm Boole(tt) •Ví dụ: Tìm dạng tối thiểu của biểu thức Boole sau •Phương pháp Quine Mc Cluskey a/. wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz b/. wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz Bước 1 Bước 2 c/. wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ Số Xâu Số Xâu Số Xâu bit wxyz+ wxyz hạng bit hạng bit hạng 1 xyz 111 (1,2) xz 1-1 (1,2,3,4) z --1 2 xyz 101 (1,3) yz -11 3 xyz 011 (2,4) yz -01 4 xyz 001 (3,4) xz 0-1 5 xyz 000 (4,5) xy 00- • Kết quả: z+xy Gv: Huỳnh Thị Thu Thủy 143 Gv: Huỳnh Thị Thu Thủy 144 36 5/10/2013 7- Tối tiểu hoá hàm Boole(tt) TỔNG KẾT CHƯƠNG 4 1. Đại số Boole • Ví dụ: Tìm dạng tối thiểu của biểu thức BlBoole sau bằng PP Qui ne Mc Clus key 2. Biểuthu thức Boole và hàm Boole wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz+ wxyz 3. Các hằng đẳng thức của đại số Boole 4. Tính đối ngẫu 5. Các cổnggg logic 6. Bộ cộng 7. Tối tiểu hoá hàm Boole Gv: Huỳnh Thị Thu Thủy 145 Gv: Huỳnh Thị Thu Thủy 146 NỘI DUNG 1. Đại cương về đồ thị 2. Đường đi – chu trình Chương 5: ĐỒ THỊ 3. Biểu diễn đồ thị bằng ma trận 4. Bài toán về đường đi Gv: Huỳnh Thị Thu Thủy 147 Gv: Huỳnh Thị Thu Thủy 148 37 5/10/2013 1- Đại cương về đồ thị 1- Đại cương về đồ thị – VD: Đồ thị biểu diễn sự cạnh tranh các loài • Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh trong 1 môi trường sinh thái; và các c ạnh nốiicác các đỉnh đó. •Nhiều bài toán thuộc các lĩnh vực rất khác nhau có thể giải được bằng mô hình đồ thị. – VD: Đồ thị biểu diễn sự cạnh tranh các loài –Kết cục của cuộc thi đấu thể thao;... trong 1 môi trường sinh thái; kết cục của cuộc thi đấu thể thao;... Gv: Huỳnh Thị Thu Thủy 149 Gv: Huỳnh Thị Thu Thủy 150 1- Đại cương về đồ thị (tt) 1- Đại cương về đồ thị (tt) •Các loại đồ thị: – Ví dụ: Đơn đồ thị: Đỉnh đồ thị là vị trí các máy – Định ngh ĩa1a 1: Một đơn đồ thị G=(V,E) g ồm1m 1 tính; cạnh là các đường điệnthon thoại. tập không rỗng V mà các phần tử của nó gọi là các đỉnh và 1 tập E mà các phần tử của nó Destroit New York gọi là các cạnh, đó là các cặp không thứ tự Chicago của các đỉnh phân biệt. San Francisco – Ví d ụ:Gi: Giả sử 11m mạng máy tính gồmmcácmáy các máy Denver tính và các đường điện thoại. Washington Los Angeles Đơn đồ thị Gv: Huỳnh Thị Thu Thủy 151 Gv: Huỳnh Thị Thu Thủy 152 38 5/10/2013 1- Đại cương về đồ thị (tt) 1- Đại cương về đồ thị (tt) • Định nghĩa 2: Một đa đồ thị G=(V,E) gồm – Ví dụ: Đa đồ thị: Có nhiều đường điện thoại mộttt tậppcác các đỉnh V, mộttt tậppcácc các cạnh E và giữa các máy tính trong mạng. 1 hàm f từ E tới { {u,v}| u,v  V, u  v}. Các Destroit cạnh e1, e2 được gọi là song song hay New York cạnh bội nếu f(e )=f(e ). 1 2 Chicago – Ví dụ: Giả sử 1 mạng máy tính gồm các máy San Francisco tính và cá c đđờường điện thoại. Denver Washington Los Angeles Đa đồ thị Gv: Huỳnh Thị Thu Thủy 153 Gv: Huỳnh Thị Thu Thủy 154 1- Đại cương về đồ thị (tt) 1- Đại cương về đồ thị (tt) • Định nghĩa 3: Một giả đồ thị G=(V,E) gồm – Ví dụ: Giả đồ thị: Có thể có đường điện thoại mộttt tậppcác các đỉnh V, mộttt tậppcácc các cạnh E và từ một máy tới chính nó. 1 hàm f từ E tới { {u,v}| u,v  V}. Một cạnh Destroit là một khuyên nếu f(e)={u} với 1 đỉnh u New York nào đó. Chicago – Ví dụ: Giả sử 1 mạng máy tính gồm các máy San Francisco tính và cá c đđờường điện thoại. Denver Washington Los Angeles Giả đồ thị Gv: Huỳnh Thị Thu Thủy 155 Gv: Huỳnh Thị Thu Thủy 156 39 5/10/2013 1- Đại cương về đồ thị (tt) 1- Đại cương về đồ thị (tt) • Định nghĩa 4: Một đồ thị có hướng – Ví dụ: Các đường điện thoại trong 1 mạng máy tính có thể hoạt động chỉ theo 1 chiều. Khi có các G=(V, E) gồmmm mộttt tậppcác các đỉnh V, mộttt tập đường điện thoại 2 chiều được biểu diễn bằng 1 các cạnh E là các cặp có thứ tự của các cặp cạnh có chiều ngược lại. phần tử thuộc V. • Ví dụ: Mạng truyền thông có các đường Destroit New York điện thoại 1 chiều. Chicago San Francisco Denver Washington Đồ thị có hướng Los Angeles Gv: Huỳnh Thị Thu Thủy 157 Gv: Huỳnh Thị Thu Thủy 158 1- Đại cương về đồ thị (tt) 1- Đại cương về đồ thị (tt) • Định nghĩa 5: Một đa đồ thị có hướng – Ví dụ: Đa đồ thị có hướng: Có thể có nhiều G=(V, E) gồmmm mộttt tậppcác các đỉnh V, mộttt tập đường điện thoại 1 chiều từ mỗi địa phương các cạnh E và 1 hàm f từ E tới { {u,v}| u,v tới máy chủ ở New York và có thể có nhiều đường từ máy chủ tới các máy ở xa.  V}. Các cạnh e1, e2 là cạnh bội nếu Destroit New York f(e1)=f(e2). Chicago San Francisco Denver Washington Los Angeles Đa đồ thị có hướng Gv: Huỳnh Thị Thu Thủy 159 Gv: Huỳnh Thị Thu Thủy 160 40 5/10/2013 1- Đại cương về đồ thị (tt) Đường đi – chu trình • Bảng tổng kết các loại đồ thị: • Đường đi – chu trình Euler • Đường đi – chu trình Hamilton LoạiCạnh Có cạnh bội? Có khuyên? Đơn đồ thị Vô hướng Không Không Đa đồ thị Vô hướng Có Không Giả đồ thị Vô hướng Có Có Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng Có Có Gv: Huỳnh Thị Thu Thủy 161 Gv: Huỳnh Thị Thu Thủy 162 Đường đi – chu trình Euler Đường đi – chu trình Euler (tt) – Trong đa đồ thị có hướng, đường đi hay chu • Định nghĩa 1: trình gọi là đơn nếu nó không chứa cùng 1 – Đường đi độ dài n từ u tới v, với n là 1 số cạnh quá 1 lần. nguyên dương, trong 1 đồ thị vô hướng là 1 –Một đồ thị vô hướng được gọi là liên thông dãy các cạnh e , e , , e của đồ thị sao cho nếu có đường đi giữa mọi cặp đỉnh phân biệt 1 2 n của đồ thị. f(e1)={x0,x1}, f(e2)={x1,x2},.., f(en)={xn-1,xn}, với ab – Ví dụ: a b x0=uxu,xn=v. c c – Đường đi gọi là chu trình nếu nó bắt đầu và d f d kết thúc tại cùng 1 đỉnh, tức u=v. g h fg Gv: Huỳnh Thị Thu Thủy 163 Gv: Huỳnh Thị Thu Thủy 164 41 5/10/2013 Đường đi – chu trình Euler (tt) Đường đi – chu trình Euler (tt) • Định lý: Giữa mọi cặp đỉnh phân biệt của • Định nghĩa 3: Đồ thị có hướng gọi là liên 1 đồ thị vôôh hướng liên thông lu ôn c ó thông yếu nếu có đường đi giữa 2 đỉnh đường đi đơn. bất kỳ của đồ thị vô hướng nền. • Định nghĩa 2: Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b • Định nghĩa 4: Chu trình đơn chứa tất cả và từ btb tớiia,v a, vớimi mọi đỉnh a, b của đồ thị. các cạnh của đồ thị G gọi là chu trình Euler. Đường đi Euler trong G là đường đi đơn chứa mọi cạnh của G. Gv: Huỳnh Thị Thu Thủy 165 Gv: Huỳnh Thị Thu Thủy 166 Đường đi – chu trình Euler (tt) Đường đi – chu trình Hamilton • Ví dụ: Tìm chu trình Euler (nếu có) • Định nghĩa: Đường đi x0, x1, .., xn trong đồ thị GG(VE)=(V,E) được gọiilà là đờđường đi Hamilton nếu V={x , x , .., x } và x ≠ x với a b a b a g 0 1 n i j 0ijn. c c • Chu trình x0,x1, .., xn,x0 (n>1) trong đồ thị g d g d b G=(V,E) g ọilài là chu trình Hamilton nếu c d x0,x1, ..,xn là đường đi Hamilton. Gv: Huỳnh Thị Thu Thủy 167 Gv: Huỳnh Thị Thu Thủy 168 42 5/10/2013 Đường đi – chu trình Hamilton(tt) Biểu diễn đồ thị bằng ma trận • Định lý: Giả sử G là 1 đồ thị liên thông • Ma trận liền kề với n đỉnh, trong đó n3. – Giả sử GG(VE)là1=(V,E) là 1 đồ thị đơn, trong đó |V|= n v à các đỉnh v1,v2,..vn – Khi đó, G có chu trình Hamilton nếu bậc –Ma trận liền kề A của G là ma trận không-một cấp nxn của mỗi đỉnh ít nhất bằng n/2. có phần tử hàng i cột j bằng 1 nếu vi và vj liền kề nhau, và bằng 0 nếu chúng không được nối với nhau. – Tức là: A= [aij] với 1 nếu {vi,vj} là 1 cạnh của G •aij={ 0 nếu không có cạnh nối đỉnh vi với đỉnh vj Gv: Huỳnh Thị Thu Thủy 169 Gv: Huỳnh Thị Thu Thủy 170 Biểu diễn đồ thị bằng ma trận(tt) Biểu diễn đồ thị bằng ma trận • Ví dụ: Biểu diễn đồ thị bằng ma trận liền kề • Ma trận liên thuộc abcd – Giả sử G=(V,E) là đồ thị vô hướng. Khi đó, ma trận liên thuộc của V và E là ma trận a0111 ab M=[m ] trong đó: b1010 ij c1100 1 nếu cạnh ej nối với đỉnh vi d d1000 c –mij={ 0 nếu cạnh ej không nối với đỉnh vi Gv: Huỳnh Thị Thu Thủy 171 Gv: Huỳnh Thị Thu Thủy 172 43 5/10/2013 Biểu diễn đồ thị bằng ma trận(tt) Bài toán về đường đi • Ví dụ: Biểu diễn đồ thị bằng ma trận liên thuộc •Thuật toán tìm đường đi ngắn nhất: e1 e2 e3 e4 e5 e6 –Thuật toán Dijkstra - 1959 v 1 10000 1 –Thuật toán Floyd v2 0 01101 v3 0 00011 v1 v 2 e6 v3 v4 1 0 1 0 0 0 e3 e4 e e5 v5 0 10110 1 e2 v4 v5 Gv: Huỳnh Thị Thu Thủy 173 Gv: Huỳnh Thị Thu Thủy 174 Thuật toán Dijkstra Thuật toán Dijkstra (tt) • While z  S • Procedure Dijkstra(G: đơn đồ thị liên Begin thông có trọng số) u:=đỉnh không thuộc S có nhãn L(u) nhỏ nhất For i:=1 to n S:=S  {u} L(v ):=; { G có các đỉnh a=v0,v1,..,vn=z  For tất cả các đỉnh v không thuộc S i và trọng số w(v , v ), với  L(a):=0; i j if L(u)+W(u,v)<L(v) then L(v):=L(u)+W(u,v) w(v ,v )= nếu {v ,v } không là  S:=; i j i j {Thêm vào S đỉnh có nhãn nhỏ nhất và sửa đổi nhãn của các đỉnh 1 cạnh trong G } không thuộc S} End; {Ban đầu các nhãn được khởi tạo sao cho nhãn của a bằng không, các đỉnh khác bằng  , tập S rỗng } {L(z) = độ dài đường đi ngắn nhất từ a đến z} Gv: Huỳnh Thị Thu Thủy 175 Gv: Huỳnh Thị Thu Thủy 176 44 5/10/2013 Thuật toán Floyd Bài tập • Procedure Floyd (G: đơn đồ thị có trọng số) 1. Tìm đường đi ngắn nhất từ S đến t Fori:=1tonFor i:=1 to n For j:=1 to n Sx x t { D(vi,vj) là độ dài  1 2 d(vi,vj):=w(vi,vj) đường đi ngắnnhất  S0 7 2 9 For i:=1 to n giữa v và v } For j:=1 to n i j  For k:=1 to n x1 011 if d(vj,vi)+ d(vi,vk)< d(vj,vk) then x2 03 d(vj,vk):=d(vj,vi)+ d(vi,vk) t0 Gv: Huỳnh Thị Thu Thủy 177 Gv: Huỳnh Thị Thu Thủy 178 Bài tập 1. Tìm đường đi ngắn nhất từ S đến t Bài tập Sx1 x2 t 2. Tìm đường đi ngắn nhất từ A đến E l 072 9  SSS A BCDE l 3 25 A0 1 4 202  x2 Sx2 l 324 B01533  x2 Sx1 C 0 1 3 Đường đi ngắn nhất từ S đến t là: S x2  x1 t D02 Độ dài đường đi là: 4 E0 Gv: Huỳnh Thị Thu Thủy 179 Gv: Huỳnh Thị Thu Thủy 180 45 5/10/2013 Bài tập TỔNG KẾT CHƯƠNG 5 3. Tìm đường đi ngắn nhất từ A đến G; Từ G đến C ABCDEFG 1. Đại cương về đồ thị A 0 38 27 47 2 25 32 2. Đường đi – chu trình B300 0 21214333 3. Biểu diễn đồ thị bằng ma trận C3210 3623624 4. Bài toán về đường đi D173 370 361026 E291035110 3130 F 4 38 34 3 42 0 9 G432723134990 Gv: Huỳnh Thị Thu Thủy 181 Gv: Huỳnh Thị Thu Thủy 182 46