Module also offered within study programmes:
General information:
Name:
Graphs and Their Uses
Course of study:
2018/2019
Code:
JIS-1-603-s
Faculty of:
Physics and Applied Computer Science
Study level:
First-cycle studies
Specialty:
-
Field of study:
Applied Computer Science
Semester:
6
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
prof. dr hab. Burda Zdzisław (zdzislaw.burda@agh.edu.pl)
Academic teachers:
dr inż. Strzałka Elżbieta (Elzbieta.Strzalka@fis.agh.edu.pl)
prof. dr hab. Burda Zdzisław (zdzislaw.burda@agh.edu.pl)
Module summary

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

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
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 Project,
Presentation
Skills
M_U001 Umiejętność implementacji algorytmów grafowych. Umiejętność pracy w zespole w projekcie informatycznym. IS1A_U06, IS1A_U01, IS1A_U02 Project,
Presentation
M_U002 Umiejętność samodzielnego zdobywania wiedzy na dany temat. Umiejętność przygotowania prezentacji na podstawie zdobytej wiedzy. IS1A_U01, IS1A_U02 Presentation
Knowledge
M_W001 Wiedza na temat podstawowych pojęć w teorii grafów i na temat algorytmów grafowych. IS1A_W01, IS1A_W03, IS1A_W02 Activity during classes
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Umiejętność pracy w zespole. Umiejętność zabierania głosu w dyskusji merytorycznej. Świadomość przydatności algorytmów grafowych w praktycznych zagadnieniach. - - + - - + - - - - -
Skills
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. - - - - - + - - - - -
Knowledge
M_W001 Wiedza na temat podstawowych pojęć w teorii grafów i na temat algorytmów grafowych. + - + - - + - - - - -
Module content
Lectures:
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

Laboratory classes:
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.

Seminar classes:
Referat 20 min.

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

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 90 h
Module ECTS credits 3 ECTS
Participation in lectures 30 h
Participation in laboratory classes 15 h
Participation in seminar classes 15 h
Completion of a project 14 h
Realization of independently performed tasks 10 h
Contact hours 6 h
Additional information
Method of calculating the final grade:

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.

Prerequisites and additional requirements:

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

Recommended literature and teaching resources:

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;

Scientific publications of module course instructors related to the topic of the module:

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.

Additional information:

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