Bài giảng Toán rời rạc - Phần thứ nhất: Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê

Phần thứ nhất

LÝ THUYẾT TỔ HỢP

Combinatorial Theory

Fall 2009

1

Toán rời rạc

Nội dung

Chương 0. Mở đầu

Chương 1. Bài toán đếm

Chương 2. Bài toán tồn tại

Chương 3. Bài toán liệt kê tổ hợp

Chương 4. Bài toán tối ưu tổ hợp

2

Toán rời rạc

Chương 3

BÀI TOÁN LIỆT KÊ

3

Toán rời rạc

NỘI DUNG

1. Giới thiệu bài toán

2. Thuật toán và độ phức tạp

3. Phương pháp sinh

4. Thuật toán quay lui

4

Toán rời rạc

Giíi thiÖu bµi to¸n

⚫ Bài toán đưa ra danh sách tất cả cấu hình tổ hợp

thoả mãn một số tính chất cho trước được gọi là

bài toán liệt kê tổ hợp.

⚫ Do số lượng cấu hình tổ hợp cần liệt kê thường là

rất lớn ngay cả khi kích thước cấu hình chưa lớn:

• Số hoán vị của n phần tử là n!

• Số tập con m phần tử của n phần tử là n!/(m!(n-

m)!

⚫ Do đó ần có quan niệm thế nào là giải bài

toán liệt kê tổ hợp

5

Giíi thiÖu bµi to¸n

⚫ Bài toán liệt kê tổ hợp là giải được nếu như

ta có thể xác định một thuật toán để theo đó

có thể lần lượt xây dựng được tất cả các cấu

hình cần quan tâm.

⚫ Một thuật toán liệt kê phải đảm bảo 2 yêu

cầu cơ bản:

• Không được lặp lại một cấu hình,

• không được bỏ sót một cấu hình.

6

Chương 3. Bài toán liệt kê

1. Giới thiệu bài toán

2. Thuật toán và độ phức tạp

3. Phương pháp sinh

4. Thuật toán quay lui

7

Toán rời rạc

Khái niệm bài toán tính toán

⚫ Định nghĩa. Bài toán tính toán F là ánh xạ từ tập các xâu nhị phân

độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn:

F : {0, 1}* → {0, 1}*.

⚫ Ví dụ:

⚫ Mỗi số nguyên x đều có thể biểu diễn dưới dạng xâu nhị phân là cách

viết trong hệ đếm nhị phân của nó.

⚫ Hệ phương trình tuyến tính Ax = b có thể biểu diễn dưới dạng xâu là

ghép nối của các xâu biểu diễn nhị phân của các thành phần của ma

trận A và vectơ b.

⚫ Đa thức một biến:

P(x) = a₀+ a₁x + ... + a_nxⁿ,

hoàn toàn xác định bởi dãy số n, a₀, a₁, ..., a_n, mà để biểu diễn dãy số

này chúng ta có thể sử dụng xâu nhị phân.

8

Khái niệm thuật toán

⚫ Định nghĩa. Ta hiểu thuật toán giải bài toán đặt ra là

một thủ tục xác định bao gồm một dãy hữu hạn các bước

cần thực hiện để thu được đầu ra cho một đầu vào cho

trước của bài toán.

⚫ Thuật toán có các đặc trưng sau đây:

• Đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào

đó.

• Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán

đưa ra các dữ liệu tương ứng với lời giải của bài toán.

• Chính xác (Precision): Các bước của thuật toán được mô tả

chính xác.

9

Khái niệm thuật toán

• Hữu hạn (Finiteness): Thuật toán cần phải đưa được

đầu ra sau một số hữu hạn (có thể rất lớn) bước với

mọi đầu vào.

• Đơn trị (Uniqueness): Các kết quả trung gian của

từng bước thực hiện thuật toán được xác định một

cách đơn trị và chỉ phụ thuộc vào đầu vào và các kết

quả của các bước trước.

• Tổng quát (Generality): Thuật toán có thể áp dụng để

giải mọi bài toán có dạng đã cho.

10

Độ phức tạp của thuật toán

⚫ Độ phức tạp tính toán của thuật toán được xác định như là lượng

tài nguyên các loại mà thuật toán đòi hỏi sử dụng.

⚫ Có hai loại tài nguyên quan trọng đó là thời gian và bộ nhớ.

⚫ Việc tính chính xác được các loại tài nguyên mà thuật toán đòi hỏi

là rất khó. Vì thế ta quan tâm đến việc đưa ra các đánh giá sát thực

cho các đại lượng này.

⚫ Trong giáo trình này ta đặc biệt quan tâm đến đánh giá thời gian

cần thiết để thực hiện thuật toán mà ta sẽ gọi là thời gian tính của

thuật toán.

11

Độ phức tạp của thuật toán

⚫ Rõ ràng: Thời gian tính phụ thuộc vào dữ liệu vào.

⚫ Ví dụ: Việc nhân hai số nguyên có 3 chữ số đòi hỏi thời gian khác

hẳn so với việc nhân hai số nguyên có 3*10⁹chữ số!

⚫ Định nghĩa. Ta gọi kích thước dữ liệu đầu vào (hay độ dài dữ

liệu vào) là số bít cần thiết để biểu diễn nó.

⚫ Ví dụ: Nếu x, y là đầu vào cho bài toán nhân 2 số nguyên, thì kích

thước dữ liệu vào của bài toán là n = log |x| + log |y| .

⚫ Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm

của độ dài dữ liệu vào.

12

Phép toán cơ bản

⚫ Đo thời gian tính bằng đơn vị đo nào?

⚫ Định nghĩa. Ta gọi phép toán cơ bản là phép

toán có thể thực hiện với thời gian bị chặn bởi

một hằng số không phụ thuộc vào kích thước dữ

liệu.

⚫ Để tính toán thời gian tính của thuật toán ta sẽ

đếm số phép toán cơ bản mà nó phải thực hiện.

13

Các loại thời gian tính

⚫ Chúng ta sẽ quan tâ m đến:

• Thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi

bộ dữ liệu đầu vào kích thước n. Thời gian như vậy sẽ được

gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích

thước n.

• Thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi

bộ dữ liệu đầu vào kích thước n. Thời gian như vậy sẽ được

gọi là thời gian tính tồi nhất của thuật toán với đầu vào kích

thước n.

• Thời gian trung bình cần thiết để thực hiện thuật toán trên tập

hữu hạn các đầu vào kích thước n. Thời gian như vậy sẽ được

gọi là thời gian tính trung bình của thuật toán.

14

Ký hiệu tiệm cận

Asymptotic Notation

⚫ Q, O, W

⚫ Được xác định đối với các hàm nhận giá trị nguyên

không âm

⚫ Dùng để so sánh tốc độ tăng của hai hàm

⚫ Được sử dụng để mô tả thời gian tính của thuật toán

⚫ Thay vì nói chính xác, ta có thể nói thời gian tính là,

chẳng hạn, Q(n²)

15

Ký hiệu Q

Đối với hàm g(n) cho trước, ta ký hiệu Q(g(n)) là tập các hàm

Q(g(n)) = {f(n) | tồn tại các hằng số c₁, c₂và n₀sao cho

0  c₁g(n)  f(n)  c₂g(n), với mọi n  n₀}

Ta nói rằng g(n) là đánh giá tiệm cận đúng cho f(n)

16

Ví dụ

⚫ 10n²- 3n = Q(n²)

⚫ Với giá trị nào của các hằng số n₀, c₁, và c₂thì bất

đẳng thức sau đây là đúng với n ≥ n₀:

c₁n²≤ 10n²- 3n ≤ c₂n²

⚫ Ta có thể lấy c₁bé hơn hệ số của số hạng với số mũ

cao nhất, còn c₂lấy lớn hơn hệ số này, chẳng hạn:

c₁=9 < 10 < c₂= 11, n₀= 10.

⚫ Tổng quát, để so sánh tốc độ tăng của các đa thức,

cần nhìn vào số hạng với số mũ cao nhất

17

Ký hiệu O

Đối với hàm g(n) cho trước, ta ký hiệu O(g(n)) là tập các hàm

O(g(n)) = {f(n) | tồn tại các hằng số dương c và n₀sao cho:

f(n)  cg(n) với mọi n  n₀}

Ta nói g(n) là cận trên tiệm cận của f(n)

18

Ví dụ: Ký hiệu O lớn

⚫ Chứng minh: f(n) = n²+ 2n + 1 là O(n²)

• Cần chỉ ra: n²+ 2n + 1 ≤ c*n²

với c là hằng số nào đó và khi n > n₀nào đó

⚫ Ta có:

2n²≥ 2n khi n ≥ 1

và n²≥ 1 khi n ≥ 1

⚫ Vì vậy

n²+ 2n + 1 ≤ 4*n²với mọi n ≥ 1

⚫ Như vậy hằng số c = 4, và n₀=1

19

Ví dụ: Ký hiệu O lớn

⚫ Rõ ràng: Nếu f(n) là O(n²) thì nó cũng là O(n^k) với k > 2.

⚫ Chứng minh: f(n) = n²+ 2n + 1O(n).

⚫ Phản chứng. Giả sử trái lại, khi đó phải tìm được hằng số

c và số n₀để cho:

n²+ 2n + 1 ≤ c*n khi n ≥ n₀

⚫ Suy ra

n²< n²+ 2n + 1 ≤ c*n với mọi n ≥ n₀

⚫ Từ đó ta thu được:

n < c với mọi n ≥ n₀?!

20

Bài giảng Toán rời rạc - Phần thứ nhất: Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê - Nguyễn Đức Nghĩa