Opis kursu

Tytuł kursu

Znajdowanie najkrótszych dróg i najkrótszych oraz najniższych drzew

Cel kursu

Celem kursu jest przekazanie uczestnikom podstawowej wiedzy na temat teorii grafów oraz obliczeń na grafach.

Tematyka kursu

Wykład poświęcony jest elementom teorii grafów i obliczeń na grafach. Grafy odgrywają podwójną rolę w informatyce. Z jednej strony, są modelami obliczeń – w tej roli najczęściej występują drzewa – lub odzwierciedlają strukturę połączeń komunikacyjnych, a z drugiej – wiele problemów o praktycznych zastosowaniach jest definiowanych na grafach jako strukturach połączeń (zależności) między elementami. W pierwszej części wykładu zostaną przedstawione problemy,  które miały wpływ na rozwój teorii grafów oraz dużą ich popularność. Druga część jest poświęcona wykorzystaniu drzew jako schematów obliczeń i algorytmów, a w trzeciej części zostaną przedstawione klasyczne problemy obliczeniowe na grafach, takie jak: znajdowanie najkrótszych dróg i  znajdowanie najkrótszego drzewa rozpinającego w grafie z obciążonymi połączeniami. Rozwiązania problemów będą prezentowane w specjalnym oprogramowaniu.

1. Grafy jako modele różnych sytuacji
2. Trzy klasyczne zagadnienia
   1. Grafy Eklera
   2. Malowanie map
   3. Grafy Hamiltona i problem komiwojażera
3. Przykłady zastosowań grafów w informatyce
   1. Drzewa wyrażeń
   2. Drzewa algorytmów
   3. Drzewa Huffmana – krótkie kody
4. Algorytmy na grafach
   1. Grafy i ich komputerowe reprezentacje
   2. Znajdowanie najkrótszych dróg w grafach
   3. Znajdowanie najkrótszych drzew rozpinających w grafach

Struktura kursu

Kurs składa się z następujących elementów:

1. Wykład wprowadzający do kursu (video)
2. Zeszyt dydaktyczny do kursu - w formacie PDF,
3. Prezentacja PowerPoint do kursu - w formacie .ppt,
4. Materiały dodatkowe
5. Test z pytaniami sprawdzającymi wiedzę

Sposób realizacji kursu

Kurs jest przeznaczony do realizacji w trybie samokształcenia lub pod kierunkiem nauczyciela. Po zapoznaniu się ze wszystkimi elementami kursu oraz wykonaniu testu sprawdzającego wiedzę, uczestnik otrzymuje prawo do samodzielnego wystawienia certyfikatu potwierdzającego zrealizowanie kursu e-learningowego „Znajdowanie najkrótszych dróg i najkrótszych oraz najniższych drzew” przygotowanego przez Warszawską Wyższą Szkołę Informatyki.

O wykładowcy

Prof. dr hab. Maciej M. Sysło jest wykładowcą Uniwersytetu Wrocławskiego oraz Uniwersytetu Mikołaja Kopernika w Toruniu. Specjalizuje się w teorii grafów, matematyce dyskretnej, algorytmice, optymalizacji oraz dydaktyce informatyki. W latach 2010-2012 prowadził szkolenia z zakresu algorytmiki i programowania w ramach projektu Informatyka +. Prof. dr hab. Maciej M. Sysło jest koordynatorem merytorycznym w projekcie  „Informatyka – mój sposób na poznanie i opisanie świata – program nauczania informatyki z elementami przedmiotów matematyczno-przyrodniczych”