intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Toán rời rạc ngành công nghệ thông tin

Chia sẻ: Nguyen Lan | Ngày: | Loại File: PDF | Số trang:222

Thêm vào BST
Báo xấu
824
lượt xem 196
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với sự nổ lực hết mình của bản thân, chúng tôi thiết nghĩ đây sẽ là tài liệu tham khảo tốt cho các giáo viên giảng dạy học phần toán rời rạc, các học viên cao học ngành Phương pháp giảng dạy Toán, các thí sinh thi vào cao học ngành công nghệ thông tin, …

Chủ đề:

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

Lưu

Nội dung Text: Toán rời rạc ngành công nghệ thông tin

  1. www.VIETMATHS.com www.VIETMATHS.com B GIÁO D C VÀ ðÀO T O TRƯ NG ð I H C NÔNG NGHI P HÀ N I m VŨ KIM THÀNH o .c s h TOÁN R I R C t a (Giáo trình dành cho sinh viên ngành công ngh thông tin) m t ie .v w w w Hà n i 2008 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..0
  2. www.VIETMATHS.com www.VIETMATHS.com M CL C 5 L i nói ñ u m Chng 1. THU T TOÁN 7 1. ð nh nghĩa 7 o 2. Mô t thu t toán b ng lưu ñ 8 3. Mô t thu t toán b ng ngôn ng ph ng Pascal 9 .c 4. ð ph c t p c a thu t toán 14 5. Thu t toán tìm ki m 18 6. Thu t toán ñ quy 19 7. M t s thu t toán v s nguyên 23 s BÀI T P CHƯƠNG 1 28 h Chng 2. BÀI TOÁN ð M 32 1. Nguyên lý c ng và nguyên lý nhân 32 t 2. Ch nh h p. Hoán v . T h p. 35 3. Nguyên lý bù tr 42 a 4. Gi i các h th c truy h i 44 5. Bài toán li t kê. 51 m 6. Bài toán t n t i 61 BÀI T P CHƯƠNG 2 64 t Chng 3. CÁC KHÁI NI M CƠ B N V ð TH 69 1. Các ñ nh nghĩa v ñ th và bi u di n hình h c c a ñ th 69 ie 2. Bi u di n ñ th b ng ñ i s 79 3. S ñ ng c u c a các ñ th 82 4. Tính liên thông trong ñ th 84 .v 5. S n ñ nh trong, s n ñ nh ngoài và nhân c a ñ th 88 6. S c s c a ñ th 91 BÀI T P CHƯƠNG 3 93 w Chng 4. ð TH EULER, ð TH HAMILTON, ð TH PH NG 98 1. ð th Euler 98 2. ð th Hamilton 103 w 3. ð thi ph ng 108 BÀI T P CHƯƠNG 4 113 w Chng 5. CÂY VÀ M T S NG D NG C A CÂY 117 1. Cây và các tính ch t cơ b n c a cây 118 2. Cây nh phân và phép duy t cây 122 3. M t vài ng d ng c a cây 126 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..1
  3. www.VIETMATHS.com www.VIETMATHS.com 4. Cây khung (cây bao trùm) c a ñ th 131 5. H chu trình ñ c l p 134 6. Cây khung nh nh t 136 BÀI T P CHƯƠNG 5 142 m Chng 6. M T S BÀI TOÁN T I ƯU TRÊN ð TH 147 1. Bài toán ñư ng ñi ng n nh t trong ñ th 147 2. Tâm, Bán kính, ðư ng kính c a ñ th 152 o 3. M ng và Lu ng 153 4. Bài toán du l ch 160 BÀI T P CHƯƠNG 6 166 .c Chng 7. ð I S BOOLE 172 1. Hàm Boole 172 s 2. Bi u th c Boole 174 3. ð nh nghĩa ñ i s Boole theo tiên ñ 176 h 4. Bi u di n các hàm Boole 177 5. Các c ng logic 183 t 6 T i thi u hoá hàm Boole 185 BÀI T P CHƯƠNG 7 193 a ð I CƯƠNG V TOÁN LOGIC 197 Ph chng. 1. Lôgic m nh ñ 197 m 2. Công th c ñ ng nh t ñúng và công th c ñ ng nh t b ng nhau trong lôgic m nh ñ 201 3. ði u ki n ñ ng nh t ñúng trong lôgic m nh ñ 205 t 4. Lôgic v t 208 BÀI T P PH CHƯƠNG 213 ie M t s bài t p làm trên máy tính 216 M t s thu t ng dùng trong giáo trình 218 .v Tài li u tham kh o 221 w w w Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..2
  4. www.VIETMATHS.com www.VIETMATHS.com L I NÓI ð U Toán R i r c (Discrete mathematics) là môn toán h c nghiên c u các ñ i tư ng r i r c. Nó ñư c ng d ng trong nhi u ngành khoa h c khác nhau, ñ c bi t là trong tin h c b i quá trình x lý thông tin trên máy tính th c ch t là m t quá trình r i r c. m Ph m vi nghiên c u c a Toán R i r c r t r ng, có th chia thành các môn h c khác nhau. Theo quy ñ nh c a chương trình môn h c, giáo trình này ñ c p ñ n các lĩnh v c: Thu t toán và bài toán ñ m; Lý thuy t ñ th ; ð i s Logic và ñư c chia thành 8 o chương: - Chương 1 ñ c p ñ n m t trong các v n ñ cơ b n nh t c a Thu t toán ñó là ñ .c ph c t p v th i gian c a thu t toán. - Chương 2 nói v các nguyên lý cơ b n c a Bài toán ñ m. - Các chương 3, 4, 5 và 6 trình bày v Lý thuy t ñ th và các ng d ng. ðây là ph n s chi m t tr ng nhi u nh t c a giáo trình. Trong ñó có các chương v các khái ni m cơ b n c a ñ th , các ñ th ñ c bi t như ñ th Euler, ñ th Hamilton, ñ th ph ng, Cây h cùng các ng d ng c a các ñ thi ñ c bi t này. Riêng chương 6 dành cho m t v n ñ tr ng là m t s bài toán t i ưu trên ñ th ho c bài toán t i ưu ñư c gi i b ng cách ng t d ng lý thuy t ñ th . - Chương 7 là các ki n th c cơ b n v ð i s Boole, m t công c h u hi u trong a vi c thi t k các m ch ñi n, ñi n t . Cu i giáo trình là ph chương: Nh ng khái ni m cơ b n v toán Logic ñ ngư i m h c có th t nghiên c u thêm v Toán Logic. Trong m i chương chúng tôi c g ng trình bày các ki n th c cơ b n nh t c a chương ñó cùng các thí d minh h a c th . Vì khuôn kh s ti t h c nên chúng tôi t lư c b m t s ch ng minh ph c t p. Cu i m i chương ñ u có các bài t p ñ ngư i h c ie ng d ng, ki m ch ng các lý thuy t ñã h c, ñ ng th i cũng cung c p m t s ñáp s c a các bài t p ñã cho. Cũng c n nói thêm r ng toán R i r c không ch ñư c ng d ng trong tin h c mà .v còn ñư c ng d ng trong nhi u ngành khoa h c khác. B i v y giáo trình cũng có ích cho nh ng ai c n quan tâm ñ n các ng d ng khác c a môn h c này. Tác gi xin chân thành c m ơn các b n ñ ng nghi p ñã ñ ng viên và góp ý cho w vi c biên so n giáo trình này. ð c bi t chúng tôi xin c m ơn Nhà giáo ưu tú Nguy n ðình Hi n ñã hi u ñính và cho nhi u ý ki n ñóng góp b ích và thi t th c. w Vì trình ñ có h n và giáo trình ñư c biên so n l n ñ u nên không tránh kh i các thi u sót. Tác gi r t mong nh n ñư c các ý ki n ñóng góp c a các ñ ng nghi p và b n ñ c v các khi m khuy t c a cu n sách. w TÁC GI Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..3
  5. www.VIETMATHS.com www.VIETMATHS.com CHƯƠNG1. THU T TOÁN m 1. ð nh nghĩa. 2. Mô t thu t toán b ng lưu ñ . 3. Mô t thu t toán b ng ngôn ng ph ng Pascal. o 3.1. Câu l nh Procedure (th t c) ho c Function (hàm). 3.2. Câu l nh gán. .c 3.3. Kh i câu l nh tu n t . 3.4. Câu l nh di u ki n. 3.5. Các câu l nh l p. s 4. ð ph c t p c a thu t toán. h 4.1. Khái ni m ñ tăng c a hàm. 4.2. ð tăng c a t h p các hàm. t 4.3. ð ph c t p c a thu t toán. 5. Thu t toán tìm ki m a 5.1. Thu t toán tìm ki m tuy n tính (còn g i là thu t toán tìm ki m tu n t ). 5.2. Thu t toán tìm ki m nh phân. 6. Thu t toán ñ quy. m 6.1. Công th c truy h i. 6.2. Thu t toán ñ quy. t 6.3. ð quy và l p 7. M t s thu t toán v s nguyên. ie 7.1. Bi u di n các s nguyên. 7.2. C ng và nhân trong h nh phân. .v 1. ð nh nghĩa Thu t toán (algorithm) là m t dãy các quy t c nh m xác ñ nh m t dãy các thao tác trên các ñ i tư ng sao cho sau m t s h u h n bư c th c hi n s ñ t ñư c m c tiêu w ñ t ra. T ñ nh nghĩa c a thu t toán cho th y các ñ c trưng (tính ch t) cơ b n c a thu t toán w là: a. Y u t vào, ra: • ð u vào (Input): M i thu t toán có m t giá tr ho c m t b giá tr ñ u vào w t m t t p xác ñ nh ñã ñư c ch rõ. • ð u ra (Output): T các giá tr ñ u vào, thu t toán cho ra các giá tr c n tìm g i là k t qu c a bài toán. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..4
  6. www.VIETMATHS.com www.VIETMATHS.com b. Tính d ng: Sau m t s h u h n bư c thao tác thu t toán ph i k t thúc và cho k t qu . c. Tính xác ñ nh: Các thao tác ph i rõ ràng, cho cùng m t k t qu dù ñư c x lý trên các b x lý khác nhau (hai b x lý trong cùng m t ñi u ki n không th cho hai k t qu khác nhau). m d. Tính hi u qu Sau khi ñưa d li u vào cho thu t toán ho t ñ ng ph i ñưa ra k t qu như ý mu n. o e. Tính t ng quát Thu t toán ph i ñư c áp d ng cho m i bài toán cùng d ng ch không ph i ch cho m t t p ñ c bi t các giá tr ñ u vào. .c Có nhi u cách mô t thu t toán như: Dùng ngôn ng t nhiên; dùng lưu ñ (sơ ñ kh i); dùng m t ngôn ng l p trình nào ñó (trong giáo trình này dùng lo i ngôn ng mô t s g n như ngôn ng l p trình Pascal và g i là ph ng Pascal); … h 2. Mô t thu t toán b ng lưu ñ Sau khi có thu t toán ñ gi i bài toán, trư c khi chuy n sang ngôn ng l p trình, ngư i t ta thư ng ph i th hi n thu t toán dư i d ng sơ ñ . Sơ ñ ñó g i là lưu ñ c a thu t toán. Các ký hi u quy ư c dùng trong lưu ñ ñư c trình bày trong b ng 1. a B ng 1. Các ký hi u quy ư c dung trong lưu ñ thu t toán Tên ký hi u Ký hi u Vai trò c a ký hi u m Kh i m ñ u Dùng ñ m ñ u ho c k t thúc ho c k t thúc thu t toán Kh i vào ra ðưa d li u vào và in k t qu t Kh i tính toán Bi u di n các công th c tính toán ie và thay ñ i giá tr các ñ i tư ng Kh i ñi u ki n Ki m tra các ñi u ki n phân nhánh .v Chương trình con G i các chương trình con w Hư ng ñi c a Hư ng chuy n thông tin, liên h thu t toán gi a các kh i Thí d : Thu t toán gi i phương trình b c hai ax2 + bx + c = 0 g m các bư c sau: w 1) Xác ñ nh các h s a, b, c (thông tin ñ u vào) 2) Ki m tra h s a: w c - N u a = 0: Phương trình ñã cho là phương trình b c nh t, nghi m là: x = − . b - N u a ≠ 0: Chuy n sang bư c 3. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..5
  7. www.VIETMATHS.com www.VIETMATHS.com ∆ = b2 – 4ac. 3) Tính bi t th c 4) Ki m tra d u c a bi t th c ∆ - N u ∆ ≥ 0: Phương trình có nghi m th c - N u ∆ < 0: Phương trình có nghi m ph c 5) In k t qu m Lưu ñ c a thu t toán ñư c trình bày trong hình 1 B tñ u o Nh p a, b, c .c Sai a=0 ðúng s c ∆ = b2 = 4ac x=− h b Sai ∆≥0 ðúng t a b −b+ ∆ Ph n th c = − x1 = 2a 2a m −∆ −b+ ∆ Ph n o = x2 = 2a 2a t ie Thông báo k t qu K t thúc .v Hình 1. Lưu ñ gi i phương trình b c hai 3. Mô t thu t toán b ng ngôn ng ph ng Pascal w ð gi i bài toán trên máy tính ñi n t ph i vi t chương trình theo m t ngôn ng l p trình nào ñó (Pascal, C, Basic, ...). M i ngôn ng l p trình có m t quy t c c u trúc riêng. ð thay vi c mô t thu t toán b ng l i, có th mô t thu t toán b ng các c u trúc l nh w tương t như ngôn ng l p trình Pascal và g i là ngôn ng ph ng Pascal. Các câu l nh chính dùng ñ mô t thu t toán g m có: Procedure ho c Function; câu l nh gán; các câu l nh ñi u ki n; các vòng l p. Ngoài ra khi c n gi i thích các câu l nh w b ng l i, có th ñ các l i gi i thích trong d u (* ... *) ho c {…}. Nghĩa là ngôn ng ph ng Pascal hoàn toàn tương t ngôn ng l p trình Pascal, nhưng không có ph n khai báo. Tuy nhiên, ph i nêu rõ ñ u vào (Input) và ñ u ra (output) c a thu t toán. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..6
  8. www.VIETMATHS.com www.VIETMATHS.com 3.1. Câu l nh Procedure (th t c) ho c Function (hàm) ð ng ngay sau câu l nh này là tên c a th t c hoăc tên hàm. Các bư c th c hi n c a thu t toán ñư c mô t trong th t c (hàm) ñư c b t ñ u b i t khóa begin và k t thúc b i t khóa end. m Thí d 1 Function Max(a, b, c) (* Hàm tìm s l n nh t trong 3 s a, b, c *) Begin o (* thân hàm*) End; .c Thí d 2 Procedure Giai_phuong_trình_bac_hai (* Th t c gi i phương trình b c hai *) Begin s (* thân th t c *) End; h Chú ý r ng, khi mô t thu t toán b ng function, trư c khi k t thúc (end) thu t toán ph i tr v (ghi nh n) giá tr c a function ñó. t 3.2. Câu l nh gán a Dùng ñ gán giá tr cho các bi n. Cách vi t: Tên bi n := giá tr gán m Thí d : x := a; (*bi n x ñư c gán giá tr a*) max := b; (*bi n max ñư c gán giá tr b*) t 3.3. Kh i câu l nh tu n t ðư c m ñ u b ng t khóa begin và k t thúc b ng end như sau: ie begin Câu l nh 1; Câu l nh 2; .v ... ..... Câu l nh n; end; w Các l nh ñư c th c hi n tu n t t câu l nh th nh t ñ n câu l nh cu i cùng. 3.4. Câu l nh ñi u ki n w Có hai d ng: d ng ñơn gi n và d ng l a ch n. a. D ng ñơn gi n: Cách vi t: if then câu l nh ho c kh i câu l nh; w Khi th c hi n, ñi u ki n ñư c ki m tra, n u ñi u ki n th a mãn thì câu l nh (kh i câu l nh) ñư c th c hi n, n u ñi u ki n không th a mãn thì l nh b b qua. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..7
  9. www.VIETMATHS.com www.VIETMATHS.com b. D ng l a ch n: Cách vi t: if then câu l nh ho c kh i câu l nh 1 else câu l nh ho c kh i câu l nh 2; Khi th c hi n, ñi u ki n ñư c ki m tra, n u ñi u ki n th a mãn thì câu l nh (kh i câu l nh) 1 ñư c th c hi n, n u ñi u ki n không ñư c th a mãn thì câu l nh (kh i câu l nh) 2 ñư c th c hi n. m Thí d 1. Thu t toán tìm s l n nh t trong 3 s th c a, b, c. - ð u tiên cho max = a; o - So sánh max v i b, n u b > max thì max = b; - So sánh max v i c, n u c > max thì max = c. Function max(a,b,c) .c Input: 3 s th c a,b,c; Output: S l n nh t trong 3 s ñã nh p; s Begin x := a; h if b > x then x:= b; if c > x then x:= c; t max := x; End; a Thí d 2. Thu t toán gi i phương trình b c hai ax2 + bx + c = 0 Procedure Giai_phuong_trinh_bac2; m Input: Các h s a, b, c; Output: Nghi m c a phương trình; begin t if a = 0 then x := -c/b; if a ≠ 0 then ie begin ∆ := b2 – 4ac; .v if ∆ ≥ 0 then begin x1 = (– b – ∆ )/2a ; w x2 = (– b + ∆ )/2a; end else w begin Ph n th c := -b/2a; w Ph n o := ( − ∆ )/2a; end; end; end; Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..8
  10. www.VIETMATHS.com www.VIETMATHS.com 3.5. Các câu l nh l p Có hai lo i: Lo i có bư c l p xác ñ nh và lo i có bư c l p không xác ñ nh. a. Lo i có bư c l p xác ñ nh: Cách vi t như sau: for bi n ñi u khi n := giá tr ñ u to giá tr cu i do câu l nh ho c kh i câu l nh; m Khi th c hi n, bi n ñi u khi n ñư c ki m tra, n u bi n ñi u khi n nh hơn ho c b ng giá tr cu i thì câu l nh (kh i câu l nh) ñư c th c hi n. Ti p ñó bi n ñi u khi n s tăng thêm 1 ñơn v và quá trình ñư c l p l i cho ñ n khi bi n ñi u khi n l n hơn giá tr cu i thì o vòng l p d ng và cho k t qu . Như v y h t vòng l p for s bư c l p là giá tr cu i (c a bi n ñi u khi n) tr giá tr ñ u c ng m t. .c Thí d : Tìm giá tr l n nh t c a dãy s a1, a2, …,an. Thu t toán: ð u tiên cho giá tr l n nh t (max) b ng a1, sau ñó l n lư t so sánh max v i các s ai (i = 2, 3, …, n), n u max < ai thì max b ng ai, n u max > ai thì max không ñ i. s Function max_day_so; h Input: Dãy s a1, a2, … ,an; Output: Giá tr l n nh t (max) c a dãy s ñã nh p; begin t max := a1 ; a for i:= 2 to n do if ai > max then max := ai ; max_day_so := max; m end; Chú thích: Vòng l p for còn cách vi t lùi bi n ñi u khi n như sau: t for bi n ñi u khi n := giá tr cu i downto giá tr ñ u do câu l nh ho c kh i câu l nh; Vi c th c hi n câu l nh này tương t như khi vi t bi n ñi u khi n tăng d n. ie b. Lo i có bư c l p không xác ñ nh: Có hai cách vi t Cách th nh t: while ñi u ki n do câu l nh ho c kh i câu l nh; .v Khi th c hi n, ñi u ki n ñư c ki m tra, n u ñi u ki n ñư c tho mãn thì câu l nh (kh i câu l nh) ñư c th c hi n. N u ñi u ki n không tho mãn thì vòng l p d ng và cho k t qu . w Thí d : Ki m tra xem s nguyên dương m ñã cho có ph i là s nguyên t không? Thu t toán như sau: S m là s nguyên t n u nó không chia h t cho b t c s nguyên w dương khác 1 nào nh hơn ho c b ng m . Th t v y, n u m là m t h p s (không ph i là s nguyên t ), nghĩa là t n t i các s nguyên dương a, b sao cho: w m = a.b ⇒ a≤ m ho c b ≤ m V y, n u m là s nguyên t thì m không chia h t cho m i s nguyên dương i, 2≤ i≤ m Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..9
  11. www.VIETMATHS.com www.VIETMATHS.com Procedure nguyento(m); Input: S nguyên dương m; Output: True, n u m là s nguyên t ; False, n u m không ph i là s nguyên t ; begin i := 2; m while i ≤ m do begin if m mod i = 0 then nguyento := false o else nguyento := true; i := i+1; .c end; end; s Cách th hai: repeat câu l nh ho c kh i câu l nh until ñi u ki n; Khi th c hi n, câu l nh (kh i câu l nh) ñư c th c hi n, sau ñó ñi u ki n ñư c ki m h tra, n u ñi u ki n sai thì vòng l p ñư c th c hi n, n u ñi u ki n ñúng thì vòng l p d ng và cho k t qu . t Thí d : Thu t toán Ơ-clit tìm ư c s chung l n nh t c a hai s nguyên dương a, b a như sau: Gi s a > b và a chia cho b ñư c thương là q và s dư là r, trong ñó a, b, q, r là các s nguyên dương: m a = bq + r suy ra: ƯCLN(a, b) = ƯCLN(b, r) và s dư cu i cùng khác không là ư c s chung l n nh t c a a và b. t Th t v y: Gi s d là ư c s chung c a hai s nguyên dương a và b, khi ñó: r = a – ie bq chia h t cho d. V y d là ư c chung c a b và r. Ngư c l i, n u d là ư c s chung c a b và r, khi ñó do bq + r = a cũng chia h t cho d. V y d là ư c s chung c a a và b. .v Ch ng h n, mu n tìm ư c s chung l n nh t c a 111 và 201 ta làm như sau: 201 = 1. 111 + 90 111 = 1. 90 + 21 w 90 = 4. 21 + 6 21 = 3. 6 + 3 6 = 2. 3 w V y ƯCLN(111, 201) = 3 (3 là s dư cu i cùng khác 0). Function UCLN(a, b) w Input: a, b là 2 s nguyên dương; Output: UCLN(a, b); begin Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..10
  12. www.VIETMATHS.com www.VIETMATHS.com x := a; y : = b; repeat begin r := x mod y; (* r là ph n dư khi chia x cho y *) m x : = y; y := r ; if y ≠ 0 then uc := y; end; o until y = 0; UCLN := uc; .c end ; Chú ý: Khi gi i các bài toán ph c t p thì thư ng ph i phân chia bài toán ñó thành s các bài toán nh hơn g i là các bài toán con. Khi ñó ph i xây d ng các th t c ho c hàm ñ gi i các bài toán con ñó, sau ñó t p h p các bài toán con này ñ gi i bài toán ban ñ u ñã h ñ t ra. Thu t ng tin h c g i các chương trình gi i bài toán con ñó là các chương trình con. Thí d : Tìm s nguyên t nh nh t l n hơn s nguyên dương m ñã cho. t Procedure So_nguyen_to_lon_hon(m); Input: S nguyên dương m; a Output: n là s nguyên t nh nh t l n hơn m; begin m n := m + 1; while nguyento(n) = false do n := n + 1; end; t 4. ð ph c t p c a thu t toán ie Có hai lý do làm cho m t thu t toán ñúng có th không th c hi n ñư c trên máy tính. ðó là do máy tính không ñ b nh ñ th c hi n ho c th i gian tính toán quá dài. Tương ng v i hai lý do trên ngư i ta ñưa ra hai khái ni m: .v - ð ph c t p không gian c a thu t toán, ñ ph c t p này g n li n v i các c u trúc d li u ñư c s d ng. V n ñ này không thu c ph m vi c a môn h c này. - ð ph c t p th i gian c a thu t toán, ñ ph c t p này ñư c th hi n qua s lư ng w các câu l nh v các phép gán, các phép tính s h c, phép so sánh, … ñư c s d ng trong thu t toán khi các giá tr ñ u vào có kích thư c ñã cho. w 4.1. Khái ni m ñ tăng c a hàm Trư c h t xét thí d : Gi s th i gian tính toán c a m t thu t toán ph thu c vào kích thư c n c a ñ u vào theo công th c: w t(n) = 60n2 + 9n + 9 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..11
  13. www.VIETMATHS.com www.VIETMATHS.com B ng sau cho th y khi n l n, t(n) x p x s h ng 60n2 : t(n) = 60n2 + 9n + 9 60n2 n 10 9099 6000 100 600 909 600 000 1 000 60 009 009 60 000 000 m 10 000 6 000 090 009 6 000 000 000 ð nh nghĩa: Cho f(x) và g(x) là hai hàm t t p s nguyên ho c t p s th c vào t p o các s th c. Ngư i ta nói f(x) là O(g(x)) hay f(x) có quan h big-O v i g(x), ký hi u f(x) = O(g(x)), n u t n t i hai h ng s C và k sao cho: .c | f(x) | ≤ C. | g(x) |, ∀x ≥ k. Thí d 1. t(n) = 60n2 + 9n + 9 = O(n2) Th t v y: ∀n ≥ 1, ta có: | 60n2 + 9n +9| = 60n2 + 9n +9 s  9 9 = n 2  60 + + 2  h  n n ≤ n (60 + 9 + 9) = 78n2. 2 t V y C = 78; k = 1. Tương t ta có th ch ng minh: a Pn(x) = a0xn + a1xn-1 + ... + an = O(xn) , x ∈ R. Thí d 2. f(n) = 1 + 2 + 3 + ... + n < n + n + n + ... + n = n.n = n2. V y f(n) = O(n2). m Thí d 3. Ta có: n! < nn , suy ra: n! = O(nn); (C = k = 1) Thí d 4. ∀n: n! < nn , lg(n!) < n lgn , t suy ra lg(n!) = O(nlgn); (C = k = 1) Thí d 5. Ta có: lgn < n , suy ra lgn = O(n) ; (C = k = 1) ie Có th hi u ñơn gi n quan h f(x) = O(g(x)) là f(x) và g(x) là "cùng c p", tuy nhiên g(x) là hàm ñơn gi n nh t có th ñ i di n cho f(x) v ñ l n cũng như t c ñ bi n thiên. .v 4.2. ð tăng c a t h p các hàm ð nh lý: N u f1(x) = O(g1(x)) và f2(x) = O(g2(x)) Thì: 1) (f1 + f2)(x) = O(max{g1(x), g2(x)}). w 2) (f1.f2)(x) = O(g1(x).g2(x)) Ch ng minh: Theo gi thi t, ta có: | f1(x)| ≤ C1 | g1(x)) | , ∀x > k1 w | f2(x)| ≤ C2 | g2(x)) | , ∀x > k2 Ch n k = max(k1; k2) thì c hai b t ñ ng th c ñ u tho mãn. Do ñó: 1) |(f1 + f2)(x)| = |f1(x) + f2(x)| ≤ |f1(x)| + |f2(x)| ≤ w ≤ C1|g1(x)| + C2|g2(x)| ≤ (C1 + C2)g(x) ñây g(x) = max{|g1(x)|, |g2(x)|}. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..12
  14. www.VIETMATHS.com www.VIETMATHS.com 2) |(f1.f2)(x)| = |f1(x)|.|f2(x)| ≤ C1C2 |g1(x)|.|g2(x)| = C1C2|g1(x)g2(x)| H qu : N u f1(x) = O(g(x)), f2(x) = O(g(x)) thì (f1+f2)(x) = O(g(x)) Thí d . Cho ñánh giá O c a các hàm: 1/ f(n) = 2nlg(n!) + (n3 + 3)lgn , n ∈ N. 2/ f(x) = (x + 1)lg(x2 + 1) + 3x2 , x ∈ R. m Gi i: 1) Ta có: lg(n!) = O(nlgn) ⇒ 2nlg(n!) = O(n2lgn) (n3 + 3)lgn = O(n3lgn) V y f(n) = O(n3lgn) o 2) Ta có: lg(x2 + 1) ≤ lg2x2 = lg2 + 2lgx ≤ 3lgx , ∀x > 1 ⇒ lg(x2 + 1) = O(lgx) ⇒ (x + 1)lg(x2 + 1) = O(xlgx) .c M t khác: 3x2 = O(x2) và max{xlgx; x2} = x2. V y f(x) = O(x2). s 4.3. ð ph c t p c a thu t toán Như ñã nói ph n ñ u c a m c 4, chúng ta ch ñ c p ñ n ñ ph c t p v th i gian h c a thu t toán. ð ph c t p v th i gian c a thu t toán ñư c ñánh giá qua s lư ng các phép toán mà thu t toán s d ng. Vì v y ph i ñ m các phép toán có trong thu t toán. Các phép toán ph i ñ m là: t - Các phép so sánh các s nguyên ho c s th c; - Các phép tính s h c: c ng, tr , nhân, chia; a - Các phép gán; - Và b t kỳ m t phép tính sơ c p nào khác xu t hi n trong quá trình tính toán. m Gi s s các phép toán c a thu t toán là f(n), trong ñó n là kích thư c ñ u vào, khi ñó ngư i ta thư ng quy ñ ph c t p v th i gian c a thu t toán v các m c: • ð ph c t p O(1), g i là ñ ph c t p h ng s , n u f(n) = O(1). t • ð ph c t p O(logan), g i là ñ ph c t p logarit, n u f(n) = O(logan). (ði u ki n a > 1) ie • ð ph c t p O(n), g i là ñ ph c t p tuy n tính, n u f(n) = O(n). • ð ph c t p O(nlogan), g i là ñ ph c t p nlogarit n u f(n) = O(logan). (ði u ki n a > 1) .v • ð ph c t p O(nk), g i là ñ ph c t p ña th c, n u f(n) = O(nk). • ð ph c t p O(an), g i là ñ ph c t p mũ, n u f(n) = O(an). (ði u ki n a > 1) • ð ph c t p O(n!), g i là ñ ph c t p giai th a, n u f(n) = O(n!). w Thí d 1. Tìm ñ ph c t p c a thu t toán ñ gi i bài toán: Tìm s l n nh t trong dãy n s nguyên a1, a2, …, an ñã cho: Procedure max(a1, a2, …, an); w Input: Dãy s a1, a2, ... , an; Output: S l n nh t (max) c a dãy s ñã cho; begin w max := a1; for i := 2 to n do Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..13
  15. www.VIETMATHS.com www.VIETMATHS.com if ai > max then max := ai; end; M i bư c c a vòng l p for ph i th c hi n nhi u nh t 3 phép toán: phép gán bi n ñi u khi n i, phép so sánh ai v i max và có th là phép gán ai vào max; vòng l p có (n – 1) bư c (i = 2, 3, …, n) do ñó nhi u nh t có c th y 3(n - 1) phép toán ph i th c hi n. Ngoài m ra thu t toán còn ph i th c hi n phép gán ñ u tiên max := a1. V y s phép toán nhi u nh t mà thu t toán ph i th c hi n là: 3(n – 1) + 1 = 3n – 2 = O(n) o ð ph c t p v th i gian c a thu t toán là ñ ph c t p tuy n tính. Thí d 2. ð ph c t p c a thu t toán nhân ma tr n. .c Procedure nhân_matran; Input: 2 ma tr n A = (aij)m x p và B = (bij)p x n; Output: ma tr n tích AB = (cij)m x n ; s Begin for i:=1 to m do h for j:=1 to n do begin t cij := 0; for k:=1 to p do a cij := cij + aikbkj ; end; End. m S phép c ng và s phép nhân trong thu t toán trên là: V i m i ph n t cij ph i th c hi n p phép nhân và p phép c ng. Có t t c m.n ph n t cij, v y ph i th c hi n 2mnp phép t c ng và phép nhân. ð xác ñ nh ñ ph c t p c a thu t toán, ta gi s A, B là hai ma tr n vuông c p n, ie nghĩa là m = n = p. như v y ph i c n 2n3 phép c ng và phép nhân. V y ñ ph c t p c a thu t toán là O(n3) – ñ ph c t p ña th c. M t ñi u thú v là, khi nhân t 3 ma tr n tr lên thì s phép tính c ng và nhân ph .v thu c vào th t nhân các ma tr n y. Ch ng h n A, B, C là các ma tr n có kích thư c tương ng là 30×20, 20×40, 40×10. Khi ñó: N u th c hi n theo th t ABC =A(BC) thì tích BC là ma tr n kích thư c 20×10 và c n th c hi n 20.40.10 = 8000 phép tính c ng và nhân. Ma tr n A(BC) có kích thư c w 30×10 và c n th c hi n 30.20.10 = 6000 phép c ng và nhân. T ñó suy ra c n th c hi n 8000+6000 = 14000 phép tính c ng và nhân ñ hoàn thành tích ABC. Tương t , n u th c hi n theo th t ABC = (AB)C thì c n th c hi n 30.20.40 phép w tính c ng và nhân ñ th c hi n tích AB và 30.40.10 phép c ng và nhân ñ th c hiên tích (AB)C. Do ñó s các phép tính c ng và nhân ph i th c hi n ñ hoàn thành tích ABC là 24000+12000 = 36000 phép tính. w Rõ ràng hai cách nhân cho k t qu v s lư ng các phép tính ph i th c hi n là khác nhau. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..14
  16. www.VIETMATHS.com www.VIETMATHS.com 5. Thu t toán tìm ki m Bài toán tìm ki m ñư c phát bi u như sau: Tìm trong dãy s a1, a2, …, an m t ph n t có giá tr b ng s a cho trư c và ghi l i v trí c a ph n t tìm ñư c. Bài toán này có nhi u ng d ng trong th c t . Ch ng h n vi c tìm ki m t trong t ñi n, vi c ki m tra l i chính t c a m t ño n văn b n, … m Có hai thu t toán cơ b n ñ gi i bài toán này: Thu t toán tìm ki m tuy n tính và thu t toán tìm ki m nh phân. Chúng ta l n lư t xét các thu t toán này. o 5.1. Thu t toán tìm ki m tuy n tính (còn g i là thu t toán tìm ki m tu n t ). ðem so sánh a l n lư t v i ai (i = 1, 2, …, n) n u g p m t giá tr ai = a thì ghi l i v trí .c c a ai, n u không g p giá tr ai = a nào (ai ≠ a. ∀i) thì trong dãy không có s nào b ng a. Procedure Tim_tuyen_tinh_phan_tu_bang_a; s Input: a và dãy s a1, a2, ... , an; Output: V trí ph n t c a dãy có giá tr b ng a, ho c là s 0 n u không tìm h th y a trong dãy; begin t i := 1; while (i ≤ n and ai ≠ a) do i := i + 1; a if i ≤ n then vitri := i else vitri := 0; end; m Như v y n u a ñư c tìm th y v trí th i c a dãy (ai = a) thì câu l nh i := i + 1 trong vòng l p while ñư c th c hi n i l n (i = 1, 2, …, n). N u a không ñư c tìm th y, câu l nh ph i th c hi n n l n. V y s phép toán trung bình mà thu t toán ph i th c hi n là: t 1 + 2 + . . . + n n(n + 1) n + 1 = = = O(n) ie n 2n 2 V y, ñ ph c t p c a thu t toán tìm ki m tuy n tính là ñ ph c t p tuy n tính. 5.2. Thu t toán tìm ki m nh phân. .v Gi thi t r ng các ph n t c a dãy ñư c x p theo th t tăng d n. Khi ñó so sánh a 1 + n  v is gi a dãy, n u a < am v i m =  (c n nh c l i r ng ph n nguyên c a x: [x] là 2 w  s nguyên nh nh t có trong x) thì tìm a trong dãy a1, …,am , n u a > am thì tìm a trong dãy am+1, …, an. ð i v i m i dãy con (m t n a c a dãy ñã cho) ñư c làm tương t ñ ch ph i w tìm ph n t có giá tr b ng a m t n a dãy con ñó. Quá trình tìm ki m k t thúc khi tìm th y v trí c a ph n t có giá tr b ng a ho c khi dãy con ch còn 1 ph n t . Ch ng h n vi c tìm s 8 trong dãy s 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22 w ñư c ti n hành như sau: Dãy ñã cho g m 14 s h ng, chia dãy thành 2 dãy con: 5, 6, 8, 9, 11, 12, 13 và 15, 16, 17, 18, 19, 20, 22 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..15
  17. www.VIETMATHS.com www.VIETMATHS.com Vì 8 < 13 nên ti p theo ch c n tìm dãy ñ u tiên. Ti p t c chia ñôi thành 2 dãy: 5, 6, 8, 9 và 11, 12, 13; vì 8 < 9 nên l i ch ph i tìm dãy 5, 6, 8, 9. L i chia ñôi dãy này thành 2 dãy con 5, 6 và 8, 9 th y ngay 8 thu c v dãy con 8, 9 và quá trình tìm ki m k t thúc, v trí c a s 8 trong dãy ñã cho là th ba Procedure Tim_nhi_phan_phan_tu_bang_a; m Input: a và dãy s a1, a2, ... , an ñã x p theo th t tăng; Output: V trí ph n t c a dãy có giá tr b ng a, ho c là s 0 n u không tìm th y trong dãy; o Begin i := 1; (* i là ñi m mút trái c a kho ng tìm ki m*) .c j := n; (* j là ñi m mút ph i c a kho ng tìm ki m*) while i < j do begin s 1 + j  ; m :=  2 h  if a > am then i := m+1 t else j := m; end; a if a = ai then vitri := i else vitri := 0; end; m ð ph c t p c a thu t toán tìm ki m nh phân ñư c ñánh giá như sau: Không gi m t ng quát có th gi s ñ dài c a dãy a1, a2, …, an là n = 2k v i k là s nguyên dương. (N u n không ph i là lũy th a c a 2, luôn tìm ñư c s k sao cho 2k – 1 < n < 2k do ñó có th t xem dãy ñã cho là m t ph n c a dãy có 2k ph n t ). Như v y ph i th c hi n nhi u nh t k l n chia ñôi các dãy s (m i n a dãy c a l n chia ñôi th nh t có 2k – 1 ph n t , c a l n chia ie ñôi th hai có 2k – 2 ph n t , …, và c a l n chia ñôi th k là 2k – k = 20 = 1 ph n t ). Nói cách khác là nhi u nh t có k vòng l p while ñư c th c hi n trong thu t toán tìm ki m nh phân. Trong m i vòng l p while ph i th c hi n hai phép so sánh, và vòng l p cu i cùng khi .v ch còn 1 ph n t ph i th c hi n 1 phép so sánh ñ bi t không còn 1 ph n t nào thêm n a và 1 phép so sánh ñ bi t a có ph i là ph n t ñó hay không. T ñó th y r ng thu t toán ph i th c hi n nhi u nh t 2k + 2 = 2[log2n] + 2 = O(logn) phép so sánh. w V y, ñ ph c t p c a thu t toán tìm ki m nh phân là ñ ph c t p logarit. 6. Thu t toán ñ quy w 6.1. Công th c truy h i ðôi khi r t khó ñ nh nghĩa m t ñ i tư ng nào ñó m t cách tư ng minh, nhưng có th w ñ nh nghĩa ñ i tư ng ñó qua chính nó v i ñ u vào nh hơn. Cách ñ nh nghĩa như v y g i là cách ñ nh nghĩa b ng truy h i ho c ñ nh nghĩa b ng ñ quy và nó cho m t công th c g i là công th c truy h i. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..16
  18. www.VIETMATHS.com www.VIETMATHS.com ð nh nghĩa: ð nh nghĩa b ng truy h i bao g m các quy t c ñ xác ñ nh các ñ i tư ng, trong ñó có m t s quy t c dùng ñ xác ñ nh các ñ i tư ng ban ñ u g i là các ñi u ki n ban ñ u; còn các quy t c khác dùng ñ xác ñ nh các ñ i tư ng ti p theo g i là công th c truy h i. Thí d 1. Dãy s an ñư c ñ nh nghĩa b ng ñ quy như sau: m a0 = 3; an = an – 1 + 3. Trong ñó a0 = 3 là ñi u ki n ban ñ u, còn an = an – 1 + 3 là công th c truy h i. o Thí d 2. ð nh nghĩa b ng ñ quy giai th a c a s t nhiên n là: GT(0) = 1; GT(n) = n.GT(n – 1). Vì GT(n) = n! = n(n-1)(n-2)…1 = n.GT(n-1). Trong ñó GT(0) = 1 là ñi u ki n ban ñ u, còn .c GT(n) = n.GT(n – 1) là công th c truy h i. Thí d 3. Dãy s F0, F1, F2, …, Fn ñư c ñ nh nghĩa: s F0 = 0; F1 = 1; Fn = Fn – 1 + Fn – 2 . ðó chính là ñ nh nghĩa b ng ñ quy c a dãy s có tên là dãy Fibonacci. Trong ñó h F0 = 0, F1 = 1 là các ñi u ki n ban ñ u, còn Fn = Fn – 1 + Fn – 2 là công th c ñ quy. D th y m t s s h ng ñ u tiên c a dãy là: 0; 1; 1; 2; 3; 5; 8; 13; 21; … t 6.2. Thu t toán ñ quy. a Nhi u khi vi c gi i bài toán v i ñ u vào xác ñ nh có th ñưa v vi c gi i bài toán ñó v i giá tr ñ u vào nh hơn. Ch ng h n: m n! = n . (n-1)! hay UCLN(a, b) = UCLN(a mod b, b) , a > b ð nh nghĩa: M t thu t toán g i là ñ quy n u thu t toán ñó gi i bài toán b ng cách rút g n liên ti p bài toán ban ñ u t i bài toán cũng như v y nhưng v i d li u ñ u vào nh t hơn. D th y cơ s c a thu t toán là công th c truy h i. ie Thí d 1. Tính giai th a c a s t nhiên n b ng ñ quy. Function GT(n); .v Input: S t nhiên n; Output: Giá tr c a n!; Begin w if n = 0 then GT(0) := 1 else GT(n) := n*GT(n – 1); End; w Thí d 2. Tính s h ng c a dãy Fibonacci b ng ñ quy. Function Fibonacci(n); w Input: V trí th n c a dãy Fibonacci; Output: Giá tr Fn c a dãy Fibonaci; Begin Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..17
  19. www.VIETMATHS.com www.VIETMATHS.com if n = 0 then Fibonacci(0) := 0 else if n = 1 then Fibonacci(1) := 1 else Fibonacci(n) := Fibonacci(n-1) + Fibonacci(n-2); End; Thí d 3. Thu t toán ñ quy tìm UCLN(a, b). m Function UCLN(a, b); Input: Hai s nguyên dương a và b; Output: Ư c s chung l n nh t c a a và b; o Begin if b = 0 then UCLN(a, b) := a .c else if a > b then UCLN(a, b) := UCLN(a mod b, b) else UCLN(a, b) := UCLN(b mod a, a); End; s Bây gi chúng ta th tìm ñ ph c t p v th i gian c a m t vài thu t toán vi t b ng ñ h quy. Ch ng h n xét thu t toán ñ quy tính s h ng c a dãy Fibonacci, ñ tính Fn ta bi u di n Fn = Fn – 1 + Fn – 2 , sau ñó thay th c hai s này b ng t ng c a hai s Fibonacci b c t th p hơn. Quá trình ti p t c như v y cho ñ n khi F0 và F1 xu t hi n thì ñư c thay b ng các giá tr c a chúng trong ñ nh nghĩa. a M i bư c ñ quy cho t i khi F0 và F1 xu t hi n, các s Fibonacci ñư c tính hai l n. Ch ng h n gi n ñ cây hình 2 cho ta hình dung cách tính F5 theo thu t toán ñ quy. T m ñó có th th y r ng ñ tính Fn c n th c hi n Fn + 1 – 1 phép c ng. F5 t F4 F3 ie F3 F2 F2 F1 .v F2 F1 F1 F0 F1 F0 w F1 F0 w Hình 2. Lư c ñ tính F5 b ng ñ quy ð ph c t p c a thu t toán ñ quy tìm ư c s chung l n nh t c a hai s nguyên dương a, b (thí d 3): UCLN(a,b) = UCLN(a mod b,b), n u a ≥ b (a mod b là ph n dư khi w chia a cho b) ñư c ñánh giá b ng cách ng d ng dãy Fibonacci. Trư c h t b ng quy n p toán h c chúng ta ch ng minh s h ng t ng quát c a dãy Fibonacci th a mãn: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..18
  20. www.VIETMATHS.com www.VIETMATHS.com 1+ 5 Fn > αn – 2, ∀n ≥ 3, trong ñó α = . (1) 2 Th t v y: Ta có: α < 2 = F3, nghĩa là (1) ñúng v i n = 3. m Gi s Fn > αn – 2 ñúng v i n, xét v i n+1. D th y α là m t nghi m c a phương trình x2 – x – 1 = 0 nên suy ra α2 = α + 1. T ñó: αn – 1 = α2αn – 3 = (α + 1)αn – 3 = αn – 2 + αn – 3 . o Theo gi thi t quy n p, n u n ≥ 4, ta có Fn – 1 > αn – 3 và Fn > αn – 2. Thay vào ñ nh nghĩa c a dãy Fibonacci: .c Fn + 1 = Fn + Fn – 1 > αn – 2 + αn – 3 = αn – 1 V y Fn > αn – 2 , ∀n ≥ 3. s Công th c (1) ñư c ch ng minh. Tr l i thu t toán ñ quy tìm ư c s chung l n nh t c a hai s nguyên dương a, b (a h ≥ b). ð ph c t p c a thu t toán ñư c ñánh giá qua s lư ng các phép chia dùng trong thu t toán này. t ð t r0 = a, r1 = b, ta có: r0 = r1q1 + r2; 0 ≤ r2 < r1, a r1 = r2q2 + r3; 0 ≤ r3 < r2, ..... m rn – 2 = rn – 1 qn – 1 + rn ; 0 ≤ rn < rn – 1, rn – 1 = rn qn ; Như v y ph i dùng n phép chia ñ tìm rn = UCLN(a,b). Các thương q1, q2, …, qn – 1 luôn t l n hơn ho c b ng 1, còn qn ≥ 2. T ñó suy ra: rn ≥ 1 = F2, ie rn – 1 ≥ 2rn = 2F2 = F3, rn – 2 ≥ rn – 1 + rn ≥ F3 + F2 = F4, .v ... r2 ≥ r3 + r4 ≥ Fn – 1 + Fn – 2 = Fn, b = r1 ≥ r2 + r3 ≥ Fn + Fn – 1 = Fn + 1. w trong ñó Fn là s h ng th n trong dãy Fibonacci. V y n u n là s các phép chia trong thu t toán Ơ-clit tìm ư c s chung l n nh t c a hai s nguyên dương a, b thì b ≥ Fn + 1, trong ñó Fn là s Fibonacci th n. w 1+ 5 Fn + 1 > αn – 1 v i n > 2 và α = nên b > αn – 1. Do 2 w 1 n −1 T ñó: lgb > (n – 1) lgα > ( vì lgα ≈ 0,208 > ). 5 5 n – 1 < 5lgb ⇒ n < 5lgb + 1 = O(lgb). V y: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình Giáo trình Toán R i r c…….……………………..19
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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