Bài giảng Cấu trúc dữ liệu và giải thuật

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giới thiệu môn học Giới thiệu môn học 2 Giới thiệu  Môn học giới thiệu Các cấu trúc dữ liệu cơ bản Các giải thuật điển hình trên các cấu trúc dữ liệu đó  Dùng phương pháp hướng thủ tục.  Ngôn ngữ lập trình minh hoạ Mã giả (pseudocode) C++ Giới thiệu môn học 3 Nội dung  Chương 0: GIỚI THIỆU CHUNG  Chương 1: DANH SÁCH (LIST)  Chương 2: STACK-QUEUE  Chương 3: ĐỆ QUY  Chương 4: KỸ THUẬT TÌM KIẾM (SEARCHING)  Chương 5: KỸ THUẬT SẮP XẾP (SORTING)  Chương 6: CÂY (TREE)  ÔN TẬP - KIỂM TRA (REVIEW – TEST) Giới thiệu môn học 4 Tài liệu  [1] C_and_DataStructure - P. S. Deshpande, O. G. Kakde (Bắt buộc mỗi SV phải có)  [2] Bài giảng & Bài thực hành CTDL - Trường ĐHCN.  [3] Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường DHKHTN – DHQG TP.HCM.  [4] Cấu trúc dữ liệu, Nguyễn Trung Trực, Trường DHBK – DHQG TP.HCM. Giới thiệu môn học 5 Vấn đề ngôn ngữ lập trình  Dùng C++ để diễn đạt => Có vấn đề?  Mã giả (pseudo code) Giả lập, thường là dễ hiểu, không chi tiết đến các kỹ thuật lập trình Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên Hoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, tựa C++ Giới thiệu môn học 6 Giải thuật bằng mã giả  Ví dụ: Mã giả của bubble sort Giải thuật 1 Giải thuật 2 Algorithm Bubble sort Input: The list A of n elements is given Output: The list A is sorted 1. loop for n time 1.1. for each pair in the list 1.1.1. if it is not in ordered 1.1.1.1. exchange them End Bubble sort Algorithm Bubble sort Input: The list A of n elements is given Output: The list A is sorted 1. for outter in 0..(n-2) 1.1. for inner in 0..(n-2- outter) 1.1.1. if Ainner+1 < Ainner 1.1.1.1. swap Ainner, Ainner+1 End Bubble sort Giới thiệu môn học 7 Giải thuật bằng ngôn ngữ lập trình  Ví dụ: Lập trình cụ thể Bubble sort Giải thuật 1: Pascal Giải thuật 2: C++ procedure BubbleSort(var A: list); var i,j: int; begin for i := 1 to n-1 do for j := 1 to (n-1-i) do if A[j+1] < A[j] then begin tmp := A[j]; A[j] := A[j+1]; A[j+1] := tmp; end; end; void BubbleSort(list A) { int i, j; for (i=0; i < n-2; i++) for (j=0; j<(n-2-i); j++) if (A[j+1] < A[j]) { tmp := A[j]; A[j] := A[j+1]; A[j+1] := tmp; } } Giới thiệu môn học 8 So sánh mã giả và NNLT  Nhận xét: Mã giả 1: gần với cách trao đổi của con người nhất nhưng khó lập trình nhất Mã giả 2: dễ lập trình hơn  Phương pháp: Đầu tiên: cách giải quyết vấn đề bằng máy tính số (giải thuật bằng mã giả) Sau đó: ngôn ngữ lập trình cụ thể  Học: Nhớ giải thuật (mã giả) Dùng NNLT cụ thể để minh chứng Giới thiệu môn học 9 Cấu trúc môn học  Cấu trúc: Lý thuyết: 45 tiết Thực hành: 60 tiết Đồ án môn học  Tỉ lệ điểm: Kiểm tra giữa kỳ : 20% Thực hành và bài tập lớn: 30% Thi cuối kỳ: 50% Giới thiệu môn học 10 Bài tập thực hành  Đề bài tập: Bài tập cho hàng tuần (file) Các bài trong tài liệu tham khảo Tự sưu tầm  Giải bài tập: Giờ thực hành Tự giải bài tập Giới thiệu môn học 11 Đồ án môn học  Mục đích: Hiểu bài Làm bài ở nhà theo từng SV  Chọn đồ án (1 sinh viên thực hiện 1 đồ án –viết tay tất cả các bài tập thực hành và các bài tập làm thêm. Sv nộp theo đúng thời hạn quy định (tuần thứ 14 của HK))  Đánh giá: thang điểm 10/10  Hình thức: Báo cáo và mã lệnh, nộp thông qua lớp trưởng. Giới thiệu môn học 12 Thực hành  Mục đích: Rèn luyện khả năng làm bài độc lập Sử dụng nhuần nhuyễn các kiến thức đã học. Giải bài tập + Trao đổi các thắc mắc  Thời lượng: 60 tiết (12 buổi) Giới thiệu môn học 13 Các hình thức kiểm tra  Thi giữa kỳ (20%)  Thực hiện giải thuật bằng tay  Thiết kế cấu trúc dữ liệu theo yêu cầu  Đánh giá độ phức tập giải thuật  Viết mã lệnh  Đồ án môn học (30%)  Trình bày giải thuật chi tiết bằng mã giả  Hiện thực bằng ngôn ngữ lập trình C++  Báo cáo  Thi cuối kỳ (50%)  Chỉ được thi cuối kỳ khi các điểm thi giữa kỳ và đồ án >= 5  SV sẽ bị cấm thi nếu nghỉ quá 20% số tiết