Bài giảng Cấu trúc dữ liệu và giải thuật - Giới thiệu môn học

Cùng tìm hiểu giới thiệu chung; danh sách (list); stack-queue; đệ quy; kỹ thuật tìm kiếm (searching); kỹ thuật sắp xếp (sorting);... được trình bày cụ thể trong "Bài giảng Cấu trúc dữ liệu và giải thuật - Giới thiệu môn học".
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 - Giới thiệu môn họcCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giới thiệu môn họcGiớ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++ 2 GiớithiệumônhọcNộ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) 3 GiớithiệumônhọcTà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. 4 GiớithiệumônhọcVấ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++ 5 GiớithiệumônhọcGiả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 Algorithm Bubble sort Input: The list A of n elements is Input: The list A of n elements is given given Output: The list A is sorted Output: The list A is sorted 1. for outter in 0..(n-2) 1. loop for n time 1.1. for inner in 0..(n-2- outter) 1.1. for each pair in the list 1.1.1. if Ainner+1 < Ainner 1.1.1. if it is not in ordered 1.1.1.1. swap Ainner, Ainner+1 1.1.1.1. exchange them End Bubble sort End Bubble sort 6 GiớithiệumônhọcGiả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); void BubbleSort(list A) var i,j: int; { begin int i, j; for i := 1 to n-1 do for (i=0; i < n-2; i++) for j := 1 to (n-1-i) do for (j=0; jSo 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 8 GiớithiệumônhọcCấ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% 9 GiớithiệumônhọcBà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 10 GiớithiệumônhọcĐồ á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. 11 GiớithiệumônhọcThự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) 12 GiớithiệumônhọcCác hình thức kiểm tra Thi giữa kỳ (20%)  Thực hiện ...