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

MÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢC

Chia sẻ: Nguyễn Gia Thế | Ngày: | Loại File: PPT | Số trang:22

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

Bạn được làm thuê cho một công ty với tư cách là nhà thiết kế thuật toán. • Công ty sẽ tham gia thị trường cạnh tranh “bandersnatch cao cấp”. • Có phương pháp nào để tạo ra một tập các quy cách kĩ thuật cho mỗi bài toán của thị trường bandersnatch đặt ra?Xác định chính xác bài toán = tham vấn phòng bandersnatch. • Lao vào công việc với đầy bầu nhiệt huyết.Vài tuần trôi qua • Giấy tờ tràn ngập • Không tìm được bất kì thuật toán nào – phải mất hàng năm để xây dựng một thuật toán cho một modun – Có rất nhiều modun cho bài toán...

Chủ đề:

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

Lưu

Nội dung Text: MÁY TÍNH, ĐỘ PHỨC TẠP VÀ TÍNH KHÔNG THỂ GIẢI ĐƯỢC

  1. MÁY TÍNH, ĐỘ PHỨC TẠP VÀ MÁY TÍNH KHÔNG THỂ GIẢI ĐƯỢC Giảng viên : PGS.TSKH VŨ ĐÌNH HÒA
  2. MỞ ĐẦU TÌNH HUỐNG  • Bạn được làm thuê cho một công ty với tư cách là nhà thiết kế thuật toán. • Công ty sẽ tham gia thị trường cạnh tranh “bandersnatch cao cấp”. • Có phương pháp nào để tạo ra một tập các quy cách kĩ thuật cho mỗi bài toán của thị trường bandersnatch đặt ra?
  3. MỞ ĐẦU PHẢI LÀM GÌ? • Xác định chính xác bài toán = tham vấn phòng bandersnatch. • Lao vào công việc với đầy bầu nhiệt huyết
  4. MỞ ĐẦU KẾT QUẢ • Vài tuần trôi qua • Giấy tờ tràn ngập • Không tìm được bất kì thuật toán nào – phải mất hàng năm để xây dựng một thuật toán cho một modun – Có rất nhiều modun cho bài toán
  5. MỞ ĐẦU PHẢI LÀM THẾ NÀO PH • Nếu viết báo cáo rằng “Tôi thật ngu ngốc vì không thể tìm được thuật toán nào” →Bạn sẽ bị sa thải’ • Cần chứng minh rằng bài toán được giao là không thể giải dễ dàng được
  6. MỞ ĐẦU LỜI KHUYÊN • Việc chứng minh tính không thể giải được = chứng minh không tồn tại một thuật toán hữu hiệu. • Lý thuyết sau đây chỉ ra rằng cần chứng minh bài toán của bạn là bài toán NP-đầy đủ. • Nó có độ khó tương đương với độ khó lớp các bài toán khác mà nhiều chuyên gia phải bó tay.
  7. MỞ ĐẦU LỜI KHUYÊN • Tính NP­đầy đủ cho ta thấy: →Khả năng tìm ra thuật toán tốt cho  bài toán khó. →Cách chuyển hướng tiếp cận: giải  gần đúng hoặc tìm lời giải cho những  trường hợp đặc biệt 
  8. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Một bài toán/vấn đề là gì?: →Một câu hỏi có tính tổng quát cần được trả lời. →Thường chứa một số tham số hay biến tự do chưa được xác định giá trị. →Miêu tả:(1) các tham số, (2) các yêu cầu về câu trả lời.
  9. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Bài toán:  →Ví dụ: Bt “Người du lịch”. C = c1 , c2 ,  , cm } { ٧ Các thành phố ( ) ٧ Các khoảng cách  d c ,c i j ?  Yêu cầu: tìm hoán vị tròn  cπ1 , cπ2 ,  , cπm m −  1 sao cho tổng trọng số cạnh: ∑(cπ( i ) , cπ( i + ) ) + (cπ( m ) , cπ(1) )  d d 1 i =  1 nhỏ nhất.  ‫ ٭‬Ý nghĩa: 
  10. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Một dữ kiện/input của bài toán: c1 C ={c1 , c2 , c3 , c4 } d ( 1 , c2 ) = 5 9   c 10 10 c3 d ( 1 , c3 ) = 6 c 5 c2 3 c4 d ( 1 , c4 ) = c 9 9 d (c2 , c3 ) =6 c1 , c2 , c4 , c3 Sắp d ( 2 , c4 ) = c 9 xếp: Là lời giải: lengthmin = 27 d ( 3 , c4 ) = c 3
  11. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Thuật toán: →Gồm các thủ tục “từng bước-từng bước” giải quyết bài toán. →Có thể xem như một chương trình viết bằng ngôn ngữ máy. • Một TT giải quyết được bài toán П nếu nó có lời giải cho mọi dữ kiện/input I của bài toán đó. toán
  12. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Thuật toán:  Thế nào là một TT hiệu quả (efficiency)? – Chạy được với tất cả các input. – Thời gian tính toán nhanh nhất. Yêu cầu về thời gian có tính quyết định xem một thuật toán có hiệu quả để đưa vào thực tế hay không
  13. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Thuật toán: Yêu cầu về thời gian – Có thể miêu tả hàm một biến (Kích thước của một bài  toán cụ thể)       – Đo kích thước của bài toán cụ thể theo cách thông  thường – Ex, bài toán “người thương gia đi du lịch” có kích  –Đểước lm st cáchng m cxác thì phải xét cả số các khoảng th tính à ộố lượ chính ác thành phố.   cách và độ lớn các khoảng cách giữa các thành phố.
  14. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Lược đồ mã hóa: – Miêu tả đầu vào của một bài toán cụ thể bằng  một chuỗi kí tự. – Độ dài đầu vào của trường hợp I của bài toán  П là số kí tự trong chuỗi kí tự của lược đồ mã  hóa. – Độ dài này là cách đo hình thức của kích  thước bài toán cụ thể П(I).
  15. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Lược đồ mã hóa: – Ví dụ:  Bài toán người thương gia đi du lịch.     ‫٭‬Lđmh sử dụng bộ kí tự:     {c, [, ], /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}    ‫٭‬Chuỗi mã hóa: “c[1] c[2] c[3] c[4] // 10 / 5 / 9 // 6 / 9 // 3”    ‫ ٭‬Độ dài đầu vào là 32. ‫ ٭‬Các trường hợp bài toán phức tạp, có thể mã hóa  bằng chuỗi tương tự, không phải chuỗi rời rạc. 
  16. BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC  TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN • Hàm thời gian: Cho mỗi kích thước đầu vào một lượng thời  gian lớn nhất để giải quyết trường hợp của bài  toán đó
  17. THUẬT TOÁN THỜI GIAN ĐA THỨC  THU VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI  ĐƯỢC • 1 hàm f(n) là O(g(n)) khi       hằng c, k:     |f(n)|=k • 1 thuật toán thời gian đa thức có độ phức tạp là  O(p(n)) với p(n) là một hàm đa thức. • n chỉ kích thước đầu vào • 1 thuật toán thời gian lũy thừa nếu hàm phức tạp thời  gian của nó không có giới hạn. (bao gồm cả một số hàm phức tạp thời gian không  log n n đa thức như             )
  18. THUẬT TOÁN THỜI GIAN ĐA THỨC  THU VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI  ĐƯỢC • Bảng so sánh một số hàm phức tạp thời  gian lũy thừa và đa thức. Size n Time  complexity  10 20 30 40 50 60 function n .00001s .00002s .00003s .00004s .00005s .00006s n2 .0001s .0004s .0009s .0016s .0025s .0036s n3 .001s .008s .0027s .064s .125s .216s n5 .1s 3.2s 24.3s 1.7m 5.2m 13.0m 2n .001s 1.0s 17.9m 12.7d 35.7y 366c 3n .059s 58m 6.5y 3855c 2 x 108 c 1.3 x 1013 c
  19. THUẬT TOÁN THỜI GIAN ĐA THỨC  THU VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI  ĐƯỢC • Ảnh hưởng của công nghệ máy tính đến  các hàm phức tạp thời gian Computer 100  Time  Computer  Present  complexity  times faster 1000 times  computer function faster n N1 100N1 1000N1 n2 N2 10N2 31.6N2 n3 N3 10N3 4.64N3 n5 N4 2.5N4 3.98N4 2n N5 N5+6.64 N5+9.97 3n N6 N6+4.19 N6+6.29
  20. THUẬT TOÁN THỜI GIAN ĐA THỨC  THU VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI  ĐƯỢC • Một bài toán là không thể giải được nếu quá khó  để tìm ra một thuật toán thời gian đa thức để giải  quyết nó. • Với kích thước bài toán có hạn thì việc so sánh  giữa thuật toán đa thức hữu hiệu và thuật toán  lũy thừa không hữu hiệu có nhiều ngoại lệ. • Ex: xem bảng so sánh ở slide trước, thuật toán  2n nhanh hơn thuật toán n5 với n
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
11=>2