1. TÊN HỌC PHẦN Cấu trúc dữ liệu và giải thuật -
SỐ ĐƠN VỊ HỌC TRÌNH
4 Đơn vị học trình (Lý thuyết) -
ĐỐI TƯỢNG
Sinh viên hệ Đại Học Chính Qui năm 3 (học kỳ 1) -
PHÂN BỔ THỜI GIAN
LÝ THUYẾT TRÊN LỚP : 4 ĐƠN VỊ HỌC TRÌNH THỰC HÀNH : 30 GIỜ (TỰ THỰC HÀNH) -
ĐIỀU KIỆN
Tin học đại cương Cơ sở lập trình -
MÔ TẢ VẮN TẮT
Cấu trúc dữ liệu và giải thuật ( Data Structure and Algorithm ) là một môn học cơ sở trong chương trình đào tạo sinh viên chuyên ngành Hệ thống thông tin kinh tế Môn học giúp sinh viên thực sự hiểu được tầm quan trọng của giải thuật và các tổ chức dữ liệu - hai thành tố quan trọng nhất của một chương trình lập cho máy tính điện tử. Sinh viên được trang bị những kiến thức cơ bản về các kiểu cấu trúc dữ liệu thông dụng và các giải thuật trên các cấu trúc dữ liệu ấy. Các kiểu cấu trúc dữ liệu được nghiên cứu bao gồm: Danh sách (List), Mảng (Array), Danh sách liên kết (Linked List), Ngăn xếp (Stack), Hàng đợi (Queue), Cây (Tree) , Bảng băm và Đồ thị (Graph). -
NHIỆM VỤ CỦA SINH VIÊN
- Tham dự đầy đủ các buổi học trên lớp - Làm các bài tập lớn và bài tập từng chương - Thực hành tại Phòng máy tính - Tham dự kỳ kiểm tra quá trình -
TÀI LIỆU HỌC TẬP
Cấu trúc dữ liệu- NXB Thống kê , 1999 Đỗ Xuân Lôi - Cấu trúc dữ liệu và giải thuật - KHKT . 1995 Niclaus Wirth - Algorithms + Data Structure = Programs - Prentice Hall, 1976 Robert Kruse - Data structure and Program Design - Halifax , Canada , 1999 Knuth - The Art of computer programing Vol 3 Sorting and Searching - Wesley 1973
-
TIÊU CHUẨN ĐÁNH GIÁ SINH VIÊN
Dự lớp : Trên 85 % tổng số giờ học Thực hiện và nộp các bài tập Tham gia làm việc trong giờ lý thuyết (giải bài tập, báo cáo,…) -
THANG ĐIỂM
Thang điểm kiểm tra quá trình : 10 điểm Thang điểm kiểm tra học phần : 10 điểm Điểm kết thúc học phần = 30%điểm quá trình + 70%điểm kiểm tra học phần -
MỤC TIÊU CỦA HỌC PHẦN
Yêu cầu sinh viên nắm vững và hiểu các cấu trúc dữ liệu từ cơ bản đến phức tạp, các giải thuật tìm kiếm , sắp xếp trên các cấu trúc dữ liệu đã đề cập. Việc chứng minh một số thuật toán, cách tính độ phức tạp , các cấu trúc dữ liệu phức tạp sẽ được đơn giản hóa tối đa hoặc bỏ qua.Các ví dụ và chương trình minh họa được thiết kế dựa trên mã giả để có thể cài đặt bằng các ngôn ngữ lập trình trên MTĐT cá nhân (xem như bài tập thực hành dựa trên ngôn ngữ C#). Các giải thuật ứng dụng trong thực tế liên quan đến những cấu trúc dữ liệu cũng sẽ được trình bày nhằm giúp cho sinh viên hiểu rõ hơn tầm quan trọng của việc thiết kế, xây dựng, tổ chức các cấu trúc dữ liệu trong những ứng dụng tin học (đặc biệt là tin học quản lý) và trong lĩnh vực công nghệ thông tin nói chung. Dựa trên một ngôn ngữ lập trình đã được trình bày và hướng dẫn trong môn Lập trình cơ sở, sinh viên sẽ thực hiện các bài tập liên quan đến các cấu trúc dữ liệu được trình bày :thiết kế, xây dựng các thao tác trên cấu trúc dữ liệu, vận dụng cấu trúc dữ liệu trong các ứng dụng thực tế,…Môi trường thực hành chủ yếu vẫn là giao diện console đơn giản (khi trình bày lý thuyết và 1 số bài tập đơn giản), tuy nhiên nhằm chuẩn bị cho các môn học trong các học kỳ còn lại, sinh viên sẽ được yêu cầu thực hiện một số bài tập cơ bản liên quan đến môi trường GUI (Graphics user Interface) và sử dụng các cấu trúc dữ liệu đã được cài đặt sẵn của .NET -
NỘI DUNG CHI TIẾT CỦA HỌC PHẦN
Chương/Bài | Nội Dung | LT | TH | | MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT | 1-Giải thuật Một số khái niệm,Hiệu suất của giải thuật Phương pháp diễn đạt giải thuật Phương pháp thiết kế giải thuật | 5 | | | DANH SÁCH ĐẶC (CONDENSED LIST) | 1- Tổ chức vật lý và logic 2- Các thao tác cập nhật trên danh sách đặc : Khởi động ds, duyệt ds,thêm 1 phần tử vào cuối ds, chèn 1 phần tử vào vị trí i trong ds, xóa 1 phần tử ở vị trí i trong ds, trộn 2 ds, ghép 2 ds,… 3- Tìm kiếm Các p/pháp : tìm tuần tư, tìm với lính canh, tìm nhị phân 4- Sắp xếp trong Phương pháp chèn trực tiếp Phương pháp chọn trực tiếp Phương pháp đổi chỗ trực tiếp (Bubble Sort) Phương pháp Shakesort Phương pháp chèn với độ dài bước giảm dần ShellSort) Phương pháp sắp xếp cây (Heap Sort- Sắp xếp vun đống) Phương pháp sắp xếp phân hoạch (Quick Sort) 5-Các Giải Thuật Sắp Xếp Ngoài Giải thuật Trộn trực tiếp (Straight Merge) Giải thuật Trộn tự nhiên (Natural Merge) Trộn N đường cân bằng Trộn đa pha N đường cân bằng Kỹ thuật phân phối đường chạy ban đầu 6-Tổng kết Danh Sách Đặc : Ưu, khuyết 7-Tìm hiểu và sử dụng lớp ArrayList: Giới thiệu lớp ArrayList, các vùng thông tin, các phương thức, khai báo-sử dụng các đối tượng của ArrayList. Sử dụng lớp ArrayList trong các giải thuật. | 10 | 20 | | DANH SÁCH LIÊN KẾT (LINKED LIST) | 1- Vấn đề 2- Khái niệm về biến con trỏ 3- Danh sách liên kết đơn Tổ chức, các thao tác : khởi động, duyệt ds, thêm đầu/cuối ds, chèn trước/sau một phần tử, xóa 1 phần tử, giải phóng ds, ghép 2 ds,… Ví dụ : Ứng dụng của danh sách liên kết trong sắp xếp Topo 4- Danh sách liên kết kép Tổ chức, các thao tác : khởi động, duyệt ds, thêm đầu/cuối ds, chèn trước/sau một phần tử, xóa 1 phần tử, giải phóng ds, ghép 2 ds… Ví dụ : Ứng dụng danh sách liên kết kép trong việc quản lý bộ nhớ động 5- Danh sách liên kết vòng Tổ chức, các thao tác : khởi động, duyệt ds, thêm đầu/cuối ds, chèn trước/sau một phần tử, xóa 1 phần tử, giải phóng ds, ghép 2 ds… Ví dụ : Ứng dụng danh sách liên kết vòng trong việc thể hiện và tính toán trên các đa thức 6- Danh sách liên kết tổng quát Tổ chức và biểu diễn Một số ví dụ: +Sử dụng danh sách liên kết tổng quát để thể hiện và tính toán trên các đa thức tổng quát +Chương trình thu gom rác trong việc quản lý bộ nhớ trong 7- Ứng dụng của DSLK 8- Một số cấu trúc dữ liệu khác dựa trên danh sách Queue(Hàng đợi) :Tổ chức, biểu diễn bằng DS đặc, bằng DS liên kết, các thao tác cơ bản, các ví dụ ứng dụng Stack (chồng) : Tổ chức, biểu diễn bằng DS đặc, bằng DS liên kết, các thao tác cơ bản, các ví dụ ứng dụng 9- Giới thiệu lớp Stack, Queue trong .NET : các vùng thông tin, các phương thức, khai báo và sử dụng,ứng dụng các lớp này trong các ứng dụng | 15 | 30 | | CÂY (TREE) | 1- Định Nghĩa 2- Cây Nhị Phân Tổ chức/Biểu diễn cây nhị phân Duyệt cây 3- Cây nhị phân tìm kiếm (BST - Binary Search Tree) Thêm 1 phần tử vào cây BST Tạo 1 cây BST Tìm 1 phần tử có khóa X trong cây BST Xóa 1 khóa trên BST 4- Cây AVL (Anderson - Velski - Landis) Tổ chức-Biểu diễn cây AVL Ưu&Khuyết cây AVL Thêm 1 khóa vào cây AVL Xóa 1 khóa trên cây AVL 5- Cây tìm kiếm tối ưu Tổ chức-Biểu diễn cây tìm kiếm tối ưu Xây dựng cây tìm kiếm tối ưu Ví dụ minh họa và ứng dụng của cây TKTƯu 6- Biểu diễn cây tổng quát bằng cây nhị phân Vấn đề Cách tổ chức và biểu diễn Duyệt cây tổng quát Ví dụ áp dụng 7- B-Cây Vấn đề Cách tổ chức và biểu diễn Duyệt các nút trên B-cây Thêm 1 nút vào B-cây Xóa 1 nút trên B-cây | 15 | 20 | | BẢNG BĂM (HASH TABLE) | 1- Vấn đề 2- Bảng Băm (Hash Table) Tổ chức- Biểu diễn Các thao tác cơ bản trên cấu trúc dữ liệu bảng băm Các p/pháp chọn hàm băm Các phương pháp xử lý đụng độ 3-Các ví dụ minh họa ứng dụng bảng băm 4-Tổng kết bảng băm 5-Giới thiệu lớp HashTable : các vùng thông tin, các phương thức, khai báo-sử dụng,… | 10 | 10 | | ĐỒ THỊ (GRAPH) | 1- Đồ thị có hướng Tổ chức, biểu diễn Các tháo tác cơ bản, Các giải thuật thường dùng 2- Đồ thị vô hướng Tổ chức, biểu diễn Các tháo tác cơ bản, Các giải thuật thường dùng 3- Ví dụ minh họa và Ứng dụng của đồ thị | 5 | 10 | Ghi chú : -Phần thực hành : không tính vào số đơn vị học trình và là số giờ đề nghị để cung cấp cho sinh viên -Để đánh giá chính xác kết quả học tập của sinh viên có thể yêu cầu kiểm tra bài tập thực hành cộng thêm vào điểm quá trình.
| Phản hồi () >> |
 |
 |
Đề cương môn học 
Thôi cố vậy 
