intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:77

Thêm vào BST
Báo xấu
156
lượt xem 31
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

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 Thuật toán: Chương 1 - GV. Nguyễn Thanh Cẩm

  1. 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
  2. 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
  3. 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
  4. 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
  5. Đá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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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:  Thí dụ: Tính toán Cộng Trừ 2PS Nhân Chia 2PS 2PS 2PS Nguyễn Thanh Cẩm
  17. 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (5)  Mô đun hóa bài toán:  Thí dụ: Cộng 2 PSố Quy đồng Giản ước BCNN UCLN Nguyễn Thanh Cẩm
  18. 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Mô đun hóa Ưu điểm Hạn chế cho phép tách bài toán Việc phân bài toán ra thành các phần độc thành các bài toán con, lập. là một việc làm không Việc tìm hiểu cũng như dễ dàng. sửa chữa chỉnh lý sẽ Thiết kế thuật toán mất dễ dàng hơn. nhiều thời gian và công sức. Nguyễn Thanh Cẩm
  19. 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (6)  Tinh chỉnh từng bước (Stepwise refinement):  Tinh chỉnh từng bước là phương pháp thiết kế thuật toán gắn liền với lập trình.  Nó phản ánh tinh thần của quá trình mô-đun hóa bài toán và thiết kế kiểu top-down. Nguyễn Thanh Cẩm
  20. 1.2 Thiết kế - Phân tích – Đánh giá thuật toán Thiết kế thuật toán (7)  Tinh chỉnh từng bước (Stepwise refinement):  Thí dụ: Viết chương trình sắp xếp một dãy n số nguyên khác nhau theo thứ tự tăng dần. Nguyễn Thanh Cẩm
ADSENSE

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.

 

Đồng bộ tài khoản
2=>2