III. NỘI DUNG MÔN HỌC: Chương 1 :Thuật toán và độ phức tạp 5 tiết (2/3/0)
1.1. Thuật toán và các đặc trưng của thuật toán.
1.2. Đánh giá độ phức tạp của thuật toán bằng ký hiệu ô lớn.
Chương 2 : Cấu trúc dữ liệu. Kiểu dữ liệu trừu tượng 5 tiết (2/3/0) -
Dữ liệu cơ sở và dữ liệu có cấu trúc (CTDL). Các phương pháp kiến tạo CTDL.
-
Mô hình dữ liệu. Kiểu dữ liệu trừu tượng. Vai trò ủa trừu tượng hoá dữ liệu trong thiết kế chương trình.
Chương 3 : Danh sách 13 tiết (8/5/0)
3.1. Danh sáchvà các phép toán tren danh sách.
3.2. Cài đặt danh sách bởi mảng (mô tả CTDL biểu diễn và thủ tục thực hiện các phép toán trên danh sách ).
3.3. Cài đặt danh sách bởi danh sách liên kết.
3.4. Các dạng danh sách liên kết.
3.5. Ngăn xếp : Định nghĩa và cài đặt.
3.6. Hàng đợi : Định nghĩa và cài đặt.
Chương 4: Cây 10 tiết (7/3/0)
4.1. Các phương pháp cài đặt câu.
4.2. Các phương pháp duyệt cây.
4.3. Cây nhị phân.
4.4. Cây tìm kiếm nhị phân.
Chương 5: Tập hợp 11 tiết (7/4/0)
5.1. Các phương pháp cài đặt tập hợp đơn giản.
5.2. Từ điển.
5.3. Bảng băm mở và băm đóng.
5.4. Hàng ưu tiên. Cài đặt hàng ưu tiên bởi cây thứ tự bộ phận.
Chương 6: Các phương pháp thiết kế thuật toán 11 tiết (6/5/0)
6.1. Chia để trị.
6.2. Tham lam.
6.3. Quay lui.
6.4. Quy hoạch động.
Chương 7:Các thuật toán sắp xếp 8 tiết (5/3/0)
7.1. Các phương pháp sắp xếp đơn giản : Lựa chọn, xen vào, nổi bọt.
7.2. Sắp xếp nhanh.
Chương 8: Các thuật toán đồ thị 12 tiết (8/4/0)
8.1. Các phương pháp cài đặt đồ thị.
8.2. Duyệt đồ thị theo bề rộng và theo độ sâu.
8.3. Đồ thị định hướng không có chu trình. Sắp xếp topo.
8.4. Đường đi ngắn nhất. Các thuật toán Dijkstra và Floyd.
8.5. Cây bao chùm ngắn nhất. Các thuật toán Prim và Kruskal.
IV. DỰ KIẾN KIỂM TRA VÀ THI:
-
Kiểm tra giữa học kỳ:
-
Thi kết thúc học phần:
V. TÀI LIỆU THAM KHẢO:
-
Đinh Mạnh Tường. Cấu trúc dữ liệu và thuật toán.
Nhà xuất bản KH & KT, 2002
-
A. V. Aho, J. E. Hocroft, J. D. Ulman. Data Structures and Algorithms. Addson-Wesley, 1983.
-
Gregory L. Heileman. Data Structures & Other Objects using C++. Addson-Wesley, 1998.
VI. NGƯỜI BIÊN SOẠN: TS. Đinh Mạnh Tường
NHẬP MÔN HỆ CƠ SỞ DỮ LIỆU
Thời lượng 3 đvht = 45 tiết (35/10/0)
I. MÔN HỌC TIÊN QUYẾT:
-
Tin học cơ sở
-
Toán rời rạc
II. MỤC TIÊU MÔN HỌC:
+ Mục tiêu chung:
-
Trang bị cho sinh viên các kiến thức về cơ sở dữ liệu, các mô hình cơ sở dữ liệu và phương pháp thiết kế cơ sở dữ liệu.
+ Mục tiêu cụ thể:
-
Khái niệm cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, mô hình cơ sở dữ liệu
-
Mô hình liên kết thực thể, mô hình quan hệ, phụ thuộc hàm chuẩn hoá
-
Ngôn ngữ SQL, cơ sở dữ liệu phân tán.
III. NỘI DUNG MÔN HỌC:
Chương 1: Các khái niệm cơ bản về hệ cơ sở dữ liệu
1.1. Cơ sở dữ liệu
-
Định nghĩa cơ sở dữ liệu
-
Các yêu cầu về cơ sở dữ liệu
1.2. Hệ quản trị cơ sở dữ liệu
1.2.1. Định nghĩa hệ quản trị cơ sở dữ liệu
1.2.2. Các chức năng của một hệ quản trị cơ sở dữ liệu
1.2.3. Những ưu điểm khi sử dụng hệ quản trị cơ sở dữ liệu
1.3. Mô hình cơ sở dữ liệu
Chương 2: Mô hình thực thể- liên kết
2.1. Các thành phần cơ bản của mô hình thực thể-liên kết
2.2.1. Kiểu thực thể, tập thực thể, khoá
-
Thực thể và thuộc tính
-
Kiểu thực thể, tập thực thể, khoá và tập giá trị
2.1.2. Liên kết, kiểu liên kết, vai trò và các ràng buộc cấu trúc
-
Kiểu liên kết, tập hợp và thể hiện
-
Cấp liên kết, tên vai trò và liên kết đệ quy
-
Các ràng buộc trên các kiểu liên kết
-
Thuộc tính của các kiểu liên kết
-
Các kiểu thực thể yếu
2.1.3. Lược đồ ER, các quy ước đặt tên
-
Đặt tên các cấu trúc của sơ đồ
-
Một số cách biểu diễn khác nhau của sơ đồ ER
2.2. Xây dựng một mô hình ER
-
Các quy tắc quản lý cho một bài toán cụ thể
-
Xây dựng mô hình thực thể- liên kết
Chương 3: Mô hình quan hệ, các ràng buộc quan hệ và đại số quan hệ
3.1. Các khái niệm của mô hình quan hệ
3.1.1. Miền thuộc tính và quan hệ
3.1.2. Các đặc trưng của của quan hệ
3.1.3. Ký hiệu mô hình quan hệ
3.2. Các ràng buộc quan hệ, lược đồ CSDL quan hệ
3.2.1. Các ràng buộc miền
3.2.2. Ràng buộc khoá và ràng buộc trên các gái trị rỗng (null)
3.2.3. Cơ sở dữ liệu quan hệ và lược đồ cơ sở dữ liệu quan hệ
3.2.4. Toàn vẹn thực thể, toàn vẹn quy chiếu và khoá ngoài
3.3. Các phép toán quan hệ
3.3.1. Các phép táon cập nhật
3.3.2. Các phép toán đại số quan hệ
-
Phép chọn
-
Phép chiếu
-
Dãy các phép toán và đặt lại tên
-
Các phép toán tập hợp
-
Phép nối, phép chia
-
Các hàm nhóm và các phép nhóm
3.4. Chuyển đổi mô hình thực thể-liên kết thành mô hình quan hệ
3.4.1. Các quy tắc chuyển đổi.
3.4.2. Chuyển đổi mô hình cụ thể.
Chương 4: Phụ thuộc hàm và chuẩn hoá cơ sở dữ liệuquan hệ
4.1. Các nguyên tắc thiết kế lược đồ quan hệ
4.1.1. Ngữ nghĩa của các thuộc tính quan hệ
4.1.2. Thông tin dư thừa trong các bộ và cập nhật dị thường
4.1.3. Các giá trị rỗng trong các bộ
4.1.4. Tạo ra các bộ giả
4.2. Các phụ thuộc hàm
4.2.1. Định nghĩa phụ thuộc hàm
4.2.2. Các quy tắc suy diễn
4.2.3. Sự tương đương của các tập phụ thuộc hàm
4.2.4. Các tập tối tiểu của các phụ thuộc hàm
4.3. Các dạng chuẩn dựa trên khoá chính
4.3.1. Nhập môn về chuẩn hoá
4.3.2. Dạng chuẩn 1
4.3.3. Dạng chuẩn 2
4.3.4. Dạng chuẩn 3
4.3.5. Dạng chuẩn Boyce-Codd
Chương 5: Giới thiệu ngôn ngữ SQL
5.1. Giới thiệu SQL
5.1.1. Sơ lược lịch sử
5.1.2. Các dạng đặc trưng
5.1.3. Tập lệnh của SQL
5.2. Các lệnh định nghĩa dữ liệu
5.2.1. Tạo cấu trúc cơ sở dữ liệu
5.2.2. Tạo bảng cơ sở dữ liệu
5.2.3. Các ràng buộc toàn vẹn SQL
5.3. Các lệnh quản trị dữ liệu
5.3.1. Nhập dữ liệu
5.3.2. Kiểm tra nội dung của bảng
5.3.3 Lưu giữ nội dung của bảng
5.3.4. Thêm dữ liệu
5.3.5. Sửa đổi dữ liệu
5.3.6. Khôi phục nội dung dữ liệu của bảng
5.4. Các truy vấn
5.4.1. Đọc một phần nội dung của bảng
5.4.2. Các phép toán logic
5.4.3. Các phép toán đặc biệt
5.4.4. Sắp xếp một danh sách
5.4.5. Loại bỏ sự trùng lặp
5.4.6. Các hàm số SQL
5.4.7. Nhóm dữ liệu
5.4.8. Bảng ảo : tạo một view
5.4.9. SQL chỉ số
5.4.10. Nối các bảng
Chương 6: Khái niệm về cơ sở dữ liệu phân tán
6.1. Sự ra đời của cơ sở dữ liệu phân tán
6.1.1. Điều kiện ra đời của CSDL phân tán
6.1.2. Các ưu điểm của CSDL phân tán
6.2. Xử lý phân tán và cơ sở dữ liệu phân tán
6.2.1. Xử lý phân tán
6.2.2. Cơ sở dữ liệu phân tán
6.3. Hệ quản trị CSDL phân tán
6.3.1. Chức năng
6.3.2. Các thành phần
6.4. Các đặc trưng trong suốt của cơ sở dữ liệu phân tán
6.4.1. Trong suốt phân tán
6.4.2. Trogn suốt giao dịch
6.4.3. Trong suốt thao tác và tối ưu câu hỏi
6.5. Thiết kế cơ sở dữ liệu phân tán
6.5.1. Phân đoạn dữ liệu
6.5.2. Sao chép dữ liệu
6.5.3. Định vị dữ liệu
IV. DỰ KIẾN KIỂM TRA VÀ THI:
-
Kiểm tra giữa kỳ:
-
Thi kết thúc học phần:
V. TÀI LIỆU THAM KHẢO:
VI. NGƯỜI BIÊN SOẠN: TS. Nguyễn Tuệ
Chia sẻ với bạn bè của bạn: |