Giải thuật và lập trình

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (469.76 KB, 7 trang )

(1)<div class='page_container' data-page=1>

LÊ MINH HOÀNG

Bài gi

ả

ng chuyên

đề

</div>
(2)<div class='page_container' data-page=2></div>
(3)<div class='page_container' data-page=3>

L

ờ

i c

ả

m

ơ

n

Tôi mu

ố

n bày t

ỏ

lòng bi

ế

t

ơ

n

đố

i v

ớ

i nh

ữ

ng ng

ườ

i th

ầ

y

đ

ã ch

ỉ

d

ạ

y t

ậ

n tình trong nh

ữ

ng n

ă

m tháng

đầ

y khó kh

ă

n khi tơi m

ớ

i b

ướ

c vào h

ọ

c tin h

ọ

c và l

ậ

p trình. S

ự

hi

ể

u bi

ế

t và lịng nhi

ệ

t tình c

ủ

a các

th

ầ

y không nh

ữ

ng

đ

ã cung c

ấ

p cho tôi nh

ữ

ng ki

ế

n th

ứ

c quý báu mà còn là t

ấ

m g

ươ

ng sáng cho tôi

noi theo khi tôi

đứ

ng trên b

ụ

c gi

ả

ng c

ũ

ng v

ớ

i t

ư

cách là m

ộ

t ng

ườ

i th

ầ

y.

Cu

ố

n tài li

ệ

u này

đượ

c vi

ế

t d

ự

a trên nh

ữ

ng tài li

ệ

u thu th

ậ

p

đượ

c t

ừ

nhi

ề

u ngu

ồ

n khác nhau, b

ở

i

công s

ứ

c c

ủ

a nhi

ề

u th

ế

h

ệ

th

ầ

y trò

đ

ã t

ừ

ng gi

ả

ng d

ạ

y và h

ọ

c t

ậ

p t

ạ

i Kh

ố

i Ph

ổ

thơng chun Tốn-

Tin,

Đạ

i h

ọ

c S

ư

ph

ạ

m Hà N

ộ

i, cịn tơi ch

ỉ

là ng

ườ

i t

ổ

ng h

ợ

p l

ạ

i. Qua

đ

ây, tôi mu

ố

n g

ử

i l

ờ

i c

ả

m

ơ

n

t

ớ

i các

đồ

ng nghi

ệ

p

đ

ã

đọ

c và

đ

óng góp nh

ữ

ng ý ki

ế

n q báu, c

ả

m

ơ

n các b

ạ

n h

ọ

c sinh - nh

ữ

ng

con ng

ườ

i

đ

ã tr

ự

c ti

ế

p làm nên cu

ố

n sách này.

Do th

ờ

i gian h

ạ

n h

ẹ

p, m

ộ

t s

ố

chuyên

đề

tuy

đ

ã có nh

ư

ng ch

ư

a k

ị

p ch

ỉ

nh s

ử

a và

đư

a vào tài li

ệ

u.

B

ạ

n

đọ

c có th

ể

tham kh

ả

o thêm trong ph

ầ

n tra c

ứ

u. R

ấ

t mong nh

ậ

n

đượ

c nh

ữ

ng l

ờ

i nh

ậ

n xét và góp

ý c

ủ

a các b

ạ

n

để

hoàn thi

ệ

n cu

ố

n sách này.

Tokyo, 28 tháng 4 n

ă

m 2003

</div>
(4)<div class='page_container' data-page=4></div>
(5)<div class='page_container' data-page=5>

MỤC LỤC

PH

Ầ

N 1. BÀI TỐN LI

Ệ

T KÊ ... 1

§1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP...2

1.1. CHỈNH HỢP LẶP...2

1.2. CHỈNH HỢP KHƠNG LẶP...2

1.3. HỐN VỊ...2

1.4. TỔ HỢP...3

§2. PHƯƠNG PHÁP SINH (GENERATION) ...4

2.1. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N ...5

2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ...6

2.3. LIỆT KÊ CÁC HỐN VỊ...8

§3. THUẬT TỐN QUAY LUI ...12

3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N...12

3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ...13

3.3. LIỆT KÊ CÁC CHỈNH HỢP KHƠNG LẶP CHẬP K ...15

3.4. BÀI TỐN PHÂN TÍCH SỐ...16

3.5. BÀI TỐN XẾP HẬU...18

§4. KỸ THUẬT NHÁNH CẬN...24

4.1. BÀI TỐN TỐI ƯU...24

4.2. SỰ BÙNG NỔ TỔ HỢP ...24

4.3. MƠ HÌNH KỸ THUẬT NHÁNH CẬN...24

4.4. BÀI TOÁN NGƯỜI DU LỊCH ...25

4.5. DÃY ABC ...28

PH

Ầ

N 2. C

Ấ

U TRÚC D

Ữ

LI

Ệ

U VÀ GI

Ả

I THU

Ậ

T ... 33

§1. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC...34

1.1. XÁC ĐỊNH BÀI TOÁN...34

1.2. TÌM CẤU TRÚC DỮ LIỆU BIỂU DIỄN BÀI TỐN ...34

1.3. TÌM THUẬT TỐN ...35

1.4. LẬP TRÌNH ...37

1.5. KIỂM THỬ...37

1.6. TỐI ƯU CHƯƠNG TRÌNH ...38

§2. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT ...40

2.1. ĐỘ PHỨC TẠP TÍNH TỐN CỦA GIẢI THUẬT ...40

2.2. XÁC ĐỊNH ĐỘ PHỨC TẠP TÍNH TỐN CỦA GIẢI THUẬT...40

2.3. ĐỘ PHỨC TẠP TÍNH TỐN VỚI TÌNH TRẠNG DỮ LIỆU VÀO...43

</div>
(6)<div class='page_container' data-page=6>

TÀ

I

L

I

Ệ

U

Đ

Ọ

C

T

H

Ê

M

[1]

Christian Charras, Thierry Lecroq.

Handbook of Exact String-Matching Algorithms.

G

ầ

n 20 thu

ậ

t tốn tìm ki

ế

m chu

ỗ

i, có di

ễ

n gi

ả

i

đầ

y

đủ

.

[2]

Reinhard Diestel.

Graph Theory

. M

ộ

t cu

ố

n sách chuyên v

ề

Lý thuy

ế

t

đồ

th

ị

.

[3]

Johan Håstad.

Advanced Algorithms.

[4]

Andrew J. Manson.

Speaker Matching.

Bài báo nói v

ề

các thu

ậ

t tốn tìm b

ộ

ghép trên

đồ

th

ị

t

ổ

ng quát, c

ả

trong tr

ườ

ng h

ợ

p

đồ

th

ị

có tr

ọ

ng s

ố

[5]

Eva Milková.

Graph Theory and Information Technology

. M

ộ

t s

ố

thu

ậ

t toán v

ề

bài

toán cây bao trùm t

ố

i ti

ể

u.

[6]

Dave Mount.

Design and Analysis of Computer Algorithms.

[7]

Nguy

ễ

n Xuân My, Tr

ầ

n

Đỗ

Hùng, Lê S

ĩ

Quang.

M

ộ

t s

ố

v

ấ

n

đề

ch

ọ

n l

ọ

c trong tin h

ọ

c.

Cu

ố

n sách r

ấ

t phù h

ợ

p cho h

ọ

c sinh ph

ổ

thơng trung h

ọ

c u thích vi

ệ

c gi

ả

i các bài toán

tin h

ọ

c

[8]

Nguy

ễ

n

Đứ

c Ngh

ĩ

a, Nguy

ễ

n Tơ Thành.

Tốn r

ờ

i r

ạ

c

. M

ộ

t cu

ố

n sách r

ấ

t c

ă

n b

ả

n dành

cho sinh viên ngành tin h

ọ

c.

[9]

Kenneth H. Rosen.

Discrete Mathematics and its Applications (B

ả

n d

ị

ch ti

ế

ng Vi

ệ

t:

Toán h

ọ

c r

ờ

i r

ạ

c

ứ

ng d

ụ

ng trong tin h

ọ

c)

. Cu

ố

n sách vi

ế

t d

ướ

i d

ạ

ng giáo trình r

ấ

t d

ễ

hi

ể

u, có h

ệ

th

ố

ng bài t

ậ

p

đượ

c s

ắ

p x

ế

p r

ấ

t khoa h

ọ

c.

</div>
(7)<div class='page_container' data-page=7>

In memory of committed teachers and excellent students.

</div>

Giải thuật và lập trình

<b>LÊ MINH HOÀNG </b>

Bài gi

ả

ng chuyên

đề

L

ờ

i c

ả

m

ơ

n

<i>Tôi mu</i>

<i>ố</i>

<i>n bày t</i>

<i>ỏ</i>

<i> lòng bi</i>

<i>ế</i>

<i>t </i>

<i>ơ</i>

<i>n </i>

<i>đố</i>

<i>i v</i>

<i>ớ</i>

<i>i nh</i>

<i>ữ</i>

<i>ng ng</i>

<i>ườ</i>

<i>i th</i>

<i>ầ</i>

<i>y </i>

<i>đ</i>

<i>ã ch</i>

<i>ỉ</i>

<i> d</i>

<i>ạ</i>

<i>y t</i>

<i>ậ</i>

<i>n tình trong nh</i>

<i>ữ</i>

<i>ng n</i>

<i>ă</i>

<i>m tháng </i>

<i>đầ</i>

<i>y khó kh</i>

<i>ă</i>

<i>n khi tơi m</i>

<i>ớ</i>

<i>i b</i>

<i>ướ</i>

<i>c vào h</i>

<i>ọ</i>

<i>c tin h</i>

<i>ọ</i>

<i>c và l</i>

<i>ậ</i>

<i>p trình. S</i>

<i>ự</i>

<i> hi</i>

<i>ể</i>

<i>u bi</i>

<i>ế</i>

<i>t và lịng nhi</i>

<i>ệ</i>

<i>t tình c</i>

<i>ủ</i>

<i>a các </i>

<i>th</i>

<i>ầ</i>

<i>y không nh</i>

<i>ữ</i>

<i>ng </i>

<i>đ</i>

<i>ã cung c</i>

<i>ấ</i>

<i>p cho tôi nh</i>

<i>ữ</i>

<i>ng ki</i>

<i>ế</i>