1 w jaki sposób uczyć programowania (w szkole) Najważniejsze aspekty w metodyce nauczania programowania, czyli w jaki sposób uczyć programowania (w szkole) Krzysztof Diks, II UW

2 Podsumowanie wyników z matury 2013 2 Poziom podstawowy: Dla zdających najtrudniejsze okazało się zadanie 4. z zakresu algorytmiki i programowania. Poziom rozszerzony: Trudność maturzystom sprawiły zadania 6.b i 6.c z zakresu algorytmiki i programowania.

3 3

4 4 2005

5 5 2005

6 6 2007

7 Przyczyna 7 Nie wyartykułowano, co ma być celem początkowej fazy nauki programowania. Celami wstępnej fazy nauki programowania nie powinny być: szczegółowe poznanie (składni) wybranego języka programowania szczegółowe poznanie (składni) wybranego języka programowania kształcenie umiejętności tworzenia (często technicznych) aplikacji kształcenie umiejętności tworzenia (często technicznych) aplikacji szczegółowe poznawanie środowisk wspierających pracę programisty szczegółowe poznawanie środowisk wspierających pracę programisty

8 Przyczyna 8 Nie zdefiniowano co to jest programowanie dla początkujących adeptów informatyki. KD, GJ: Programowanie, to formalny sposób zapisywania algorytmów, a co za tym idzie nie należy w procesie nauczania rozdzielać algorytmiki i programowania.

9 Wady istniejących podręczników do uczenia elementów programowania (w liceach) 9 rozdzielenie nauki programowania od układania algorytmów rozdzielenie nauki programowania od układania algorytmów duży nacisk na nauczanie składni i szczegółów duży nacisk na nauczanie składni i szczegółów technicznych języka programowania, zamiast na uczenie rozumienia podstawowych konstrukcji programistycznych (zapisywania algorytmów) brak kształcenia umiejętności projektowania poprawnych brak kształcenia umiejętności projektowania poprawnychalgorytmów dominujące używanie schematów blokowych (listy kroków) dominujące używanie schematów blokowych (listy kroków) do zapisywania algorytmów nieciekawe, techniczne przykłady nieciekawe, techniczne przykłady dominacja odtwórczych zadań dominacja odtwórczych zadań wprowadzanie „klasycznych” algorytmów bez uzasadniania wprowadzanie „klasycznych” algorytmów bez uzasadniania dlaczego zaliczamy je do klasyki (ze względu na wagę rozwiązywanego problemu? ze względu na wagę i ogólność użytych w nich metod?)

10 10 Rozdzielenie nauki programowania od układania algorytmów …W rozdziale II (Algorytmika i programowanie - problemy zaawansowane) poszerzamy wiadomości dotyczące wprowadzania danych i wyprowadzania wyników, m.in. losowanie danych. Systematyzujemy wiedzę uczniów dotyczącą typów danych w języku Turbo Pascal. Uczniowie poznają zasady przetwarzania rekordów i plików, w tym plików tekstowych. Zapoznają się z cechami programowania obiektowego na przykładzie języka Object Pascal. Dowiadują się, na czym polega programowanie zdarzeniowe - tworzą interfejs użytkownika w systemie Delphi. Poznają elementy analizy algorytmów. Analizują wybrane algorytmy sortowania oraz algorytmy wykonujące operacje na liczbach naturalnych. Poznają reprezentację danych numerycznych w komputerze oraz wybrane algorytmy numeryczne. …

11 11 Duży nacisk na nauczanie składni i szczegółów technicznych języka programowania, zamiast na uczenie rozumienia podstawowych konstrukcji programistycznych (zapisywania algorytmów) …Kolejną pętlą w C++ jest pętla while. Pętla ta wykonuje się kolejny raz, gdy wyrażenie jest prawdziwe (czyli ma wartość różną od zera). Składnia pętli while while (wyrażenie) instrukcja; gdzie: wyrażenie-wyrażenie przyjmujące wartość logiczną „prawda” albo „fałsz” instrukcja - instrukcja wykonywana w pętli Napiszmy prosty program wyświetlający na ekranie znaki podane z klawiatury do momentu, aż podamy znak „k”.

12 12 #include #include using namespace std; int main() { char z; cout > z; while (z != ‘k’) { cout > z; } cout

13 13 Brak kształcenia umiejętności projektowania poprawnych algorytmów …Metodami, jakie się w takich przypadkach stosuje zajmiemy się w przyszłym roku. Na co dzień muszą wystarczyć poniższe zasady: staraj się wykorzystywać sprawdzone pewne algorytmy; mogą to być procedury, staraj się wykorzystywać sprawdzone pewne algorytmy; mogą to być procedury, ale też fragmenty poprzednio wykorzystywanych algorytmów; gromadź takie stałe fragmenty gry w swojej podręcznej biblioteczce; na etapie tworzenia algorytmu możesz być wizjonerem, artystą, na etapie sprawdzania, na etapie tworzenia algorytmu możesz być wizjonerem, artystą, na etapie sprawdzania, czy algorytm działa zgodnie z Twoimi zamierzeniami, powinieneś być skrupulatnym, podejrzliwym kontrolerem, który sprawdza każdy szczegół, nie wierzy nikomu, nawet sobie; ćwicz – pisz programy, podpatruj, jak inni to robią, stale szukaj nowych, lepszych ćwicz – pisz programy, podpatruj, jak inni to robią, stale szukaj nowych, lepszychrozwiązań…

14 14 Dominujące używanie schematów blokowych (listy kroków) do zapisywania algorytmów Problem algorytmiczny:Badanie, czy podana liczba jest pierwsza Dane wejściowe: liczba naturalna n > 1 – badana liczba Dane wyjściowe: napis „liczba pierwsza”, gdy n jest liczbą pierwszą, lub napis „liczba złożona”, gdy n jest liczbą złożoną Zmienne pomocnicze: liczba naturalna i – potencjalny dzielnik; i > 1 1.Wczytaj n. 2.Zmiennej pomocniczej i przypisz wartość 2. 3.Jeśli kwadrat liczby i jest większy od liczby n, to wypisz „liczba pierwsza” i zakończ. 4.Jeśli reszta z dzielenia n przez i wynosi 0, wypisz ‘liczba złożona” i zakończ. 5.Zwiększ o 1 wartość zmiennej pomocniczej i. 6.Przejdź do kroku 3.

15 15 Nieciekawe, techniczne przykłady Przykład użycia instrukcji iteracyjnej while uses CRT; var powtórz:boolean; procedure sprawdz(var powtorz: boolean); var c:char; begin write(‘Czy powtórzyć (nacisnij t/T jeśli TAK)? ‘); write(‘Czy powtórzyć (nacisnij t/T jeśli TAK)? ‘); c := ReadKey; Writeln(c); c := ReadKey; Writeln(c); powtorz := UpCase(c)=‘T’; powtorz := UpCase(c)=‘T’; writeln writelnend;begin powtorz := True; powtorz := True; while powtorz do begin while powtorz do begin czytajDane(m,n); wypisz(m,n); czytajDane(m,n); wypisz(m,n); sprawdz(powtorz); sprawdz(powtorz); end endend.

16 16 Dominacja odtwórczych zadań Napisz program realizujący algorytm z przykładu 5. Posłuż się danymi generowanymi losowo. Zanotuj, ile operacji każdorazowo wykonał program (liczba operacji będzie równa numerowi znalezionego elementu lub n, gdy element nie zostanie znaleziony). Oblicz średnią liczbę operacji dla wszystkich wykonań programu.

17 17 Wprowadzanie „klasycznych” algorytmów bez uzasadniania dlaczego zaliczamy je do klasyki (ze względu na wagę rozwiązywanego problemu? ze względu na wagę i ogólność użytych w nich metod?) Z podstawy programowej: algorytmy wyszukiwania i porządkowania (sortowania), np.: – jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze: algorytm naiwny i optymalny, w zbiorze: algorytm naiwny i optymalny, – algorytmy sortowania ciągu liczb: bąbelkowy, przez wybór, przez wstawianie liniowe lub binarne, przez scalanie, szybki, przez wstawianie liniowe lub binarne, przez scalanie, szybki, kubełkowy. kubełkowy.

18 Wstęp do programowania w ujęciu algorytmicznym - podstawy 18 Sylabus: algorytm (specyfikacja, dziedzina algorytmiczna, algorytm (specyfikacja, dziedzina algorytmiczna, zapisywanie algorytmów) kodowanie algorytmów (instrukcje: warunkowa i iteracji) kodowanie algorytmów (instrukcje: warunkowa i iteracji) funkcja funkcja zmienne zmienne projektowanie iteracji, poprawność algorytmu projektowanie iteracji, poprawność algorytmu tablice tablice złożoność obliczeniowa algorytmu złożoność obliczeniowa algorytmu

19 W jaki sposób układamy i zapisujemy algorytmy - przykłady 19 Zadanie 1 – pierwiastek dyskretny Dane: nieujemna liczba całkowita n Wyniki: nieujemna liczba całkowita p taka, że p 2

20 20 Algorytm w języku naturalnym: weź 0 na kandydata dopóki następnik kandydata spełnia nierówność pierwiastka: niech ten następnik będzie nowym kandydatem niech ten następnik będzie nowym kandydatem aktualny kandydat to poszukiwany pierwiastek dyskretny Python: def pierwiastekDyskretny(n): k = 0 while (k+1)*(k+1)

21 21 C++: int pierwiastekDyskretny(int n) { int k = 0; while ( (k+1)*(k+1)

22 Przyśpieszanie algorytmu – projektowanie pętli od środka 22 Spostrzeżenie 1: pierwiastek dyskretny p z n leży w przedziale [0..n] Spostrzeżenie 2: załóżmy, że p leży w przedziale [le..pr] i niech k będzie liczbą całkowitą z tego przedziału, wówczas jeśli (k+1)*(k+1) n, to p leży w przedziale [le..k-1]

23 Projektowanie wnętrza pętli 23 Asercja: le

24 Python: 24 def pierwiastekDyskretny(n): assert n >= 0 le = 0 pr = n while True: assert (le*le n) k = (le + pr) / 2 if (k+1)*(k+1) n: pr = k-1 continue assert (k n) assert (k n)break return k

25 25 int pierwiastekDyskretny(int n){ int le, pr, k; assert (n >= 0); le = 0; pr = n; while (True){ assert ((le*le n)); k = (le + pr) / 2; if ((k+1)*(k+1) n){ pr = k-1; continue; } assert ((k n)); assert ((k n));break;} return k; }