Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Grafy i ich zastosowania
Tok studiów:
2018/2019
Kod:
JIS-1-603-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka Stosowana
Semestr:
6
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
prof. dr hab. Burda Zdzisław (zdzislaw.burda@agh.edu.pl)
Osoby prowadzące:
dr inż. Strzałka Elżbieta (Elzbieta.Strzalka@fis.agh.edu.pl)
prof. dr hab. Burda Zdzisław (zdzislaw.burda@agh.edu.pl)
Krótka charakterystyka modułu

Celem kursu jest poznanie podstawowych pojęć i zagadnień dotyczących zastosowania grafów i algorytmów grafowych oraz nauka samodzielnej ich implementacji.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Wiedza na temat podstawowych pojęć w teorii grafów i na temat algorytmów grafowych. IS1A_W01, IS1A_W03, IS1A_W02 Aktywność na zajęciach
Umiejętności
M_U001 Umiejętność implementacji algorytmów grafowych. Umiejętność pracy w zespole w projekcie informatycznym. IS1A_U06, IS1A_U01, IS1A_U02 Projekt,
Prezentacja
M_U002 Umiejętność samodzielnego zdobywania wiedzy na dany temat. Umiejętność przygotowania prezentacji na podstawie zdobytej wiedzy. IS1A_U01, IS1A_U02 Prezentacja
Kompetencje społeczne
M_K001 Umiejętność pracy w zespole. Umiejętność zabierania głosu w dyskusji merytorycznej. Świadomość przydatności algorytmów grafowych w praktycznych zagadnieniach. IS1A_K03, IS1A_K01 Projekt,
Prezentacja
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Wiedza na temat podstawowych pojęć w teorii grafów i na temat algorytmów grafowych. + - + - - + - - - - -
Umiejętności
M_U001 Umiejętność implementacji algorytmów grafowych. Umiejętność pracy w zespole w projekcie informatycznym. - - + - - - - - - - -
M_U002 Umiejętność samodzielnego zdobywania wiedzy na dany temat. Umiejętność przygotowania prezentacji na podstawie zdobytej wiedzy. - - - - - + - - - - -
Kompetencje społeczne
M_K001 Umiejętność pracy w zespole. Umiejętność zabierania głosu w dyskusji merytorycznej. Świadomość przydatności algorytmów grafowych w praktycznych zagadnieniach. - - + - - + - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
Grafy i ich zastosowania

1 Wstęp
motywacja
zarys historyczny

2 Podstawowe pojęcia i definicje
grafy i digrafy
podgrafy, izomorfizm
spójność, silna spójność, ścieżki, cykle
stopnie wierzchołków
grafy eulerowskie, grafy hamiltonowskie
grafy dwudzielne (k-dzielne), grafy regularne

3 Reprezentacja i implementacja grafów
macierz sąsiedztwa
lista sąsiedztwa
sekwencje graficzne

4 Grafy drzewiaste
zliczanie drzew
kod Prüfera
zastosowania drzew: minimalne drzewa rozpinające, drzewa przeszukiwań

5 Podstawowe algorytmy
przeszukiwanie w głąb i wszerz
drzewa rozpinające (a. Kruskala, a. Prima)
najkrótsze ścieżki (a. Bellmana-Forda, a. Dijkstry, a. Floyda-Warshalla)
silnie spójne składowe
problem chińskiego listonosza

6 Grafy planarne – kolorowanie grafów i map
definicja i kryterium planarności (tw. Kuratowskiego)
wzór Eulera
grafy dualne
kolorowanie grafów i map

7 Przepływy na sieciach
związek przepływu z przekrojami
wyznaczanie maksymalnego przepływu (a. Forda-Fulkersona)

8 Procesy dynamiczne na grafach i łańcuchy Markowa
błądzenie przypadkowe
epidemie
transport na sieci
algorytm page rank

9 Perkolacja
sformułowanie problemu
wyszukiwanie klastrów (a. Hoshena-Kopelmana)
wyznaczanie progu perkolacji

10 Grafy losowe i sieci złożone
grafy Erdösa-Rényi’ego
grafy rosnące
randomizacja grafów
symulacje Monte-Carlo grafów losowych

11 Problem i komiwojażera
heurystyka przybliżonego rozwiązania
metoda wyżarzania

12 Wzmianka o innych problemach związanych z grafami
problem kojarzenia
problem spełnialności
sieci bayesowskie
diagramy Woronoja

Ćwiczenia laboratoryjne:
Wykonanie ćwiczeń projektowych z zastosowaniem algorytmów grafowych.

Wykonanie sześciu zadań informatycznych polegających na implementacji algorytmów grafowych. Zadania będą wykonywane w grupach 3-4 osobowych.

Zajęcia seminaryjne:
Referat 20 min.

Wygłoszenie 20-minutowego referatu na wybrany temat z listy lub na inny temat uzgodniony z prowadzącym.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 90 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 30 godz
Udział w ćwiczeniach laboratoryjnych 15 godz
Udział w zajęciach seminaryjnych 15 godz
Wykonanie projektu 14 godz
Samodzielne studiowanie tematyki zajęć 10 godz
Dodatkowe godziny kontaktowe z nauczycielem 6 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

OCENA KOŃCOWA

W ramach kursu możną uzyskać 0-100 pkt.

1. za zadania projektowe 0-60
2. za seminarium 0-25
3. za nieobowiązkowe kolokwium (-10)-15

Skala ocen:

0-50 ndst
51-60 dst
61-70 +dst
71-80 db
81-90 +db
91-100 bdb

Ad 1.
6 zestawów zadań projektowych wykonywanych w grupach 3-4 osobowych. Za każdy zestaw można uzyskać 0-10 pkt. Zadania zostaną sformułowane w trakcie pierwszych 5-6 ćwiczeń. Później nastąpi
etap prezentacji rozwiązań w wybranych terminach (10-15 min na projekt).

Ad 2.
Referat (prezentacja multimedialna) 20 min. : temat do wyboru z listy albo temat samodzielnie zaproponowany i uzgodniony z prowadzącym. Referat wymaga samodzielnego opracowania. Ocenie podlega przekazana wiedza, jakość prezentacji oraz odpowiedzi na pytania. Aby uzyskać niezerową liczbę punktów z seminarium należy mieć co najmniej 10 obecności na zajęciach seminaryjnych.

Ad 3.
Na ostatnim wykładzie odbędzie się nieobowiązkowe kolokwium. Osoby, które do niego
nie przystąpią, nie otrzymają za nie punktów. Osoby, które przystąpią do kolowium, mogą
maksymalnie zyskać do 15 punktów albo stracić do 10 punktów.
Punkty, będące składnikiem oceny, zostaną naliczone zgodnie ze wzorem p=x-10,
gdzie x jest liczbą z zakresu 0-25 i oznacza liczbę punktów, które można zdobyć w kolokwium.

Wymagania wstępne i dodatkowe:

Podstawy matematyki dyskretnej oraz podstawowa wiedza nt. algorytmów i struktur danych.

Zalecana literatura i pomoce naukowe:

1 R. J. Wilson, Wprowadzenie do teorii grafów, PWN 2004;
2 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT 2005;
3 W. Lipski, Kombinatoryka dla programistów, WNT 2004;
4 W. M. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne, PWN 1985;
5 N. Deo, Teoria grafów i jej zasotosowania w informatyce i technice, PWN 1980;
6 V. Bryant, Aspekty kombinatoryki, WNT 1997;

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. L. Bogacz, Z. Burda, W. Janke, B. Waclaw, A program generating homogeneous random graphs with given weights, Comp. Phys. Comm. 173 (2005) 162.

2. B. Waclaw, L. Bogacz, Z. Burda, W. Janke, Monte-Carlo methods for generation of random graphs, Proceedings of the conference Path Integrals: New Trends and Perspectives, (2008) 342 World Scientific Publishing.

3. Z. Burda, J.D. Correia, A. Krzywicki, Statistical Ensemble of Scale-free Random Graphs, Phys. Rev. E 64 (2001) 046118.

4. S. Bilke, Z. Burda, J. Jurkiewicz, Simplicial Quantum Gravity on a Computer, Comp. Phys. Comm. 85 (1995) 278.

5. J. Ambjorn, P. Bialas, Z. Burda, J. Jurkiewicz, B. Petersson, Effective Sampling of Random Surfaces by Baby Universe Surgery, Phys. Lett. B 325 (1994) 337.

Informacje dodatkowe:

Sposób i tryb wyrównania zaległości powstałych wskutek nieobecności studenta na zajęciach: wyrównywanie zaległości jest możliwe; student uzgadnia to bezpośrednio z osobą prowadzącą odpowiednie zajecia