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

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.
Nội dung trích xuất từ tài liệu:
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ẬTGiảng viên : Hồ Sĩ ĐàmEmail damhs@vnu.edu.vnGiớ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ôiNội dungChương I : Thuật toán và phân tích thuật toánChương II : Đệ quyChương III : Các dữ liệu có cấu trúcChương IV : Danh sáchChương V : CâyChương VI : Bảng bămChương VII : Sắp xếpChương VIII : Tìm kiếmChương IX : Đồ thịChương X : Các kỹ thuật thiết kế thuậ toánCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬTTOÁ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ánCHƯƠNG I:THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN1. Giải bài toán trên máy tínhBước 1. Xác định bài toán: Xác định tập Input và OutputBướ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ÁN1. 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ÁN1. Giải bài toán trên máy tính*) Cách liệt kê *) Sơ đồ khốiB1: 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ÁN1. 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; BeginBướ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 BeginBướ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ÁN1. Giải bài toán trên máy tínhBướ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ÁN2. 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ÁN3. 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ệuVí dụ: mảng, bản gi, file,xâu,..CHƯƠNG I:THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN4. Bài toán và thuật toán4.1. Bài toán Xác định rõ Input và OutputVí dụ:Kiểm tra xem N có phải là số nguyên tố haykhô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ÁN4. Bài toán và thuật toán4.2. Thuật toán Thuật toán để giải một bài toán là mộtdãy hữu hạn các thao tác đươc sắp xếptheo một trật tự xác định sao cho sau khithực hiện dãy thao tác đó, từ Input c ủabài toán này, ta nhận được Output cầ ...