Wróć do informacji o e-podręczniku Wydrukuj Pobierz materiał do PDF Pobierz materiał do EPUB Pobierz materiał do MOBI Zaloguj się, aby dodać do ulubionych Zaloguj się, aby skopiować i edytować materiał Zaloguj się, aby udostępnić materiał Zaloguj się, aby dodać całą stronę do teczki
Oceń projekt

Minimalne drzewo rozpinające grafu

Scenariusz lekcji

Temat lekcji:

Minimalne drzewo rozpinające grafu

Cele lekcji:

Wiadomości:

Uczeń potrafi:

  • podać definicje podstawowych pojęć teorii grafów: ścieżka, cykl, minimalne drzewo rozpinające, graf ważony, macierz kosztów, drzewo rozpinające, długość ścieżki;

  • omówić problem odszukania minimalnego drzewa rozpinającego;

  • omówić sposób opisu grafu ważonego w pliku tekstowym;

  • opisać macierz kosztów i jej znaczenie dla grafu ważonego;

  • opisać algorytm Kruskala wyszukujący minimalne drzewo rozpinające;

  • opisać algorytm Prima wyszukujący minimalne drzewo rozpinające;

  • podać przykłady wykorzystania poznanych algorytmów.

Umiejętności:

Uczeń potrafi:

  • zapisać algorytm Prima w postaci listy kroków;

  • zapisać algorytm Kruskala w postaci listy kroków;

  • utworzyć plik tekstowy zawierający opis grafu ważonego;

  • implementować algorytm Prima w VB .NET;

  • implementować algorytm Kruskala w VB .NET.

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=334.

Uwarunkowania techniczne

  • lokalna sieć komputerowa składająca się ze stanowisk uczniowskich, z zainstalowanym VB .NET i 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 podstawowych pojęć z teorii grafów

  • podanie tematu lekcji

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

Faza realizacyjna

– omówienie podstawowych pojęć z teorii grafów (20 min)

  • przypomnienie pojęć: graf, graf skierowany, krawędź, wierzchołek grafu

  • omówienie przykładowego grafu ważonego

  • zapisanie grafu ważonego w macierzy kosztów i omówienie jej budowy

  • omówienie pojęć: cykl, drzewo rozpinające, minimalne drzewo rozpinające

  • pokazanie minimalnego drzewa rozpinającego dla narysowanego grafu

  • pokazanie sposobu zapisu grafu ważonego w pliku tekstowym

– wyszukiwanie minimalnego drzewa rozpinającego za pomocą algorytmu Prima (30 min)

  • omówienie algorytmu Prima

  • zapisanie algorytmu Prima w postaci listy kroków

  • zapisanie przykładowego grafu na tablicy i wyszukanie minimalnego drzewa rozpinającego z wykorzystaniem algorytmu Prima

  • otwarcie nowego projektu w VB .NET

  • zaprojektowanie interfejsu aplikacji według scenariusza zadania

  • analiza algorytmu Prima i zaprojektowanie procedury realizującej ten algorytm

  • kodowanie aplikacji i sprawdzenie poprawności jej działania

  • sprawdzenie programu dla różnych grafów zapisanych w plikach tekstowych

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

– wyszukiwanie minimalnego drzewa rozpinającego za pomocą algorytmu Kruskala (25 min)

  • omówienie algorytmu Kruskala

  • zapisanie algorytmu Kruskala w postaci listy kroków

  • zapisanie przykładowego grafu na tablicy i wyszukanie minimalnego drzewa rozpinającego z wykorzystaniem algorytmu Kruskala

  • zaprojektowanie procedury realizującej algorytm Kruskala

  • modyfikacja interfejsu aplikacji i dodanie drugiej procedury realizującej algorytm Kruskala

  • kodowanie aplikacji i sprawdzenie poprawności jej działania

  • sprawdzenie programu dla różnych grafów zapisanych w plikach tekstowych

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

Faza podsumowująca

– podsumowanie lekcji (5 min)

  • przypomnienie poznanych algorytmów

  • omówienie różnic pomiędzy algorytmami

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, Warszawa 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] J. Białowąs, Kompendium programisty VB .Net, http://www.otwartaszkola.edu.pl/DesktopDefault.aspx?tabid=334

Załączniki

Czas trwania lekcji:

2 x 45 minut

Uwagi

RfLR6o5P5o2H8

Pobierz załącznik

Plik PDF o rozmiarze 86.69 KB w języku polskim
R1Ex8iujJ2V5z

Pobierz załącznik

Plik DOC o rozmiarze 78.00 KB w języku polskim