BÀI 1: TỔNG QUÁT VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Một dãy hữu hạn các chỉ thị có thể thi hành để đạt mục tiêu đề ra nào đó. Bài giảng giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao
Môn: Cấu trúc dữ liệu và giải thuật (IT003)
Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Thông tin:
Tác giả:
Thông tin :
Môn:
Cấu trúc dữ liệu và giải thuật (IT003)
Trường:
Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Tác giả:
Tài liệu liên quan:
Preview text:
TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ẬT 1 U ẢI TH GI VÀ
Số tiết lý thuyết: 45 LIỆU Ữ
Số tiết thực hành: 30 D C Ú TR ẤU C 1
Tài Liệu Tham Khảo
Đỗ Văn Nhơn, Trịnh Quốc Sơn. Giáo trình Cấu Trúc
Dữ Liệu và Giải Thuật, ĐHQG Tp. HCM, 2015.
Đỗ Xuân Lôi, 2009, Giáo trình Cấu Trúc Dữ Liệu & Giải
thuật, NXB ĐHQG Hà nội, Tái bản lần thứ 11.
Nguyễn Đức Nghĩa, 2013, Cấu Trúc Dữ Liệu & Giải thuật, ẬT 1 U
NXB Bách Khoa Hà nội, ISSN 978 6049 112782. ẢI TH
Mark Allen Weiss, 2014, Data Structures and Algorithm GI VÀ
Analyis in C++, Fourth Edition, Pearson Education, Inc., LIỆU publishing as Addison-Wesley. Ữ D C Ú TR ẤU C 2
Tài Liệu Tham Khảo
Robert Sedgewick. Cẩm nang thuật toán (bản dịch
của nhóm tác giả ĐH KHTN), NXB Khoa học kỹ thuật, 1994.
P. S. Deshpande, O. G. Kakde. C & Data Structures, 2004. ẬT 1 U
Dr. Dobb's. Algorithms and Data Structures, 1999 ẢI TH GI
A.V. Aho, J.E Hopcroft, J.D Ullman. Data structures VÀ
and Algorithms, Addison Wesley, 1983. LIỆU Ữ D C Ú TR ẤU C 3 Hình Thức Thi
Thành phần đánh giá CĐRMH (Gx) Trọng số (%)
A1. Điểm quá trình: G2, G3, G4, G7 20%
Kiểm tra trên lớp, bài tập… (GV lý 10% thuyết qui định) Seminar nhóm 10% A2. Thi giữa kỳ G1, G2, G3, G4 20% ẬT 1 U
A3. Thành phần cuối kỳ thực hành G5, G8, G9 20%
GV thực hành cho các bài tập đánh
giá trong qúa trình học thực hành ẢI TH
Thang điểm, số lượng bài tập đánh GI
giá do GV thực hành qui định và công VÀ
bố cho SV trong buổi thực hành đầu tiên. LIỆU Ữ
A4. Thành phần cuối kỳ lý thuyết G1, G2, G3, G4, G5 40% D C Ú
Thi lý thuyết đề chung TR ẤU C 4 CHƯƠNG 1 ẬT 1
TỔNG QUAN VỀ CTDL VÀ THUẬT TOÁN U ẢI TH GI VÀ LIỆU Ữ D C Ú TR ẤU C 5 Nội Dung
Tổng quan về CTDL và thuật toán
Các tiêu chuẩn của CTDL Vai trò của CTDL
Độ phức tạp của thuật toán ẬT 1
Thực hiện và hiệu chỉnh chương trình U ẢI TH
Tiêu chuẩn của chương trình GI VÀ LIỆU Ữ D C Ú TR ẤU C 6
Khái Niệm Về CTDL Và Thuật Toán Niklaus Wirth:
CTDL + Thuật toán = Chương trình
Cần nghiên cứu về thuật toán và CTDL! ẬT 1 U ẢI TH GI VÀ LIỆU Ữ D C Ú TR ẤU C 7
Sự Cần Thiết Của Thuật Toán
Tại sao sử dụng máy tính để xử lý dữ liệu? Nhanh hơn. Nhiều hơn.
Giải quyết những bài toán mà con người
không thể hoàn thành được.
Làm sao đạt được những mục tiêu đó? ẬT 1 U
Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu ẢI TH
hình máy chi phí cao GI VÀ
Nhờ vào các thuật toán hiệu quả: thông minh LIỆU và chi phí thấp Ữ D C Ú
“Một máy tính siêu hạng vẫn không thể cứu vãn một TR
thuật toán tồi!” ẤU C 8 Thuật Toán
Thuật toán: Một dãy hữu hạn các chỉ thị có thể
thi hành để đạt mục tiêu đề ra nào đó.
Ví dụ: Thuật toán tính tổng tất cả các số nguyên
dương nhỏ hơn n gồm các bước sau: Bước 1: S=0, i=1; Bước 2: nếu i ẬT 1 U
Ngược lại: qua bước 4; ẢI TH Bước 3: GI VÀ i=i+1; LIỆU Quay lại bước 2; Ữ D C Ú
Bước 4: Tổng cần tìm là S. TR ẤU C 9
Các Tiêu Chuẩn Của Thuật Toán Xác định Hữu hạn Đúng Tính hiệu quả ẬT 1 U ẢI TH Tính tổng quát GI VÀ LIỆU Ữ D C Ú TR ẤU C 10
Biễu Diễn Thuật Toán
Dạng ngôn ngữ tự nhiên
Dạng lưu đồ (sơ đồ khối) Dạng mã giả Ngôn ngữ lập trình ẬT 1 U ẢI TH GI VÀ LIỆU Ữ D C Ú TR ẤU C 11
Biểu Diễn Bằng Ngôn Ngữ Tự Nhiên
NN tự nhiên thông qua các bước được tuần tự
liệt kê để biễu diễn thuật toán. Ưu điểm:
Đơn giản, không cần kiến thức về về cách
biểu diễn (mã giả, lưu đồ,...) ẬT 1 U Nhược điểm: ẢI TH GI
Dài dòng, không cấu trúc. VÀ LIỆU
Đôi lúc khó hiểu, không diễn đạt được thuật Ữ D toán. C Ú TR ẤU C 12 Lưu Đồ
Là hệ thống các nút, cung hình dạng khác nhau
thể hiện các chức năng khác nhau. A A Thực hiện A Gọi hàm A Vào / Ra dữ liệu ẬT 1 U ẢI TH Đúng GI B Begin VÀ End Sai LIỆU Ữ
Nút giới hạn bắt đầu / D C
Điều kiện rẻ nhánh B Ú
kết thúc chương trình TR ẤU C 13
Biểu Diễn Bằng Lưu Đồ Bắt đầu a = a max 0 Tìm phần tử mang
giá trị lớn nhất i = 1 trong mảng iS a là lớn nhất Kết thúc ẬT 1 max U ẢI TH Đ GI VÀ Đ a < a max i a =a max i LIỆU Ữ D C S Ú i = i+1 TR ẤU C 14
Biểu Diễn Bằng Mã Giả
Ngôn ngữ tựa ngôn ngữ lập trình:
Dùng cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C.
Dùng các ký hiệu toán học, biến, hàm. Ưu điểm: ẬT 1 U
Đỡ cồng kềnh hơn lưu đồ khối. ẢI TH GI Nhược điểm: VÀ LIỆU
Không trực quan bằng lưu đồ khối. Ữ D C Ú TR ẤU C 15
Biểu Diễn Bằng Mã Giả
Một số quy ước
1. Các biểu thức toán học
2. Lệnh gán: “=” (AB)
3. So sánh: “==”, “!=”
4. Khai báo hàm (thuật toán) ẬT 1 U
Thuật toán () ẢI TH GI Input: VÀ Output: LIỆU Ữ D C Ú End TR ẤU C 16
Biểu Diễn Bằng Mã Giả 5. Các cấu trúc: Cấu trúc chọn:
if … then … [else …] fi Vòng lặp: while … do ẬT 1 U
do … while (…) ẢI TH
for … do … od GI VÀ
6. Một số câu lệnh khác: LIỆU Ữ
Trả giá trị về: return [giá trị] D C Ú Lời gọi hàm: (tham số) TR ẤU C 17
Biểu Diễn Bằng Mã Giả
Ví dụ: Tìm phần tử lớn nhất trong mảng một chiều. a =a ; max 0 i=1; ẬT 1 U while (iẢI TH if (a = a ; max i max i GI VÀ i++; LIỆU Ữ end while; D C Ú TR ẤU C 18
Biểu Diễn Bằng Ngôn Ngữ Lập Trình
Dùng ngôn ngữ máy tính (C, Pascal,...) để diễn tả
thuật toán, CTDL thành câu lệnh.
Kỹ năng lập trình đòi hỏi cần học tập và thực hành (nhiều).
Dùng phương pháp tinh chế từng bước để ẬT 1 U
chuyển hoá bài toán sang mã chương trình cụ ẢI TH thể. GI VÀ LIỆU Ữ D C Ú TR ẤU C 19
Độ Phức Tạp Của Thuật Toán
Một thuật toán hiệu quả:
Chi phí cần sử dụng tài nguyên thấp: Bộ nhớ,
thời gian sử dụng CPU, …
Phân tích độ phức tạp thuật toán:
N là khối lượng dữ liệu cần xử lý. ẬT 1 U
Mô tả độ phức tạp thuật toán qua một hàm ẢI TH f(N). GI
Hai phương pháp đánh giá độ phức tạp của VÀ thuật toán: LIỆU Ữ D C
Phương pháp thực nghiệm. Ú TR
Phương pháp xấp xỉ toán học. ẤU C 20