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

Cấu trúc dữ liệu và giải thuật là tập tài liệu học tập và tham khảo của sinh viên ngành Công nghệ Thông tin ở nhiều cơ sở đào tạo cao đẳng, đại học và sau đại học.
Nội dung trích xuất từ tài liệu:
Giới thiệu môn học: Cấu trúc dữ liệu và giải thuậtCẤ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++ Giới thiệu môn học 2Nộ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 3Tà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 4Vấ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 5Giả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. loop for n time 1. for outter in 0..(n-2) 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 Giới thiệu môn học 6Giả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 Giới thiệu môn học 8Cấ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 9Bà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 10Đồ á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 11Thự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 12Cá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 Giới thiệu môn học 13 ...