Nội dung ôn tập môn thi: tin học cơ sở (dành cho thi tuyển sinh cao học ngành: Khoa học máy tính)

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI NỘI DUNG ÔN TẬP MÔN THI: TIN HỌC CƠ SỞ (DÀNH CHO THI TUYỂN SINH CAO HỌC NGÀNH: KHOA HỌC MÁY TÍNH) PHẦN I: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Phân tích thuật toán, độ phức tạp thuật toán, phân lớp thuật toán. Các cấu trúc dữ liệu cơ bản: Khái niệm kiểu dữ liệu trừu tượng Danh sách các phương pháp cài đặt Ngăn xếp và hàng đợi, cài đặt và ứng dụng Cây tổng quát, cây nhị phân và các cách cài đặt, các ứng dụng. Đồ thị các phương pháp biểu diễn, các phương pháp duyệt đồ thị Các thuật toán sắp xếp: chọn trực tiếp (Selection sort), chèn (Insertion sort), nổi bọt (Bubble sort), nhanh (Quick sort), vun đống (Heap sort), trộn (Merge sort). So sánh các phương pháp sắp xếp. Các thuật toán tìm kiếm: Tìm kiếm tuần tự, tìm kiếm nhị phân Cây tìm kiếm nhị phân (BST) Tìm kiếm theo địa chỉ (băm theo địa chỉ) Các chiến lược thiết kế thuật toán: “Chia để trị” “Quay lui- vét cạn” “Tham lam” Qui hoạch động PHẦN II. PHƯƠNG PHÁP VÀ NGÔN NGỮ LẬP TRÌNH Các yếu tố cơ bản của chương trình: Biến, hằng, hàm, biểu thức,… Các cấu trúc điều khiển cơ bản Chương trình con: Các loại chương trình con: thủ tục và hàm. Các loại tham số, cơ chế truyền tham số Hiệu ứng phụ (side effect) Đệ qui và khử đệ qui Lập trình có cấu trúc: Các phương pháp môđun hoá, thiết kế một chương trình (trên -xuống, dưới-lên) Lập trình hướng đối tượng: Các đặc trưng của lập trình hướng đối tượng; Các khái niệm cơ bản (lớp đối tượng, đối tượng, đối tượng con trỏ,…) Tính kế thừa, các loại kế thừa. Phương thức tĩnh, phương thức ảo. Hàm cấu tử, huỷ tử. Phương pháp lập trình hướng đối tượng, ưu điểm của chương trình hướng đối tượng. Sử dụng ngôn ngữ bậc cao (Pascal hay C++) để cài đặt thuật toán PHẦN III. LÍ THUYẾT CƠ SỞ DỮ LIỆU Các khái niệm cơ bản: Cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, hệ cơ sở dữ liệu. Kiến trúc của một hệ cơ sở dữ liệu. Tính độc lập giữa dữ liệu và chương trình Các chức năng của một hệ quản trị cơ sở dữ liệu Mô hình cơ sở dữ liệu Mô hình thực thể liên kết: Các thành phần cơ bản của mô hình thực thể liên kết. Các nguyên lý thiết kế. Sơ đồ biểu diễn mô hình thực thể liên kết Mô hình dữ liệu quan hệ Các khái niệm cơ bản: miền, thuộc tính, quan hệ, lược đồ quan hệ, khoá của lược đồ quan hệ. Các ràng buộc toàn vẹn. Đại số quan hệ và phép tính quan hệ. Ngôn ngữ SQL2 Phụ thuộc hàm, phụ thuộc đa trị. Các dạng chuẩn 1NF, 2NF, 3NF, BCNF, 4NF. Tách- kết nối không mất thông tin và tách bảo toàn phụ thuộc (đối với một tập phụ thuộc hàm F). Các phương pháp, các thuật toán để chuẩn hoá lược đồ quan hệ Chuyển đổi mô hình thực thể liên kết sang mô hình quan hệ Cơ sở dữ liệu phân tán: Khái niệm CSDL phân tán, phân biệt với một CSDL tập trung Các mục tiêu của một hệ quản trị CSDL phân tán. Kiến trúc của một hệ quản trị CSDL phân tán Cơ sở dữ liệu hướng đối tượng: Các khái niệm trong cách tiếp cận hướng đối tượng. Hệ CSDL hướng đối tượng – quan hệ với SQL3 TÀI LIỆU THAM KHẢO (Phần I và Phần II) Aho, J.E. Hopcroft, J. D. Ulman, Data structures and algorithms, Addison- Wesley, 1983. R. Sedgevick, Algorithms, Addison- Wesley, 1990. Bản dịch tiếng Việt: Cẩm nang thuật toán (tập 1,2). N.Wirth, Data structures + algorithms = programs, Prentice-Hall, 1976. Bản dịch tiếng Việt: Cấu trúc dữ liệu + giải thuật = chương trình. Bruno R.Preiss, Data structures and algorithms with object-oriented design patterns in C++ John Wiley & Son, 1999 Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 1993. Đinh Mạnh Tường, Cấu trúc dữ liệu và giải thuật, NXB Đại học Quốc gia Hà Nội, 2001. Nguyễn Tô Thành, Lập trình nâng cao trên ngôn ngữ Pascal, NXB Đại học Quốc gia Hà Nội, 2001. TÀI LIỆU THAM KHẢO (Phần III) Hector Garcia- Molina, Jeffrey D.Ulman, Jennifer Widom, Abraham Silberschatz, Henry F.Kor, S.Sudarshan, Database Systems concepts, McGraw - Hill Companies, Inc, 1977 3. R. Elmesri, Shamkant B. Navathe, Fundmentals of Database Systems, Addison Wesley, 2000 4. C.J.Date, An Introduction to Database System, seventh edition Addition - Wesley, 2000 5. Ullman J.D., Principles of Database Systems, 2nd Ed, Computer science Press, Rockville, MD, 1982 6. Hồ Thuần, Hồ Cẩm Hà, Cơ sở dữ liệu: nguyên lý và thực hành, Nxb Giáo dục, 2004. 7. Nguyễn Kim Anh, Nguyên lý của các hệ cơ sở dữ liệu Nxb Đại học Quốc gia Hà Nội, 2004.