Boi duong hoc sinh gioi tin hoc 8

1
Các vấn đề chung,
Nội dung các chuyên đề cần bồi dưỡng cho HS, (9)
Tổ chức một giờ dạy và học cụ thể. (29)
2
Trang bị kiến thức chuyên ngành,
Hình thành và phát triển các các tính cách phẩm chất nghề nghiệp,
Tạo lập và cũng cố lòng say mê tìm hiểu, khám phá,
Rèn luyện đạo đức, tính cách .
3

4
5
Các giải thuật cơ sở,
Kỹ thuật lập trình.
Các bài toán có kích thước lớn và độ phức tạp cao
Các giải thuật cho từng lớp bài toán,
Nghệ thuật lập trình.

6
BÀI TẬP
Phần lớn các bài tập nên phát biểu dưới dạng bài toán thực tế  HS xây dựng mô hình toán học, xác định giải thuật và cấu trúc dữ liệu, lập trình và hiệu chỉnh;
Hình thức có tác động lớn đến HS: cách phát biểu trau chuốt và hài hước, hình vẽ, ví dụ;
Cần xác định rõ miền xác định của mọi tham số;
Nội dung phải có tính trung lập cao: tránh các vấn đề nhậy cảm, bạo lực.

7
Từ cụm lúa von thứ nhất thí nghiệm viên chiết xuất được A phân tử chất Giberline (một chất kích thích tăng trưởng thực vật) đựng vào bình 1, từ cụm lúa von thứ nhất thí nghiệm viên chiết xuất được B phân tử chất Giberline đựng vào bình 2. Sau đó hai bình này được đổ chung vào một chai để cất giữ trong tủ lạnh.
Hãy cho biết trong chai có bao nhiêu phân tử Giberline.
Dữ liệu: Vào từ file văn bản GIB.INP gồm một dòng chứa 2 số nguyên A và B (0 ≤ A, B ≤ 1018).
Kết quả: Đưa ra file văn bản GIB.OUT kết quả tìm được dưới dạng số nguyên.

BÀI TẬP
8
Các giải thuật số và xử lý số lớn ,
Xâu và xử lý xâu,
Kỹ thuật lập trình,
Vét cạn, đệ quy và tìm kiếm quay lui,
Các bài toán tổ hợp,
Quy hoạch động,
Đồ thị,
Các bài toán có nội dung hình học,
Xử lý bit và các loại cơ số,


9
Trò chơi,
Ngữ pháp hình thức và ô tô mát hữu hạn,
Cấu trúc dữ liệu,
Lô gic và đại số mệnh đề,
Sắp xếp và tìm kiếm,
Các bài toán tương tác người – máy,
Lớp bài toán giao nộp kết quả,
Đánh giá độ phức tạp của giải thuật (O lớn).
10
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.
11
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.
12
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.

13
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.
14
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.

15
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, . . .
16
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.
17
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.

18
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, . . .

19
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.
20
Ô 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.

21
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.
22
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.


23
Các phương pháp sắp xếp với dãy kích thước nhỏ,
Quick Sort,
Heap Sort,
Tìm kiếm dữ liệu trên tập đã sắp xếp,
Kỹ thuật phòng đệm trong tìm kiếm.

24
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.

25
Đặ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.

26
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.

27
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,

28
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.
29
Chuyên đề: Kỹ thuật tổ chức dữ liệu,
Mục tiêu phụ:
Lập trình Ô tô mat,
Loang theo chiều rộng.
Thời lượng:90 phút,
Đối tượng: Mới bắt đầu học, đã biết về khái niệm hoán vị.
30
Nhận dạng: Phép biến đổi cơ sở + Trạng thái + Dãy phép biến đổi,
Tập trạng thái đích: 24
1 ABCD 7 BACD 13 CABD 19 DABC
2 ABDC 8 BADC 14 CADB 20 DACB
3 ACBD 9 BCAD 15 CBAD 21 DBAC
4 ACDB 10 BCDA 16 CBDA 22 DBCA
5 ADBC 11 BDAC 17 CDAB 23 DCAB
6 ADCB 12 BDCA 18 CDBA 24 DCBA

31
Biến MT thành ô tô mat tương ứng:
ST:String[4]
Procedure FS;
Begin
ST := ST[2]+ST[1]+ST[3]+ST[4]
End;

Procedure FR;
Begin
ST := ST[4]+copy(ST,1,3)
End;

32
Chương trình con tính trạng thái cuối theo dãy biến đổi SI:
Procedure SD;
Var l, i: byte;
Begin l:= length(SI);
For i := 1 to l do
case SI[i] of
‘R’: FR;
‘S’: FS
end
End;
33
Sử dụng:
Const T:string[120] =
‘ABCD*ABDC*ACBD*ACDB*ADBC*ADCB*
BACD*BADC*BCAD*BCDA*BDAC*BDCA*
CABD*CADB*CBAD*CBDA*CDAB*CDBA*
DABC*DACB*DBAC*DBCA*DCAB*DCBA*’;


34
Khảo sát loang theo chiều rộng:
BEGIN
Repeat
Write(‘ SI = ‘); readln(SI);
If SI = ‘*’ then break;
SD;
K:= (pos(ST,T)-1) div 5 +1;
Writeln (‘ K =‘,k)
Until false
END.
35
Hướng dẫn cập nhật mảng BD bằng cách loang theo chiều rộng với việc sử dung CT đã lập:
Const BD:array[1..24] of string[10] =
(‘I’, ’2’, ’3’, ‘4’, ’5’, ’6’,
‘7’, ’8’, ’9’, 10’,’11’,’12’,
‘13’,’14’,’15’, 16’,’17’,’18’,
‘19’,’20’,’21’, 22’,’23’,’24’);
BD[i] ghi nhận xâu ngắn nhất biến đổi từ trạng thái 1 về trạng thái i.
36
Sau khi đã cập nhật tất cả các phần tử của BD – sửa lại chương trình chính để nhập SI từ file input và đưa ra file Output BD[k].
Nhận xét:
Không bỏ phí sản phẩm lập trình Giai đoạn I,
Dùng máy tính để hỗ trợ tư duy và lập trình,
Có thể lập trình tự động hóa khâu loang theo chiều rộng để cập nhật BD, nhưng như vậy – không kinh tế!
Lưu ý kỹ thuật loang theo chiều rộng,
Đặc thù lập trình bài toán loại Ô tô mat.
37
Các tiểu xảo lập trình:
Cách tìm thứ tự của trạng thái SI,
Đánh số các phần tử BD để tránh nhầm lẫn khi cập nhật,
Có thể sửa lại kiểu dữ liệu của BD sau khi cập nhật xong.
Mở rộng và nâng cấp CT: Luật “Lượng đổi thì chất đổi”: với dòng biến đổi SI lớn (~ 106 – 107 ký tự) cần sơ bộ rút gọn SI

38
Xây dựng mô đun tự động hóa khâu ghi nhận BD[i], so sánh kết quả và chi phí lập trình với cách làm ở lớp,
Lập trình với trường hợp file Input chứa xâu có thể tới 107 ký tự.
39
CƠ SỞ HÓA CÁC PHÉP XỬ LÝ
40
Eugène Charles Catalan (1814–1894)

41
SƠ ĐỒ TÍNH TOÁN
Chuẩn bị:
P0=1
Pj=0, j = 1 ÷ n,
Tiến:
k=1 ÷ n
Pj=Pj+Pj-1 , J=1 ÷ k
Lùi:
Pj=Pj-Pj-1 , J=k ÷ 1

42
Nhận xét
Thường phải làm việc với số lớn,
Chỉ sử dụng 2 phép tính: Cộng và trừ!

Tương tự:
Tam giác Pascal,
Bài toán đổi tiền,
Phân tích một số thành tổng k số hạng,
Tất cả các bài toán liên quan tới thứ tự từ điển.
43
THỨ TỰ TỪ ĐIỂN
Phương tiện sắp xếp tập đối tượng bất kỳ,
Phương tiện truy xuất trực tiếp từng đối tượng riêng lẻ:
Một tập con,
Một hoán vị,
Một cách phân rã,
Một nhánh cây,
. . . . . . . . . . . . . .
44
DỮ LIỆU ĐỐI TƯỢNG
45
TỔNG QUÁT HÓA
46
VÍ DỤ
Thuật toán tìm kiếm quay lui (BackTraking):
Chuan_bi;
Repeat
Mo_rong;
Ktra;
While not good do
Begin
Thay_doi;
Ktra
End;
Ktra_ket_thuc
Until Ket_thuc;
47
VÍ DỤ
Quy hoạch động:
Lặp lại phép xử lý với các giá trị của một tham số (Được 1 dòng hoặc cột),
Lặp lại bước xử lý trên với các tham số (Được các dòng hoặc cột).
Loang:
Mô tả loang từ một điểm,
Tìm các điểm xuất phát và khởi động loang.
48