zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Hệ điều hành

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

Chia sẻ: Minh Anh | Ngày: | Loại File: PDF | Số trang:40

Báo xấu

72
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Chương 2: GIẢI THUẬT
Nội Dung 1. Đị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. 2 Cá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 3 Cá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 4 Cá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 5 Cá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. 6 Cá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: 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng
Đặc Tả Giải Thuật GCD(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ặp return 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. 8 Cá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ự: 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng
Đặc Tả Giải Thuật Sequential_Search(listNames, name) length ← length of listNames matchFound ← false index ← 1 while matchFound = false AND index
Phân Tích Giải Thuật • Phân tích giải thuật (analyzing algorithm): Nếu chúng ta biết chiều dài của mỗi câu lệnh và có bao nhiêu tên trong danh sách, chúng ta có thể tính được thời gian để thực thi giải thuật. • Tuy nhiên, thường thì chúng ta không biết giải thuật giải quyết vấn đề trong bao lâu và thời gian cần giải quyết vấn đề sẽ thay đổi theo độ lớn của vấn đề. • Giải thuật tìm kiếm tuần tự sẽ cần thời gian lâu hơn nếu số lần so sánh nhiều hơn. Những lệnh khác của giải thuật chỉ thực thi 1 lần, nhưng những lệnh trong vòng lặp sẽ 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng
Phân Tích Giải Thuật thực thi nhiều lần miễn là điều kiện lặp còn đúng. • Nếu tên cần tìm cần tìm nằm giữa danh sách thì giải thuật sẽ chỉ tìm một nửa danh sách. Nhưng nếu tên cần tìm ở cuối hoặc không có trong danh sách thì giải thuật sẽ phải tìm tất cả các tên trong danh sách. • Thời gian thực thi của giải thuật tìm kiếm tuần tự sẽ tăng tỷ lệ theo kích thước của danh sách. • Chúng ta nói rằng “bậc tăng” của giải thuật tìm kiếm tuần tự là n, ký hiệu là T(n). Chúng ta cũng nói rằng một giải thuật mà bậc tăng của nó giới hạn trong một yếu tố không đổi 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng
Phân Tích Giải Thuật nào đó có theta của n, ký hiệu Θ(n). Lưu ý: T(n) là hàm theta của g(n): T(n) = Θ(g(n)) nếu ∃ các hằng số dương c1, c2, n0 sao cho với mọi n >= n0: c1g(n)
Phân Tích Giải Thuật Insertion_Sort(numList) length ← length of numList numIndex ← 2 while(numIndex 0 { numList[sortedIndex + 1] ← numList[sortedIndex] sortedIndex ← sortedIndex - 1 } numList[sortedIndex + 1] = newNum numIndex ← numIndex + 1 } end 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng
Phân Tích Giải Thuật • Để phân tích thời gian thực thi của giải thuật sắp xếp bằng phương pháp chèn trực tiếp, đầu tiên chúng ta lưu ý là thời gian thực thi tỷ lệ với số phần tử cần sắp xếp n. Ngoài ra, mỗi phần tử đang xét phải được so sánh một hay nhiều lần với các phần tử đã được sắp. Trong trường hợp tốt nhất, danh sách cần sắp xếp đã có thứ tự rồi, khi này mỗi phần tử chỉ so sánh một lần, vì thế trường hợp tốt nhất của giải thuật là Θ(n). • Trong trường hợp xấu nhất, danh sách cần sắp xếp có thứ tự ngược, khi này mỗi phần tử đang xét sẽ so sánh với tất cả phần tử đã 15 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng
Phân Tích Giải Thuật được sắp. Phần tử thứ 2 so sánh với phần tử đầu, phần tử thứ 3 so sánh với phần tử thứ 2 và phần tử đầu, … Ví dụ danh sách có 4 phần tử có thứ tự ngược, số lần so sánh sẽ là 6. Nói chung, số lần so sánh trong trường hợp xấu nhất của giải thuật này là 𝑛𝑛 𝑛𝑛 + 1 𝑛𝑛2 − 𝑛𝑛 − 𝑛𝑛 = 2 2 • Khi n lớn thì n2 lớn hơn rất nhiều so với n, vì vậy thời gian thực thi của giải thuật trong trường hợp này là T(n) = Θ(n2). • Trong trường hợp trung bình, mỗi phần tử đang xét sẽ so sánh với một nửa phần tử đã 16 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng
Phân Tích Giải Thuật được sắp. Vì vậy, thời gian thực thi của giải thuật trong trường hợp này cũng là T(n) = Θ(n2). 3. Sắp xếp bằng phương pháp trộn (merge sort) - thời gian thực thi T(n) = Θ(n log2n): merge(listA, listB) index ← 1 while listA is not empty AND listB is not empty if listA[1] < listB[1] sortedList[index] ← listA[1] discard listA[1] 17 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng
Phân Tích Giải Thuật else sortedList[index] ← listB[1] discard listB[1] index ← index + 1 while listA is not empty sortedList[index] ← listA[1] discard listA[1] index ← index + 1 while listB is not empty sortedList[index] ← listB[1] discard listB[1] index ← index + 1 return sortedList 18 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng
Phân Tích Giải Thuật • Trong hàm merge(), các phần tử được di chuyển từ một trong hai danh sách ban đầu là listA và listB vào danh sách kết quả sortedList. Trong đó, tổng số phần tử di chuyển bằng với tổng số phần tử của hai danh sách ban đầu. Vì vậy, thời gian thực thi của hàm merge() là Θ(nA + nB), với nA + nB là tổng số phần tử của hai danh sách. • Giải thuật sắp xếp bằng phương pháp trộn sẽ sử dụng hàm merge() ở trên để trộn hai danh sách có thứ tự thành danh sách mới cũng có thứ tự: 19 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng
Phân Tích Giải Thuật merge_sort(numList) length ← length of numList if length > 1 listA ← first half of numList listB ← second half of numList resultA ← merge_sort(listA) resultB ← merge_sort(listB) sortedList ← merge(resultA, resultB) return sortedList else return numList end 20 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.