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

Chia sẻ: Codon_03 Codon_03 | Ngày: | Loại File: PPT | Số trang:13

Thêm vào BST

Báo xấu

62
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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".

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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Ấ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 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ới thiệu môn học
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) 3 Giới thiệu môn học
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. 4 Giới thiệu môn học
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++ 5 Giới thiệu môn học
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 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ới thiệu môn học
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); 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; j
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 8 Giới thiệu môn học
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% 9 Giới thiệu môn học
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 10 Giới thiệu môn họ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ới thiệu môn học
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) 12 Giới thiệu môn học
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 13 Giới thiệu môn học