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 và tư duy thuật toán

Chia sẻ: Codon_02 Codon_02 | Ngày: | Loại File: PPT | Số trang:46

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

Bài giảng Thuật toán và tư duy thuật toán với mục tiêu củng cố khái niệm và những đặc trưng cơ bản về thuật toán; củng cố và phân tích thêm về thiết kế thuật toán; nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT.

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 và tư duy thuật toán

  1. RÈN LUYỆN TƯ DUY VÀ KHẢ NĂNG CÀI ĐẶT  THUẬT TOÁN  Ở TRƯỜNG PT
  2. Mục tiêu    Củng cố khái niệm và những đặc trưng cơ  bản  về thuật toán.    Củng cố và phân tích thêm về thiết kế thuật  toán    Nâng cao hiệu quả giảng dạy thuật  toán  và cài  đặt thuật toán ở PT   Hồ Cẩm Hà­ĐHSPHN
  3. 1. THUẬT TOÁN •  Khái niệm thuật toán •  Máy tính và thuật toán •  Đánh giá thuật toán 3
  4. 1.1 KHÁI NIỆM THUẬT TOÁN (1) • Không đề cập đến khái niệm hình thức chính xác của thuật  toán (định nghĩa thông qua mô hình máy Turing).    Xem xét một số định nghĩa (không hình thức) ít nhiều khác  nhau  • Bản chất  mô tả một cách thức mà một nhiệm vụ hay một  tiến trình được thực hiện như thế nào của thuật toán. 4
  5. 1.1 KHÁI NIỆM THUẬT TOÁN (2) Định nghĩa 1(K.Rosen): Một thuật toán là một thủ tục xác định để giải một bài toán  (vấn đề), sử dụng một số hữu hạn bước. Mỗi bước có thể  gồm một hoặc một số thao tác/phép toán. 5
  6. 1.1 KHÁI NIỆM THUẬT TOÁN (3) Định nghĩa 2.(G. Brookshear)  Một thuật toán là một tập hợp có thứ tự các bứớc không  nhập nhằng, thực hiện được, xác định một tiến trình có kết  thúc, (tức việc thực hiện thuật toán phải dẫn tới một kết  thúc).  6
  7. 1.1 KHÁI NIỆM THUẬT TOÁN (4) Định nghĩa 3.(A. V. Aho, J.E. Hopcroft, J. D. Ullman)   Thuật toán là một dãy hữu hạn các câu lệnh, mỗi câu lệnh  đều có một ý nghĩa rõ ràng và có thể được thực hiện với một  lượng công sức hữu hạn trong một thời gian hữu hạn.  7
  8. 1.1 KHÁI NIỆM THUẬT TOÁN (5) Định nghĩa 4. (C. A. Shaffer)  Một thuật toán là một bảng chỉ dẫn để giải một bài toán, trong  đó các bước là cụ thể và không nhập nhằng. Thuật toán phải  đúng đắn theo nghĩa nó phải tính đúng hàm mong muốn ,  chuyển đổi mỗi đầu vào (dữ liệu vào) thành đầu ra (dữ liệu ra)  đúng, có độ dài hữu hạn và phải kết thúc với mọi dữ liệu vào  hợp lệ. 8
  9. 1.1 KHÁI NIỆM THUẬT TOÁN (6) Các tính chất:  Đầu vào (dữ liệu vào)  có các giá trị đầu vào được lấy từ một tập xác định.   Đầu ra (kết quả ra)  Từ một tập các giá trị đầu vào, thuật toán sản sinh ra các giá  trị đầu ra thuộc một tập xác định. Các giá trị đầu ra chứa lời giải  của bài toán. Tính xác định   Các bước trong một thuật toán phải được  định nghĩa chính  9 xác (không nhập nhằng).
  10. 1.1 KHÁI NIỆM THUẬT TOÁN (7) Các tính chất (tiếp)  Tính hữu hạn  Phải cho kết quả (đầu ra) mong đợi sau một số hữu hạn  bước  (có thể rất lớn) với mọi đầu vào thuộc tập các dữ liệu vào  hợp  lệ.  Tính hiệu quả  Phải có khả năng thực hiện mỗi bước của thuật toán một  cách  đúng đắn (chính xác) và trong một thời gian chấp nhận  được. Tính tổng quát (phổ dụng)  phải được áp dụng cho mọi bài toán có chung một dạng, mà  không phải chỉ cho riêng một tập các dữ liệu vào đặc biệt. 10
  11. 1.1 KHÁI NIỆM THUẬT TOÁN (8) Không chỉ có trong tin học, có nhiều thuật toán mô tả nhiều loại  tiến trình của đời sống hàng ngày như đan áo len, làm một loại  bánh, chơi một bản nhạc, pha một tách cà phê,...   Nói chung, một tác nhân thực hiện một tiến trình được gọi là một    bộ xử lý. Một bộ xử lý có thể là một người, một máy tính hay một  thiết bị cơ hoặc điện nào đó. 11
  12. 1.2 Máy tính và thuật toán (1) MT là một bộ xử lý đặc biệt với các đặc trưng về • Tốc độ  •  Tính tin cậy   •  Bộ nhớ •  Chi phí 12
  13. 1.2 Máy tính và thuật toán (2) Để bộ xử lý có thể thực thi một tiến trình:  Nó phải đ­ược cung cấp một thuật toán thích hợp  Nó phải có khả năng lý giải (cũng gọi là thông dịch)  thuật toán,  tức phải có khả năng : – hiểu đ­ược ý nghĩa mỗi  bước của thuật toán ; – thực hiện đ­ược thao tác ( phép toán) t­ương ứng. VD 13
  14. 1.2 Máy tính và thuật toán (3) Trư­ờng hợp bộ xử lý là một máy tính thì thuật toán phải đư­ợc  biểu thị d­ưới dạng một chư­ơng trình Để thực thi một tiến trình trên một máy tính, cần phải :  Thiết kế một thuật toán (đư­a ra một mô tả tiến trình phải đ­ ược thực hiện như­ thế nào);  Biểu thị thuật toán thành một chư­ơng trình trong một ngôn ngữ  lập trình thích hợp (cài đặt);  Cho máy tính thực hiện chư­ơng trình (chạy chư­ơng trình). 14
  15. 1.2 Máy tính và thuật toán (4)  Vai trò của thuật toán là cơ bản. Không có thuật toán không  có chư­ơng trình  không có gì để thực hiện.  Các thuật toán còn là cơ bản: độc lập với ngôn ngữ đư­ợc dùng  để biểu thị thuật toán; độc lập với các máy tính thực hiện  chúng.   Các thuật toán có thể đ­ược thiết kế và nghiên cứu độc lập với  công nghệ hiện hành: các kết quả vẫn giữ nguyên giá trị bất kể  sự ra đời của các máy tính và các ngôn ngữ lập trình mới.  15
  16. 1.3 Đánh giá thuật toán Xem tài liệu 16
  17. THẢO LUẬN THÊM Thế nào là không nhập nhằng?   Thông tin về trạng thái của tiến trình phải đủ để xác định  duy nhất và đầy đủ các hành động được đòi hỏi ở mỗi bước  Thực hiện mỗi bước không đòi hỏi kỹ năng sáng tạo mà chỉ  cần có khả năng làm theo các mệnh lệnh. 17
  18. 2. THIẾT KẾ THUẬT TOÁN (1)   Các cấu trúc điều khiển  Tinh chế thuật toán từng bước một  Tính đơn thể.   Các chiến lược thiết kế thuật toán 18
  19. 2. THIẾT KẾ THUẬT TOÁN (2) Việc thiết kế một thuật toán là một công việc trí óc  khó khăn, đòi hỏi phải có  sáng tạo, sự am hiểu lĩnh  vực  ứng dụng và không thể đư­a ra một tập các quy  tắc chung.  Không có thuật toán nào cho việc thiết kế thuật  toán. 19
  20. 2.1 Các cấu trúc điều khiển Cấu trúc tuần tự Thông th­ường các bước của một thuật toán đ­ược thực hiện theo  đúng trình tự viết của chúng:  Các bước đư­ợc thực hiện từng bước một ;  Mỗi bước đư­ợc thực hiện đúng một lần ;  Thứ tự các bứớc đ­ược thực hiện chính là thứ tự chúng đư­ợc  viết trong thuật toán ;  Sự dừng của bước cuối cùng kéo theo sự dừng của thuật toán. 20
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