M C L CỤ Ụ
I- S l c lý l ch tác gi :ơ ượ ị ả ............................................................................................ 2
II. S l c đc đi m tình hình đn v :ơ ượ ặ ể ơ ị .................................................................... 2
III. M c đích yêu c u c a gi i pháp:ụ ầ ủ ả ........................................................................ 3
1. Th c tr ng ban đu tr c khi áp d ng gi i phápự ạ ầ ướ ụ ả ................................................ 3
2. S c n thi t ph i áp d ng gi i phápự ầ ế ả ụ ả .................................................................... 3
3. N i dung gi i pháp ộ ả ............................................................................................... 4
3.1. Ti n trình th c hi nế ự ệ ........................................................................................ 4
3.2. Th i gian th c hi n: ờ ự ệ ...................................................................................... 4
3.3 Bi n pháp t ch cệ ổ ứ ............................................................................................ 4
IV. Hi u qu c a gi i phápệ ả ủ ả ..................................................................................... 20
V. M c đ nh h ng: ứ ộ ả ưở .......................................................................................... 20
VI. K t lu nế ậ ............................................................................................................... 20
1. Nh ng bài h c kinh nghi mữ ọ ệ ................................................................................ 20
2. Nh ng ki n ngh , đ xu tữ ế ị ề ấ ................................................................................. 21
TÀI LI U THAM KH OỆ Ả ......................................................................................... 22
1
S GD&ĐT AN GIANGỞ
TR NG THPT AN PHÚƯỜ C NG HÒA XÃ H I CH NGHĨA VI T NAMỘ Ộ Ủ Ệ
Đc l p - T do - H nh phúcộ ậ ự ạ
An Giang, ngày 24 tháng 12 năm 2018
BÁO CÁO
K t qu th c hi n sáng ki n, c i ti n, ế ả ự ệ ế ả ế gi i pháp k thu t, qu n lý, tácả ỹ ậ ả
nghi pệ, ng d ng ti n b k thu tứ ụ ế ộ ỹ ậ ho c nghiên c u khoa h c s ph m ngặ ứ ọ ư ạ ứ
d ngụ
I- S l c lý l ch tác gi :ơ ượ ị ả
- H và tên: Nguy n Phi Hùng.ọ ễ Nam, n : Nam.ữ
- Ngày tháng năm sinh: 19/09/1986.
- N i th ng trú: xã Vĩnh H i Đông, huy n An Phú, t nh An Giang.ơ ườ ộ ệ ỉ
- Đn v công tác: Tr ng THPT An Phú.ơ ị ườ
- Ch c v hi n nay: T phó chuyên môn.ứ ụ ệ ổ
- Lĩnh v c công tác: giáo viên Tin h c.ự ọ
II. S l c đc đi m tình hình đn v :ơ ượ ặ ể ơ ị
* Thu n l iậ ợ
Đc s quan tâm cua S GD&ĐT An Giang, s hô tr tich c c cua câp y ươ ư ơ ư ơ ư ủ
va chinh quyên đia ph ng, s đoan kêt, quyêt tâm nâng cao chât l ng giao duc cua ươ ư ươ
tâp thê cán b , giáo viên, nhân viên và h c sinh tr ng THPT An Phú. Ban Châp ộ ọ ườ
hanh Đang bô, Ban Th ng vu Đang y đa th c hiên tôt công tac lanh đao và đat ươ ủ ư
nhiêu thanh tich nôi bât.
Công tác chuyên môn luôn đc lãnh đo nhà tr ng quan tâm ch đo: nângượ ạ ườ ỉ ạ
cao chât l ng giao viên, nâng cao trinh đô chuyên môn; tiêp tuc đôi m i ph ng ươ ơ ươ
phap giang day va phát huy kh năng t h c, tr i nghi m sáng t o c a hoc sinh … ả ự ọ ả ệ ạ ủ
* Khó khăn
Nhà tr ng có k ho ch b i d ng h c sinh gi i t đu năm nh ng th iườ ế ạ ồ ưỡ ọ ỏ ừ ầ ư ờ
gian ôn t p không nhi u, ph n l n là các em t h c.ậ ề ầ ớ ự ọ
Tuy đc đào t o đúng chuyên ngành nh ng giáo viên gi ng d y tin h cượ ạ ư ả ạ ọ
trong nhà tr ng ph n l n là giáo viên tr , ch a có nhi u kinh nghi m trong vi cườ ầ ớ ẻ ư ề ệ ệ
b i d ng h c sinh gi i.ồ ưỡ ọ ỏ
2
Tuy yêu thích môn h c nh ng tâm lý h c sinh v n xem tin h c là môn phọ ư ọ ẫ ọ ụ
ch a có v trí quan tr ng. Bên c nh ph huynh h c sinh v n ch a th y đc xu thư ị ọ ạ ụ ọ ẫ ư ấ ượ ế
và t m quan tr ng c a công ngh thông tin (CNTT) nên không đu t nhi u choầ ọ ủ ệ ầ ư ề
con em trong v n đ này.ấ ề
* Tên báo cáo gi i pháp: “ảV n d ng ph ng pháp sinh đ gi i m t s bàiậ ụ ươ ể ả ộ ố
toán li t kê t h p theo th t t ệ ổ ợ ứ ự ừ đi n”ể.
* Lĩnh v c: ựChuyên môn.
III. M c đích yêu c u c a gi i pháp:ụ ầ ủ ả
1. Th c tr ng ban đu tr c khi áp d ng gi i phápự ạ ầ ướ ụ ả
Trong th i đi ngày nay, th gi i đang di n ra quá trình tin h c hóa trongờ ạ ế ớ ễ ọ
nhi u lĩnh v c ho t đng c a xã h i. Tin h c phát tri n nhanh nh vũ bão và đã trề ự ạ ộ ủ ộ ọ ể ư ở
thành m t ngành khoa h c đóng vai trò quan tr ng không th thi u đi v i s phátộ ọ ọ ể ế ố ớ ự
tri n c a xã h i.ể ủ ộ
Trong nh ng năm g n đây, các em h c sinh t c p ti u h c cho đn phữ ầ ọ ừ ấ ể ọ ế ổ
thông đã đc trang b nh ng hi u bi t ban đu v máy tính, bi t đc l i ích c aượ ị ữ ể ế ầ ề ế ượ ợ ủ
máy tính trong đi s ng và h c t p.Vi c h c sinh ti p c n v i tin h c đã t o n nờ ố ọ ậ ệ ọ ế ậ ớ ọ ạ ề
t ng c s ban đu đ đnh h ng cho các em có s thích và năng khi u nghiên c uả ơ ở ầ ể ị ướ ở ế ứ
khoa h c theo ngành khoa h c công ngh cao.ọ ọ ệ
Môn tin h c giúp h c sinh b c đu làm quen v i ph ng pháp gi i quy tọ ọ ướ ầ ớ ươ ả ế
v n đ theo quy trình công ngh và k năng s d ng máy tính ph c v h c t p vàấ ề ệ ỹ ử ụ ụ ụ ọ ậ
cu c s ng. Tin h c có ý nghĩa to l n đi v i s phát tri n trí tu , t duy thu t toán,ộ ố ọ ớ ố ớ ự ể ệ ư ậ
góp ph n hình thành h c v n ph thông cho h c sinh.ầ ọ ấ ổ ọ
Qua th c t gi ng d y môn Tin h c t i tr ng THPT An Phú, nh t là trongự ế ả ạ ọ ạ ườ ấ
công tác b i d ng h c sinh gi i, b n thân luôn suy nghĩ làm th nào đ các emồ ưỡ ọ ỏ ả ế ể
ti p c n m t cách t t nh t, d hi u nh t v i các thu t toán. Chính vì th tôi luônế ậ ộ ố ấ ễ ể ấ ớ ậ ế
chú tr ng đn vi c phân tích và h ng d n ọ ế ệ ướ ẫ gi i thu t đ các em ả ậ ể có th ểv n d ngậ ụ
và gi i ảbài toán theo ph ng pháp hi u qu nh t.ươ ệ ả ấ
2. S c n thi t ph i áp d ng gi i phápự ầ ế ả ụ ả
Nhi u qu c gia ý th c đc t m quan tr ng c a tin h c và có nh ng đu tề ố ứ ượ ầ ọ ủ ọ ữ ầ ư
l n vào lĩnh v c này đc bi t là lĩnh v c giáo d c nh m đào t o m t đi ngũ triớ ự ặ ệ ự ụ ằ ạ ộ ộ
th c tr có n n t ng tin h c v ng vàng nh m đáp ng nhu c u ngày càng cao c aứ ẻ ề ả ọ ữ ằ ứ ầ ủ
xã h i. Vi c đa tin h c vào gi ng d y t i các tr ng t c p Ti u H c đn THPTộ ệ ư ọ ả ạ ạ ườ ừ ấ ể ọ ế
nh m m c đích ph c p các ki n th c c b n v Tin h c, ngoài ra còn giúp h cằ ụ ổ ậ ế ứ ơ ả ề ọ ọ
sinh có kh năng phân tích, t ng h p, tr u t ng hóa, khái quát hóa v n đ, đcả ổ ợ ừ ượ ấ ề ặ
bi t là phát tri n kh năng t duy. Mu n v y ngoài vi c d y đi trà, h ng nghi pệ ể ả ư ố ậ ệ ạ ạ ướ ệ
và d y ngh c n t o đi u ki n cho h c sinh có năng khi u tin h c đc phát tri nạ ề ầ ạ ề ệ ọ ế ọ ượ ể
kh năng l p trình đ gi i quy t t t các bài toán.ả ậ ể ả ế ố
3
Đ có th phát huy nh ng tài năng tin h c thông qua ôn luy n đi tuy n h cể ể ữ ọ ệ ộ ể ọ
sinh gi i, đòi h i ng i d y ph i ti p c n v i nhi u d ng bài toán khó và n mỏ ỏ ườ ạ ả ế ậ ớ ề ạ ắ
v ng các ph ng pháp gi i quy t bài toán đó. Bài toán trong tin h c th ng r t đaữ ươ ả ế ọ ườ ấ
d ng và ph c t p, m i bài toán có th có nhi u ph ng pháp gi i khác nhau. Đ cóạ ứ ạ ỗ ể ề ươ ả ể
th l a ch n ph ng pháp thích h p cho bài toán, chúng ta có th phân chia các bàiể ự ọ ươ ợ ể
toán thành các d ng bài toán t ng quan và ch ra ph ng pháp gi i phù h p.ạ ổ ỉ ươ ả ợ
Bài toán li t kê là m t trong nh ng l p bài toán khó, có nhi u ph ng phápệ ộ ữ ớ ề ươ
gi i l p bài toán này và m t trong nh ng cách gi i hi u qu và phù h p nh t là sả ớ ộ ữ ả ệ ả ợ ấ ử
d ng Ph ng pháp sinh. Chính vì v y nên tôi ch n đ tài: ụ ươ ậ ọ ề “V n d ng ph ng phápậ ụ ươ
sinh đ gi i m t s bài toán li t kê t h p theo th t t đi n”ể ả ộ ố ệ ổ ợ ứ ự ừ ể trong ôn luy n h cệ ọ
sinh gi i môn Tin h c.ỏ ọ
3. N i dung gi i pháp ộ ả
3.1. Ti n trình th c hi nế ự ệ
Thông th ng, đ gi i m t bài toán theo m t ph ng pháp b t kì, tôi th ngườ ể ả ộ ộ ươ ấ ườ
h ng d n h c sinh ti p c n theo quy trình sau:ướ ẫ ọ ế ậ
3.2. Th i gian th c hi n: ờ ự ệ
Gi i pháp đc áp d ng trong quá trình b i d ng h c sinh gi i t nămả ượ ụ ồ ưỡ ọ ỏ ừ
2017-2018 đn nay.ế
3.3 Bi n pháp t ch cệ ổ ứ
Trong quá trình gi i bài t p, đ gi i đc bài toán d ng li t kê t h p theoả ậ ể ả ượ ạ ệ ổ ợ
th t t đi n b ng Ph ng pháp sinh thì ph i th a mãn hai đi u ki n sau:ứ ự ừ ể ằ ươ ả ỏ ề ệ
- T yêu c u c a đ bài, ta ph i xác đnh đc c u hình đu tiên và c u ừ ầ ủ ề ả ị ượ ấ ầ ấ
hình cu i cùng;ố
- T c u hình đang có, n u ch a ph i là c u hình cu i cùng ta ph i xây ừ ấ ế ư ả ấ ố ả
d ng đc thu t toán đ sinh c u hình ti p theo.ự ượ ậ ể ấ ế
Ph ng pháp sinh có th đc mô t nh sau:ươ ể ượ ả ư
4
Đc và phân ọ
tích đềThi t k ế ế
thu t toánậVi t ch ng ế ươ
trình Ki m thể ử
* M t s ký hi u đc dùng trong l u đ thu t toán:ộ ố ệ ượ ư ồ ậ
Trong đ tài này, tôi xin trình bài ba d ng toán c b n có th s d ng ề ạ ơ ả ể ử ụ
Ph ng pháp sinh đ x lí:ươ ể ử
5