Teoria grafów - zajęcia fakultatywne WM-I-S2-ZF4
Celem przedmiotu jest zapoznanie studentów z podstawowymi pojęciami z zakresu teorii grafów oraz ich zastosowaniami. Na zajęciach omówione zostaną takie zagadnienia jak grafy eulerowskie i hamiltonowskie, problem komiwojażera i problem chińskiego listonosza. Studenci zapoznają się też z własnościami grafów planarnych, problemem kolorowania grafów oraz twierdzeniem o 4 barwach. Omówione zostanie także twierdzenie Halla o kojarzeniu małżeństw.
Dyscyplina naukowa, do której odnoszą się efekty uczenia się
Grupa przedmiotów ogólnouczenianych
Opis nakładu pracy studenta w ECTS
Poziom przedmiotu
Symbol/Symbole kierunkowe efektów uczenia się
Typ przedmiotu
Wymagania wstępne
Koordynatorzy przedmiotu
Efekty kształcenia
WYKŁAD
Student
W1 - wyjaśnia pojęcia związane z teorią grafów (I2_W10),
W2 - omawia klasyczne problemy grafowe (np. problem chińskiego listonosza, problem mostów królewieckich, kolorowanie grafów i map) (I2_W10),
W3 - wyjaśnia działanie wybranych algorytmów grafowych (I2_W10),
W4 - omawia zastosowania teorii grafów w innych dziedzinach nauki (I2_W10).
ĆWICZENIA
Student
U1 - wykorzystuje różne reprezentacje grafów (graficzne i algebraiczne), w tym macierz incydencji, macierz sąsiedztwa oraz ciąg stopni, do analizy ich struktury i identyfikacji wybranych własności grafów (I2_U09),
U2 - samodzielnie wyszukuje, krytycznie ocenia i wykorzystuje informacje z literatury i wykładu do analizy, prezentacji i rozwiązywania złożonych problemów grafowych (I2_U09),
U3 - samodzielnie dobiera i stosuje odpowiednie metody dowodzenia w celu wykazania wybranych własności grafów, w szczególności grafów planarnych, prostych i dwudzielnych (I2_U09),
U4 - krytycznie dobiera i stosuje metody i narzędzia teorii grafów do rozwiązywania różnorodnych problemów (I2_U09).
Kryteria oceniania
Dla wszystkich efektów przyjmuje się następujące kryteria oceny we wszystkich formach weryfikacji:
ocena 5: osiągnięty w pełni (bez uchwytnych niedociągnięć),
ocena 4,5: osiągnięty niemal w pełni i nie są spełnione kryteria przyznania wyższej oceny,
ocena 4: osiągnięty w znacznym stopniu i nie są spełnione kryteria przyznania wyższej oceny,
ocena 3,5: osiągnięty w znacznym stopniu – z wyraźną przewagą pozytywów – i nie są spełnione kryteria przyznania wyższej oceny,
ocena 3: osiągnięty dla większości przypadków objętych weryfikacją i nie są spełnione kryteria przyznania wyższej oceny,
ocena 2: nie został osiągnięty dla większości przypadków objętych weryfikacją.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: