Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật: Phần 1

Phần 1 "Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật" gồm nội dung chương 1, chương 2. Nội dung phần 1 trình bày thuật toán và cấu trúc dữ liệu, các bài toán tìm kiếm (searching). Mời bạn đọc tham khảo để hiểu hơn về các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật: Phần 1 Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật MỤC LỤC LỜI NÓI ĐẦU .................................................................................................................................... 1 CHƯƠNG 1: THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU ....................................................... 2 1. Thuật toán (giải thuật) - Algorithm ............................................................................................. 2 1.1. Định nghĩa thuật toán ....................................................................................................................2 1.2. Đặc trưng của thuật toán ..............................................................................................................2 2. Biểu diễn thuật toán ..................................................................................................................... 2 2.1. Mô tả các bước thực hiện .............................................................................................................2 2.2. Sử dụng sơ đồ (lưu đồ) giải thuật (flowchart)............................................................................3 3. Độ phức tạp thuật toán – Algorithm Complexity ..................................................................... 3 3.1. Các tiêu chí đánh giá thuật toán ..................................................................................................3 3.2. Đánh giá thời gian thực hiện thuật toán .....................................................................................4 3.3. Các định nghĩa hình thức về độ phức tạp thuật toán ...............................................................5 3.4. Các lớp thuật toán..........................................................................................................................6 4. Cấu trúc dữ liệu – Data structure ............................................................................................... 8 4.1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật...........................................................................8 4.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu...................................................................................8 4.3. Các kiểu dữ liệu cơ bản của ngôn ngữ C ..................................................................................8 4.4. Các kiểu dữ liệu có cấu trúc .........................................................................................................8 4.5. Một số kiểu dữ liệu có cấu trúc cơ bản ......................................................................................8 5. Các chiến lược thiết kế thuật toán. ............................................................................................ 8 5.1. Chiến lược vét cạn (Brute force) .................................................................................................8 5.2. Chiến lược quay lui (Back tracking / try and error) ...................................................................9 5.3. Chia để trị (Divide and Conquer) ...............................................................................................12 5.4. Chiến lược tham lam (Greedy) ..................................................................................................12 5.5. Qui hoạch động (Dynamic Programming) ................................................................................13 6. Bài tập .......................................................................................................................................... 13 CHƯƠNG 2: TÌM KIẾM (SEARCHING) ................................................................................ 14 1. Bài toán tìm kiếm ........................................................................................................................ 14 2. Tìm kiếm tuần tự (Sequential search)...................................................................................... 14 3. Tìm kiếm nhị phân (binary search)........................................................................................... 16 4. Bài tập .......................................................................................................................................... 18 -i- Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật CHƯƠNG 3: SẮP XẾP (SORTING) ....................................................................................... 19 1. Bài toán sắp xếp ......................................................................................................................... 19 2. Sắp xếp gián tiếp ........................................................................................................................ 19 3. Các tiêu chuẩn đánh giá một thuật toán sắp xếp .................................................................. 20 4. Các phương pháp sắp xếp cơ bản .......................................................................................... 21 4.1. Sắp xếp chọn (Selection sort) ....................................................................................................21 4.2. Sắp xếp đổi chỗ trực tiếp (Exchange sort)...............................................................................23 4.3. Sắp xếp chèn (Insertion sort) .....................................................................................................25 4.4. Sắp xếp nổi bọt (Bubble sort)...................................................................................... ...