zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật - GV. Hồ Sĩ Đàm

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

Báo xấu

193
lượt xem 43
download

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

Bài giảng Cấu trúc dữ liệu và giải thuật gồm 10 chương. Nội dung bài giảng trình bày các vấn đề thuật toán và phân tích thuật toán, đệ quy, các dữ liệu có cấu trúc, danh sách, cây, bảng băm, sắp xếp, tìm kiếm, đồ thị, các kỹ thuật thiết kế 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 Cấu trúc dữ liệu và giải thuật - GV. Hồ Sĩ Đàm

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giảng viên : Hồ Sĩ Đàm Email damhs@vnu.edu.vn
Giới thiệu  Thời lượng: 4 buổi  Mục tiêu: - Giới thiệu đề cương phần cấu trúc dữ liệu và thuật toán ( môn Tin học cơ sở); - Giải đáp thắc mắc của thi sinh.
̀ ̣ ̉ Tai liêu tham khao – Thomas H. Cormen, Introduction to Algorithms, MIT Press, 1990 – R. Sedgevick,Algorithms Addison- Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán ( t ập 1, 2). – Hồ Sĩ Đàm, Nguyễn Việt, Hà Bùi Thế Duy – Đinh Mạnh Tường, Đỗ Xuân Lôi
Nội dung Chương I : Thuật toán và phân tích thuật toán Chương II : Đệ quy Chương III : Các dữ liệu có cấu trúc Chương IV : Danh sách Chương V : Cây Chương VI : Bảng băm Chương VII : Sắp xếp Chương VIII : Tìm kiếm Chương IX : Đồ thị Chương X : Các kỹ thuật thiết kế thuậ toán
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN  Giải bài toán trên máy tính  Mô hình dữ liệu  Cấu trúc dữ liệu  Bài toán và thuật toán
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính Bước 1. Xác định bài toán: Xác định tập Input và Output Bước 2. Lựa chọn hoặc thiết kế thuật toán a) Lựa chọn hoặc thiết kế thuật toán – Giải bài toán  nhiều thuật toán – Không gian ? – Thời gian ?; – Cài đặt ?
CHƯƠNG I: TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính b) Mô tả thuật toán • Input: Hai số nguyên dương a và b; • Output: q và r : a= bq+r. • Ý tưởng: - Nếu a < b thì q = 0 và r = a. Kết thúc. - Nếu a > b thì a giảm đi b và q tăng lên 1. L ặp cho đến khi a < b.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính *) Cách liệt kê *) Sơ đồ khối B1: Nhập a và b; B2: q ⇐ 0; B3: Nếu a < b thì r ⇐ a rồi chuyển đến B5; B4: a ⇐ a - b, q ⇐ q + 1 rồi quay về B3; B5: Đưa ra r và q. Kết thúc.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính Uses Crt; Uses Crt; Var a, b, q, r: integer; Var a, b, q, r: integer; Begin Bước 3. Viết chương Begin Clrscr; Clrscr; trình: Writeln (‘Chuong trinh chia Euclid’); Writeln (‘Chuong trinh chia Euclid’); Write (‘Nhap so a: ’); Write (‘Nhap so a: ’);  Chọn CTDL; Readln (a); Readln (a); Write (‘Nhap so b: ’); Write (‘Nhap so b: ’);  Ngôn ngữ lập trình Readln (b); Readln (b); q:=0; q:=0; While aa >= b Do While >= b Do Begin Begin Bước 4. Hiệu chỉnh: Dec(a,b); Dec(a,b); Inc(q); Inc(q);  Xây dựng các bộ input End; End; r:= a; r:= a; (test) tiêu biểu; Writeln (‘Thuong qq = ’, q); Writeln (‘Thuong = ’, q); Writeln (‘Phan du r r = ’, r); Writeln (‘Phan du = ’, r);  Chạy thử. Readln; Readln; End. End.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính Bước 5. Viết tài liệu:  Hướng dẫn sử dụng;  Thuật toán, Cấu trúc dữ liệu;  …….
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 2. Mô hình dữ liệu (Data model)  Là các trừu tượng :đồ thị, tập hợp, danh sách, cây...  Hai khía cạnh: – Giá trị (kiểu dữ liệu) – Các phép toán ( operation)  Chương trình có thể truy xuất đến các vùng lưu trữ.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 3. Cấu trúc dữ liệu (Data structures)  Là các đơn vị cấu trúc (construct) của NNLT dùng để biểu diễn các mô hình dữ liệu Ví dụ: mảng, bản gi, file,xâu,..
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán 4.1. Bài toán Xác định rõ Input và Output Ví dụ: Kiểm tra xem N có phải là số nguyên tố hay không? - Input : Số nguyên dương N - Output : Trả lời N là số nguyên tố hay không?
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán 4.2. Thuật toán Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đươc sắp xếp theo một trật tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input c ủa bài toán này, ta nhận được Output cần tìm.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán Ví dụ: Tìm giá trị lớn nhất của dãy số a1, a2,..…,aN, Input : Số nguyên dương N và dãy a1, a2, ,..., aN. Output : Tìm Max là giá trị lớn nhất của dãy đã cho. Ý tưởng: Khởi tạo Max=a1. Với mỗi i, nếu ai > Max thì thay giá trị Max= ai.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán 4.3. Mô tả thuật toán a) Cách liệt kê B1. Nhập N và dãy a1, ..., aN B2. Đặt Max = a1, i = 2. B3. Nếu i > N thì đến b. 5. B4. 4.1. N ếu ai > Max thì Max = ai. 4.2. Đặt i=i+1 rồi quay b.3. B5. Đưa ra Max rồi kết thúc.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán b) Sơ đồ khối  Dùng: Ovan, Chữ nhật, Hình thoi,Mũi tên,…
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán c) Ngôn ngữ điều khiển  Dùng các ký hiệu và quy tắc  Cách thiết lập thứ tự các thao tác cấu trúc điều khiển.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán 4.4. Các đặc trưng chính a)Tính kết thúc (tính đóng) b)Tính xác định (đơn nghĩa) Có đúng một thao tác để được thực hiện hoặc dừng.
CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán c)Tính chi tiết Phụ thuộc vào đối tượng thực hiện d)Tính phổ dụng với input thay đổi e) Đại lượng vào f) Đại lượng ra

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.