Nội dung

Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan Họ và tên : Nguyễn Thị Lan Chức vụ : Giáo viên Trường : Trung học cơ sở Trần Cao Tên đề tài SKKN: HƯỚNG DẪN HỌC SINH GIẢI BÀI TOÁN SẮP XẾP TIN HỌC 8. Phần I. PHẦN MỞ ĐẦU I. ĐẶT VẤN ĐỀ 1. Lí do chọn đề tài Hiện nay trong hầu hết các lĩnh vực hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhiều nhất để khai thác thông tin một cách nhanh chóng và chính xác (ví dụ như: tra cứu từ điển, tìm sách trong thư viện, tra cứu thông tin về nhân viên trong một cơ quan, tra cứu điểm thi của một học sinh trong một trường học,…). Để đạt được mục tiêu tìm kiếm một cách nhanh chóng thì dữ liệu cần phải được sắp xếp sẵn, ngăn nắp, khoa học theo một trật tự, một hệ thống nhất định. Khi xây dựng một hệ thống quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong các chủ đề được quan tâm hàng đầu. Trong khi đó, với học sinh bậc THCS, việc lập trình giải quyết các bài toán, đặc biệt là các bài toán sắp xếp còn rất lúng túng, phương pháp còn nghèo nàn, thuật toán còn đơn điệu, điều này dẫn đến việc giải quyết các bài toán sắp xếp còn rất nhiều hạn chế. N¨m häc 2014 - 2015 Trang: 3 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn Xuất phát từ thực trạng của vấn đề trên,ThÞ sau mộtLan thời gian dài tìm hiểu, nghiên cứu tôi xây dựng chuyên đề: “Hướng dẫn học sinh giải bài toán sắp xếp” với mong muốn mang lại cho các em một cái nhìn tổng thể về bài toán sắp xếp nói chung, các thuật toán sắp xếp nói riêng, từ đó có thể tiếp cận được với các bài toán quản lý thông tin sau này. 2. Đối tượng nghiên cứu và phạm vi nghiên cứu a) Đối tượng nghiên cứu - Học sinh lớp 8 trường THCS Trần Cao b) Phạm vi nghiên cứu: Tìm hiểu và vận dụng các lý thuyết cơ bản về một số phương pháp sắp xếp như: phương pháp chọn trực tiếp (Selection Sort), chèn trực tiếp (Insertion Sort), sắp xếp nổi bọt (Bubble Sort), sắp xếp kiểu vun đống (Heap Sort), sắp xếp nhanh (Quick Sort), sắp xếp với độ dài bước giảm dần (Shell Sort),… Áp dụng đối với: - Phần: Câu lệnh lặp (xác định); Lặp với số lần chưa biết trước; Làm việc với dãy số; Kiểu dữ liệu mảng. - Bộ môn Tin học lớp 8. II. PHƯƠNG PHÁP TIẾN HÀNH Chuyên đề chủ yếu sử dụng các phương pháp nghiên cứu sau: - Phương pháp nghiên cứu lí luận: Nghiên cứu các vấn đề mang tính lí luận có liên quan đến đề tài (Muốn học tốt lập trình phải có thuật toán tốt, muốn có thuật toán tốt đòi hỏi học sinh phải tiếp cận với nhiều dạng bài toán, nhiều cách giải quyết bài toán,...) - Phương pháp điều tra: Với phương pháp này tôi tiến hành điều tra học sinh bằng các phiếu trắc nghiệm (chỉ rõ tính đúng, sai của thuật toán, dự đoán kết quả của thuật toán), các bài thực hành trên phòng máy để nắm chắc trình độ nhận thức, kỹ năng thực hành của từng đối tượng học sinh. Trên cơ sở đó làm nền tảng đối chiếu kết quả trước và sau khi thực hiện chuyên đề. N¨m häc 2014 - 2015 Trang: 4 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ - Phương pháp phỏng vấn: Thông qua việc trao Lan đổi trực tiếp thẳng thắn với học sinh về các biện pháp giúp các em thực hành tốt bộ môn, tôi đã nhận được những mong muốn, những băn khoăn, ..., và cả những ý kiến đóng góp của các em. Cũng từ đây tôi hình thành nên các giải pháp cho chuyên đề. - Phương pháp tạo tình huống: Thông qua các bài tập tạo tình huống, các bài tập có tính chất minh chứng tôi dần dần dẫn các em vào vấn đề và hướng dẫn các em tìm cách giải quyết. - Phương pháp quan sát, đánh giá, tổng hợp: Thông qua quá trình quan sát học sinh thực hành, đánh giá, tổng hợp kết quả thực hành giúp tôi có giải pháp để thực hiện và điều chỉnh chuyên đề của mình cho phù hợp và có hiệu quả nhất. Phần II. NỘI DUNG I. MỤC TIÊU CỦA ĐỀ TÀI - Trình bày được ý tưởng, thuật giải (thuật toán) của một số phương pháp sắp xếp thông dụng. - Giới thiệu được Code diễn đạt thuật giải. - Mô tả được thuật toán của phương pháp bằng ví dụ cụ thể. II. CÁC GIẢI PHÁP THỰC HIỆN Một số thuật toán sắp xếp: 1. Sắp xếp chọn trực tiếp (Selection Sort) 2. Sắp xếp chèn trực tiếp (Insertion Sort) 3. Sắp xếp nổi bọt (Bubble Sort) 4. Sắp xếp phân hoạch (Quick Sort) 5. Sắp xếp với bước giảm dần (Shell Sort) 6. Sắp xếp vun đống (Heap Sort) 1. Sắp xếp chọn trực tiếp (Selection Sort)  Ý tưởng: N¨m häc 2014 - 2015 Trang: 5 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ - Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa Lan phần tử này về vị trí đầu của dãy. Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại. - Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí dẫn đầu.  Thuật toán: Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ Đầu ra: a- mảng đã được sắp xếp tăng dần Bước 1: i = 0 Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1] Bước 3: Hoán vị a[i] với a[min] Bước 4: • nếu i Dừng thuật toán  Cài đặt (code): … Type mang:array[1..20] of integer; Function SelectionSort(a:mang, n:integer): integer; Var i, j, vtmin, tam: integer; Begin Writeln(‘------SAP XEP CHON TRUC TIEP------’); For i≔1 to n-1 do Begin N¨m häc 2014 - 2015 Trang: 6 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 Vtmin≔i; NguyÔn ThÞ Lan For j≔i+1 to n do If a[vtmin]>a[j] then vtmin≔j; {Hoan doi vi tri cua a[i] va a[vtmin]} Tam≔a[i]; A[i]≔a[vtmin]; A[vtmin]≔tam; End; Writeln(‘Day so sau khi sap xep la:’); For i≔1 to n do Write(a[i],’ ’); End; …  Ví dụ minh họa: Cho dãy số (mảng a): 12 2 8 5 1 6 4 15 Yêu cầu: Sắp xếp dãy số tăng dần. Mô tả các bước chạy khi thực hiện thuật toán với dãy trên: i=0 => j = 1 ¸ 7 và vtmin = 4 => Hoán đổi a[0] và a[4] N¨m häc 2014 - 2015 Trang: 7 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 N¨m häc 2014 - 2015 Trang: 8 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 2. Sắp xếp chèn trực tiếp (Insertion Sort)  Ý tưởng: Giả sử có dãy a0, a1,…,ai-1 đã được sắp xếp. Ý tưởng của thuật toán là chèn thêm phần tử mới ai vào vị trí thích hợp của đoạn a 1…ai-1 sao cho được dãy mới a1…ai đã được sắp xếp N¨m häc 2014 - 2015 Trang: 9 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Nguyên tắc sắp xếp như sau: đoạn gồm phần tử aLan 0 đã được sắp xếp, thêm a1 vào được a0,a1 đã được sắp xếp, tiếp tục thêm a 2 vào được a0, a1, a2 đã sắp xếp…tiếp tục để thêm an vào để được a0,a1,…,an đã sắp xếp.  Thuật toán: Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ Đầu ra: a- mảng đã được sắp xếp tăng dần Bước 1: i=1 //giả sử a[0] đã được sắp xếp Bước 2: x=a[i], tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i-1] để chèn a[i] vào Bước 3: đổi chỗ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để được vị trí chèn a[i] vào Bước 4: chèn a[i] vào vị trí pos tìm được bằng cách gán a[pos]=a[i] Bước 5: i=i+1 Nếu i lặp lại bước 2 Ngược lại => Dừng thuật toán  Cài đặt: … Type mang:array[1..20] of integer; Function InsertionSort(a:mang, n:integer): integer; Var i, j, pos, x: integer; Begin Writeln(‘------SAP XEP CHEN TRUC TIEP------’); For i≔2 to n do Begin N¨m häc 2014 - 2015 Trang: 10 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan X≔a[i]; {Luu gia tri cua phan tu a[i] de tranh khi de khi roi cho} Pos≔i-1; While (pos >= 1) and (a[pos]>x) do Begin A[pos+1]≔a[pos]; Pos≔pos-1; End; A[pos+1]≔x; {chen x vao day} End; Writeln(‘Day so sau khi sap xep la:’); For i≔1 to n do Write(a[i],’ ’); End;  Ví dụ minh họa:  Cho dãy số a: a = 12 2 8 5 1 6 4 15 Sắp xếp dãy tăng dần Mô tả các bước chạy khi thực hiện thuật toán với dãy trên: N¨m häc 2014 - 2015 Trang: 11 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 N¨m häc 2014 - 2015 Trang: 12 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 3. Sắp xếp nổi bọt (Bubble Sort) Ý tưởng: Xuất phát từ đầu dãy hay cuối dãy và tiến hành đổi chỗ cặp phần tử kế cận nhau để đưa phần tử nhỏ hơn hoặc lớn hơn về vị trí cao nhất hay thấp nhất trong dãy. Sau khi đã chuyển vị tjrí này không xét nữa => Lặp lại quá trình này khi dãy không còn phần tử nào nữa  Thuật toán: Bước 1: i = 0 Bước 2: j = n-1 //duyệt từ cuối đến ptử thứ i Trong khi j>i thực hiện nếu a[j] < a[j-1] thì hoán đổi hai phần tử j=j-1 Bước 3: i=i+1 N¨m häc 2014 - 2015 Trang: 13 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 ThÞ Lan Nếu i>=n-1 => Hết dãy và dừngNguyÔn thuật toán Ngược lại lặp lại bước 2  Cài đặt: … Type mang = array[1..20] of integer; Function BubbleSort(a:mang, n:integer): integer; Var i, j, tg: integer; Begin Writeln(‘----SAP XEP NOI BOT ----’); For i≔1 to n do For j≔n downto i+1 do If a[j]x) - Dãy con 3: ai,..aj=x + Với x là giá trị của một phần tử tuỷ ý trong dãy ban đầu. + Sau khi phân hoạch, dãy ban đầu được chia làm 3 phần : ak < x, vớI k=1..i ak = x, vớI k=i..j ak > x, vớI k=j..N  Thuật toán: Giải thuật để sắp xếp một dãy al…ar Bước 1 : Phân hoạch dẫy al…ar thành các dãy con :  Dãy con 1 : al…aj < x N¨m häc 2014 - 2015 Trang: 17 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9  NguyÔn ThÞ Lan Dãy con 2 : aj+1…ai-1 =x  Dãy con 3 : ai…ar > x Bước 2 :  Nếu (lx j--; Bước 2c : Nếu i=j : dừng.  Cài đặt: … Type mang = array[1..20] of integer; {----- Ham hoan vi gia tri hai bien-----} Function Hoanvi(x,y:integer):integer; Var tam:integer; Begin Tam≔x; N¨m häc 2014 - 2015 Trang: 18 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan X≔y; Y≔tam; End; {------------------Ham QuickSort---------------} Function QuickSort(a:mang; l,r:integer):integer; Var I, j, x, n:integer; Begin Writeln(‘------SAP XEP PHAN HOACH------’); X≔a[(l+r) div 2]; I≔l; J≔r; Repeat While a[i]x do dec(j); If (i<=j) then Begin Hoanvi(a[i],a[j]); Inc(i); Dec(j); End; Until (ik : dừng. Nếu i<=k : lặp lại bước 2.  Cài đặt: Giả sử chọn được dãy độ dài h[1], h[2],…,h[k], … Procedure ShellSort (a: mang, n:integer, h:mang, k: integer); N¨m häc 2014 - 2015 Trang: 21 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 Var NguyÔn ThÞ Lan step, i, j, x, len: integer; Begin for step:=0 to k-1 do Begin Len:=h[step]; for i:=len to n-1 do Begin X:=a[i]; J:=i-len; while (x-1)do //sắp xếp dãy con chứa x Begin {bằng phương pháp chèn trực tiếp} a[j+len]:=a[j]; j:=j-len; End; a[j+len]:=x; End; End; End; … 6. Sắp xếp vun đống (Heap Sort)  Định nghĩa Heap: N¨m häc 2014 - 2015 Trang: 22 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ - Giả sử sắp xếp giảm dần, khi đó Heap được định nghĩaLan là một dãy các phần tử a1, a2, ..., an thỏa các quan hệ : ai <= a2i. ai <= a2i+1 {(ai, a2i), (ai, a2i+1) là các cặp phần tử liên đới} - Và có các tính chất sau : Tính chất 1: Phần tử a1 (đầu Heap) luôn là phần tử nhỏ nhất trong Heap Tính chất 2: Cắt bỏ một số phần tử về phía phải của Heap thì dãy con còn lại vẫn là một Heap.  Ví dụ:  Thuật toán: Giải thuật Heapsort trải qua 2 giai đoạn: - Giai đoạn 1:Hiệu chỉnh dãy số ban đầu thành heap; - Giai đoạn 2:Sắp xếp dãy số dựa trên heap: Bước 1: Ðưa phần tử nhỏ nhất về vị trí đúng ở cuối dãy. Hoán vị(a1,aN); N¨m häc 2014 - 2015 Trang: 23 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn Lan Bước 2:Loại bỏ phần tử nhỏ nhất raThÞ khỏi dãy: N = N-1; Hiệu chỉnh phần còn lại của dãy từ a1, a2,…, an thành một heap. Bước 3: Nếu N > 1 (heap còn phần tử ): lặp lại bước 1. Ngược lại: Dừng N¨m häc 2014 - 2015 Trang: 24 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 N¨m häc 2014 - 2015 Trang: 25 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan * Cài đặt: … Type mang = array[1..20] of integer; {----Thủ tục hỗ trợ----} Procedure Shift(a: mang; l,r: integer); Var x, i, j, cont: integer; I: = l; j: = 2*i+1; cont : = 1; //(ai,aj),(ai,aj+1)là các phần tử liên đới x: = a[i ]; while ((j<=r) and (cont)) do Begin If (j a[j+1) then {xác định phần tử liên đới nhỏ nhất a[j]} J:=j+1; {thỏa quan hệ liên đới ,dừng hiệu chỉnh} if (a[j]>x) then cont: = 0 N¨m häc 2014 - 2015 Trang: 26 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan else Begin hoanvị(a[i],a[j]); i: = j; {xét tiếp khả năng hiệu chỉnh lan truyền} j:=2*i+1; End; End; End; Thủ tục hiệu chỉnh dãy ban đầu a[1], a[2],…, a[n] thành Heap: Procedure CreateHeap(a:mang, n:integer); Var i:integer; Begin i := n div 2; while (i > 0) do Begin Dec(i); Shift(a,i,n-1); End;  Sắp xếp dãy a[1], a[2], …,a[n] bằng Heap. void Heapsort(float a[ ],int N) Var r: integer; Begin r := n-1; N¨m häc 2014 - 2015 Trang: 27 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan while (r > 0) do Begin Hoanvi(&a[0],&a[r]); Dec(r); Shift(a,0,r); End; End; Trên đây là một số phương pháp sắp xếp thông dụng được áp dụng trên tập dãy số. Mỗi phương pháp đều có ưu, nhược và độ phức tạp điểm riêng, tùy theo khả năng, theo sở thích và đặc biệt tùy theo từng bài toán cụ thể các em có thể chọn cho mình một cách giải ngắn gọn mà hiệu quả nhất. Phần III. KẾT LUẬN I. NHẬN ĐỊNH CHUNG Sau gần 2 năm học thực hiện chuyên đề (Năm học 2013 – 2014 và học kỳ I năm học 2013 – 2014), kinh nghiệm Hướng dẫn học sinh giải bài toán sắp xếp đã giúp tôi có được những kết quả đáng ghi nhận như: - Đại đa số học sinh biết cách thực hiện và thực hiện được bài toán sắp xếp dữ liệu trên kiểu dữ liệu mảng - Học sinh không còn sợ bài toán sắp xếp nữa, nhiều học sinh còn mở rộng áp dụng sắp xếp Họ và tên theo nguyên tắc sắp xếp a, b, c,… và trong một số bài toán quản lý thông tin khác. - Đặc biệt các em nhận thấy rõ một chân lí: Máy tính là một công cụ lao động tuyệt với nhưng tất cả những khả năng mà máy tính có được đều do con N¨m häc 2014 - 2015 Trang: 28 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 ThÞ Lan người chỉ dẫn cho nó thông quaNguyÔn các câu lệnh. Và bây giờ chính các em là người viết ra các câu lệnh đó. Đây là thành công lớn nhất mà tôi thu được vì đó chính là niềm say mê của các em đối với môn học. Sau một thời gian thực hiện chuyên đề kiến thức và kỹ năng thực hành của học sinh tiến bộ lên rõ rệt, điều này được thể hiện rõ nhất trong các bài kiểm tra (lý thuyết và thực hành), kết quả kiểm tra ngày một nâng lên. Kết quả cụ thể như sau: Năm học 2012- 2013 (Trước khi thực hiện chuyên đề) Giỏi Khá Trung bình Yếu 15% 30% 50% 5% 30% 50% 18% 2% Năm học 2013- 2014 (Trong, sau khi thực hiện chuyên đề) Bên cạnh việc nâng cao chất lượng đại trà môn học, chất lượng mũi nhọn của bộ môn cũng ngày được khẳng định. Học sinh khối 8, khối 9 của tôi khi tham gia các cuộc thi Tin học trẻ các em cũng tỏ ra rất vững vàng với các bài toán lập trình, đặc biệt là bài toán sắp xếp. Kết quả này có được là xây trên cơ sở những tiết thực hành hiệu quả của cả thày và trò. Kinh nghiệm này sẽ được tôi tiếp tục áp dụng và ngày một hoàn thiện hơn nữa trong năm học 2014 – 2015 và những năm học tiếp theo. II. KINH NGHIỆM ÁP DỤNG GIẢI PHÁP. Để chuyên đề “Hướng dẫn học sinh giải bài toán sắp xếp - Tin học 8” được thực hiện thực sự hiệu quả, giáo viên và học sinh cần thực hiện tốt một số nội dung sau: 1. Đối với giáo viên: - Nắm chắc kiến thức về bài toán sắp xếp, ý tưởng, thuật toán, độ phức tạp của các phương pháp sắp xếp. N¨m häc 2014 - 2015 Trang: 29 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn Lan - Nắm chắc cơ sở vật chất phòng máy viThÞ tính (gồm máy tính và các thiết bị khác) để có kế hoạch tham mưu với Ban giám hiệu nhà trường cùng các tổ chức khác mua sắm tu bổ để đảm bảo điều kiện thực hành cho học sinh. - Có kế hoạch thực hành cụ thể chi tiết ngay từ đầu năm học. Đảm bào 100% các tiết thực hành các em được thực hiện trên máy tính. - Nắm chắc chương trình, chuẩn kiến thức kỹ năng của từng phần học, từng bài và từng tiết (đặc biệt là tiết thực hành) - Chuẩn bị chu đáo hệ thống bài tập thực hành, bài kiểm tra thực hành để đánh giá chất lượng thực hành bộ môn của học sinh. Hệ thống các câu hỏi bài tập này ngoài việc đảm bảo chính xác về mặt nội dung kiến thức còn phải có tính liên hệ, ứng dụng thực tiễn để gây hứng thú cho học sinh. - Chuẩn bị sổ theo dõi kết quả thực hành và thực hiện đánh giá kết quả thực hành thường xuyên, có hiệu quả. - Tận tâm hướng dẫn học sinh thực hành, quan tâm động viên các em để học sinh tiến bộ. 2. Đối với học sinh: - Có ý thức học tập tốt. - Nắm chắc kiến thức lý thuyết lập trình, có kiến thức toán học trung bình trở lên, chịu khó đọc và viết các từ (cụm từ) tiếng anh sử dụng trong tin học. - Nắm được một số thuật toán cơ bản trong lập trình (thuật toán thêm dần, thuật toán sắp xếp, thuật toán đổi chỗ, tìm số lớn nhất, tìm số nhỏ nhất, …) - Có kỹ năng thao tác máy tính tốt (đặc biệt kỹ năng soạn, sửa lỗi và chạy chương trình) - Có ý thức và thái độ đúng đắn về phần mềm máy tính và vai trò của máy chúng, từ đó không ngừng học tập và nghiên cứu xây dựng phần mềm máy tính của bản thân. N¨m häc 2014 - 2015 Trang: 30 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan III. ĐIỀU KIỆN THỰC HIỆN GIẢI PHÁP - Chuyên đề này được thực hiện đối với môn tin học lớp 8 (phần lập trình cơ bản) trong phần: Câu lệnh lặp (xác định); Lặp với số lần chưa biết trước; Làm việc với dãy số và Kiểu dữ liệu mảng. - Giáo viên và hoc sinh đều có sự chuẩn bị chu đáo cho tiết học, phần học. IV. KIẾN NGHỊ Đề nâng cao chất lượng dạy và học bộ môn tin học nói chung và nâng cao chất lượng giờ thực hành môn tin học 8 nói riêng, với vai trò là người phụ trách phòng vi tính, người trực tiếp giảng dạy bộ môn tin học trong nhà trường, tôi có một số kiến nghị như sau: * Với Nhà trường: - Có kế hoạch tu bổ, mua sắm máy tính, trang thiết bị để đảm bảo số lượng máy tính có chất lượng cho học sinh thực hành (đảm bảo 1 – 2 hs/ 1 máy tính). - Tăng cường thêm sách tham khảo bộ môn Tin học, đặc biệt là sách tham khảo về phần lập trình. - Có kế hoạch và tổ chức các cuộc thi như: Tin học trẻ (cấp trường) hay Thi viết phần mềm sáng tạo, … để tạo ra một sân chơi bổ ích cho các em, giúp các em có động lực học tập, sáng tạo. Đặc biệt các cuộc thi này sẽ giúp các em nhận ra rằng Tin học là môn khoa học có nhiều ứng dụng to lớn trong đời sống xã hội và chiếc máy tính là một công cụ lao động tuyệt vời nhưng tất cả những khả năng mà máy tính có được đều do con người ban cho nó. Tin học nói chung và máy tính điện tử nói riêng hiện có những việc chưa thể làm được nhưng một ngày không xa nữa chính các em – thế hệ trẻ tương lai của đất nước – sẽ là những người giải mã được điều đó, các em sẽ biến điều chưa thể thành có thể bằng quyết tâm học tập của mình. * Với Phòng giáo dục đào tạo: N¨m häc 2014 - 2015 Trang: 31 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. NguyÔn ThÞ Lan ®Gi¸o ¸n Tin häc 9 ThÞ - Tin học là môn học màNguyÔn đòi hỏi giáo viên giảngLan dạy phải cập nhật kiến thức mới liên tục. Do đó viêc tự tích lũy kinh nghiệm cho bản thân tôi vẫn thực hiện thường xuyên, tuy nhiên cơ hội học hỏi kinh nghiệm của các đồng nghiệp cùng chuyên ngành khác là không có nhiều. Chính vì vậy bản thân tôi rất mong muốn nếu có thể hàng năm Phòng giáo dục nên tổ chức các chuyên đề liên quan đến bộ môn Tin học để những giáo viên Tin như chúng tôi có cơ hội mở rộng kiến thức. - Bên cạnh việc tiếp tục tổ chức cuộc thi Tin học trẻ như hàng năm vẫn thực hiện, tôi thấy nên bổ sung thêm một nội dung bắt buộc là thi viết phần mềm sáng tạo để động viên khích lệ học sinh cũng là để học sinh huyện Phù Cừ phát huy khả năng lập trình sáng tạo ngang tầm với các huyện khác trong tỉnh. KẾT LUẬN CHUNG: Trên đây là nội dung chuyên đề Hướng dẫn học sinh giải bài toán sắp xếp- Tin học 8 mà tôi đã nghiên cứu và áp dụng. Sau một thời gian cũng khá dài để thực hiện bản thân tôi cũng gặt hái được một số kết quả đáng khích lệ, chính vì vậy xin được trao đổi cùng đồng nghiệp. Rất mong được sự quan tâm, đóng góp ý kiến tận tình của đồng nghiệp, đặc biệt là đồng nghiệp cùng chuyên ngành Tin học để giải pháp này của tôi ngày được hoàn thiện hơn nữa. Để qua những thuật toán đơn giản mà hiệu quả này sẽ chắp cánh ước mơ sáng tạo của các em bay cao bay xa hơn nữa, để một tương lai không xa kia các em sẽ biến những điều chưa thể thành có thể. Xin trân trọng cảm ơn! LỜI CAM ĐOAN: Tôi xin cam đoan sáng kiến kinh nghiệm này là do tôi đúc rút được trong quá trình trực tiếp giảng dạy, không sao chép nội dung của người khác. Trần Cao, ngày 24 tháng 3 năm 2015 N¨m häc 2014 - 2015 Trang: 32 Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ NgườiLan viết Nguyễn Thị Lan N¨m häc 2014 - 2015 Trang: 33