nội dung chuyên đề
1. các giải thuật số và xử lý số lớn ,
2. xâu và xử lý xâu,
3. kỹ thuật lập trình,
4. vét cạn, đệ quy và tìm kiếm quay lui,
5. các bài toán tổ hợp,
6. quy hoạch động,
7. đồ thị,
8. các bài toán có nội dung hình học,
9. xử lý bit và các loại cơ số,
10.trò chơi,
11.ngữ pháp hình thức và ô tô mát hữu hạn,
12.cấu trúc dữ liệu,
13.lô gic và đại số mệnh đề,
14.sắp xếp và tìm kiếm,
15.các bài toán tương tác người – máy,
16.lớp bài toán giao nộp kết quả,
17.đánh giá độ phức tạp của giải thuật (o
lớn).
giẢi thuẬt và sỐxỬ lý sỐ lỚn
 kiểm tra tính nguyên tố, tìm số nguyên tố,
 kiểm tra nguyên tố cùng nhau,
 xác định số dư, ưscln, bscnn,
 lưu trữ số lớn,
 các phép cộng, trừ,
 nhân số lớn,
 so sánh hai số,
 kỹ thuật lập trình áp dụng với các bài toán
xử lý số lớn.
xâu và xử lí xâu
 hàm và thủ tục chuẩn,

 xâu palindrome,
 xâu con và xâu con chung,
 nén và giải mã xâu,
 xâu và cấu trúc cây,
 các giải thuật xử lý xâu.
kỹ thuật lập trình
 kỹ năng trình bày giải thuật và thảo luận,
 kỹ thuật xây dựng chương trình top-
down,
 các công tác chuẩn bị ngoài máy,
 lập trình theo công thức truy hồi,
 xác định đơn vị dữ liệu và đơn vị xử lý,
 kỹ thuật dữ liệu hóa giải thuật,
 kỹ thuật khảo sát và lập trình nhiều giai
đoạn,
 các tiểu xảo lập trình,
 kỹ thuật chuẩn bị tests và hiệu chỉnh
chương trình.
vét cạn, đệ quy, quay lui
 vai trò của vét cạn,
 giải thuật tham lam,
 hạn chế phạm vi kiểm tra, tìm kiếm,
 vai trò và phạm vi ứng dụng của đệ quy,
 đệ quy và sơ đồ lặp,
 sơ đồ tìm kiếm quay lui,
 các bài toán mẫu.
tổ hợp
 hoán vị, chỉnh hợp, tổ hợp,
 tập con và thứ tự từ điển,
 nguyên lý dirichle,

 dãy số fibonacci,
 tam giác pascal,
 mã grey,
 số catalan và các bài toán biểu thức
ngoặc,
 số stirling.
quy hoạch động
 nguyên lý quy hoạch động,
 bài toán cái túi,
 đệ quy và quy hoạch động,
 vấn đề dẫn xuất phương án tối ưu,
 các bài toán giải theo phương pháp quy
hoạch động: đổi tiền, phân tích một số ra
tổng các số hạng, bài toán trò chơi, . . .
đồ thị
 các khái niệm cơ bản,
 biểu diễn đồ thị,
 tìm đường đi ngắn nhất,
 chu trình euler, hamington,
 cây khung,
 song liên thông,
 đồ thị hai phía,
 cây đỏ đen, cây tứ phân, cây nhị phân cân
bằng
 luồng và ghép cặp,
 tìm kiếm theo chiều rộng, theo chiều sâu.
các bài toán có nội dung hình học
 các dạng tọa độ, biểu diễn điểm, đường
thẳng, đoạn thẳng,
 dạng biểu diễn véc tơ,

 điểm trong, điểm ngoài,
 vị trí tương đối giữa các đoạn thẳng,
đường thẳng, đường tròn, chữ nhật, . . .
 bao lồi,
 chu vi và diện tích đa giác,
 giao và không giao nhau,
 quản lý sai số làm tròn.
xử lí bit và cơ số
 các phép xử lý bit,
 kỹ thuật đánh dấu bằng bit,
 các loại cơ số đặc biệt: cơ số 3, cơ số nhị
phân âm, cơ số nhị phân fibonacci, . . .
trò chơi
 trò chơi đối kháng và không đối kháng,
 trò chơi nim, euclid,
 số grundy,
 chiến lược điều khiển,
 trò chơi ma trận,
 kỹ thuật bảng phương án.
ngôn ngữ hình thức và automat
 ô tô mát hữu hạn tiền định (dfa),
 các tham số và dạng bài toán cơ bản,
 ô tô mát và nhận dạng văn phạm,
 đặc thù lập trình giải bài toán ô tô mát,
 không gian điều khiển và không gian
trạng thái,
 stack và nhận dạng văn phạm,
 nhận dạng chu trình và xác định trạng
thái,
 kỹ thuật loang hai phía.

cấu trúc dữ liệu
 các loại cấu trúc dữ liệu cơ sở,
 stack, queu,
 các loại cây tìm kiếm,
 quản lý heap,
 hàm băm,
 cây hậu tố,
 dữ liệu vòng tròn,
 dữ liệu nén,
 quan hệ giữa dữ liệu và độ phức tạp của
giải thuật.
logic và đại số mệnh đề
 các phép tính lô gic,
 các hằng đẳng thức cơ sở của đại số mệnh
đề,
 biến đổi và rút gọn biểu thức lô gic,
 cực tiểu hóa biểu thức lô gic,
 phương pháp “cards tối ưu”,
 kỹ thuật lập trình với các bài toán lô gic
phức tạp.
các bài toán tương tác người và máy
 lớp bài toán tương tác,
 đặc trưng lập trình, thư viện hỗ trợ tương
tác,
 chiến lược chỉnh lý điều khiển: “sai và
chỉnh”,
 kỹ thuật hiệu chỉnh chương trình.
lớp bài toán giao nộp kết quả
 đặc trưng của các bài toán cho trước
input,

 lựa chọn, tổ chức điểm ngắt để ngừng và
chạy tiếp chương trình,
 tổ chức hoạt động song song: thực hiện
chương trình và giải các bài toán khác,
 tổ chức kiểm soát tiến độ tìm lời giải.
độ phứt tạp thuật toán
 khái niệm o lớn,
 các giải thuật độ phức tạp o(nlogn),
 các giải thuật độ phức tạp o(n2) và cao
hơn,
 bài toán np – khó,
 kích thước bài toán và lựa chọn giải thuật.
công tác giảng dạy
 ban đầu cần cung cấp cho hs các đoạn ct
chuẩn xác, giúp hs kết nối chúng thành
chương trình hoàn thiện,
 tập cho hs trình bày lại giải thuật trên
ngôn ngữ của dữ liệu,
 giữ tiến độ lập trình đủ chậm – thiết kế ct
chính trước và khung chương trình,
 tập thói quen vừa lập trình vừa kiểm tra,
hiệu chỉnh,
 mỗi bài toán thường liên quan tới vài ba
chuyên mục khác nhau, kể cả các vấn đề
chưa chính thức triển khai, gv cần giới
thiệu:
 chủ đề liên quan,
 dự kiến thời điểm xem xét cụ thể,
chi tiết và đầy đủ,
 cấu trúc dữ liệu tương ứng,

 giải thuật,
 nhấn mạnh chủ đề chính,
 xử lý tương tự với các v/đ đã dạy,
 nhưng để cho hs chủ động giải quyết.
 3 

phẦn 1. bài toán liỆt kê
§1. nhẮc lẠi mỘt sỐ kiẾn thỨc đẠi sỐ tỔ hỢp
1.1. chỈnh hỢp lẶp
1.2. chỈnh hỢp không lẶp
1.3. hoán vỊ
1.4. tỔ hỢp
§2. phương pháp sinh (generation)
2.1. sinh các dãy nhỊ phân đỘ dài n
2.2. liỆt kê các tẬp con k phẦn tỬ
2.3. liỆt kê các hoán vỊ
§3. thuẬt toán quay lui
3.1. liỆt kê các dãy nhỊ phân đỘ dài n
3.2. liỆt kê các tẬp con k phẦn tỬ
3.3. liỆt kê các chỈnh hỢp không lẶp chẬp k
3.4. bài toán phân tích sỐ
3.5. bài toán xẾp hẬu
§4. kỸ thuẬt nhánh cẬn
4.1. bài toán tỐi ưu
4.2. sỰ bùng nỔ tỔ hỢp
4.3. mô hình kỸ thuẬt nhánh cẬn
4.4. bài toán ngưỜi du lỊch
4.5. dãy abc
phẦn 2. cẤu trúc dỮ liỆu và giẢi thuẬt
§1. các bưỚc cơ bẢn khi tiẾn hành giẢi các bài

toán tin hỌc
1.1. xác đỊnh bài toán
1.2. tìm cẤu trúc dỮ liỆu biỂu diỄn bài toán
1.3. tìm thuẬt toán
1.4. lẬp trình
1.5. kiỂm thỬ
1.6. tỐi ưu chương trình
§2. phân tích thỜi gian thỰc hiỆn giẢi thuẬt
2.1. giỚi thiỆu
2.2. các ký pháp đỂ đánh giá đỘ phỨc tẠp tính
toán
2.3. xác đỊnh đỘ phỨc tẠp tính toán cỦa giẢi
thuẬt
2.4. đỘ phỨc tẠp tính toán vỚi tình trẠng dỮ
liỆu vào
2.5. chi phí thỰc hiỆn thuẬt toán
§3. đỆ quy và giẢi thuẬt đỆ quy
3.1. khái niỆm vỀ đỆ quy
3.2. giẢi thuẬt đỆ quy3.3. ví dỤ vỀ giẢi thuẬt
đỆ quy
3.4. hiỆu lỰc cỦa đỆ quy
§4. cẤu trúc dỮ liỆu biỂu diỄn danh sách
4.1. khái niỆm danh sách
4.2. biỂu diỄn danh sách trong máy tính
§5. ngăn xẾp và hàng đỢi
5.1. ngăn xẾp (stack
5.2. hàng đỢi (queue
§6. cây (tree)
6.1. đỊnh nghĩa
6.2. cây nhỊ phân (binary tree)

6.3. biỂu diỄn cây nhỊ phân
6.4. phép duyỆt cây nhỊ phân
6.5. cây k_phân
6.6. cây tỔng quát
§7. ký pháp tiỀn tỐ, trung tỐ và hẬu tỐ
7.1. biỂu thỨc dưỚi dẠng cây nhỊ phân
7.2. các ký pháp cho cùng mỘt biỂu thỨc7.3.
cách tính giá trỊ biỂu thỨc
7.4. chuyỂn tỪ dẠng trung tỐ sang dẠng hẬu
tỐ
7.5. xây dỰng cây nhỊ phân biỂu diỄn biỂu
thỨc
§8. sẮp xẾp (sorting)
8.1. bài toán sẮp xẾp
8.2. thuẬt toán sẮp xẾp kiỂu chỌn
(selectionsort)
8.3. thuẬt toán sẮp xẾp nỔi bỌt (bubblesort)
 4 

8.4. thuẬt toán sẮp xẾp kiỂu chèn
(insertionsort)
8.5. sẮp xẾp chèn vỚi đỘ dài bưỚc giẢm dẦn
(shellsort)
8.6. thuẬt toán sẮp xẾp kiỂu phân đoẠn
(quicksort)
8.7. thuẬt toán sẮp xẾp kiỂu vun đỐng
(heapsort)
8.8. sẮp xẾp bẰng phép đẾm phân phỐi
(distribution counting
8.9. tính Ổn đỊnh cỦa thuẬt toán sẮp xẾp

(stability)
8.10. thuẬt toán sẮp xẾp bẰng cơ sỐ (radix
sort)
8.11. thuẬt toán sẮp xẾp trỘn (mergesort
8.12. cài đẶt
8.13. đánh giá, nhẬn xét
§9. tìm kiẾm (searching)
9.1. bài toán tìm kiẾm
9.2. tìm kiẾm tuẦn tỰ (sequential search)
9.3. tìm kiẾm nhỊ phân (binary search)
9.4. cây nhỊ phân tìm kiẾm (binary search tree -
bst)
9.5. phép băm (hash)
9.6. khoá sỐ vỚi bài toán tìm kiẾm
9.7. cây tìm kiẾm sỐ hỌc (digital search tree -
dst)
9.8. cây tìm kiẾm cơ sỐ (radix search tree - rst)
9.9. nhỮng nhẬn xét cuỐi cùng
phẦn 3. quy hoẠch đỘng
§1. công thỨc truy hỒi
1.1. ví dỤ
1.2. cẢi tiẾn thỨ nhẤt
1.3. cẢi tiẾn thỨ hai
1.4. cài đẶt đỆ quy
§2. phương pháp quy hoẠch đỘng
2.1. bài toán quy hoẠch
2.2. phương pháp quy hoẠch đỘng
§3. mỘt sỐ bài toán quy hoẠch đỘng
3.1. dãy con đơn điỆu tăng dài nhẤt
3.2. bài toán cái túi

3.3. biẾn đỔi xâu
3.4. dãy con có tỔng chia hẾt cho k
3.5. phép nhân tỔ hỢp dãy ma trẬn
3.6. bài tẬp luyỆn tẬp
phẦn 4. các thuẬt toán trên đỒ thỊ
§1. các khái niỆm cơ bẢn
1.1. đỊnh nghĩa đỒ thỊ (graph)
1.2. các khái niỆm
§2. biỂu diỄn đỒ thỊ trên máy tính
2.1. ma trẬn kỀ (adjacency matrix
2.2. danh sách cẠnh (edge list)
2.3. danh sách kỀ (adjacency list)
2.4. nhẬn xét
§3. các thuẬt toán tìm kiẾm trên đỒ thỊ
3.1. bài toán
3.2. thuẬt toán tìm kiẾm theo chiỀu sâu (depth
first search)
3.3. thuẬt toán tìm kiẾm theo chiỀu rỘng
(breadth first search)
3.4. đỘ phỨc tẠp tính toán cỦa bfs và dfs
§4. tính liên thông cỦa đỒ thỊ
4.1. đỊnh nghĩa
4.2. tính liên thông trong đỒ thỊ vô hưỚng
4.3. đỒ thỊ đẦy đỦ và thuẬt toán warshall
4.4. các thành phẦn liên thông mẠnh
§5. vài Ứng dỤng cỦa dfs và bfs
5.1. xây dỰng cây khung cỦa đỒ thỊ
5.2. tẬp các chu trình cơ sỞ cỦa đỒ thỊ
5.3. bài toán đỊnh chiỀu đỒ thỊ
5.4. liỆt kê các khỚp và cẦu cỦa đỒ thỊ

§6. chu trình euler, đưỜng đi euler, đỒ thỊ euler
6.1. bài toán 7 cái cẦu
6.2. đỊnh nghĩa
6.3. đỊnh lý
6.4. thuẬt toán fleury tìm chu trình euler
6.5. cài đẶt
 5 

6.6. thuẬt toán tỐt hơn
§7. chu trình hamilton, đưỜng đi hamilton, đỒ thỊ
hamilton
7.1. đỊnh nghĩa
7.2. đỊnh lý
7.3. cài đẶt
§8. bài toán đưỜng đi ngẮn nhẤt
8.1. đỒ thỊ có trỌng sỐ
8.2. bài toán đưỜng đi ngẮn nhẤt
8.3. trưỜng hỢp đỒ thỊ không có chu trình âm -
thuẬt toán ford bellman
8.4. trưỜng hỢp trỌng sỐ trên các cung không
âm - thuẬt toán dijkstra
8.5. thuẬt toán dijkstra và cẤu trúc heap
8.6. trưỜng hỢp đỒ thỊ không có chu trình -
sẮp xẾp tô pô
8.7. đưỜng đi ngẮn nhẤt giỮa mỌi cẶp đỈnh -
thuẬt toán floyd
8.8. nhẬn xét
§9. bài toán cây khung nhỎ nhẤt
9.1. bài toán cây khung nhỎ nhẤt
9.2. thuẬt toán kruskal (joseph kruskal - 1956)

9.3. thuẬt toán prim (robert prim - 1957)
§10. bài toán luỒng cỰc đẠi trên mẠng
10.1. các khái niỆm
10.2. mẠng thẶng dư và đưỜng tăng luỒng
10.3. thuẬt toán ford-fulkerson (l.r.ford &
d.r.fulkerson - 1962)
10.4. thuẬt toán preflow-push (goldberg - 1986)
10.5. mỘt sỐ mỞ rỘng
§11. bài toán tìm bỘ ghép cỰc đẠi trên đỒ thỊ hai
phía
11.1. đỒ thỊ hai phía (bipartite graph)
11.2. bài toán ghép đôi không trỌng và các khái
niỆm
11.3. thuẬt toán đưỜng mỞ
11.4. cài đẶt
§12. bài toán tìm bỘ ghép cỰc đẠi vỚi trỌng sỐ
cỰc tiỂu trên đỒ thỊ hai phía - thuẬt toán hungari
12.1. bài toán phân công
12.2. phân tích
12.3. thuẬt toán
12.4. bài toán tìm bỘ ghép cỰc đẠi vỚi trỌng
sỐ cỰc đẠi trên đỒ thỊ hai phía
12.5. nâng cẤp
§13. bài toán tìm bỘ ghép cỰc đẠi trên đỒ thỊ
13.1. các khái niỆm
13.2. thuẬt toán edmonds (1965)
13.3. thuẬt toán lawler (1973)
13.4. cài đẶt
13.5. đỘ phỨc tẠp tính toán
chương 1: kĩ thuẬt phân tích giẢi thuẬt

1.1 tỔng quan
1.2 sỰ cẦn thiẾt phẢi phân tích giẢi thuẬt
1.3 thỜi gian thỰc hiỆn cỦa giẢi thuẬt
1.4 tỶ suẤt tăng và ðỘ phỨc tẠp cỦa giẢi thuẬt
1.5 cách tính ðỘ phỨc tẠp
1.6 phân tích các chương trình ðỆ quy
1.7 tỔng kẾt chương 1
bài tẬp chương 1
chương 2: sẮp xẾp
2.1 tỔng quan
2.2 bài toán sẮp xẾp
2.3 các phương pháp sẮp xẾp ðơn giẢn
2.4 quicksort
2.5 heapsort
2.6 binsort
2.7 tỔng kẾt chương 2
bài tẬp chương 2
chương 3: kĩ thuẬt thiẾt kẾ giẢi thuẬt
3.1 tỔng quan
3.2 kĩ thuẬt chia ðỂ trỊ
3.3 kĩ thuẬt “tham ăn
3.4 quy hoẠch ðỘng
3.5 kĩ thuẬt quay lui
3.6 kĩ thuẬt tìm kiẾm ðỊa phương
3.7 tỔng kẾt chương 3
bài tẬp chương 3
chương 4: cẤu trúc dỮ liỆu và giẢi thuẬt lưu trỮ
ngoài
4.1 tỔng quan
4.2 mô hình xỬ lý ngoài

4.3 ðánh giá các giẢi thuẬt xỬ lý ngoài
4.4 sẮp xẾp ngoài