Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1

KHOA CÔNG NGHỆ THÔNG TIN

CẤU TRÚC DỮ LIỆU & GIẢI (Data Structure and Algorithm) THUẬT

CHƯƠNG 1: GIỚI THIỆU VÀ ĐÁNH GIÁ GIẢI THUẬT

GVGD:

HỌC KỲ I – NĂM HỌC 2020-2021

KHÓA 25T-IT

MỘT SỐ NHÓM GIẢI THUẬT CƠ BẢN

01.

CÁC VẤN ĐỀ PHÂN TÍCH GIẢI THUẬT

02.

CẤU TRÚC NGÔN NGỮ MÁY TÍNH

03.

NỘI DUNG

GIỚI THIỆU PHÂN TÍCH GIẢI THUẬT

04.

MỘT SỐ NHÓM GIẢI THUẬT PHỔ BIẾN

感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com

1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN) 2. GIẢI THUẬT CHIA ĐỂ TRỊ 3. GIẢI THUẬT QUY HOẠCH ĐỘNG 4. GIẢI THUẬT GREEDY ( THAM LAM) 5. GIẢI THUẬT HEURISTIC 6. GIẢI THUẬT XÁC SUẤT

3 KHOA CÔNG NGHỆ THÔNG TIN

1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN)

• Giải thuật áp dụng giải quyết những vấn đề mang tính xâu chuỗi ( tăng dần)

cần xem xét tất cả các trường hợp xảy ra.

• Ví dụ: Tìm giá trị M trong một danh sách chưa có thứ tự L

4 KHOA CÔNG NGHỆ THÔNG TIN

1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN)

• Ưu điểm lớn nhất của giải thuật này là đơn giản.

• Dể dàng chứng minh sự đúng đắn: bằng cách phân tích hết không gian

nghiệm, nên nếu tồn tại một đáp án thì chắc chắn giải thuật sẽ tìm thấy.

• Thông thường trong thực tế giải thuật này thường được dùng để tìm giải

thuật hiệu quả hơn.

• Cần bao nhiêu phép so sánh cần để tìm giá trị M trong danh sách L trong

trường hợp xấu nhất?

5 KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ

• Giải thuật chia để trị bao gồm:

• Chia nhỏ vấn đề thành những vấn đề nhỏ giống nhau.

• Tiếp tục tìm đáp án trong những không gian nhỏ.

• Cuối cùng kết hợp các đáp án riêng lẻ thành một đáp án lớn cho vấn đề

chính.

• Công cụ chính thường dùng cho giải pháp chia để trị là đệ quy:

• Vấn đề chính được giảm thành một trường hợp cơ sở đơn giản nhất.

• Một trường hợp cơ sở được giải quyết, sau đó những vấn đề đơn giản

hơn có thể giải quyết.

6 KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ)

• Hãy tìm một người tên N trong danh sách L được sắp xếp theo bảng chữ cái:

• Giải thuật chia để trị sẽ thực hiện như sau:

• Nếu danh sách L chỉ có một phần tử sẽ được so sánh và trả về kết quả.

• Còn lại chia danh sách thành hai phần LeftHalf và RightHalf.

▪ Nếu N lớn hơn phần tử cuối cùng của LeftHalf lặp lại quá trình với

RightHalf.

▪ Còn lại thì lặp lại quá trình trên LeftHalf.

7 KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ)

8 KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG

• Giải thuật thực hiện như sau:

▪ Chia vấn đề thành những vấn đề con.

▪ Giải quyết các vấn đề con và nhớ kết quả của nó.

▪ Kết hợp thành đáp án cho vấn đề chính.

• Giải thuật phù hợp với các bài toán cần sử dụng nhiều lần vấn đề con khi

tính toán giải pháp cho vấn đề chính.

9 KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG

• Giải thuật thực hiện như sau:

▪ Chia vấn đề thành những vấn đề con.

▪ Giải quyết các vấn đề con và nhớ kết quả của nó.

▪ Kết hợp thành đáp án cho vấn đề chính.

• Giải thuật phù hợp với các bài toán cần sử dụng nhiều lần vấn đề con khi

tính toán giải pháp cho vấn đề chính.

10 KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci

• Đầu tiên, nếu dùng giải thuật brute-force để tính toán chuỗi số Fibonacci, giá

trị Fib(n) sẽ phụ thuộc vào tất cả giá trị phía trước Fib(n-1), Fib(n-2),

Fib(n-3)…

11 KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci

• Đối với trường hợp này chúng ta dùng giải

thuật quy hoach động để nhớ các giá trị phụ.

• Trước khi tính toán một giá trị, giải thuật kiểm

tra đáp án đã được ghi nhận (nhớ) chưa?

• Nếu rồi sẽ dùng giá trị lưu, còn chưa sẽ tính

toán và nhớ lại.

12 KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci • Việc nhớ yêu cầu dùng một cấu trúc dữ liệu giúp dễ dàng tìm kiếm.

• Để nhận ra lợi ích từ việc ghi lại các giá trị và tra cứu các giá trị được

tính toán trước, điều quan trọng là để các cấu trúc dữ liệu này hoạt động

hiệu quả

• Việc lựa chọn cấu trúc dữ liệu sẽ tác động đến hiệu quả tổng thể của các giải

pháp

• Cấu trúc dữ liệu sẽ được đề cập sau trong phần môn học…

13 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM

• Bài toán yêu cầu tìm kết quả tốt nhất từ một tập hợp các khả năng, ví dụ:

tuyến đường rẻ nhất, khoảng cách ngắn nhất, số đồng xu ít nhất.

• Chiến lược tham lam: Ở mỗi bước, hãy thực hiện lựa chọn tối ưu cục bộ và

hy vọng đạt được giải pháp tối ưu toàn cục.

14 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM

• Vấn đề tối ưu hóa là một vấn đề mà đề bài cần tìm, nhưng không chỉ là một giải

pháp mà còn là giải pháp khả thi tốt nhất.

• Các thuật toán tham lam thường hoạt động đủ tốt để tối ưu hóa vấn đề.

• Các thuật toán tham lam hoạt động bằng cách xác định giải pháp cho một vấn đề

nhỏ trung gian

• Bạn xác định giải pháp tốt nhất có thể cho vấn đề trung gian, không tính đến kết

quả tương lai

• Chiến lược là bằng cách chọn mức tối ưu cục bộ tại mỗi bước, để đạt được mức

tối ưu toàn cục.

15 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

• Giả sử rằng chúng tôi muốn đổi một số số tiền thành số lượng tối thiểu đồng xu gồm

penny (0.01USD), nickel(0.05USD), dime(0.1USD) và quarter(0.25USD)

• Chúng ta cần tìm A(Pennies) + B(Nickles) + C(Dimes) + D(Quarters) = số tiền cần

đổi …như vậy tổng của : A+B+C+D là số đồng xu nhỏ nhất có thể.

16 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

• Chiến lược tham lam hoạt động như sau:

• Bắt đầu với đồng quarter(0.25) và sử dụng càng nhiều xu càng tốt mà không

vượt quá số tiền yêu cầu.

• Nếu không đạt được tổng tiền, thì tiếp tục sử dụng càng nhiều xu dimes(.10)

càng tốt mà không vượt quá số tiền yêu cầu.

• Nếu không đạt được tổng số, thì tiếp tục sử dụng như nhiều xu niken (0.05) có

thể mà không vượt quá số tiền yêu cầu.

• Nếu không đạt được tổng số, thì tiếp tục sử dụng như nhiều xu penny (0.01) cần

thiết để đạt được số tiền yêu cầu.

17 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

18 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – phân tích

• Giải thuật có vấn đề thú vị như cần tối ưu hóa đủ cho hầu hết các trường hợp và vấn

đề có thể giải quyết thông qua tối ưu hóa các bài toán con.

• Dễ hiểu và dễ phát triển thuật toán khả thi.

• Có thể khó để cho thấy nó hoạt động, khi nó hoạt động và tại sao nó hoạt động…

• Bản chất của mọi bằng chứng thuật toán tham lam là để cho thấy rằng giải pháp

tổng thể tốt nhất có thể là đạt được thông qua tối ưu hóa các vấn đề phụ

19 KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – phân tích

• Trong một số trường hợp, các thuật toán tham lam sẽ không mang lại giải pháp tối

ưu

• Trong một số trường hợp, nó có thể mang lại câu trả lời chưa tốt.

• Trong một số trường hợp, giải thuật không trả lời được.

• Xét lại ví dụ trước, hãy tưởng tượng các xu chúng ta có là 0,25, 0,10 và 0,04 xu

• Bằng trực giác, chúng ta có thể đổi được 0,41 xu tiền lẻ thành 1x 0,25 + 4x0,04

• Thuật toán tham lam sẽ thất bại hoàn toàn – cần đổi với 0,39 hoặc 0,43 xu, như nó

sẽ đã cam kết sử dụng một xu

20 KHOA CÔNG NGHỆ THÔNG TIN

GIẢI THUẬT XÁC XUẤT

• Đôi khi việc tìm kiếm các giải pháp tối ưu mất nhiều chi phí và chúng ta sẵn sàng

dùng một giải pháp "đủ tốt" cho một nhóm các bài toán.

• Có một số thuật toán các kỹ thuật để tạo ra các giải pháp:

• Heuristic

• Xác suất,… chúng ta sẽ khám phá một số trong số này trong các slide sau

• Khái niệm "tính đúng đắn" cho những thuật toán sẽ khác!

21 KHOA CÔNG NGHỆ THÔNG TIN

…

• Chúng ta tiếp tục một số phương pháp tiếp cận thuật toán sau:

• thuật toán heuristic

• thuật toán xác suất

• Đây là những thuật toán hoàn hảo cho một thế giới không hoàn hảo!

22 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC

• Thuật toán - Quy tắc hoặc giải pháp, thủ tục cụ thể để đảm bảo cung cấp câu trả lời

đúng nếu theo trình tự đos.

• Heuristic - Quy tắc ngón tay cái hoặc chiến lược không chính thức, hoạt động theo

một số hoàn cảnh, nhưng không đảm bảo mang lại câu trả lời đúng, giống như kinh

nghiệm, hay thói quen.

23 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC

• Thuật toán - Quy tắc hoặc giải pháp, thủ tục cụ thể để đảm bảo cung cấp câu trả lời

đúng nếu theo trình tự đó.

• Heuristic - Quy tắc ngón tay cái hoặc chiến lược không chính thức, hoạt động theo

một số hoàn cảnh, nhưng không đảm bảo mang lại câu trả lời đúng, giống như kinh

nghiệm, hay thói quen.

24 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC

• Các thuật toán heuristic được bắt nguồn từ một sự kết hợp giữa kinh nghiệm, trực

giác và được biết đến một cách chính thức. Các thuật toán heuristic:

• Có thể đưa ra một giải pháp chấp nhận được cho một vấn đề (hoặc lớp vấn đề)

trong nhiều tình huống thực tế

• Được sử dụng nhưng không có bằng chứng chính thức về tính đúng đắn hoặc sự

tối ưu

• Đưa ra các câu trả lời đúng, nhưng thường không tính toán giải pháp tối ưu hoặc

sử dụng tài nguyên một cách tối ưu.

• Các thuật toán Heuristic được sử dụng khi không có giải pháp tối ưu, bị hạn chế về

thời gian, nguồn lực hoặc theo bất kỳ hoàn cảnh nào đó.

25 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC

• Hai mục tiêu chính của chúng ta là tìm thuật toán

• Với thời gian chạy và tài nguyên đã biết

• Tạo ra câu trả lời tối ưu

• Trong việc phát triển các thuật toán heuristic, nó là thường bỏ qua một hoặc cả hai

mục tiêu. Một thuật toán heuristic có thể tìm thấy:

• Giải pháp đủ tốt hoặc khá tốt – không khả năng chứng minh có những cái tốt

hơn

• Câu trả lời hiệu quả một cách hợp lý - không có bằng chứng nào cho thấy chúng

ta có thể làm tốt hơn.

26 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC – ví dụ

• Câu hỏi: Có nên mua nhà không?

• Giá thuê: 2 phòng ngủ, gara = $ 1600 mỗi tháng

• Mua: 3 phòng ngủ, gara, sân vườn = 250.000 USD

• Giảm 20% = $ 50k

• Khoản vay = $ 200k

• Lãi suất = 6%, hoặc $ 600 tháng trong 30 năm cho mỗi $ 100k

• Thế chấp = $ 1200

• Thuế & Bảo hiểm = $ 300

• Chi phí hàng tháng = $ 1500

• $ 1500 để mua <$ 1600 để thuê, vì vậy trong trường hợp này, chúng ta nên mua.

27 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC – ví dụ

• Chúng ta phát triển một thuật toán có thể tính toán chính xác mua hoặc thuê.

• Có những yếu tố khác mà chúng tôi có thể có hoặc không có thể định lượng trong

một thuật toán như vậy như:

• tiết kiệm thuế

• nâng cao giá trị tài sản, nhà lên giá

• liệu chúng ta sẽ sống trong ngôi nhà trong 5 năm

• thẩm mỹ: kiến trúc, nội ngoại thất ngôi nhà

• Tiện ích khu vực, hàng xóm, trường học, v.v.…

• Khi chúng ta thêm nhiều yếu tố, điều này càng phức tạp thuật toán và một số yếu tố

không xác định

28 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC – WHY?

• Nếu giải thuật Heuristics không được đảm bảo cung cấp giải pháp chính xác, vậy tại

sao mọi người sử dụng chúng?

• Chúng có thể giúp đơn giản hóa quyết định bằng cách một số phân tích hoặc

giảm một số yếu tố để đơn giản hóa việc đại diện và dễ dàng trong quyết định

thực hiện (hãy nghĩ về ví dụ mua so với thuê)

• Mặc dù chúng có thể không tạo ra một trả lời theo cách hiệu quả nhất, nhưng

câu trả lời có thể đủ tốt trong hầu hết trường hợp.

• Các thuật toán heuristic có thể là một tập các thiên vị, sai số và tính không chắc

chắn

29 KHOA CÔNG NGHỆ THÔNG TIN

5. XÂY DỰNG GIẢI THUẬT HEURISTIC

• Các thuật toán heuristic thường được xây dựng từ các mô hình dựa trên các loại

tương tự ghép nối vấn đề-giải pháp

• “Nếu nó có mỏ rộng, phẳng, ... nếu nó biết bơi,… thì nó có khả năng là một con

vịt ”

• Các giải pháp thuật toán heuristic đi kèm với một số mức độ

tin cậy (có thể dự đoán được)

• Trong ví dụ trên, chúng ta có thể đưa ra một kết luận không chính xác với thông

tin đã cho.

• Tuy nhiên, nếu chúng tôi thêm vào,… “Nếu nó tạo ra một âm thanh quác quác,…

”thì kết quả sẽ chắc chắn hơn

30 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Bài toán kinh điển.

• Vấn đề tìm đường đi cho người giao hàng là một trong những vấn đề tính toán khó

đã biết:

• Một người giao hàng phải đến n địa điểm, đi qua mỗi địa điểm chỉ một lần, bắt

đầu từ một trong số chúng là kho hàng, và quay trở lại nó. Chi phí(khoảng cách)

vận tải giữa các địa điểm đã có.

• Vấn đề là đến thăm từng địa điểm theo cách nào để giảm thiểu chi phí

• Giả sử các địa điểm nằm trong một mảng từ 1 đến n, với Add[i] là địa chỉ của điểm i

• Giả sử một ma trận chi phí sao cho cost(i, j) là chi phí đi từ Add[i] đến Add[j]

31 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Bài toán kinh điển.

• Nếu bạn chọn tính toán tất cả những giải pháp có thể và tính toán câu trả lời tối ưu

• nó sẽ mất (n-1)! các lần lặp lại. Điều này thực sự có nghĩa là?

• Giả sử có 21 địa chỉ, các lần bắt buộc để tìm ra giải pháp tối ưu sẽ là 20! hoặc là

2,432,902,008,176,640,000 lần

• Nếu mỗi lần tính yêu cầu 1 mili giây thì nó sẽ mất khoảng 800 thế kỷ để tính toán

• kiểm tra toàn diện tất cả các giải pháp khả thi là ….

32 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Bài toán kinh điển.

• Nếu bạn chọn tính toán tất cả những giải pháp có thể và tính toán câu trả lời tối ưu

• nó sẽ mất (n-1)! các lần lặp lại. Điều này thực sự có nghĩa là?

• Giả sử có 21 địa chỉ, các lần bắt buộc để tìm ra giải pháp tối ưu sẽ là 20! hoặc là

2,432,902,008,176,640,000 lần

• Nếu mỗi lần tính yêu cầu 1 mili giây thì nó sẽ mất khoảng 800 thế kỷ để tính toán

• kiểm tra toàn diện tất cả các giải pháp khả thi là ….

33 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Bài toán kinh điển 🡪 Heuristic .

• Vì chúng ta không có thuật toán tốt hơn tìm ra giải pháp tốt nhất, chúng tôi sẽ sử

dụng thuật toán heuristic như sau:

• Giả sử rằng nhân viên giao hàng ở Add[i]

• Lựa chọn của anh ấy (hoặc cô ấy) cho địa điểm tiếp theo để ghé thăm nên được

chọn trong đó cost[i, j] là chi phí nhỏ nhất trong tất cả các cost[i, j], trong đó j là

những điểm mà nhân viên giao hàng chưa đến thăm

• Điều này chắc chắn tốt hơn (về mặt tính toán) so với đang làm (n-1)! lặp lại…

34 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Bài toán kinh điển 🡪 Heuristic .

• Thuật toán này dựa trên thuật toán tham lam chọn chi phí rẻ nhất ở mỗi bước - giả

định là tổng các giải pháp từng phần sẽ là giải pháp tổng thể tốt nhất.

• Mặc dù điều này có thể mang lại câu trả lời đủ tốt, nó sẽ không phải là câu trả lời tối

ưu.

• Ví dụ như chuyến đi cuối cùng về nhà có thể sẽ tốn kém hơn tối ưu và điều này có

thể không đủ tốt trong vài trường hợp cụ thể!

35 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Ứng dụng phổ biến.

• Có nhiều loại vấn đề thuật toán heuristic được sử dụng:

• phân tích tiếp thị và bán hàng.

• chẩn đoán y tế và truyền mầm bệnh.

• điều tra dân số, nhân khẩu học và phân tích dân số.

• tài chính và phân tích thị trường tài chính

• thống kê bảo hiểm và phân tích tính toán

• kiểm tra chính tả và ngữ pháp

• nhận dạng giọng nói

• • trí tuệ nhân tạo… và những thứ tương tự khác các ứng dụng…

36 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Tradeoff.

• Heuristics nhằm thúc đẩy:

• hiệu suất tính toán

• đơn giản hóa các vấn đề.

• Heuristics thường đi kèm với chi phí

• độ chính xác và / hoặc độ chính xác

• hiệu quả tính toán

• thuyết tất định

• Một thuật toán heuristic thường là tốt nhất mà chúng tôi có thể làm được, tuy nhiên,

chúng ta thường phải định lượng lại ý nghĩa của "tốt nhất“.

37 KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC Chuyên sâu.

• Do thời gian, chúng ta sẽ không khám phá nhiều thuật toán heuristic hoặc ví dụ

• Chỉ riêng nhiều thuật toán này có thể chủ đề của một khóa học nâng cao trong

• các thuật toán. Một số công việc thú vị bao gồm:

• Simulated Annealing Algorithm

• Tabu Search Algorithm

• Swarm Intelligence

• Evolutionary Algorithms

• Neural Networks

• Support Vector Machines (SVMs)

38 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT

• Thuật toán xác suất là một thuật toán mà kết quả, cách tìm kết quả có được phụ thuộc

vào cơ hội.

• Các thuật toán xác suất còn được gọi là thuật toán ngẫu nhiên.

• Các thuật toán xác suất thường được sử dụng khi mô phỏng hành vi của một thực hệ

thống theo thời gian như:

• hành vi con người

• hệ thống tài chính

• hệ thống sinh học

• tổ chức, ... và v.v.

39 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT

• Một số vấn đề xác định được sử dụng các thuật toán xác suất giải quyết (như những

thuật toán trong một mô phỏng) và quan sát các xu hướng hoặc ước lượng một giải

pháp theo thời gian.

• Trong thực tế, ngẫu nhiên các thuật toán được ước lượng bằng cách sử dụng công cụ

tạo số giả (PNG)

• Trong một số trường hợp, PNG có thể lệch khỏi dự đoán hành vi lý thuyết

• Hầu hết các triển khai PNG đều đủ tốt nguồn ngẫu nhiên cho hầu hết các thuật

toán ngẫu nhiên

40 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT

• Độ trung thực của các giải pháp được tạo ra bởi thuật toán xác suất luôn gần đúng,

nhưng thường được cải thiện tính toán được tăng lên:

• tính toán các tích phân xác định

• dự đoán hành vi thị trường tài chính

• mô hình hóa tải mạng

• lập mô hình lưu lượng truy cập

• Các kỹ thuật áp dụng xác suất thuật toán cho các bài toán số là ban đầu được gọi là

phương pháp Monte Carlo

41 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – why use?

• Các thuật toán xác suất:

• Sử dụng kết quả của một quá trình ngẫu nhiên như một phần thiết yếu của thuật

toán.

• Về cơ bản là "đoán" diễn biến tiếp theo của thực hiện nên được.

• Tại sao bạn làm điều này?

• Tiết kiệm khi tính toán lựa chọn tốt nhất thực tế,đặc biệt là trong trường hợp

chúng tôi biết tốt nhất sự lựa chọn là không thể tính toán.

• Tránh đưa ra một sai lệch tính toán (mô hình thiên vị) thường phổ biến trong các

thuật toán heuristic.

• Chúng ta có thể đảm bảo tính đúng đắn trong một số xác suất thống kê.

42 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – ưu điểm?

• Một khuyến khích cho việc sử dụng thuật toán xác suất là ứng dụng của họ thường

không yêu cầu toán học phức tạp

• Việc lập trình thường không đơn giản, có nghĩa là một ước lượng chấp nhận được

có thể được tính toán nhanh.

• Trong một số trường hợp, thuật toán xác suất là thuật toán đơn giản và hiệu quả nhất

có sẵn cho nhiều vấn đề phức tạp kinh điểm.

43 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – ví dụ Bữa tối của các nhà triết học

• Hãy tưởng tượng năm triết gia đang ngồi tại một bàn, với một tô mì lớn ở trung tâm,

ăn uống hoặc suy nghĩ như sau:

• Mỗi nhà triết học, có một chiếc đũa cho bên phải và một bên trái của họ

• Người ta cho rằng một triết gia phải dùng bữa với hai chiếc đũa

• Nhà triết học chỉ có thể sử dụng chiếc đũa bên trái hoặc bên phải anh ấy hoặc cô

ấy.

• Trong khi các triết gia đang ăn, họ không suy nghĩ, và trong khi suy nghĩ, họ

không ăn.

• Các triết gia không bao giờ nói chuyện với nhau, điều này tạo ra khả năng bế tắc

44 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – ví dụ Bữa tối của các nhà triết học

• Vấn đề này là một vấn đề bế tắc kinh điển có thể được giải quyết bằng thuật toán xác

suất:

45 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – ví dụ Bữa tối của các nhà triết học

• Thuật toán này sử dụng cách tung đồng xu ngẫu nhiên để phân xử giữa chiếc đũa nào để

nhặt lên.

• Thuật toán này không có bế tắc với một xác suất 1 (không nhỏ,… không)

• Cách duy nhất để thoát khỏi bế tắc là nếu tất cả các thực khách đồng thời nhận được

đầu hoặc đuôi liên tục và mãi mãi - về mặt lý thuyết là có thể nhưng ở xa vời.

• Cho rằng một lần tung đồng xu có thể có hai kết quả ở cơ hội 50-50, sau đó ở trên

tình huống thực tế là một sự kiện không có xác suất.

• Lưu ý rằng thuật toán này rất đơn giản và giải pháp rất hiệu quả cho một vấn đề

phức tạp

46 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – ví dụ Bữa tối của các nhà triết học

• Có vấn đề với thuật toán này như tốt:

• Không có bằng chứng trực tiếp rằng điều này cụ thể thuật toán không có bế tắc - chỉ

bằng chứng gián tiếp đưa ra những gì chúng ta biết về thống kê tung đồng xu.

• Không có bằng chứng trực tiếp thuật toán này dẫn đến công bằng - với xác suất

thống kê của một 50% kết quả theo thời gian, chúng tôi có thể kết luận rằng theo

thời gian, thuật toán công bằng

• Không có bằng chứng trực tiếp rằng thuật toán này là không bị chết đói - một lần

nữa chúng tôi giả định một thống kê xác suất của một kết quả 50% theo thời gian,

chúng tôi có thể kết luận rằng không có một triết gia nào bị bỏ đói.

47 KHOA CÔNG NGHỆ THÔNG TIN

6. GIẢI THUẬT XÁC SUẤT – Trade-off

• Chúng tôi thường mong đợi các thuật toán máy tính hành xử chính xác theo cùng một

cách Tuy nhiên, mọi lúc, điều này thường có nghĩa là rằng một số lớp vấn đề không thực

tế có thể giải quyết được:

• Các thuật toán xác suất từ bỏ thuộc tính này - luôn luôn có khả năng xảy ra thuật

toán sẽ tạo ra một kết quả sai

• Các lập trình viên có nghĩa vụ phải chỉ ra rằng cơ hội thất bại là rất nhỏ

48 KHOA CÔNG NGHỆ THÔNG TIN

49 KHOA CÔNG NGHỆ THÔNG TIN

CẦN PHÂN TÍCH NHỮNG GÌ?

• Cho đoạn code phía dưới, chúngta có thể phân tích: • Tốc độ tính toán thực thi nhanh như thế nào? • Bao nhiêu bộ nhớ yêu cầu cho giải thuật • Độ chính xác của giải thuật

• Chúng ta sẽ phântích dựa vào những điều chúng ta

biết.

50 KHOA CÔNG NGHỆ THÔNG TIN

WHICH IS “FASTER”?

51 KHOA CÔNG NGHỆ THÔNG TIN

VAI TRÒ CỦA PHẦN CỨNG TRONG PHÂN TÍCH GIẢI THUẬT

• Chắc chắn là kết quả chay n giá trị thì Deep Blue sẽ nhanh hơn.

• Tuy nhiên điều này không xác định là giải thuật tốt bởi tốt có nghĩa là tính kinh

tế khi chạy chương trình.

• Hiệu suất của giải thuật, chúng ta không xét các thông số phần cứng, khả năng

của flatform với đánh giá giải thuật.

52 KHOA CÔNG NGHỆ THÔNG TIN

VAI TRÒ CỦA NGÔN NGỮ MÁY TRONG PHÂN TÍCH GIẢI THUẬT

• Chúng tôi có thể xem xét các vấn đề ngôn ngữ:

• biên dịch hay thông dịch ngôn ngữ.

• Hiệu quả của tệp thực thi.

• Chúng tôi có thể kiểm tra từng dòng lệnh cô lập và sau đó:

• Kiểm tra từng dòng lệnh cô lập

• Tổng hợp chi tiết phân tích các dòng lệnh.

• Rút ra kết luận về vai trò của ngôn ngữ trong hiệu suất

53 KHOA CÔNG NGHỆ THÔNG TIN

PHÂN TÍCH GIẢI THUẬT-nguyên tắc 1

• Tách phân tích thuật toán khỏi phần cứng và ngôn ngữ máy tính:

• Tất nhiên là vấn đề phần cứng, nhưng hiệu suất của tất cả phần cứng phụ

thuộc vào phần mềm, thuật toán và cấu trúc dữ liệu.

• Ngôn ngữ chắc chắn đóng một vai trò trong hiệu suất, nó có xu hướng là một

hằng số có thể được tính toán khi phân tích thuật toán

• Vì những lý do này, chúng tôi cần phân tích hiệu suất thuật toán tách biệt khỏi

phần cứng mà nó chạy trên

54 KHOA CÔNG NGHỆ THÔNG TIN

PHÂN TÍCH GIẢI THUẬT-nguyên tắc 2

• Dùng toán học vừa đủ và không nhiều hơn:

• Phân tích chi tiết, chính thức và hoàn toàn nghiêm ngặt liên quan đến toán

học phức tạp:

• Đây có thể là một nguồn lỗi mới khi phân tích thuật toán.

• nó cần nhiều thời gian để có giá trị đúng trong hầu hết vấn đề trong thế

giới thực.

• Nó hữu ích và thiết thực hơn để:

• Sử dụng toán học đơn giản cho phép chúng ta phân tích xu hướng thuật toán.

• Tập trung vào bản chất của thuật toán đóng góp đáng kể nhất vào tăng trưởng

- phần còn lại có thể được trừu tượng hóa phần còn lại

55 KHOA CÔNG NGHỆ THÔNG TIN

•

Tại sao quan tâm? Các thuật toán được thiết kế kém:

• Có thể khiến bạn nghĩ rằng bạn cần nhiều hơn phần cứng tinh vi, nhanh hơn

và đắt tiền.

• Sẽ không sử dụng hết phần cứng hiệu quả

• Có thể dẫn đến phần mềm cồng kềnh, phức tạp gây khó khăn cho việc gỡ lỗi

và bảo trì.

• Thường là nguồn gốc của các lỗi phức tạp rất khó để tìm ra cách sửa chữa

56 KHOA CÔNG NGHỆ THÔNG TIN

NHU CẦU 🡪 GIẢI PHÁP

• Một thuật toán mô tả một thủ tục tính toán cụ thể cho đạt được mối quan hệ đầu

vào / đầu ra được chỉ định bởi yêu cầu

57 KHOA CÔNG NGHỆ THÔNG TIN

CẦN PHÂN TÍCH NHỮNG GÌ?

58 KHOA CÔNG NGHỆ THÔNG TIN

ĐIỀU CHÚNG TA CẦN • Những gì chúng tôi cần để hỗ trợ phân tích:

• Một cách mô tả các thủ tục thuật toán trong điều khoản của:

• Các thao tác cơ bản

• Cấu trúc điều khiển để kết hợp các hành động cơ bản

• Một cách mô tả dữ liệu mà thuật toán hoạt động trên:

• Dữ liệu cơ bản phi cấu trúc

• Dữ liệu có cấu trúc

• Tìm hiểu thêm về điều này phần sau trong môn học…

59 KHOA CÔNG NGHỆ THÔNG TIN

MỐI QUAN TÂM CHÍNH

• Các thao tác của thuật toán phải được thực hiện trong một khoảng thời gian hữu

hạn bằng cách sử dụng một lượng tài nguyên hữu hạn:

• Các thao tác mất nhiều thời gian là không tốt

• Các thao tác yêu cầu tài nguyên vô hạn là không tốt

• Những gì chúng ta coi là một hành động cơ bản sẽ phụ thuộc vào mức độ trừu

tượng, nhưng xem xét các nguyên tắc # 1 và # 2

• Giữ ngôn ngữ trung lập

• Bỏ qua phần cứng

• Giữ cho phép toán càng đơn giản càng tốt

• Tập trung vào bản chất thuật toán

60 KHOA CÔNG NGHỆ THÔNG TIN

Thao tác cơ bản

• Khai báo

• Kiểu biến;

• int A; string name

• Gán

• Biến = giá trị;

• a = 45; x = y

• Các toán tử toán học cơ bản

• Result = variable-value operator variable-value

• y = a+b; z = 5.0/e; j = k*l; r = 2*(22/7)*(r^2)

61 KHOA CÔNG NGHỆ THÔNG TIN

Thao tác cơ bản

• Các chức năng và chương trình con cơ bản

• Read (), write (), print (), ..

• Các chức năng giả định phải được xác định rõ ràng trước khi sử dụng

• Tìm hiểu thêm về các hàm và chương trình con sau này

62 KHOA CÔNG NGHỆ THÔNG TIN

Cấu trúc điều khiển

• Cấu trúc kiểm soát cần thiết

• Cấu trúc điều khiển

• Trình tự trực tiếp

• do X, then do Y

• Rẻ nhánh

• if Q then do X, else do Y

• Vòng lặp

• do Z exactly X times

• do Z until Q becomes true

• while Q is

63 KHOA CÔNG NGHỆ THÔNG TIN

Ví dụ

• Ở đây chúng tôi xác định một hàm Euclidian cho tìm mẫu số chung lớn nhất

• Hàm read () giả định đọc dữ liệu người dùng nhập từ một số nguồn - bản chất

chính xác của việc làm thế nào là không quan trọng đối với phân tích của

chúng ta.

• Lưu ý rằng chúng tôi tập trung vào bản chất của thuật toán, không kiểm tra

đầu vào, định dạng đầu ra, xử lý lỗi và vân vân ... chúng trở thành hằng số

• Thuật toán đã được chắt lọc bản chất. Bây giờ chúng ta có thể phân tích: cách

nào chúng ta giải quyết vấn đề? Làm sao nó nhanh chóng tính toán câu trả

lời? ...

64 KHOA CÔNG NGHỆ THÔNG TIN

ĐO LƯỜNG VÀ PHÂN TÍCH GIẢI THUẬT – KÝ HIỆU O

65 KHOA CÔNG NGHỆ THÔNG TIN

XU HƯỚNG CỦA HÀM

• Giả sử chúng ta có một thuật toán F:

• Giả sử rằng thời gian chạy của thuật toán là: T = F (n) với n là lần lặp F (n)…

• Qua quan sát, chúng tôi ghi nhận:

• T = F (0) = 1

• T = F (1) = 4

• T = F (2) = 9

• …

• … chúng ta có thể kết luận rằng thời gian thực hiện cho F (n) = (n + 1)2

66 KHOA CÔNG NGHỆ THÔNG TIN

XU HƯỚNG CỦA HÀM

• Thử mô tả đặc điểm của hiệu suất của thuật toán này trên tổng số ứng dụng thời

gian chạy:

• Chúng tôi biết từ ví dụ trước của chúng tôi rằng: F (n) = (n + 1)2…

• Chúng ta có thể khái quát thêm điều này là: F (n) = (n + c)2… trong đó c là

hằng số

• Nếu chúng ta xem xét tổng quát của thuật toán trên tổng số thực thi:

• Trong trường hợp này, chúng tôi sẽ nói rằng điều này hiệu suất của thuật toán có

thể được đặc trưng là O (n2),… hoặc “Big-Oh” của n bình phương

67 KHOA CÔNG NGHỆ THÔNG TIN

XU HƯỚNG CỦA HÀM

• Sử dụng ví dụ này làm cơ sở để ví dụ về thời gian chạy…

• thời gian chạy của giải thuật

• Do đó, nói chung, chúng ta nói rằng chương trình có thời gian chạy là: O(F(n))…

hoặc… O (n)

• Chúng ta có thể nói rằng các chương trình có thể được đánh giá bằng cách so

sánh thời gian chạy của chúng hàm và bỏ qua hằng số tỷ lệ.

68 KHOA CÔNG NGHỆ THÔNG TIN

Xu hướng chính

• Giả sử chúng ta có một thuật toán với thời gian chạy của n3 + n2

• Điểm lớn của thuật toán này là gì?

• O (n3 + n2)?

• O (n3)?

• O (n2)?

• Số hạng có nghĩa nhất trong n3 + n2 là n3,…

• Chúng tôi có thể chứng minh điều này bằng rất nhiều phép toán xấu xí, hoặc

sử dụng một chút thông thường và một Excel bảng tính

69 KHOA CÔNG NGHỆ THÔNG TIN

Xu hướng chính

• Lưu ý rằng:

• n2 thể hiện một đường cong

khác đáng kể

• đường cong n3 + n2 gần giống

với đường cong cho n3

• chúng ta có thể kết luận rằng

n3 mô tả chính xác hiệu suất

của thuật toán này

70 KHOA CÔNG NGHỆ THÔNG TIN

Tại sao phải xem xét xu hướng tăng trưởng? • Tỷ lệ tăng trưởng có thể cho chúng tôi biết vấn đề chúng tôi có thể giải quyết và

có thể là một dấu hiệu cho thấyvấn đề có thể không giải quyết được

• Xem xét các thuật toán với cách chạy sau lần:

• • 100n

• • 5n2

• • n3 / 2

• • 2n

71 KHOA CÔNG NGHỆ THÔNG TIN

• Giả sử chúng ta có 1000s để chạy cùng 1

vấn đề,…

• Mức độ lớn của một vấn đề chúng ta có

thể giải quyết với từng những thuật toán

này

72 KHOA CÔNG NGHỆ THÔNG TIN

• Giả sử chúng ta có máy tính mạnh hơn 10

lần thì,…

• Mức độ lớn của một vấn đề chúng ta có

thể giải quyết với từng những thuật toán

này

73 KHOA CÔNG NGHỆ THÔNG TIN

Kết luận -1

• Rõ ràng là O (n) cho thuật toán 100n hoạt động tốt nhất theo thời gian, nhưng

những gì khác làm chúng tôi biết?

• Phân tích này cho chúng ta thấy rằng những cải tiến trong hiệu suất bộ xử lý

không chuyển thành các cải tiến tuyến tính trong hiệu suất hệ thống

74 KHOA CÔNG NGHỆ THÔNG TIN

Kết luận - 2

• Điều này làm nổi bật tầm quan trọng của các thuật toán xét về hiệu suất hệ thống.

• Miễn là chúng ta giải quyết dần dần các vấn đề lớn hơn và phức tạp hơn, chúng

ta đi đến một kết luận gần như nghịch lý:

• Khi công suất máy tính tăng và giá cả giảm, chúng tôi sẽ được thử thách để

giải quyết những vấn đề lớn hơn và phức tạp hơn

• Do đó, sự lựa chọn khôn ngoan của các thuật toán và phân tích chúng sẽ luôn

là một phần quan trọng của thiết kế phần mềm

75 KHOA CÔNG NGHỆ THÔNG TIN

Kết luận - 3

• Nếu thuật toán của bạn là O (2n) trong thời gian và đầu vào có kích thước n≥64

trở lên, đó là đầu vào lớn

• Phân tích Big Oh ngay lập tức cho bạn biết không có điểm nào làm chi tiết hơn

• phân tích, thực hiện các nghiên cứu về thời gian,hợp ngữ, mua bộ xử lý nhanh

hơn,…

• Sẽ mất nhiều hơn một trăm năm, ngay cả khi bạn có thể có được vòng lặp bên

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trường ĐH Văn Lang

KHOA CÔNG NGHỆ THÔNG TIN

CẤU TRÚC DỮ LIỆU & GIẢI (Data Structure and Algorithm) THUẬT

CHƯƠNG 1: GIỚI THIỆU VÀ ĐÁNH GIÁ GIẢI THUẬT

GVGD:

HỌC KỲ I – NĂM HỌC 2020-2021

KHÓA 25T-IT

MỘT SỐ NHÓM GIẢI THUẬT CƠ BẢN

01.

CÁC VẤN ĐỀ PHÂN TÍCH GIẢI THUẬT

02.

CẤU TRÚC NGÔN NGỮ MÁY TÍNH

03.

NỘI DUNG

GIỚI THIỆU PHÂN TÍCH GIẢI THUẬT

04.

MỘT SỐ NHÓM GIẢI THUẬT PHỔ BIẾN

3

KHOA CÔNG NGHỆ THÔNG TIN

1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN)

4

KHOA CÔNG NGHỆ THÔNG TIN

1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN)

5

KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ

6

KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ)

7

KHOA CÔNG NGHỆ THÔNG TIN

2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ)

8

KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG

9

KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG

10

KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci

11

KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci

12

KHOA CÔNG NGHỆ THÔNG TIN

3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci • Việc nhớ yêu cầu dùng một cấu trúc dữ liệu giúp dễ dàng tìm kiếm.

13

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM

14

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM

15

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

16

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

17

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – ví dụ

18

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – phân tích

19

KHOA CÔNG NGHỆ THÔNG TIN

4. GIẢI THUẬT THAM LAM – phân tích

20

KHOA CÔNG NGHỆ THÔNG TIN

GIẢI THUẬT XÁC XUẤT

21

KHOA CÔNG NGHỆ THÔNG TIN

…

22

KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC

23

KHOA CÔNG NGHỆ THÔNG TIN

5. GIẢI THUẬT HEURISTIC