Combinatorics and Graph Theory

Combinatorics and Graph Theory

Combinatorics studies the way in which discrete structures can be combined or arranged. Enumerative combinatorics concentrates on counting the number of certain combinatorial objects - e.g. the twelvefold way provides a unified framework for counting permutations, combinations and partitions. Analytic combinatorics concerns the enumeration of combinatorial structures using tools from  complex analysis and probability theory. In contrast with enumerative combinatorics which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.

Graph theory

[1]. Ngô Đắc Tân, Lý thuyết tổ hợp và đồ thị, NXB ĐHQGHN, 2004

[2]. Nguyễn Đức Nghĩa, Nguyên Tô Thành, Toán rời rạc, NXB GD, 1999

[3]. Phạm Thế Long (chủ biên), Toán rời rạc, NXB ĐHSP, 2006

[4]. Nguyễn Thế Vinh, Toán rời rạc, 2011

[5]. Hoàng Chí Thành, Giáo trình Tổ hợp, NXB ĐHQGHN, 2000
7. Nhiệm vụ của sinh viên:

7.1. Phần lý thuyết, bài tập, thảo luận

- Dự lớp  80 % tổng số thời lượng của học phần.

- Hoàn thành các bài tập được giao.

7.2. Phần bài tập lớn, tiểu luận.

- Hệ thống lại kiến thức cơ bản của mỗi chương và làm một số bài tập thêm ngoài giáo trình.

- Yêu cầu cần đạt: sinh viên hệ thống được các kiến thức cơ bản của từng chương, giải các bài tập thành thạo.

8. Tiêu chuẩn đánh giá sinh viên và thang điểm

- Điểm đánh giá bộ phận chấm theo thang điểm 10 với trọng số như sau:

• 
  Kiểm tra giữa học phần: 0,2
  
• 
  Chuyên cần: 0,1
  
• 
  Bài tập lớn, tiểu luận:
  
• 
  Điểm thi kết thúc học phần: 0,7.
  
• 
  Hình thức thi: thi viết (tự luận)
  

• 
  Điểm học phần: Là điểm trung bình chung có trọng số của các điểm đánh giá bộ phận và điểm thi kết thúc học phần làm tròn đến một chữ số thập phân.
  

Mã học phần : CAM – OPT 321

- Số tín chỉ : 4 [1;2;4] TCHP

- Số tiết : 60 LT: 55 BT: 10 KT: 2

- Loại môn học: Bắt buộc

- Các học phần tiên quyết: Đại số tuyến tính và hình học giải tích.

- Môn học trước:

- Môn học song hành:

- Các yêu cầu đối với môn học (nếu có):

- Bộ môn phụ trách: Toán ứng dụng

2. Mục tiêu của môn học.

2.1. Mục tieu về kiến thức:

Cung cấp kiến thức cơ bản về các kỹ thuật tính gần đúng, các bài toán nội suy, lớp bài toán tối ưu và ứng dụng trong thực tiễn.

- Phát triển năng lực làm việc trên các cấu trúc toán học trừu tượng thông qua việc hệ thống lại một số kiến thức trong đại số tuyến tính.

- Phát triển năng lực sử dụng ngôn ngữ toán học, thông qua việc sử dụng các ký hiệu toán học trình bày các khái niệm, chứng minh các định lý một cách khoa học, ngắn gọn,

- Hình thành kỹ năng phân tích, tổng hợp, khái quát hóa, trừu tượng hóa, cụ thể hóa

- Năng lực vận dụng toán học vào các môn học khác và vào cuộc sống, nhiều bài toán thực tế, nhiều vấn đề kỹ thuật, thực nghiệm sẽ được giải quyết bằng phương pháp bình phương bé nhất hoặc thong qua bài toán QHTT.

- Phát triển năng lực sử dụng các công cụ tính toán và máy tính cầm tay trong giải quyết các bài toán tìm gần đúng nghiệm của phương trình bằng cách thiết lập các hàm lặp trên máy tính Casio – fx 570 Ms.

- Phát triển năng lực sử dụng các kĩ thuật chứng minh toán học và năng lực xây dựng và phát triển các lập luận toán học thông qua việc chứng minh các tính chất các định lý trong nội dung học phần.

- Sử dụng các kiến thức được học giải thích được một cách rõ ràng, logic các kiến thức ở phổ thông có liên quan, đặc biệt thấy được sự tổng quát hóa của các khái niệm đã học ở phổ thông trong môn học.

- Hình thành năng lực tự học, tự nghiên cứu (biết xây dựng kế hoạch tự học, tự bồi dưỡng , tìm kiếm, khai thác, xử lý khoa học, có hiệu quả nguồn tài nguyên học tập.

- Hình thành năng lực giải bài tập toán sơ cấp ở phổ thông (bài toán tính tổng, tính tích phân hữu tỉ, bài toán QHTT hai biến)

Tạo hứng thú cho người học và khả năng áp dụng kiến thức được học vào các vấn đề của thực tiễn

Phương pháp số và tối ưu hóa được đưa vào giảng dạy ở hầu hết các trường sư phạm, các trường kĩ thuật và các trường kinh tế nó cung cấp cho người học những kiến thức về lý thuyết tìm gần đúng và một số phương pháp giải quyết bài toán Quy hoạch tuyến tính. Đây là cơ sở để nghiên cứu giải quyết một số các bài toán thực tiễn như các bài toán kinh tế, kĩ thuật...

Nội dung môn học:

+) Sai số và số gần đúng: Trong phần này sẽ giới thiệu một số khái niệm về lý thuyết sai số và công thức tính sai số.

+) Tìm gần đúng nghiệm của phương trình: Trong phần này giới thiệu một số phương pháp tìm gần đúng nghiệm của phương trình.

+ ) Tìm gần đúng nghiệm của hệ phương trình tuyến tính: Trong phần này giới thiệu một số phương pháp tìm gần đúng nghiệm của hệ phương trình.

+) Nội suy và phương pháp bình phương bé nhất: Trong phần này giới thiệu một số phương pháp nội suy đa thức và phương pháp bình phương bé nhất tìm công thức thực nghiệm của một số bài toán thực tiễn.

+) Tính gần đúng đạo hàm và tích phân xác định: Trong phần này sẽ trình bày một số phương pháp tính gần đúng đạo hàm và tích phân xác định.

+) Tìm gần đúng nghiệm của phương trình vi phân thường: Trong phần này sẽ giới thiệu một số phương pháp giải tích và phương pháp số tìm nghiệm gần đúng của phương trình vi phân thường.

+) Bài toán Quy hoạch tuyến tính: Trong phần này sẽ giới thiệu bài toán Quy hoạch tuyến tính, một số tính chất, thuật toán đơn hình giải bài toán quy hoạch tuyến tính, phương pháp hình học giải bài toán QHTT hai biến.

+) Bài toán đối ngẫu: Trong phần này sẽ giới thiệu bài toán đối ngẫu của một bài toán QHTT, mối quan hệ giữa hai bài toán.

+) Bài toán vận tải: Trong phần này sẽ giới thiệu về bài toán vận tải và thuật toán thế vị giải bài toán vận tải.

Calculating Method course presents the basic knowledge of the error theory, solution of an equation F(x) = 0, the interpolate theory, calculating approximate derivative and approximate intergral, the approximate solution of linear system, resolving approximate solution of normal differential equation; Linear Programming course presents the basic knowledge of the linear Programming problem in general and its properties, the simplex method, the dual problem, the special form of linear Programming problems as the transportation problem, syschronism produce problem.

[1]. Dương Thuỷ Vỹ, Giáo trình Phương pháp tính, NXB KH - KT, 2005.

[2] Phí Mạnh Ban, Quy hoạch tuyến tính , NXB Giáo dục, 2001.

[3]. Phí Mạnh Ban, Bài tập Quy hoạch tuyến tính , NXB Giáo dục, 2001.

[1]. Phạm Kỳ Anh, Giải tích số, NXB ĐHQG Hà Nội, 2005.

[2]. Trần Anh Bảo – Nguyễn Anh Khải – Phạm Văn Kiều – Ngô Xuân Sơn, Giải Tích số, NXB đại học Sư phạm, 2002

[3].Nguyễn Minh Chương – Nguyễn Văn Khải – Khuất Văn Ninh – Nguyễn Văn Tuấn – Nguyễn Tường, Giải tích số, NXB Giáo dục, 2007.

[4]. Tạ Văn Đĩnh, Phương pháp tính, NXB Giáo dục, 1994

[5]. Phan Văn Hạp – Lê Đình Thịnh, Phương pháp tính và các thuật toán, NXB Giáo dục, 2000..

[6]. Hà Huy Khoái, Số học thuật toán, NXB Khoa Học KT, 1997.

[7]. Trần Vũ Thiệu, Giáo trình tối ưu tuyến tính, NXB ĐHQGHN, 2004

[8]. Phí Mạnh Ban, Quy hoạch tuyến tính , NXB Giáo dục, 2001.

[9]. Phí Mạnh Ban, Bài tập Quy hoạch tuyến tính , NXB Giáo dục, 2001.

- Dự lớp  80 % tổng số thời lượng của học phần.

- Tìm hiểu trước các phần lý thuyết dưới sự hướng dẫn của giáo viên.

- Hoàn thành các bài tập được giao.

- Hệ thống lại kiến thức cơ bản của mỗi chương và làm một số bài tập thêm ngoài giáo trình.

- Yêu cầu cần đạt: sinh viên hệ thống được các kiến thức cơ bản của từng chương (cố gắng xây dựng theo bản đồ tư duy), giải các bài tập thành thạo.

8. Tiêu chuẩn đánh giá sinh viên và thang điểm

- Điểm đánh giá bộ phận chấm theo thang điểm 10 với trọng số như sau:

• 
  Kiểm tra giữa học phần: 0,2
  
• 
  Chuyên cần: 0,1
  
• 
  Bài tập lớn, tiểu luận:
  
• 
  Điểm thi kết thúc học phần: 0,7.
  
• 
  Hình thức thi: thi viết.
  

• 
  Điểm học phần: Là điểm trung bình chung có trọng số của các điểm đánh giá bộ phận và điểm thi kết thúc học phần làm tròn đến một chữ số thập phân.