Wykorzystanie drzew binarnych do sortowania

Scenariusz lekcji

Temat lekcji:

Wykorzystanie drzew binarnych do sortowania

Cele lekcji:

Wiadomości:

Uczeń potrafi:

  • podać definicję drzewa binarnego i kopca;

  • podać definicje podstawowych pojęć związanych z drzewem binarnym;

  • wymienić cechy drzewa binarnego;

  • wymienić cechy drzewa zrównoważonego i uporządkowanego;

  • podać zasadę wyliczania indeksu tablicy dla danego elementu drzewa;

  • podać zasadę tworzenia kopca;

  • podać zasadę rozbioru kopca;

  • określić efektywność sortowania przez kopcowanie.

Umiejętności:

Uczeń potrafi:

  • utworzyć drzewo binarne za pomocą tablicy w VB .NET;

  • wskazać drzewo binarne, lub kopiec w kodzie w programu w VB .NET;

  • utworzyć kopiec w programie w VB .NET;

  • dokonać rozbioru kopca w VB .NET;

  • wykorzystać drzewo binarne lub kopiec przy rozwiązywaniu typowych problemów algorytmicznych (sortowanie).

Metody nauczania

  • pogadanka;

  • laboratoryjna z elementami pokazu.

Środki dydaktyczne

  • komputery z zainstalowanym VB .NET;

  • scenariusze zadań dostępne pod adresem: http://www.otwartaszkola.edu.pl/DesktopDefault.aspx?tabid=465.

Uwarunkowania techniczne

  • lokalna sieć komputerowa składająca się ze stanowisk uczniowskich, z zainstalowanym VB .NET i programem Power Point;

  • projektor multimedialny.

Przebieg lekcji

Etap

Zadanie

Przebieg realizacji

Uwagi do realizacji

Faza przygotowawcza

– czynności organizacyjne (5 min)

– wprowadzenie do tematu lekcji (5 min)

  • przypomnienie pojęcia sortowania

  • przypomnienie poznanych algorytmów sortowania

  • podanie tematu lekcji

  • przedstawienie zagadnień, które zostaną omówione na lekcji, zaciekawienie uczniów jej treścią

Faza realizacyjna

– omówienie drzewa binarnego (10 min)

  • omówienie struktury danych nazywanej drzewem binarnym

  • omówienie podstawowych podjęć związanych z drzewem binarnym: korzeń, węzeł, liść, drzewo zrównoważone, drzewo uporządkowane

– omówienie zapisu drzewa binarnego za pomocą tablicy (10 min)

  • omówienie zasad tworzenia tablicy służącej do zapamiętania drzewa binarnego

  • narysowanie przykładowego drzewa i zapisanie go w tablicy

  • uczniowie samodzielnie zapisują w tablicy drzewo binarne narysowane przez nauczyciela

  • uczniowie samodzielnie rysują drzewo binarne na bazie tablicy zawierającej jego opis

– omówienie tworzenia
i rozbioru kopca (15 min)

  • omówienie pojęcia kopca i zasad tworzenia kopca

  • narysowania na tablicy przykładowego drzewa binarnego i zamienienie go na kopiec

  • omówienie zasad rozbioru kopca

  • dokonanie rozbioru kopca narysowanego na tablicy – uczniowie zauważają, że elementy usunięte z kopca tworzą uporządkowany ciąg – nastąpiło sortowanie danych

  • uogólnienie algorytmu sortowania przez kopcowanie

– utworzenie programu realizującego sortowanie przez kopcowanie (40 min)

  • otwarcie nowego projektu w VB .NET

  • utworzenie interfejsu aplikacji

  • utworzenie procedur tworzących kopiec i rozbierających kopiec według scenariusza zadania

  • sprawdzenie poprawności działania aplikacji

Scenariusze zadań oraz programy są dostępne pod adresem http://www.otwartaszkola.edu.pl/DesktopDefault.aspx?tabid=223

Faza podsumowująca

– podsumowanie lekcji (5 min)

  • analiz poznanego algorytmu – próba określenia jego efektywności

Bibliografia

[1] P. Wróblewski, Algorytmy – struktury danych i techniki programowania, Helion, Gliwice 1997.

[2] L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Gliwice 2001.

[3] A.A. Aho, J.E. Hopcroft, J.D. Ullman, Algorytmy i struktury danych, Helion, Gliwice 2003.

[4] H. Gantenbein, G. Dunn, A. Kalani, Ch. Payne, T. Thangarathinam, MS Visual Basic.NET 2003. Księga eksperta, Helion, Gliwice 2006.

[5] Paul Kimmel, Visual Basic.NET Księga eksperta, Helion, Gliwice 2003.

[6] Niklas Wirth, Algorytmy+struktury danych=programy, WNT, Warszawa 1999.

[7] J. Białowąs, Kompendium programisty VB .NET, http://www.otwartaszkola.edu.pl/DesktopDefault.aspx?tabid=464

Załączniki

Czas trwania lekcji:

2 x 45 minut

Uwagi

RNqhxT9pkHVip

Pobierz załącznik

Plik PDF o rozmiarze 86.85 KB w języku polskim
Rvgnr2T8HASAU

Pobierz załącznik

Plik DOC o rozmiarze 76.50 KB w języku polskim