1 Wykład 4 O algorytmach

2 Część I. ALGORYTMY

3 Uczyć algorytmów? TAK! JAK?nawet wtedy gdy nie zamierzamy uczyć programowania (przecież w arkuszach kalkulacyjnych, bazach danych a nawet w edytorze tekstu wykonywanie kolejnych czynności jest właśnie programowaniem). JAK? jako coś normalnego i zwyczajnego; algorytmy wielokrotnie wykonujemy przez całe życie; nawet nie zdajemy sobie sprawy z tego, że stosujemy algorytmy.

4 Jak uczyć? Przykłady Pojęcie Cechy Implementacja Analiza

5 Przykłady przykładów... Algorytmy działań pisemnychNaprawa przedziurawionej dętki Montaż szafy z gotowych elementów Robienie swetra na drutach Zaprogramowanie wideo lub DVD Wprowadzenie numeru telefonu do komórki

6 Algorytm to opis czynności prowadzących do określonego celu.Pojęcie algorytmu Algorytm to opis czynności prowadzących do określonego celu.

7 Wyjaśnienie pojęcia Algorytm zadaje czynności, które składają się na proces. Pieczenie ciasta z rodzynkami: to proces wykonywany ze składników przez piekarza za pomocą pieca (i innych narzędzi: trzepaczka, talerz etc.) według przepisu. Składniki = dane wejściowe, Gotowe ciasto = dane wyjściowe, Piec, przybory, piekarz = sprzęt (hardware), Przepis = algorytm.

8 Cechy algorytmów Problem algorytmicznyprecyzyjne określenie relacji między danymi wejściowymi i wyjściowymi Opis właściwej procedury obliczeniowej uwzględnienie wszystkich możliwych przypadków i reakcja na nie Poziom szczegółowości repertuar czynności, które „są znane” – czyli nie muszą być opisane algorytmem

9 Poprawność algorytmówDla każdych danych spełniających warunki określone przez problem algorytmiczny algorytm zatrzymuje się, dane wyjściowe spełniają warunki problemu (algorytm daje dobry wynik).

10 Przykłady algorytmów (1)Wydawanie reszty w sklepie Mycie zębów Ubieranie się mężczyzny w garnitur Wiązanie krawata Wiązanie sznurowadła w kokardkę Otwieranie, za pomocą kluczy, drzwi mających dwa zamki Wieszanie zasłon okiennych w pokoju Pisanie liter (według zasad kaligrafii) Temperowanie ołówka Rysowanie okręgu o danym promieniu za pomocą cyrkla Jedzenie orzecha włoskiego Obieranie pomarańczy Instalowanie gry komputerowej Wypełnianie deklaracji podatkowej PIT Wykonywanie badań okresowych

11 Przykłady algorytmów (2)Binarna reprezentacja liczby naturalnej Schemat Hornera Wyszukiwanie w ciągu elementu najmniejszego Przeszukiwanie struktury danych (plik, tablica, kolejka, drzewa, stos) Algorytm Euklidesa Wyznaczanie wartości przybliżonej pierwiastka kwadratowego Ciąg Fibonacciego Interpolacja funkcji Obliczanie pierwiastków równania kwadratowego Generowania kwadratów kolejnych liczb ale bez mnożenia Przeszukiwanie listy dwukierunkowej Sortowanie Obliczanie wyznacznika macierzy Wyznaczanie miejsc zerowych funkcji, Sito Erastostenesa Znajdowanie wartości całki oznaczonej lista z książki „Elementy informatyki – podręcznik metodyczny dla nauczyciela” pod redakcją M.Sysły

12 Zapisywanie algorytmówAlgorytmy trzeba zapisywać Metody zapisu algorytmów opis słowny schemat blokowy pseudokod

13 Zapisywanie algorytmów (1)Opis słowny w języku potocznym Dobry sposób na początek lub w początkowej fazie projektowania Mało precyzyjny Trudny do implementacji

14 Opis słowny Opis kolejnych czynności w punktach (numerowanych!)Tryb rozkazujący Przykład: Pobierz dwie liczby. Jeżeli są równe to wypisz jedną z nich i koniec. Większą zamień na różnicę większej i mniejszej. Wróć do punktu 2.

15 Zapisywanie algorytmów (2)Schematy blokowe Bardzo poglądowy („Obraz wart 1000 słów”) Dobry do prostych algorytmów Łatwy w nauczeniu się i stosowaniu Trudny do implementacji

16 Schematy blokowe Pudełka połączone liniami czytaj: aOperacja (prostokąt) – jedno wejście i jedno wyjście Warunek (romb) – jedno wejście, dwa wyjścia Start (owal) – jedno wyjście bez wejścia (tylko jedno w algorytmie) Stop (owal) – jedno wejście bez wyjścia Input, output (równoległobok) – jedno wejście i jedno wyjście czytaj: a

17 Schematy blokowe

18 Zapisywanie algorytmów (3)Pseudokod Odpowiednio precyzyjny Bliski implementacji Trudny, bo trzeba się go nauczyć

19 Pseudokod Przykład: Konwencje (do ustalenia)Stały repertuar słów kluczowych – słowa kluczowe wyróżnione Symbol operacji podstawienia Stosowanie nawiasów syntaktycznych i separatorów instrukcji Dopuszczalne operacje wejścia/wyjścia Sposób pisania komentarzy Przykład: { algorytm Euklidesa } pobierz(a); pobierz(b); dopóki a < > b jeżeli a > b to a  a – b w.p.p. b  b – a wypisz(”NWD=”,a)

20 Od czego zacząć? Od wykonania prostego algorytmuNauczyciel „dyktuje” kroki algorytmu, uczniowie wykonują Algorytm powinien być ciekawy, zabawny, zaskakujący Algorytm powinien mieć wyraźne wszystkie cechy dobrego algorytmu

21 Od czego zacząć – przykład (1)Proszę wziąć przygotowane kwadratowe kartki... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X)

22 Od czego zacząć – przykład (1)Mocno zaprasowujemy wszystkie zgięcia... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X) 3. Zaginamy wolny róg trójkąta tak aby pokrył się z wierzchołkiem trójkąta

23 Od czego zacząć – przykład (1)Proszę wziąć przygotowane kwadratowe kartki... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X) 3. Zaginamy wolny róg trójkąta tak aby pokrył się z wierzchołkiem trójkąta 4. Zaginamy i rozprostowujemy utworzony trójkąt według czerwonych linii

24 Od czego zacząć – przykład (1)Proszę wziąć przygotowane kwadratowe kartki... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X) 3. Zaginamy wolny róg trójkąta tak aby pokrył się z wierzchołkiem trójkąta 4. Zaginamy i rozprostowujemy utworzony trójkąt według czerwonych linii 5. Formułujemy „uchwyt” i zaprasowujemy

25 Od czego zacząć – przykład (1)Proszę wziąć przygotowane kwadratowe kartki... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X) 3. Zaginamy wolny róg trójkąta tak aby pokrył się z wierzchołkiem trójkąta 4. Zaginamy i rozprostowujemy utworzony trójkąt według czerwonych linii 5. Formułujemy „uchwyt” i zaprasowujemy 6. Powtarzamy czynności 3-5 dla wszystkich rogów

26 Od czego zacząć – przykład (1)Proszę wziąć przygotowane kwadratowe kartki... 1. Zginamy kartkę wzdłuż przekątnych 2. Formułujemy trójkąt wciskając do wewnątrz boki (tak aby punkty A i B pokryły się z X) 3. Zaginamy wolny róg trójkąta tak aby pokrył się z wierzchołkiem trójkąta 4. Zaginamy i rozprostowujemy utworzony trójkąt według czerwonych linii 5. Formułujemy „uchwyt” i zaprasowujemy 6. Powtarzamy czynności 3-5 dla wszystkich rogów 7. Energicznie dmuchamy w otwór trzymając za dwa sąsiednie uchwyty

27 Czy to uzyskaliście?

28 Od czego zacząć - przykład (2)Proszę przygotować kartki i ołówki... narysuj dwa trójkąty na górze drugiego kształtu narysuj kolisty kształt narysuj mniejszy kolisty kształt nieco z boku pierwszego kształtu ale zachodzący na pierwszy narysuj dwa małe kółeczka w środku trzeciego kształtu narysuj cztery owale na dole pierwszego kształtu narysuj mały kolisty kształt w środku drugiego kształtu narysuj mały świderek z drugiego boku pierwszego kształtu narysuj dwie kropki nad trzecim kształtem obok siebie zetrzyj niepotrzebne linie, (dorysuj uśmiech na zakończenie)

29 Czy to uzyskaliście?

30 Co dalej? Dalej naturalne przykłady algorytmów Nauczyciel podaje kilkaUczniowie sami wymyślają Przykłady mają być prawdziwe Przykłady mają być użyteczne Przykłady mają być wykorzystywane w życiu

31 Jeszcze dalej ... Budowa algorytmówOkreślenie danych początkowych i wyniku Pełny zapis Sprawdzenie poprawności Analiza warunków zakończenia pracy Może obliczenie złożoności (liczby operacji w najgorszym przypadku)

32 Forma lekcji Nauczyciel podaje jeden przykład tak jakby sam rozwiązywał problem Nauczyciel zadaje proste przykłady uczniom w klasie i trudniejsze jako pracę domową W czasie lekcji wspólne tworzenie algorytmu wraz z dyskusją

33 Dalej niż dalej... Implementacja algorytmurealizacja algorytmu w jakimś języku programowania wymaga umiejętności programowania realizacja algorytmu za pomocą jakiegoś specjalnego narzędzia edukacyjnego realizacja algorytmu za pomocą jakiegoś modelu

34 Narzędzia edukacyjne Program ELI (Elbox Laboratorium Informatyki)budowa algorytmu w postaci schematu blokowego z klocków testowanie poprawności algorytmu badanie złożoności (liczby operacji podstawowych) algorytmu Środek dydaktyczny zalecany przez MEN Przykład: algorytm Euklidesa

35 Narzędzia edukacyjne Program Baltie (Soukup Graphic Programing)budowa sceny z gotowych elementów interakcyjne sterowanie programem graficzne tworzenie programów Przeznaczenie dla dzieci (od 4 lat do…)

36 Przykład: algorytm Euklidesa

37 Dla zainteresowanych Algorytmy równoważne Metody budowania algorytmówrozwiązanie tego samego problemu algorytmicznego w różny sposób Metody budowania algorytmów konstrukcja algorytmów złożonych z modułów metoda „z góry na dół” lub „z dołu do góry” metoda „dziel i rządź” Czy wszystko można zalgorytmizować?

38 Nie na wszystko jest algorytmProblemy, których nie można rozwiązać algorytmicznie: Problem „stopu” Rozwiązywanie równań diofantycznych Problem domina

39 „Problem stopu” Nie istnieje uniwersalny algorytm, który dla dowolnego algorytmu i dowolnych poprawnych danych dla tego algorytmu zatrzymuje się z wynikiem TAK – gdy dany program na podanych danych wejściowych zatrzymuje się NIE – gdy dany program na podanych danych wejściowych nie zatrzymuje się

40 Dowód „problemu stopu”Oznaczenia: algorytm R na danych X nie zatrzymuje się: R(X), algorytm R na danych X zatrzymuje się: R(X). Problem stopu: Nie istnieje algorytm Q, który zawsze zatrzymuje się, taki, że Q(R#X)=”TAK” wtedy i tylko wtedy gdy R(X) Q(R#X)=”NIE” wtedy i tylko wtedy gdy R(X)

41 Dowód „problemu stopu” cd.Gdyby istniał taki algorytm Q to budujemy algorytm S: Dane wejściowe algorytm i dane do algorytmu Początek: Q(R#R) Jeżeli Q(R#R)=”TAK” to pętla nieskończona Jeżeli Q(R#R)=”NIE” to stop (wynik nieważny). Badamy S(S). Jeżeli S(S) to Q(S#S)=”NIE” i wtedy zgodnie z konstrukcją S(S) Jeżeli S(S)  to Q(S#S)=”TAK” i wtedy zgodnie z konstrukcją S(S) Sprzeczność

42 „Problem domina” Dane dla algorytmu:kwadratowe karty podzielone przekątnymi na 4 części każda część pomalowana jakimś kolorem (daną jest opis kilku typów kart). Pytanie: czy można pokryć dowolną skończoną powierzchnię kartami opisanych typów (kart nie można przekręcać) mając do dyspozycji dowolną liczbę kart każdego typu?

43 „Problem domina” – przykładNastępującym zestawem płytek można pokryć dowolny fragment płaszczyzny

44 „Problem domina” - przykładNastępującym zestawem płytek nie można pokryć płaszczyzny

45 Część II. Rekurencja

46 Przykład rozumowania Zadanie: 1 + 2 + 3 + 4 + 5 + ... + n = ?znaleźć wzór na sumę kolejnych liczb naturalnych: n = ?

47 Najpierw ilustracja

48 Potem hipoteza

49 No i dowód

50 Przykład problemu Narysować Drzewo Pitagorasa Pień – dowolny kwadratGałęzie – dwa kwadraty, których suma pól daje pień umieszczone nad pniem tak aby boki stanowiły trójkąt prostokątny Gałązki – następne kwadraty „wyrastające” z gałęzi według tej samej zasady Gałązeczki – wyrastają z gałązek tak jak gałązki na gałęziach Itd...

51 Drzewo Pitagorasa

52 Drzewo Pitagorasa

53 Własności problemu Można rozłożyć na takie same problemy ale mniejsze

54 Własności problemów Rozwiązanie całego problemu możemy zestawić z rozwiązań mniejszych problemów

55 Własności problemów Podział prowadzi do problemów, które można rozwiązać bezpośrednio

56 Problemy „rekurencyjne”Możliwy rozkład na takie same ale mniejsze problemy Rozkład prowadzi do problemów mających bezpośrednie rozwiązanie Z rozwiązań problemów mniejszych można zestawić rozwiązanie problemu głównego

57 Ogólna postać rozwiązania problemu rekurencyjnegoPROCEDURE ROZWIĄŻ(przypadek); BEGIN IF przypadek jest prosty THEN Rozwiązanie bezpośrednie ELSE Podziel przypadek na przypadki p1,p2, ...; ROZWIĄŻ(p1);ROZWIĄŻ(p2);...; Zbuduj rozwiązanie ze składowych END END;

58 Istota rekurencji Każde wywołanie procedury rekurencyjnej pamięta swój stan. To znaczy: Ma własne kopie wszystkich zmiennych lokalnych Nie widzi zmian dokonywanych na zmiennych lokalnych przez dalsze wywołania Czeka na zakończenie wszystkich dalszych wywołań

59 Przykład Odwracanie ciągu: Wejście, np. Wyjście:ABCDEFGH Wyjście: HGFEDCBA Nie znamy długości ciągu – zakończenie ‘.’

60 Przykład (cd) Rozwiązanie iteracyjneTrzeba wczytać i zapamiętać wszystkie elementy ciągu Po zakończeniu wczytywania trzeba wyświetlić od końca Wada: trzeba zorganizować strukturę danych Tablica? Nie bo ma stały rozmiar Stos? Tak Każdy wczytany umieszczany jest na górze stosu Wypisujemy stos od góry

61 Przykład (cd) Rozwiązanie rekurencyjne procedure odwroc(); var c:char;begin readln(c); if c<>’.’ then odwroc(); write(c); end;

62 Przykład (cd) Dlaczego działa? Wejście: A Wejście: B Wejście: CRóżne od ‘.’ – wywołujemy odwroc ale pamiętamy swój stan czyli moją zmienną c Wejście: B Różne od ‘.’ – wywołujemy odwroc ale pamiętamy swój stan czyli moją zmienną c, która jest inną zmienną niż poprzednie c Wejście: C Różne od ‘.’ – wywołujemy odwroc ale pamiętamy swój stan czyli moją zmienną c, która jest inną zmienną niż wszystkie poprzednie c Wejście: ‘.’ Wypisujemy moją zmienną c, a więc literę C i koniec – powrót do poprzedniego wywołania Poprzednie wywołanie czekało, a więc może działać teraz dalej – czyli wypisuje swoją zmienną c czyli literę B i koniec – powrót do poprzedniego wywołania ...

63 Jak zdobyć stówę?

64 Jak zdobbyć tę stówę?

65 Czy tak można w nieskończoność?

66 Przykłady Obliczanie reszty z dzielenia danej liczby przez inną.Obliczanie n-tej potęgi liczby Obliczanie silni danej liczby Mnożenie dwóch liczb Wypisywanie wszystkich wierzchołków drzewa binarnego Konstrukcja (siłowa) kwadratu magicznego Rozstawienie 8 hetmanów na planszy tak aby się nie szachowali Znajdowanie drogi skoczka szachowego po całej szachownicy

67 Przykłady Przechodzenie przez labirynt Wydawanie resztyWyszukiwanie w ciągu uporządkowanym Rysowanie fraktali Obliczanie wyrazów ciągów geometrycznego i arytmetycznego Szukanie pierwiastków równania (dowolnego) Obliczanie pierwiastka kwadratowego ze wzoru Newtona-Raphsona (x1-a/2, xn=(xn-1+a/xn-1)/2)