Bài giảng Các vấn đề cơ sở của khoa học máy tính: Chương 2 - ThS. Tô Oai Hùng

Bài giảng Các vấn đề cơ sở của khoa học máy tính - Chương 2: Giải thuật" trình bày các nội dung: Định nghĩa giải thuật, ví dụ về giải thuật, đặc tả giải thuật, phân tích giải thuật, giải thuật là công nghệ, mô hình hình thức tính toán. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Các vấn đề cơ sở của khoa học máy tính: Chương 2 - ThS. Tô Oai HùngChương 2: GIẢI THUẬT Nội Dung1. Định nghĩa giải thuật .2. Ví dụ về giải thuật.3. Đặc tả giải thuật.4. Phân tích giải thuật.5. Giải thuật là công nghệ.6. Mô hình hình thức tính toán. 2Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Nghĩa Giải Thuật• Định nghĩa giải thuật: Giải thuật là cách thức để giải quyết một tập các vấn đề.• Thuật ngữ “giải thuật” cũng áp dụng cho bất kỳ cách thức nào để giải quyết một vấn đề cụ thể. Cho ví dụ, các bước để thay phanh xe cũng được gọi là giải thuật.• Ví dụ: Tìm ước số chung lớn nhất.• Trong toán học, một giải thuật nổi tiếng và hữu dụng là giải thuật Euclid để tìm ước số chung lớn nhất (GCD) của hai số nguyên. Ông đã đưa ra giải thuật này vào khoảng 300 năm trước công nguyên.• Không có giải thuật Euclid, chúng ta tìm 3Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật GCD(372, 84) như thế nào? Phải phân tích hai số nguyên thành các thừa số nguyên tố và tìm thừa số chung lớn nhất.• Nếu các số nguyên này lớn, việc phân tích thành các thừa số trở nên khó khăn và tốn nhiều thời gian. Euclid đã tìm ra giải thuật một cách có hệ thống và nhanh chóng giảm kích thước của vấn đề, bằng cách thay giá trị ban đầu của hai số nguyên với giá trị nhỏ hơn cho đến khi một trong hai số bằng 0. Lúc này, GCD của hai số chính là giá trị của số còn lại.• Sau đây là giải thuật Euclid để tìm GCD của 4Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật hai số nguyên A và B: Repeat: Nếu B = 0, GCD(A, B) = A Ngược lại: Thay R bằng A modulo B Thay A bằng B Thay B bằng R• Cho ví dụ, để tìm GCD của 372 và 84: - Tìm GCD(84, 36) vì 372 % 84 = 36 - Tìm GCD(36, 12) vì 84 % 36 = 12 - Tìm GCD(12, 0) vì 36 % 12 = 0 - Vậy GCD(372, 84) = 12 5Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật• Như vậy, giải thuật là một chuỗi các phép toán thao tác trên tập giá trị nhập và sinh ra kết quả trong khoảng thời gian hữu hạn. Trong ví dụ trên, tập giá trị nhập là 2 số nguyên. Kết quả là ước số chung lớn nhất của hai số đó.• Có nhiều cách để giải quyết một lớp các vấn đề. Câu hỏi đặt ra là giải thuật nào tốt nhất? Thông thường, các nhà khoa học máy tính sử dụng các kỹ thuật để phân tích, đánh giá và so sánh hiệu quả giữa các giải thuật. 6Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật• Đặc tả giải thuật (representing algorithm): Trong ngành khoa học máy tính, giải thuật thường được đặc tả bằng mã giả (pseudocode). Mã giả đủ để cho một ngôn ngữ lập trình có thể thể hiện các tác vụ mà máy tính phải thực hiện trong giải thuật.• Mã giả cũng độc lập với bất kỳ ngôn ngữ lập trình nào. Nó thể hiện chi tiết cú pháp và làm cho người lập trình dễ dàng đặc tả các thao tác cốt lõi của một giải thuật.• Không có một mẫu chuẩn nào cho mã giả. Các nhà khoa học máy tính sử dụng mã giả của riêng mình để đặc tả một giải thuật. Ví dụ sau là một kiểu mã giả đặc tả giải thuật GCD: 7Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải ThuậtGCD(a, b) - Tên hàm và đối số While b != 0 - Trong khi b khác 0 { - Bắt đầu thân vòng lặp r ← a mod b - Gán r = a modulo b a←b - Gán a = giá trị ban đầu của b b←r - Gán b = r } - Kết thúc thân vòng lặpreturn a - Khi b = 0, kết quả trả về là a• Để minh hoạ thế nào là hiệu quả khác nhau giữa các giải thuật, chúng ta sẽ thảo luận về sự đa dạng của các giải thuật mà các nhà khoa học máy tính đã đưa ra để giải quyết các vấn đề phổ biến trong tính toán. 8Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật• Tìm kiếm tuần tự (sequential search): Giả sử chúng ta có danh sách của các sinh viên trong một lớp học, yêu cầu là hãy tìm tên của sinh viên Debbie Drawe. Giải thuật tìm kiếm tuần tự chỉ đơn giản là so sánh mỗi tên trong danh sách với tên cần tìm. Quá trình tìm kiếm kết thúc khi tên được tìm thấy hoặc khi giải thuật đã tìm hết tất cả các tên trong danh sách.• Sau đây là mã giả của giải thuật tìm kiếm tuần tự: 9Các Vấn Đề Cơ Sở của KHMT ...