Tìm hiểu chương trình đào tạo ngành Điện tử - Viễn thông hệ đại học: Phần 2

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:174

Thêm vào BST

Báo xấu

32
lượt xem 3
download

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

Nối tiếp nội dung phần 1, phần 2 cuốn sách sẽ giới thiệu tới người đọc các kiến thức cơ sở ngành, kiến thức chuyên ngành, đề cương của từng môn học theo từng khối chuyên ngành Điện tử - Viễn thông. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Tìm hiểu chương trình đào tạo ngành Điện tử - Viễn thông hệ đại học: Phần 2

III. K H Ố I K IÉ N T H Ứ C C O SỞ CỦ A N G À N H 133
XÁC SUẢT VA THÕNG KẼ 1. Số (lon vị học trình: 3 dvht 2. Phân bô thời gian Lý thuyết: 30 tiêt Bài tập: 15 tiết 3. Môn học tiên quyết Sinh viên cần được học qua môn Toán cao cấp. 4. Mục tiêu môn học Cung cấp cho sinh viên kiến thức về: - C ác khái niệm cơ bản về xác suất. - Các khái niệm về thống kê toán học. - Vai trò của xác suất- thống kê trong mô hình hoá thế giới vật lý. 5. Mô tả tóm tắt nội dung môn học Gồm hai phần: Phần các kiến thức cơ sở: cung cấp cho sinh viên các kiến thức cơ sở về xác suất - thống kê. Phần vận dụng các kiến thức cơ sở: thông qua các bài tập và một vài ví dụ về sử dụng các kiến thức này trong thực tế. 6. Phuong thức kiểm tra đánh giá Hệ số của điểm kiểm tra giữa kỳ: 0,3 Hệ số của điểm thi cuối kỳ: 0,7 7. Nội dung chi tiết môn học Số tiết (LT/BT/TH) Chương 1. Sự kiện ngẫu nhiên và xác suất 10(6/4/0) 1.1. Mở đầu: mô hình hoá thế giới vật lý 1.2 Thí nghiệm ngẫu nhiên và sự kiện ngẫu nhiên 1.3 Không gian mẫu của thí nghiệm 1.4 Định nghĩa xác suất của sự kiện ngẫu nhiên 1.4.1. Định nghĩa xác suất theo tần suất 1.4.2. Định nghĩa xác suất theo mô hình xác suất đồng khả năng 1.4.3. Định nghĩa xác suất theo tiên đề 135
1.5. Xác suất có điều kiện 1.5.1. Định nghĩa xác suất có điều kiện 1.5.2. Công thức nhân xác suất 1.5.3. Sự kiện độc lập 1.5.4. Công thức xác suất toàn phần 1.5.5. Công thức Bayes 1.6. Thí nghiệm Béc-nu-li và xác suất nhị thức Chương 2. Biến ngẫu nhiên 10(6/4/0) 2.1. Biến ngẫu nhiên và hàm phân phối 2.2. Biến ngẫu nhiên rời rạc và hàm xác suất 2.3. Biến ngẫu nhiên liên tục và hàm mật độ xác suất 2.4. Kỳ vọng, mô men, phương sai, hệ số bất đối xứng, hệ số nhọn 2.5. Các biến ngẫu nhiên rời rạc thường gặp 2.5.1. Biến ngẫu nhiên Béc-nu-li 2.5.2. Biến ngẫu nhiên nhị thức 2.5.3. Biến ngẫu nhiên Poát-xông 2.6. Biến ngẫu nhiên liên tục thường gặp 2.6.1. Biến ngẫu nhiên phân phối đều 2.6.2. Biến ngẫu nhiên phân phối mũ 2.6.3. Biến ngẫu nhiên phân phối chuẩn 2.7. Entropy Chương 3. Véc to’ngẫu nhiên 7(5/2/0) 3.1. Định nghĩa 3.2. Véc tơ ngẫu nhiên 2 chiều rời rạc 3.2.1. Hàm xác suất đồng thời 3.2.2. Hàm xác suất biên duyên 3.2.3. Hàm xác suất có điều kiện 3.2.4. Kỳ vọng có điều kiện 3.2.5. Hiệp phương sai và hệ số tương quan
3.3. Véc tơ ngẫu nhiên 2 chiều liên tục 3.3.1. Hàm phân phối đong thời 3.3.2. Hàm mật độ xác suất đồng thời 3.3.3. Hàm phân phối và mật độ xác suất có điều kiện 3.3.4. Tính độc lập cùa biến ngẫu nhiên liên tục Chưong 4. Dãy các biến ngẫu nhiên độc lập cùng phân phối 3(3/0/0) 4.1. Khái niệm và định nghĩa 4.2. Tổng các biến ngẫu nhiên độc lập cùng phân phối 4.2.1. Tổng thông thường 4.2.2. Tổng ngẫu nhiên 4.2.3. Luật số lớn 4.2.4. Luật yếu số lớn 4.2.5. Luật mạnh số lớn 4.3. Định lý giới hạn trung tâm Chương 5. Mầu ngẫu nhiên và hàm phân phối thực nghiệm 3(3/0/0) 5.1. Mầu ngẫu nhiên 5.2. Phân phối thực nghiệm và phân phối chính xác 5.3. Phân phối của các đại lượng thống kê 5.3.1. Phân phối của X 5.3.2. Phân phối ỵ 1, phân phối Student 5.3.3. Phân phối của s 2 5.3.4. Phân phối tiệm cận chuẩn Chương 6 . Ưóc lượng điểm và khoảng 7(4/3/0) 6 . 1 . Khái niệm cơ bản về ước lượng điểm và khoảng 6.2. Một số tính chất của ước lượng điểm 6.2.1. Tính không chệch 6.2.2. Tính vững 6.2.3. Tính hiệu quả 6.3. Một số phương pháp tìm ước lượng điểm 6 .3 . 1 . Phương pháp hợp lý cực đại 6.3.2. Phương pháp mô men 137
6.4. ước lượng khoảng 6.4.1. Khoảng tin cậy của giá trị trung bình khi lấy mẫu từ phân phổi chuẩn có phương sai đã biết 6.4.2. Khoảng tin cậy của giá trị trung bình khi lấy mẫu từ phân phối chuẩn có phương sai chưa biết 6.5. Khoảng tin cậy của xác suất khi cỡ mẫu lớn Chương 7. Kiểm định giả thuyết 5(3/2/0) 7.1. Khái niệm chung 7.2. Kiểm định giả thuyết về giá trị trung bình 7.3. Tiêu chuẩn ỵ 2 8. Tài liệu học tập và tham khảo • Tài liệu học tập: [1] Trần Mạnh Tuấn, Xác suất & Thống kê. Lý thuyết và thực hành tỉnh toán, Bộ sách Toán cao cấp - Viện Toán học. Nxb Đại học Quốc gia Hà Nội, 2004. • Tài liêu9 tham khảo: [ 1 ] Leon Garcia A, Probability and Random Processes for Electrical (Second E n g in e e rin g Edition), Addison Wesley, Reading, Massachusetts, 1994. [2] Viniotis Y, P ro b a b ility a n d R andom P ro ce sse s fo r E le c tric a l Engineers, WCB/McGraw-Hill, New York, 1997. 138
PHƯƠNG PHÁP TÍNH TOÁN SÔ 1. Số đon vị học trình: 3 đvht 2. Phân hổ thòi gian Lý thuyết: 30 tiêt Thực hành: 30 tiết (15 tiết quy chuẩn) 3. Môn học tiên quyết Toán cao cấp. Ngôn ngữ Pascal hay Ngôn ngữ c . 4. Mục tiêu môn học • Mục tiêu chung: - Trang bị cho sinh viên các phương pháp tính gần đúng phổ biến, thường dùng nhất để giải các bài toán đại số tuyến tính, đạo hàm, tích phân, phương trình vi phân. • Mục tiêu cụ thể: - Thực hiện được các thuật toán đơn giản bằng tính và bằng máy tính. 5. Mô tả tóm tắt nội dung môn học Cung cấp kiến thức cơ bản về phương pháp giải các bài toán, các phương trình bàng phương pháp gần đúng trên máy tính. Các bài toán liên quan như phương trình phi tuyến, ma trận nghịch đảo và trị riêng. Các bài toán nội suy hay vi tích phân gần đúng là nội dung chính của môn học này. 6. Phương thức kiếm tra đánh giá Hệ số tính điểm phần thực hành: 0,4 Hệ số tính điểm phàn lý thuyết: 0,6 7. Nội dung chi tiết môn học Số tiết (LT/BT/TH) P hần I. Lý th u y ế t Chuong 1. Vấn đề sai số 3(3/0/0) 1.1.Sai số tuyệt đối và sai số tương đối 1.1.1. Sai số tuyệt đối 1.1.2. Sai số tương đối 139
1.2. Cách viết một số gần đúrig và sai số quy tròn 1.2.1. Chữ số có nghĩa, chừ số đáng tin và cách viết một số gán đúng 1.2.2. Vấn đề quy tròn-và sai số quy tròn 1.3. Các quy tắc tính sai số 1.3.1. Công thức tính sai số 1.3.2. Sai số tính toán và sai số phương pháp 1.3.3. Sự ổn định của một quá trình tính Chương 2. Tính gần đúng nghiệm thực của một phưong trình 6(6/0/0) 2.1. Nghiệm và khoảng phân li nghiệm 2.1.1. Nghiệm và ý nghĩa hình học 2.1.2. Sự tồn tại nghiệm và khoảng phân li nghiệm 2.2. Các phương pháp tính gần đúng nghiệm thực của một phương trình 2.2.1. Phương pháp chia đôi 2.2.2. Phương pháp lặp (gần đúng liên tiếp) 2.3. Phương pháp Niu-tơn (Phương pháp tiếp tuyến) 2.4. Phương pháp dây cung Chương 3. Tính gần đúng nghiệm của một hệ phương trình đại số tuyến tính 5(5/0/0) 3.1. Các khái niệm cơ bản 3.1.1. Dạng tổng quát của một hệ phương trình đại số tuyến tính 3.1.2. Sự tồn tại và duy nhất của nghiệm 3.2. Phương pháp khử Gauss (Phương pháp giải trực tiếp) 3.2.1. Hệ tam giác, quá trình xuôi và ngược 3.2.2. Vấn đề chọn trụ 3.2.3. Sơ đồ tóm tắt cùa phương pháp 3.3. Phương pháp lặp giải hệ phương trình đại số tuyến tính 3.3.1. Mô tả phương pháp 3.3.2. Sự hội tụ và tóm tắt phương pháp Chương 4. Nội suy và phưong pháp bình phương bé nhất 5(5/0/0) 4.1. Nội suy đa thức (Đa thức Lagrangiơ và đa thức Niu-tơn) 4.1.1. Nội suy và sự duy nhất của đa thức nội suy 4.1.2. Đa thức nội suy Lagrangiơ 4.1.3. Đa thức nội suy Niu-tơn
4.2. Phương pháp bình phương bé nhất 4.2.1. Khái niệm về phương pháp 4.2.2. Xét một số trường hợp Chương 5. Tính gần đúng đạo hàm và tích phân xác định 5(5/0/0) 5.1. Tính gần đúng đạo hàm 5.1.1. Một số phương pháp tính thông dụng 5.1.2. Xét một số ví dụ 5.2. Tính gần đúng tích phân xác định 5.2.1. Công thức hình thang 5.2.2. Công thức Simsơn Chưorg 6. Tính gần đúng nghiệm của phuong trình vi phân có điều kiện đầu 6(6/0/0) (Bài toan côsi) 6 .1. Đặt vấn đề 6.1.1. Bài toán Côsi 6.1.2. Nghiệm của bài toán Côsi 6.2. Cá: phương pháp tính gần đúng 6.2.1. Phương pháp chuỗi Taylo 6.2.2. Phương pháp ơ le 6.2.3. Các phương pháp chính xác cao 6.3. Hệ phương trình và phương trình vi phân cấp cao 6.3 1. Hệ phương trình 6.3 2. Các phương pháp Phẩn II. Thực hành Bài 8 . 2,5(0/0/5) 8 . ]. Cá; bài tập về xác định sai số 8.2. Cá; bài tập về xác định nghiệm cùa 1 phương trình 8.1.1. Xác định nghiệm bằng phương pháp chia 2 và phương pháp lặp 8.1.2. Xác định nghiệm bằng phương pháp Niuton và phương pháp dây cung 141
Bài 9. 2,5(0/0/5) 9.1. Các bài tập về tính gần đúng nghiệm của 1 hệ phương trinh 9.1.1. Tính gần đủng nghiệm bàng phương pháp khử Gauss 9.1.2. Tính gần đúng nghiệm bằng phương pháp lặp 9.2. Các bài tập về phương pháp nội suy 9.2.1. Nội suy đa thức Bài 10. 2,5(0/0/5) 10.1. Bài tập về tính gần đúng đạo hàm và tích phân 10.1.1. Bài tập về tính đúng đạo hàm 10.1.2. Bài tập về tính đúng tích phân 10.2. Các bài tập vềtínhgầnđúng nghiệm của phương trình vi phân 10.2.1. Tính gầnđúngnghiệm của phương trình vi phân dùng phương pháp chuỗi Taylo 10.2.2. Tính gần đúng nghiệm của phương trình vi phân dùng phương pháp ơle và các phương pháp chính xác cao 8. Tài liệu học tập và tham khảo • Tài liệu học tập: [1] Tạ Văn Đĩnh, P h ư ơ n g pháp tính, Nxb Giáo dục, 1995. • Tài liệu tham khảo: [1] Lê Đình Thịnh, Phương pháp tính, Nxb Khoa học Kỹ thuật, 1995. [2] D. Me Cracken, Numerical Methods and Programming, 1992. [3] w. Press, Numerical Recipes in Pascal, 1990. 142
HỢP NGŨ 1. Số đon vị học trình: 3 đvht 2. Phân bô thòi gian Lý thuyết: 30 tiết Thực hành: 30 tiết (15 tiết quy chuẩn) 3. Môn học tiên quyết Đã học xong Tin học đại cương. Học trước môn cấu trúc máy tính đế làm cơ sở minh họa hoạt động của máv tính PC. 4. IVlục tiêu môn học • v ề k iế n th ứ c : Cung cấp cho sinh viên các kiến thức về: - Các khái niệm cơ bản về Cône nghệ thôníỉ tin. - Các vấn đề về lập trình, thuật toán. - Nguyên lý máy tính: cấu trúc cơ bản của máy tính, các thiết bị của máy tính, ngôn ngữ máy tính, sự tiến triển của máy tính. - Phần mềm: phần mềm hệ thống (hệ điều hành), phần mềm ứng dụng, phần mềm công cụ (các hệ dịch...). - Các lĩnh vực ứng dụng và sử dụng ngôn ngữ máy tính. • về kỹ năng: Rèn luyện cho sinh viên các kỹ năng: - Khai thác các hệ điều hành phổ thông nhất như MS DOS và MS W indow s. - Sử dụng một ngôn ngữ lập trình bậc thấp. 5. Mô tả tóm tắt nội dung môn học Gồm ba phần: Phần các kiến thức cơ sở: cung cấp cho sinh viên các kiến thức cơ sở về máy tính, phần mềm gỡ rối (debug) và ứng dụng ngôn ngữ máy tính; Phần sử dụng máy tính: cho sinh viên làm quen với máy tính, cách sử dụng các thanh ghi của CPU, bộ nhớ máy tính cho các chương trình ứng dụng; Phần ngôn ngũ’ lập trình: sinh viên học phương pháp xử lý thông tin thông qua việc học ngôn ngữ lập trình hệ thống, ngôn ngữ Assembly. 143
6. Phưoiĩg thức kiểm tra đánh giá Hệ số điểm phần lý thuyết cơ sở: 0,3 Hệ số điểm phần thực hành: 0,2 Hệ số điểm phần lập trình: 0,5 7. Nội dung chi tiết môn học Số tiết (L T /B T /T H ) Phần I. Lý thuyết Chương 1. Mỏ’đầu 3(3/0/0) 1.1. Hệ đếm 1.2. Các phép tính số học và logic 1.3. CPU 80x86 và các thanh ghi Chương 2. Assembler 6(6/0/0) 2.1. Assembler 2.2. Các lệnh di chuyển dữ liệu 2.3. Lệnh ngắt 2.4. Sử dụng bộ nhớ 2.5. Các thủ tục cơ bản Chương 3. số liệu 10(10/0/0) 3.1. Các phương thức nhập và chỉ thị số liệu 3.2. Các lệnh cho xử lý số liệu số học và logic 3.3. Các lệnh cho xâu dữ liệu 3.4. Các lệnh vào/ra Chương 4. File 2(2/0/0) 4.1. The file 4.2. Các phương thức đọc và lưu trữ dữ liệu trên file Chưong 5. Bộ nhó’và chương trình nội trú (2/0/0) 5.1. Bộ nhớ 5.2. Chương trình nội trú Chương 6. Liên kết vói ngôn ngữ bậc cao 4 (4 /0 /0 ) 6.1. InLine và tham số 6.2. Liên kết giữa các file.asm 6.3. Liên kết với file.pas 6.4. Liên kết với file.c 144
C h u o n g 7. C ác ví dụ ứng dụng CO' bản 3(3/0/0) 7 . 1 . Diểu khiển loa (Out) 7.2. Nhận dữ liệu từ Mouse (In) 7.3. Trao đối thôniĩ tin với 0 đĩa (In/Out) 7.4. Truyền tin không đồng bộ (Port Com) Phẩn II. Thực hành Bài 11. Tố chức chương trình Assembler và các biến, chương trình Debug 2,5(0/0/5) 11.1. c ác lệnh liên quan đến tổ chức các thanh ghi CPU 80x86 11.2. Các bài tập liên quan đến hoạt động của các thanh ghi đoạn 11.3. Các bài tập liên quan đến hoạt động các thanh ghi AX, BX, c x , DX Bài 12. Các bài tập liên quan xử lí dử liệu, xâu 7,5(0/0/15) 12.1. Các bài tập liên quan đến hoạt động các thanh ghi SI, DI 12.2. Các bài tập liên quan tổ chức dữ liệu cho chương trình máy tính 12.3. Các bài tập phối họp liên quan giữa các lệnh xử lý logic và xử lý số học Bài 13. C ác bài tập liên q u an đến chưoìig trìn h nội trú 2(0/0/4) 13.1. Bài tập liên quan đến hoạt độnu của ngắt cứng 13.2. Bài tập liên quan tổ chức chương trình bên trong máy tính Bài 14. C ác bài tập liên q u a n đến hệ thống, ch ư ơ n g trìn h con, liên kết file 3(0/0/6) 14.1. Các bài tập liên quan đến hoạt động các thanh ghi SP và BP 14.2. Các bài tập phối họp hoạt động giữa các tiến trình của 1 chương trình 14.3. Bài tập liên quan dến vào/ ra dừ liệu của CPU với thiết bị ngoại vi 8. Tài liệu tham khảo:. [ 1 ] PC Internal, Abacus Software 2000. [2] Quách Tuấn Ngọc (dịch ...), Nhập mônhợp ngữ, Nxb Giáo dục, 2000. [3] Asembler Introduction, Monash University. Australia, 1996. [4] Assmbly Language, Peter Norton Prentice Hall, 1996. [5] Turbo Pascal (Trict and advance), 1996. [6 ] C-Ianguage, 1998 Inc.Borland. 145
CÁU TRÚC DŨ LIỆU VÀ THUẬT TOÁN 1. Số đơn vị học trình: 3 đvht 2. Phân bổ thời gian Lý thuyết: 30 tiết Bài tập: 6 tiết Thực hành: 18 tiết (9 tiết quy chuẩn) 3. Môn học tiên quyết - Tin học đại cương. - Ngôn ngữ lập trình (ví dụ c, c ++, JAVA,..). - Nếu đã được học Toán học rời rạc trước thì tổt hơn. 4. Mục tiêu môn học Cung cấp cho sinh viên các kiến thức cơ bản về cấu trúc dừ liệu và thuật toán; kỹ năng xây dựng, lựa chọn các cấu trúc dừ liệu và các thuật toán họp lí cho các vấn đề cụ thể cần giải quyết; kỹ năng cài đặt chưcng trình bằng ngôn ngữ lập trình bậc cao. 5. Mô tả tóm tắt nội dung môn học Các lệnh cơ bản của ngôn ngữ máy tính bậc thấp. Các lệnh vao/ra, sử dụng bộ nhớ, các lệnh di chuyển, lệnh ngắt với các minh họa căn bản về điều khiển bàn phím, điều khiển loa và trao đổi dữ liệu với các 0 đĩa. 6. Phương thức kiểm tra đánh giá Hệ số điểm phần lý thuyết: 0,7 (thi viết hoặc vấn đáp). Hệ số điểm phần bài tập và thực hành: 0,3 điểm (kiểm tra tổng hợp cuối kỳ, hoặc điểm trung bình đánh giá của các bài thực hành trong cả học kỳ). 7. Nội du n g chi tiết m ôn học s ố tiết (LT/BT/TH ) Chương 1. Thuật toán và phân tích thuật toán 2(2/0/0) 1.1. Thuật toán 1.1.1. Bài toán và thuật toán 1.1.2. Mô tả thuật toán 1.1.3. Các đặc trưng thuật toán 146
1.2 Phân tích thuật toán 1.21. Lựa chọn thuật toán 1.2 2. Kí pháp đánh giá độ phức tạp thuật toán 1.2.3. Xác định độ phức tạp thuật toán 1.2.4. Áp dụniỉ đánh giá thời gian thực hiện chương trình 1.2.5. Môt số dạng hàm kí hiệu độ phức tạp thuật toán Ghi chít: Bài tập làm tại lớp học lí thuyết. Chưong 2. Đệ quy và thuật toán đệ quy 3(2/l/0) 2.1. Các khái niệm lặp, truy hồi, đệ quy 2.2. Thuật toán đệ quy 2.2.1. Định nghĩa 2.2.2. Một số ví dụ thuật toán đệ quy Ghi chú : Bài tập làm tại lófp học lí thuyết. Chưong 3. Các cấu trúc dũ' liệu 13(9/1/6) 3.1. Định nghĩa kiểu dữ liệu và biểu diễn dữ liệu 3.2. Kiểu dữ liệu và cấu trúc dữ liệu 3.3. Kiểu mảng, xâu và cấu trúc (bản ghi) 3.3.1. Mảng 1 chiều 3.3.2. Mảng 2 chiều 3.3.3. Kiểu xâu 3.3.4. Kiểu cấu trúc và cài đặt 3.4. Danh sách 3.4.1. Định nghĩa 3.4.2. Các phép toán 3.4.3. Cài đặt danh sách bàng mảng 3.4.4. Danh sách liên kết đơn, kép, vòng tròn 3.5. Ngăn xếp 3.5.1. Định nghĩa, các phép toán 3.5.2. Cài đặt ngăn xếp 3.6 Hàng đợi 3.6.1. Định nghĩa, các phép toán 147
3.6.2. Cài đặt hàng đợi Nội dung thực hành: cài đặt chương trình có sử dụng danh sách, ngăn xếp và hàng đợi Chương 4. Cây 3,5(2/1/1) 4.1. Các khái niệm 4.1.1. Định nghĩa và ví dụ 4.1.2. Cài đặt cây 4.1.3. Các phép toán trên cây 4.2. Cây nhị phân 4.2.1. Định nghĩa và một số cây nhị phân đặc biệt 4.2.2. Biểu diễn cây nhị phân bằng mảng 4.2.3. Biểu diễn cây nhị phân bàng danh sách liên kết 4.2.4. Các thuật toán duyệt cây nhị phân 4.3. Cây tìm kiếm nhị phân 4.3.1. Định nghĩa 4.3.2. Các phép toán tìm kiếm, chèn, xóa 4.4. Cây có thứ tự bộ phận (heap) 4.4.1. Định nghĩa 4.4.2. Các phép toán chèn, xóa Nội dung bài tập và thực hành: cài đặt chương trình có sử dụng các phép toán trên cây. Chương 5. sắp xếp và tim kiếm 10.5(7/1/5) 5.1. Bài toán sắp xếp 5.2. Sắp xếp chọn 5.2.1. Thuật toán 5.2.2. Ví dụ mô phỏng thuật toán 5.3. Sắp xếp chèn 5.3.1. Thuật toán 5.3.2. Ví dụ mô phỏng thuật toán 5.4. Sắp xếp nổi bọt 5.4.1. Thuật toán 5.4.2. Ví dụ mô phỏng thuật toán
5.5. Săp xêp nhanh (Quicksort) 5.5.1. Phương pháp 5.5.2. Thuật toán phàn đoạn 5.5.3. Đánh giá độ phức tạp thuật toán 5.6. Sắp xếp trộn Mergesort 5.6.1. Phương pháp 5.6.2. Thuật toán trộn 5.6.3. Đánh giá độ phức tạp thuật toán 5.7. Sắp xếp vun đống (Heapsort) 5.8. Đánh giá và so sánh các thuật toán sắp xếp 5.9. Bài toán tìm kiếm 5.10. Tìm kiếm tuần tự 5.10.1. Thuật toán và độ phức tạp 5.10.2. Ví dụ mô phỏng thuật toán 5.11. Tìm kiếm nhị phân 5.11.1. Thuật toán và đánh giá độ phức tạp thuật toán 5.11.2. Ví dụ mô phỏng thuật toán N ộ i d u n g b à i tậ p th ự c hành', cài đặt chương trình các thuật toán sắp xếp và tìm kiếm. Chương 6. Các thuật toán trên đồ thị 3,5(4/0/3) 6.1. Các kliái niệm 6.2. Biếu diễn đồ thị trong máy tính 6.2.1. Ma trận kề 6.2.2. Danh sách cạnh 6.2.3. Danh sách kề 6.3. Duyệt đồ thị 6.3.1. Duyệt theo chiều rộng 6.3.2. Duyệt theo chiều sâu 6.4. Đường đi ngắn nhất 6.4.1. Bài toán 6.4.2. Thuật toán tìm đường ngắn nhất Dijkstra
6.5. Cây khung 6.5.1. Cây khung, cây khung nhỏ nhất 6.5.2. Thuật toán J. Kruskal 6.5.3. Thuật toán Prim 6 .6 . Tính liên thông của đồ thị 6.6.1. Định nghĩa, đồ thị liên thông, đầy đủ, bao đóng 6.6.2. Thuật toán Warshal Nội dung bài tập thực hành: Cài đặt chương trình giải các bài toán (6 . 3 . 1 , 6.3.2, 6.4.2, 6.5.2, 6.5.3) C h ư ơ n g 7. C ác ki th u â t thiết kế th u â t toan 7,5(4/2/3) 7.1. Chia để trị và đệ quy 7.1.1. Các khái niệm chia để trị, kết hợp nghiệm 7.1.2. Bài toán tháp Hà nội 7.2. Duyệt 7.2.1. Duyệt tuyến tính 7.2.2. Duyệt phi tuyến (vét cạn quay lui) 7.2.3. Bài toán tám con hậu 7.3. Tham lam. 7.3.1. Các khái niệm lựa chọn ăn tham, cấu trúc tối un 7.3.2. Bài toán tô màu đồ thị 7.4. Quy hoạch động 7.4.1. Các khái niệm 7.4.2. Các bước thuật toán 7.4.3. M ộ t số ví dụ Nội dung bài tập và thực hành: Cài đặt chương trình giải các bài toán (7.1.2, 7.2.3, 7.3.2, 7.4.3) 8. T ài liệu học tậ p và th am khảo [1] Thomas H. Cormen, Introduction to Algorithms, MIT Press, 1990. [2] R. Sedgevick, Algorithms, Addison - Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán (tập 1, 2). [3] John Wiley & Son, Data structures and algorithms with object- o rie n te d d e s ig n p a tte rn s in c +\ 1999. 150
CÁU TRỦC MÁY VI TÍNH VÀ KỸ THUẬT GHÉP NÓI 1. Số đon vị học trình: 5 dvht 2. Phân bổ thòi gian Lý thuyết: 60 tiết Thực hành: 30 tiết (15 tiết quy chuẩn) 3. Mòn học tiên quyết • Các môn Toán, Nguyên lý kỹ thuật điện từ, Điện tử số và một trong số các ngôn ngữ lập trình cơ bản như Pascal, c hay Assembly. 4. Mục tiêu môn học Trang bị cho sinh viên những hiểu biết cơ bản về cấu tạo và các nguyên tắc tổ chức, hoạt động về phan cứng cũng như phần mềm của một hệ thống máy vi tính. Từ đó sinh viên có thể biết cách sử dụng máy vi tính cho các nhu cầu học tập, nghiên cứu cũng như có thể thiết kế, sử dụng chúng trong các hệ thông đo lường điềukhiến hiện đại. 5. Mô tả tóm tắt nội dung môn học Nguyên lý, chức năng các bộ vi xử lý. Bộ nhớ và các thiết bị ngoại vi. Các bus truyền dẫn, các card ghép nối và các chip bổ trợ. Phần thực hành bô trợ cho các kiến thức về lý thuyết và cung cấp khả năng giải quyết một số bài toán ghép nối máy tính trong thực tế. 6. Phương thức kiểm tra đánh giá Hệ số điểm phần ihi lý thuyết: 0 ,8 Hệ số điểm phần thi thực hành: 0,2 7. Nội dung chi tiết môn học số tiết (LT/BT/TH) Phẩn I. Lý th u y ế t Chirong 1. Giói thiệiu khái quát về máy vi tính và các thiết bị ngoại vi 7(7/0/0) 1 .1 .Máy tính và các thành phần cơ bản 1.1.1. Một số khái niệm cơ bản và phân loại 1.1.2. Các lĩnh vực ứng dụng của máy tính 1.1.3. Lịch sử phát triển của máy vi tính 151
1.1.4. Các bộ phận cơ bản của máy tính 1.1.5. Ghép nối CPU với các thiết bị ngoại vi 1.1.6. Các chương trình trong máy tính 1.2. Các phép tính số trong máy tính 1.2.1. Các hệ đếm trong máy tính 1.2.2. Mã hoá các ký tự - Bảng mã ASCII 1.2.3. Các mã phát hiện và sửa lỗi 1.2.4. Biểu diễn các số nguyên không dấu và có dấu 1.2.5. Các số có dấu chấm động 1.2.6. Các phép tính số học với số nhị phân 1.3. Các mạch điện tử số trong máy tính 1.3.1. Đại số logic 1.3.2. Các mạch điện tử số 1.3.3. Mạch tính số học và logic ALU 1.3.4. Cổng chốt số liệu vào và cửa ra 3 trạng thái Chưong 2. Các bộ vi xử lý 18(18/0/0) 2.1. Vi xử lý 8086 và họ 80x86 của Intel 2.1.1. Sơ đồ và các chân tín hiệu 2.1.2. Các thanh ghi và định địa chỉ nhớ 2.1.3. Truy nhập bộ nhớ và thiết bị vào ra 2.2. Các bộ đồng xử lý toán. 2.2.1. Cấu trúc các thanh ghi của 8087 2.2.2. Các kiểu dữ liệu trong bộ đồng xử lý 2.3. Vi xử lý 80286 2.3.1. Sơ đồ và các chân tín hiệu 2.3.2. Truy xuất bộ nhớ và vào/ra 2.4. Vi xử lý 80386 2.4.1. Cấu tạo và các thanh ghi 2.4.2. Tổ chức bộ nhớ 2.4.3. Chế độ bảo vệ phân đoạn 2.4.4. Chế độ bảo vệ phân trang 2.4.5. Chế độ 8086 ảo
2.5. Vi xử lý X0486 và Pentium 2.5.1. Kiến trúc RISC'/CISC và xử lý đường ống 2.5.2. Vi xừ lý 80486 2.5.3. Các vi xử lý Pentium 2.6. Các vi xử lý 64-bit Chưoug 3. Bộ nhớ chính 5(5/0/0) 3.1. Bộ nhớ bán dẫn 3.1.1. Phân loại 3.1.2. Nguyên lý hoạt động các linh kiện nhớ bán dẫn 3.2. Bộ nhớ chính 3.2.1. Tổ chức của một chip nhớ DRAM 3.2.2. Các chế độ làm tươi DRAM 3.2.3. Các chế độ hoạt động nhanh của DRAM 3.2.4. Các mô-đun DRAM hiện đại 3.2.5. Tổ chức vật lý bộ nhớ chính 3.2.6. Bộ nhớ cache Chương 4. Các chip bổ trọ- 10(10/0/0) 4.1. Chip điều khiển ngắt PIC-8259A 4.1.1. Cấu tạo và nguyên tắc hoạt động 4.1.2. Lập trình với 8259 4.2. Chip ghép nối ngoại vi khả trình PP1-8255A 4.2.1. Cấu tạo và nguyên tắc hoạt động 4.2.2. Lập trình với 8255 4.3. Chip định thời khả trình PIT-8253 4.3.1. Câu tạo và nguyên tắc hoạt động 4.3.2. Lập trình với 8253 4.4. Chip điều khiển thâm nhập nhớ trực tiếp DMA - 8237 4.4.1. Phương pháp DMA 4.4.2. Chip điều khiển DMAC 40. RAM CMOS và đồng hồ thời gian thực 153