MÁY TÍNH, ĐỘ PHỨC TẠP VÀ
MÁY TÍNH, ĐỘ PHỨC TẠP VÀ
TÍNH KHÔNG THỂ GIẢI ĐƯỢC
TÍNH KHÔNG THỂ GIẢI ĐƯỢC
Giảng viên : PGS.TSKH VŨ ĐÌNH HÒA
Giảng viên : PGS.TSKH VŨ ĐÌNH HÒA
MỞ ĐẦU
MỞ ĐẦU
TÌNH HUỐNG
TÌNH HUỐNG•
Bạn được làm thuê cho một công ty với tư
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ách là nhà thiết kế thuật toán.
•
Công ty sẽ tham gia thị trường cạnh tranh
Công ty sẽ tham gia thị trường cạnh tranh
“bandersnatch cao cấp”.
“bandersnatch cao cấp”.
•
Có phương pháp nào để tạo ra một tập các quy
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
cách kĩ thuật cho mỗi bài toán của thị trường
bandersnatch đặt ra?
bandersnatch đặt ra?
MỞ ĐẦU
MỞ ĐẦU

một modun
một modun
–
Có rất nhiều modun cho bài toán
Có rất nhiều modun cho bài toán
MỞ ĐẦU
MỞ ĐẦU PHẢI LÀM THẾ NÀO
PHẢI LÀM THẾ NÀO
•
Nếu viết báo cáo rằng
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
Tôi thật ngu ngốc vì không thể tìm được thuật toán
nào”
nào”
→
→
Bạn sẽ bị sa thải’
Bạn sẽ bị sa thải’
•
Cần chứng minh rằng bài toán được giao là
Cần chứng minh rằng bài toán được giao là
không thể giải dễ dàng được
không thể giải dễ dàng được
MỞ ĐẦU

Tính NP-đầy đủ cho ta thấy:
→
→
Khả năng tìm ra thuật toán tốt cho
Khả năng tìm ra thuật toán tốt cho
bài toán khó.
bài toán khó.
→
→
Cách chuyển hướng tiếp cận: giải
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
gần đúng hoặc tìm lời giải cho những
trường hợp đặc biệt
trường hợp đặc biệt
BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP
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 SỐ KHÁI NIỆM CƠ BẢN
•
Một bài toán/vấn đề là gì?
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ả
Một câu hỏi có tính tổng quát cần được trả
lời.
lời.


Các thành phố
Các thành phố
٧
٧Các khoảng cách
Các khoảng cách
? Yêu cầu: tìm hoán vị tròn
? Yêu cầu: tìm hoán vị tròn
sao cho tổng trọng số cạnh:
sao cho tổng trọng số cạnh:
nhỏ nhất.
nhỏ nhất.
٭
٭Ý nghĩa:
Ý nghĩa:
{ }
m
ccC ,,,c
21

=
( )
ji
ccd ,

MỘT SỐ KHÁI NIỆM CƠ BẢN
MỘT SỐ KHÁI NIỆM CƠ BẢN
•
Một dữ kiện/input của bài toán:
Một dữ kiện/input của bài toán:1
c
2
c
3
c
4
c
10
9
9
5
6
3
{ }
4321
,,,c cccC
=
( )
10,
21
=
ccd

27
min
=
length
BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP
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 SỐ KHÁI NIỆM CƠ BẢN
•
Thuật toán
Thuật toán
:
:
→
→
G
G
ồm các thủ tục “từng bước-từng
ồm các thủ tục “từng bước-từng
bước” giải quyết bài toán.
bước” giải quyết bài toán.→
→
Có thể xem như một chương trình viết
Có thể xem như một chương trình viết
bằng ngôn ngữ máy.
bằng ngôn ngữ máy.
•

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 SỐ KHÁI NIỆM CƠ BẢN
•
Thuật toán
Thuật toán
:
:
Yêu cầu về thời gian
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
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ể)
toán cụ thể)–
Đo kích thước của bài toán cụ thể theo cách thông
Đo kích thước của bài toán cụ thể theo cách thông
thường
thường
–
Ex, bài toán “người thương gia đi du lịch” có kích
Ex, bài toán “người thương gia đi du lịch” có kích
thước là số lượng m các thành phố.
thước là số lượng m các thành phố.–

MỘT SỐ KHÁI NIỆM CƠ BẢN
MỘT SỐ KHÁI NIỆM CƠ BẢN
BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP
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 SỐ KHÁI NIỆM CƠ BẢN
•
Lược đồ mã hóa:
Lược đồ mã hóa:
–
Ví dụ: Bài toán người thương gia đi du lịch.
Ví dụ: Bài toán người thương gia đi du lịch. ٭
٭
Lđmh sử dụng bộ kí tự:
Lđmh sử dụng bộ kí tự: {c, [, ], /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{c, [, ], /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}٭
٭
Chuỗi mã hóa:
Chuỗi mã hóa:
“
“

bài toán đó
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
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:
1 hàm f(n) là O(g(n)) khi hằng c, k: |f(n)|<=c.|g(n)| n>=k
|f(n)|<=c.|g(n)| n>=k
•
1 thuật toán thời gian đa thức
1 thuật toán thời gian đa thức
có độ phức tạp là
có độ phức tạp là
O(p(n)) với p(n) là một hàm đa thức.
O(p(n)) với p(n) là một hàm đa thức.
•
n chỉ kích thước đầu vào
n chỉ kích thước đầu vào
•
1 thuật toán thời gian lũy thừa
1 thuật toán thời gian lũy thừa
nếu hàm phức tạp
nếu hàm phức tạp
thời gian của nó không có giới hạn.
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

10 3020 5040 60
.00001s
.00002s .00003s .00004s .00005s .00006s
.0001s .0004s .0009s .0016s .0036s.0025s
.1s
.008s .0027s .064s .125s .216s.001s
3.2s 24.3s 1.7m 5.2m 13.0m
.001s 1.0s 17.9m 12.7d 35.7y 366c
.059s 58m 6.5y 3855c
2 x 10
8
c
1.3 x 10
13
c
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
•
Ảnh hưởng của công nghệ máy tính đến
Ảnh hưởng của công nghệ máy tính đến
các hàm phức tạp thời gian
các hàm phức tạp thời gian
Time
complexity
function
Present
computer
Computer 100

1
10N
2
31.6N
2
4.64N
3
10N
3
2.5N
4
3.98N
4
N
5
+6.64 N
5
+9.97
N
6
+4.19 N
6
+6.29
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
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ó
Một bài toán là không thể giải được nếu quá khó

Một số nhận xét
–
Thuật ngữ “intratability” chỉ có nghĩa tương
Thuật ngữ “intratability” chỉ có nghĩa tương
đối vì:
đối vì:
•
Độ phức tạp về thời gian được định nghĩa trong
Độ phức tạp về thời gian được định nghĩa trong
trường hợp xấu nhất
trường hợp xấu nhất
•
Một thuật toán 2
Một thuật toán 2
n
n
nghĩa là có ít nhất một trường
nghĩa là có ít nhất một trường
hợp bài toán cỡ n cần bằng ẫy thời gian.
hợp bài toán cỡ n cần bằng ẫy thời gian.
•
Hầu hết trong thực tế cần ít thời gian hơn nhiều.
Hầu hết trong thực tế cần ít thời gian hơn nhiều.
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC
•
Một số nhận xét
Một số nhận xét