Spis treści

Wprowadzenie

Film

Ćwiczenia

Podsumowanie

Słowniczek

Dla nauczyciela

Wprowadzenie

Wyszukiwanie informacji to jeden z podstawowych problemów, którymi zajmuje się algorytmika. Algorytm wyszukujący otrzymuje na wejściu określony problem i po przetestowaniu pewnej liczby możliwych wariantów, daje na wyjściu jego rozwiązanie. Algorytmy stosujące bardziej zaawansowane metody wyszukiwania, potrzebują mniej czasu na przetworzenie danych w przestrzeni poszukiwań.

Już wiesz

Przed zapoznaniem się z e-materiałem musisz wiedzieć:

- czym jest algorytm;

- jak przedstawić algorytm w postaci schematu blokowego;

- jaka jest różnica między zbiorem uporządkowanym i nieuporządkowanym.

Nauczysz się

- stosować algorytm wyszukiwania liniowego w zbiorze nieuporządkowanym;

- stosować algorytm wyszukiwania binarnego w zbiorze uporządkowanym;

- znajdować rozwiązanie problemu metodą „dziel i zwyciężaj”.

Film

Ćwiczenia

Interaktywne ćwiczenia multimedialne

Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DaXJVdqq5

Źródło: LEARNETIC SA, licencja: CC BY 4.0.

Podsumowanie

Podsumowanie

1. Wyszukiwania liniowe polega na przeglądaniu zbioru nieuporządkowanego, element po elemencie, aż do napotkania poszukiwanego elementu (sukces) lub końca listy (niepowodzenie).

2. Metoda „dziel i zwyciężaj” zakłada dzielenie problemu na mniejsze podproblemy tak długo, aż staną się wystarczająco proste do rozwiązania. Uzyskane w ten sposób rozwiązania scala się, uzyskując rozwiązanie całego zadania.

3. Na tej metodzie opiera się algorytm wyszukiwania binarnego. Dzieli on uporządkowany zbiór na coraz mniejsze części, aż do otrzymania podzbioru jednoelementowego i sprawdza, czy jest to szukany element.

4. Wyszukiwanie binarne daje bardzo dobre rezultaty w zbiorze uporządkowanym, dlatego ważnym problemem jest szybkie i efektywne porządkowanie elementów.

Słowniczek

algorytm wyszukiwania binarnego (połówkowego)

algorytm oparty na metodzie „dziel i zwyciężaj”, polegający na dzieleniu uporządkowanego zbioru na coraz mniejsze części, aż do otrzymania podzbioru jednoelementowego i sprawdzenia, czy jest to szukany element

algorytm wyszukiwania liniowego (sekwencyjnego)

algorytm polegający na przeglądaniu zbioru nieuporządkowanego, element po elemencie, aż do napotkania poszukiwanego elementu (sukces) lub końca listy (niepowodzenie)

algorytm wyszukujący

algorytm, który otrzymuje na wejściu pewien problem i daje na wyjściu jego rozwiązanie po przetestowaniu pewnej ilości możliwych wariantów

dziel i zwyciężaj

metoda projektowania algorytmów, która zakłada dzielenie problemu na mniejsze podproblemy tak długo, aż staną się wystarczająco proste do rozwiązania; uzyskane rozwiązania scala się, uzyskując rozwiązanie całego zadania

efektywność algorytmu

liczba elementarnych kroków, które algorytm musi wykonać, żeby rozwiązać dany problem

Dla nauczyciela

Scenariusz

Autor

Learnetic

Temat zajęć

O wyższości porządku nad bałaganem

Grupa docelowa

Szkoła podstawowa 7-8

Szkoła ponadpodstawowa

Ogólny cel kształcenia

Rozumienie, analizowanie i rozwiązywanie problemów.

Kształtowane kompetencje kluczowe:

1) porozumiewanie się w języku ojczystym;

2) myślenie matematyczne i podstawowe kompetencje naukowo-techniczne;

3) informatyczne (TSI kompetencje społeczeństwa informacyjnego);

4) umiejętność uczenia się;

6) inicjatywność i przedsiębiorczość;

Cele (szczegółowe) operacyjne

Uczeń:

a) stosuje przy rozwiązywaniu problemów podstawowe algorytmy wyszukiwania liniowego i binarnego;

b) wyszukuje element w zbiorze uporządkowanym i nieuporządkowanym;

c) spośród kilku możliwości, wybiera rozwiązanie kierując się zasadą „dziel i zwyciężaj”.

Metody/techniki kształcenia:

- pogadanka

- pokaz multimedialny

- ćwiczenia

- metoda problemowa

- „burza mózgów”

Formy ogranizacji pracy:

- indywidualna

- zbiorowa

Przebieg lekcji

Faza wprowadzając

- Czynności organizacyjne.

- Podanie tematu lekcji i omówienie jej przebiegu.

- Nauczyciel przypomina definicję algorytmu (jeśli uczniowie się zgłaszają, prosi ich o dokończenie definicji).

- Następnie informuje, że będziemy zajmować się algorytmami wyszukiwania, których zadaniem jest odszukanie określonej informacji w zbiorze danych.

Faza realizacyjna

- Nauczyciel przedstawia klasie zadania:

- Wyobraźmy sobie, że pomyślałem pewną liczbę z przedziału od 1 do 100. Jaki algorytm (czyli strategię) możecie zastosować, żeby odgadnąć tę liczbę? Mogę odpowiadać tylko „tak” lub „nie”.

- Uczniowie zgłaszają się i podają propozycje: możemy pytać o każdą liczbę po kolei, możemy pytać o losowo wybrane liczby („strzelać”).

- Nauczyciel pyta: ile pytań będziecie musieli zadać w najbardziej pesymistycznym przypadku?

- Jeśli uczniowie mają problem naprowadza ich na odpowiedź „100”.

- Następnie pyta, czy ilość pytań zmniejszy się, jeżeli będzie udzielał podpowiedzi „za dużo” lub „za mało”.

- Nauczyciel pomaga uczniom (jeśli jest taka potrzeba) wywnioskować, że w takiej sytuacji opłaca się „strzelać” w środek przedziału, co pozwala odrzucić połowę liczb.

- Nauczyciel proponuje uczniom grę w zgadywanie liczby.

- Grupa uczniów (np. 10 osób) wychodzi na środek klasy. Nauczyciel rozdaje im (w dowolnej kolejności) kartki, z zapisaną liczbą. Uczniowie trzymają kartki tak, żeby liczby były ukryte przed resztą klasy. Nauczyciel wyznacza jeszcze trzech uczniów, każdemu z nich wręcza pudełeczko z 10 cukierkami. Zadanie każdego z nich polega na odgadnięciu, kto trzyma kartkę ze wskazaną przez nauczyciela liczbą. Uczniowie „płacą” cukierkami za możliwość spojrzenia na kartkę. Jeśli uczeń odnajdzie szukaną kartkę, zanim „wyda” wszystkie cukierki, resztę może zachować dla siebie.

- Pierwszy uczeń pyta każdą osobę po kolei (rozdając kartki z liczbami możemy „zadbać” o to, żeby szukana liczba była odpowiednio daleko).

- Nauczyciel tasuje kartki i rozdaje je jeszcze raz.

- Drugi uczeń odkrywa kartki w wybranej przez siebie kolejności (możemy podkreślić rolę szczęśliwego trafu).

- Nauczyciel tasuje kartki i rozdaje je jeszcze raz. Informuje klasę, że tym razem liczby na kartkach są uporządkowane rosnąco.

- Trzeci uczeń stosuje strategię „wykluczenia” połowy kartek z dalszych przeszukiwań za pomocą tylko jednego „płacenia” za ujawnienie liczby osoby, która jest w środku.

- Nauczyciel omawia efektywność algorytmu na przykładzie cukierków, które udało się „zaoszczędzić”.

- Uczniowie oglądają film „Za dużo – za mało”.

- Uczniowie indywidualnie rozwiązują zadania interaktywne utrwalające wiadomości zdobyte w trakcie oglądania filmu.

- Nauczyciel omawia wszystkie zadania, uczniowie podają odpowiedzi.

Faza podsumowująca

- Nauczyciel inicjuje pogadankę w celu omówienia i utrwalenia zagadnień poruszonych w filmie: wyszukiwanie liniowe, wyszukiwanie binarne, metoda dziel i zwyciężaj, efektywność algorytmu.

Praca domowa

- Uczniowie dobierają się w pary. Jedna osoba wybiera dowolną liczbę np. z przedziału od 1 do 100 (lub innego). Druga osoba odgaduje tę liczbę, stosując metodę „dziel i zwyciężaj”. Zapisuje kolejne etapy odgadywania. Po odgadnięciu uczniowie zamieniają się rolami.

Metryczka

Tytuł

O wyższości porządku nad bałaganem

Temat lekcji z e-podręcznika, do którego e-materiał się odnosi

Brak

Przedmiot

Informatyka

Etap edukacyjny

II/szkoła podstawowa 7-8

III/szkoła ponadpodstawowa

Podstawa programowa

5. Uczeń:

1) wyjaśnia pojęcie algorytmu, podaje odpowiednie przykłady algorytmów rozwiązywania różnych problemów;

2) formułuje ścisły opis prostej sytuacji problemowej, analizuje ją i przedstawia rozwiązanie w postaci algorytmicznej;

4) opisuje sposób znajdowania wybranego elementu w zbiorze nieuporządkowanym i uporządkowanym.

Nowa podstawa programowa

Szkoła podstawowa 7-8:

I. Rozumienie, analizowanie i rozwiązywanie problemów. Uczeń:

2. stosuje przy rozwiązywaniu problemów podstawowe algorytmy:

b) wyszukiwania i porządkowania: wyszukuje element w zbiorze uporządkowanym i nieuporządkowanym oraz porządkuje elementy w zbiorze metodą przez proste wybieranie i zliczanie;

Szkoła ponadpodstawowa:

I. Rozumienie, analizowanie i rozwiązywanie problemów. Zakres podstawowy. Uczeń:

1. planuje kolejne kroki rozwiązywania problemu, z uwzględnieniem podstawowych etapów myślenia komputacyjnego (określenie problemu, definicja modeli i pojęć, znalezienie rozwiązania, zaprogramowanie i testowanie rozwiązania).

2. stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy:

3. wyróżnia w problemie podproblemy i charakteryzuje: metodę połowienia, stosuje podejście zachłanne i rekurencję;

4. porównuje działanie różnych algorytmów dla wybranego problemu, analizuje algorytmy na podstawie ich gotowych implementacji;

5. sprawdza poprawność działania algorytmów dla przykładowych danych.

Kompetencje kluczowe

Zalecenie Parlamentu Europejskiego i Rady UE z 18.12.2006, Kompetencje kluczowe:

1) porozumiewanie się w języku ojczystym;

2) myślenie matematyczne i podstawowe kompetencje naukowo-techniczne;

3) informatyczne (TSI kompetencje społeczeństwa informacyjnego);

4) umiejętność uczenia się;

6) inicjatywność i przedsiębiorczość;

Cele edukacyjne zgodne z etapem kształcenia

Po zapoznaniu się z e-materiałem uczeń:

– przeprowadza analizę problemu, sprowadzając jego rozwiązanie do zastosowania znanych metod;

– spośród kilku możliwości, wybiera rozwiązanie kierując się zasadą „dziel i zwyciężaj”;

– stosuje podejście algorytmiczne, wybierając najbardziej efektywny sposób rozwiązania problemu;

– ocenia, czy zastosowana metoda jest najszybsza, optymalizuje rozwiązanie.

Powiązanie z e-podręcznikiem

Brak

Table of Contents

Wprowadzenie

Film

Ćwiczenia

Podsumowanie

Słowniczek

Dla nauczyciela