Dekompozycja, rozpoznawanie wzorcow, abstrakcja, algorytmika
ð Podstawa programowa: I.1Myslenie komputacyjne (ang. Computational Thinking) to zestaw umiejetnosci pozwalajacych rozwiazywac problemy w sposob, ktory moze byc zrozumiany i wykonany przez czlowieka lub komputer. Termin ten spopularyzowal Jeannette Wing z Carnegie Mellon University w 2006 roku.
Myslenie komputacyjne opiera sie na czterech kluczowych etapach:
Dekompozycja to rozbicie zlozonego problemu na mniejsze, latwiejsze do rozwiazania czesci. Zamiast probowac rozwiazac caly problem naraz, dzielimy go na etapy.
Przyklad: Chcesz zorganizowac wyjazd klasowy. Zamiast myslec o wszystkim naraz, dzielisz to na: wybor miejsca, transport, nocleg, wyzywienie, harmonogram, budzet.
Rozpoznawanie wzorcow to szukanie podobienstwa miedzy problemami lub ich czesciami. Jesli rozwiazales juz podobny problem, mozesz uzyc tamtego rozwiazania jako wzorca.
Przyklad: Algorytm sortowania kart jest podobny do sortowania ksiazek na polce - w obu przypadkach porownujemy elementy i ustawiamy je w odpowiedniej kolejnosci.
Abstrakcja to odrzucenie nieistotnych szczegolow i skupienie sie na tym, co naprawde wazne. Tworzymy uproszczony model problemu.
Przyklad: Mapa metra to abstrakcja - nie pokazuje dokladnych odleglosci ani ksztaltow ulic, ale pokazuje to, co jest wazne: stacje i polaczenia miedzy nimi.
Algorytm to precyzyjny, krokowy opis rozwiazania problemu. Kazdy krok musi byc jednoznaczny i wykonalny. Po zaprogramowaniu algorytmu nalezy go przetestowac - sprawdzic, czy dziala poprawnie dla roznych danych wejsciowych.
Przyklad: Algorytm wyszukiwania slowa w slowniku: otwieramy slownik w polowie, sprawdzamy czy szukane slowo jest przed czy po aktualnej stronie, powtarzamy az znajdziemy.
Myslenie komputacyjne stosujemy codziennie, nawet nie zdajac sobie z tego sprawy:
Zanim zapiszemy rozwiazanie w jezyku programowania, warto zapisac je w pseudokodzie - uproszczonym jezyku polaczeniu polskiego i programowania:
ALGORYTM: Czy liczba jest parzysta?
WEJSCIE: liczba n
1. Oblicz reszta = n mod 2
2. JESLI reszta == 0
3. WYPISZ "Liczba jest parzysta"
4. W PRZECIWNYM RAZIE
5. WYPISZ "Liczba jest nieparzysta"
KONIECRozloz problem "organizacja imprezy urodzinowej" na co najmniej 6 mniejszych zadan. Dla kazdego podzadania napisz 2-3 konkretne kroki do wykonania.
Dekompozycja: Organizacja imprezy urodzinowej
1. Lista gosci
- Okresl ile osob zaprosic
- Przygotuj zaproszenia
- Zbierz potwierdzenia
2. Miejsce
- Wybierz lokalizacje (dom, restauracja, park)
- Sprawdz dostepnosc terminu
- Zarezerwuj miejsce
3. Jedzenie i napoje
- Okresl menu (dieta, alergie gosci)
- Zrob liste zakupow
- Zamow lub przygotuj jedzenie
4. Dekoracje
- Wybierz motyw przewodni
- Kup balony, serpentyny, obrus
- Udekoruj miejsce
5. Rozrywka
- Zaplanuj gry i zabawy
- Przygotuj muzyke
- Opcjonalnie: zamow animatora
6. Tort
- Wybierz smak i rozmiar
- Zamow lub upiecz
- Kup swieczkiZnajdz wzorzec (prawidlowosc) w ponizszych ciagach i podaj kolejny element:
a) 2, 4, 8, 16, 32, ?
b) 1, 1, 2, 3, 5, 8, 13, ?
c) PON, WTO, SRO, CZW, ?
d) A1, B2, C3, D4, ?
a) 64 (kazda liczba to podwojenie poprzedniej: *2)
b) 21 (ciag Fibonacciego: kazda liczba to suma dwoch poprzednich)
c) PIA (dni tygodnia w skrocie)
d) E5 (kolejna litera alfabetu + kolejna cyfra)Robot stoi na planszy 5x5 w lewym dolnym rogu (pole 1,1). Musi dojsc do prawego gornego rogu (pole 5,5). Robot rozumie komendy: GORA, DOL, LEWO, PRAWO. Napisz algorytm (ciag komend), ktory doprowadzi robota do celu. Nastepnie zastanow sie: ile jest mozliwych najkrotszych tras? Jakie informacje sa nieistotne (abstrakcja)?
Jedna z mozliwych tras:
PRAWO, PRAWO, PRAWO, PRAWO, GORA, GORA, GORA, GORA
Inna trasa:
GORA, PRAWO, GORA, PRAWO, GORA, PRAWO, GORA, PRAWO
Najkrotsza trasa wymaga dokladnie 4 ruchow PRAWO i 4 ruchow GORA
(lacznie 8 krokow).
Liczba mozliwych najkrotszych tras: C(8,4) = 70
Abstrakcja: Nieistotne sa kolory pol, rozmiar robota,
predkosc poruszania sie - liczy sie tylko pozycja
i dozwolone ruchy.Zastosuj wszystkie 4 etapy myslenia komputacyjnego do problemu: "Jak znalezc najkrotsza trase z domu do szkoly?". Opisz: (1) dekompozycje, (2) wzorce, (3) abstrakcje, (4) algorytm w pseudokodzie.
1. DEKOMPOZYCJA:
- Znajdz punkt startowy (dom) i koncowy (szkola)
- Okresl mozliwe drogi/trasy
- Dla kazdej trasy oblicz odleglosc/czas
- Porownaj trasy i wybierz najlepsza
2. WZORCE:
- Problem jest podobny do nawigacji GPS
- Przypomina szukanie drogi w labiryncie
- Znane algorytmy: Dijkstra, A*
3. ABSTRAKCJA:
- Nieistotne: kolor budynkow, pogoda, pora dnia
- Istotne: skrzyzowania, odleglosci miedzy nimi,
dozwolone kierunki jazdy
- Model: graf (wezly = skrzyzowania, krawedzie = drogi)
4. ALGORYTM:
START
trasy = znajdz_wszystkie_trasy(dom, szkola)
najlepsza = trasy[0]
DLA KAZDEJ trasy w trasach:
JESLI dlugosc(trasa) < dlugosc(najlepsza):
najlepsza = trasa
ZWROC najlepsza
KONIEC