Teoria grafów

Znajomość:

- zagadnień z przedmiotu Matematyka dyskretna

- algorytmów z programu przedmiotów Programowanie i algorytmika (kierunek matematyka stosowana) lub Algorytmy i struktury danych (kierunek informatyka).

- technik i metod programowania: iteracja, rekurencja, dziel i zwyciężaj, zachłanność, dynamiczność, przeszukiwanie z nawrotami oraz znajomość podstawowych struktur danych, w tym dynamicznych struktur danych (stos, kolejka, lista) oraz ich implementacji w języku C++ lub Python.

przedmiot pomocniczy

godziny kontaktowe:

30 godz. wykładu

30 godz. ćwiczeń

zadania domowe i bieżące przygotowanie się do ćwiczeń: 60 godz.

przygotowanie się do kolokwiów 20 godz.,

przygotowanie się do egzaminu: 20 godz.

zaliczenia i egzamin: 3 godz.

Razem 163 godz.

6 pkt ECTS

W1: Zna pojęcia, definicje i twierdzenia teorii grafów oraz dowody twierdzeń - K_W02, KW03

W2: Zna najważniejsze algorytmy na grafach i ich zastosowania w różnych sytuacjach decyzyjnych - K_W03

W3: Wie jak zbudować abstrakcyjny model sytuacji problemowej w postaci grafu, na drodze do poszukiwania optymalnego rozwiązania dla praktycznych problemów z różnych dziedzin życia - K_W06

U1: Potrafi konstruować modele teoretyczne dla problemu w postaci grafu, potrafi dowodzić własności i twierdzenia dotyczące omawianych zagadnień teoretycznych - K_U02, K_U06

U2: Potrafi dokonać analizy problemu decyzyjnego, dobrać odpowiednie struktury dla reprezentacji danych i metody sprzyjające znalezieniu optymalnego rozwiązania problemu decyzyjnego - K_U02, K_U17

U3: Potrafi zapisać w postaci pseudokodu oraz zaprogramować rozwiązanie problemu decyzyjnego w formalnym języku programowania, korzystając przy tym z gotowych bibliotek dla wybranych struktur danych - K_U17

K1: Pracuje twórczo przy konstruowaniu modelów grafów dla sytuacji problemowych z różnych dziedzin życia i rozważa różne możliwości modelowania, korzysta przy tym z różnych źródeł informacji - K_K02, K_K03

K2: Pracuje sumiennie, dotrzymując terminów przekazywania swoich prac, systematycznie zapoznaje się materiałem wykładu i dodatkowymi materiałami elektronicznymi - K_K01, K_K04

K3: Skutecznie i w sposób zrozumiały omawia i prezentuje wybrane algorytmy grafowe, posługując się przy tym fachową terminologią określając bibliografię - K_K02

Wykład ma charakter informacyjno-problemowy i jest połączony z pokazem wizualizacji treści i symulacji algorytmów.

Laboratoria mają charakter teoretyczno-praktyczny, rozważania teoretyczne, są połączone z praktyczną realizacją algorytmów w laboratorium komputerowym.

- drama
- inscenizacja
- pokaz
- symulacyjna (gier symulacyjnych)

- wykład informacyjny (konwencjonalny)
- wykład konwersatoryjny
- wykład problemowy

- ćwiczeniowa
- giełda pomysłów
- klasyczna metoda problemowa
- projektu
- referatu

- metody odnoszące się do autentycznych lub fikcyjnych sytuacji
- metody rozwijające refleksyjne myślenie
- metody wymiany i dyskusji

Teoria grafów jest nauką interdyscyplinarną. Prowadzi do umiejętności tworzenia abstrakcyjnego modelu dla sytuacji problemowej i przez badanie jego własności, pomaga znaleźć efektywne rozwiązanie. Ma zastosowanie we wszystkich dziedzinach życia, a szczególnej rangi nabiera w czasach, gdy rozwój sieci komputerowych powoduje konieczność analizy dużych zbiorów danych, często przy zastosowaniu sztucznej inteligencji. Konstruowanie abstrakcyjnego modelu w postaci grafu i teoretyczne rozważania są ważnym elementem całego procesu twórczego poszukiwania rozwiązania od specyfikacji problemu, przez zdefiniowanie pojęć, modelowanie sytuacji problemowej, aż do znalezienia rozwiązania, udowodnienia jego poprawności i oszacowania złożoności oraz praktycznej efektywności. Wykład wzbogacony przykładami konkretnych zastosowań omawianych aspektów teoretycznych i algorytmów, połączony z zajęciami laboratoryjnymi, jest ważnym elementem procesu kształcenia absolwenta informatyki i matematyki stosowanej.

Wykład:

Jest to klasyczny wykład dotyczący teorii grafów wzbogacony przykładami konkretnych zastosowań omawianych aspektów teoretycznych i algorytmów, w matematyce i informatyce.

Laboratorium:

Zajęcia mają charakter teoretyczno-praktyczny. Są okazją do przeprowadzania formalnych dowodów wybranych twierdzeń z teorii grafów, prezentacji algorytmów oraz komputerowych implementacji wybranych algorytmów.

Tematyka wykładów i ćwiczeń jest ściśle skorelowana i przedstawia się następująco:

1) Współczesne problemy modelowane grafami. Podstawowe definicje i własności grafów. Reprezentacje grafów w komputerze.

2) Identyczność i izomorfizm. Przeszukiwania. Porządek topologiczny.

3) Drogi i ścieżki. Najkrótsze drogi w grafie, digrafie ważonym.

4) Spójność i silna spójność.

5) Drzewa i ich własności.

6) Struktury danych dla zbiorów rozłącznych, find-union, kompresja ścieżek.

7) Drzewa przedziałowe.

8) Operacje na grafach, przechodnie domknięcie, dopełnienie.

9) Cykliczność grafu. Cykl Eulera, cykl Hamiltona.

10) Grafy dwudzielne, skojarzenia i pokrycia, twierdzenie Halla.

11) Planarność i twierdzenie Kuratowskiego.

12) Kolorowanie grafów: metody kolorowania wierzchołków, krawędzi.

13) Problem Chińskiego listonosza i komiwojażera.

14) Przepływy w sieciach i algorytmy znajdowanie maksymalnego i najtańszego przepływu, przegląd najefektywniejszych algorytmów i technik.

15) Problemy rozwiązywane technikami przepływów w sieciach.

Literatura podstawowa:

1. Lipski W., Kombinatoryka dla programistów, WNT, Warszawa 1982.

2. Wilson R.J., Wprowadzenie do teorii grafów, WN PWN, Warszawa 1998.

3. Wojciechowski J., Pieńkosz K., Grafy i sieci, WN PWN, Warszawa 2013.

4. Clark J., Holton D.A., A first look at graph theory, World Scientific Publishing Co. Pte. Ltd., Singapore, USA, UK, 2005

Literatura uzupełniająca:

1. Graham R.L., Knuth D.E., Patashnik O., Matematyka konkretna, WN PWN, Warszawa 1996.

2. Corman T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997

3. Gross J. L., Yellen J., Handbook of graph theory, CRC Press LLC, USA 2004

Literatura dostępna on-line:

Notatki i materiały wykładowcy dostępne na platformie elektronicznego wspomagania zajęć moodle.

Zaliczenie wykładu: egzamin pisemny

Studenta obowiązuje materiał prezentowany w trakcie wykładu; weryfikacja efektów: W2, W3, W6, K3

Zaliczenie ćwiczeń:

Ćwiczenia kończą się zaliczeniem na ocenę - weryfikacja efektów: U1, U2. U3, K1, K2

Przy ocenie na zaliczenie brane są pod uwagę składowe:

wyniki dwóch kolokwiów 2*30% razem 60%

systematyczne rozwiązywanie zadań domowych 30%

aktywność podczas laboratoriów 10%

Aby otrzymać zaliczenie, za każdą ze składowych oceny trzeba zdobyć co najmniej 50% punktów. Z egzaminu są zwolnione osoby, które na zaliczenie otrzymają ocenę końcową bdb lub +db. Wtedy ocena z egzaminu jest taka jak ocena z ćwiczeń

Oceny końcowe (%):

90-100 - bdb

80-89 +db

70-79 db

60-69 +dst

50-59 dst

poniżej 50% ndst

nd

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.