Bài giảng Thuật toán: Chương 1 - GV. Nguyễn Thanh Cẩm

Chương 1 Thuật toán và độ phức tạp thuộc bài giảng thuật toán, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: khái niệm thuật toán, thiết kế - phân tích – đánh giá thuật toán, biểu diễn thuật toán, ngôn ngữ diễn đạt thuật toán (tựa c), đánh giá độ phức tạp thuật toán.
Nội dung trích xuất từ tài liệu:
Bài giảng Thuật toán: Chương 1 - GV. Nguyễn Thanh Cẩm TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm Mục đích Thuật Toán Các khái niệm liên quan đến Phân tích và bài toán và Đánh giá giải quyết thuật toán bài toán Cài đặt một số Nghiên cứu thuật toán Các kỹ thuật Thiết kế thuật toán Vận dụng giải các bài toán cụ thể Nguyễn Thanh Cẩm Nội Dung C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP C2 CHIA ĐỂ TRỊ C3 QUY HOẠCH ĐỘNG C4 THUẬT TOÁN THAM LAM C5 THUẬT TOÁN QUAY LUI Nguyễn Thanh Cẩm Học liệu Slide bài giảng Tài liệu trong Tài liệu nước nước ngoài •Vũ Đình Hòa, Đỗ Trung Giáo •Richard Neapolitan, Kumarss Kiên, Thuật toán và độ Naimipour, Foundations of phức tạp thuật toán, nhà Algorithms Using C++ xuất bản đại học sư phạm trình Pseudocode, Jones and 2007 Bartlett Publishers •Đỗ Xuân Lôi, Cấu trúc dữ •Introduction to Algorithms, liệu và giải thuật, NXB Thuật toán Second Edition, Thomas H. Đại học Quốc Gia Hà Nội Cormen, Charles E. 2007 Leiserson, Ronald L. Rivest, Clifford Stein the MIT press Tài liệu khác Nguyễn Thanh Cẩm Đánh giá Kiểm tra 1 Kiểm tra 2 Kiểm tra 3 Kiểm tra giữa kỳ Kiểm tra cuối kỳ Nguyễn Thanh Cẩm THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 1.1 Khái niệm thuật toán 1.2 Thiết kế - Phân tích – Đánh giá thuật toán 1.3 Biểu diễn thuật toán 1.4 Ngôn ngữ diễn đạt thuật toán (tựa c) Đánh giá độ phức tạp thuật toán 1.5 Nguyễn Thanh Cẩm 1.1 Khái niệm thuật toán Một ví dụ về thuật toán (1) Cho A={a1, a2,…,an| aiZ với iN} Hãy mô tả các bước để tìm được phần tử lớn nhất trong dãy? Nguyễn Thanh Cẩm 1.1 Khái niệm thuật toán Một ví dụ về thuật toán (2) Ý tưởng: b1 b2 b3 b4 Max = A[1] if(A[i]>Max) Lặp lại bước 2 Dừng khi i>n Max = A[i] với i=3..n (i=2) Nguyễn Thanh Cẩm 1.1 Khái niệm thuật toán Một ví dụ về thuật toán (3)  Nhận xét:  Sau khi thực hiện trình tự các bước trên, ta sẽ nhận được đáp số của bài toán (đó là phần tử Max của dãy).  dãy hữu hạn các bước dẫn tới đáp số mong muốn của bài toán được gọi là một thuật toán. Nguyễn Thanh Cẩm 1.1 Khái niệm thuật toán Khái niệm thuật toán  Thuật toán (Algorithm) là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hoặc hành động cần thực hiện; sau khi thực hiện các bước theo một trình tự xác định, ta được lời giải của bài toán. Nguyễn Thanh Cẩm 1.1 Khái niệm thuật toán Các đặc trưng của thuật toán Tính có đầu vào Tính có đầu ra 6 đặc trưng Tính tổng quát của Tính chính xác thuật toán Tính dừng Tính khả thi Nguyễn Thanh Cẩm THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 1.1 Khái niệm thuật toán 1.2 Thiết kế - Phân tích – Đánh giá thuật toán 1.3 Biểu diễn thuật toán 1.4 Ngôn ngữ diễn đạt thuật toán (tựa c) Đánh giá độ phức tạp thuật toán 1.5 Nguyễn Thanh Cẩm 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (1)  Mô đun hóa bài toán: Bài toán Bài toán Bài toán Bài toán 1 2 3 Bài toán Bài toán Bài toán Bài toán Bài toán 1.1 1.2 3.1 3.2 3.3 Nguyễn Thanh Cẩm 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (2)  Mô đun hóa bài toán:  Thí dụ: Viết chương trình thực hiện các phép toán trên hai phân số. Nguyễn Thanh Cẩm 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (3)  Mô đun hóa bài toán:  Thí dụ: Hai phân số Nhập Tính Xuất toán Nguyễn Thanh Cẩm 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (4)  Mô đun hóa bài toán: ...