O Kursie

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
   • 2.1. Grafy Eklera
   • 2.2. Malowanie map
   • 2.3. Grafy Hamiltona i problem komiwojażera
3. Przykłady zastosowań grafów w informatyce
   • 3.1. Drzewa wyrażeń
   • 3.2. Drzewa algorytmów
   • 3.3. Drzewa Huffmana – krótkie kody
4. Algorytmy na grafach
   • 4.1. Grafy i ich komputerowe reprezentacje
   • 4.2. Znajdowanie najkrótszych dróg w grafach
   • 4.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.

Certyfikat potwierdzający realizację kursu

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”