Bồi dưỡng và PT năng khiếu Tin học

BỒI DƯỠNG
và
PHÁT TRIỂN NĂNG KHIẾU
TIN HỌC
1
NỘI DUNG LÀM VIỆC
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
YÊU CẦU CHUNG
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
CHƯƠNG TRÌNH -
SẢN PHẨM TIN HỌC

Cấu trúc dữ liệu + Giải thuật =
Chương trình
4

5
CÁC MỨC CHUẨN BỊ
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
NỘI DUNG CHUYÊN ĐỀ
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).
NỘI DUNG CHUYÊN ĐỀ
10
NỘI DUNG CHUYÊ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.
11
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.
12
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.
13
VÉT CẠN, ĐỆ QUY, TÌM KIẾM 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.
14
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.
15
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, . . .
16
ĐỒ 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.
17
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.
18
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, . . .
19
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.
20
NGÔN NGỮ HÌNH THỨC
Ô TÔ MAT
Ô 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Ấ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.
22
LÔ GIC & ĐẠ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.

23
SẮP XẾP & TÌM KIẾM
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
CÁC BÀI TOÁN TƯƠNG TÁC NGƯỜI - 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.
25
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.
26
ĐỘ PHỨC TẠP CỦA GIẢI THUẬT
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
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,
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
CÔNG TÁC GIẢNG DẠY
VÍ DỤ - RÚT GỌN
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
Phần I – hướng dẫn lập trình
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
LẬP TRÌNH – GIAI ĐoẠN I
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
LẬP TRÌNH – GIAI ĐoẠN I
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
LẬP TRÌNH – GIAI ĐoẠN I
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
LẬP TRÌNH – GIAI ĐoẠN I
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
LẬP TRÌNH – GIAI ĐoẠN I
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
LẬP TRÌNH – GIAI ĐoẠN II – CT kết quả
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
NHận xét bổ sung
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
BÀI TẬP mở rộng
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