Teoria grafów WM-MA-S2-E3-TG

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ę

matematyka

E-Learning

Grupa przedmiotów ogólnouczenianych

nie dotyczy

Opis nakładu pracy studenta w ECTS

WYKŁAD szacunkowy nakład pracy studenta: uczestnictwo w zajęciach: 30h uczestnictwo w egzaminie: 1h przygotowanie do zajęć: 7h przygotowanie do egzaminu: 12h razem 50h, co odpowiada 2 ECTS ĆWICZENIA uczestnictwo w zajęciach: 30h konsultacje z prowadzącym: 2h prace domowe: 10h samodzielne lektura: 15h przygotowanie do zaliczenia: 18h razem 75h, co odpowiada 3 ECTS

Poziom przedmiotu

średnio-zaawansowany

Symbol/Symbole kierunkowe efektów uczenia się

WYKŁAD MA2_W04 MA2_W05 MA2_W06 MA2_W07 MA2_W16 ĆWICZENIA MA2_U13 MA2_U14 MA2_U15 MA2_U23 MA2_U24 MA2_K02 MA2_K08

Typ przedmiotu

obowiązkowy

Wymagania wstępne

Wymagana jest wiedza i umiejętności z zakresu przedmiotów Elementy logiki i teorii mnogości oraz Matematyka dyskretna. Mile widziane podstawy teorii grafów.

Koordynatorzy przedmiotu

Maria Suwińska

Efekty kształcenia

WYKŁAD
Student
W1: zna podstawowe pojęcia związane z teorią grafów (MA2_W04, MA2_W05, MA2_W16),
W2: zna i rozumie klasyczne problemy grafowe (np. problem chińskiego listonosza, problem mostów królewieckich, kolorowanie grafów i map) (MA2_W04, MA2_W05, MA2_W16)
W3: zna i rozumie działanie wybranych algorytmów grafowych (MA2_W04, MA2_W05, MA2_W16),
W4: zna zastosowania teorii grafów w innych dziedzinach nauki (MA2_W06, MA2_W07, MA2_W16)

ĆWICZENIA
Student
U1: potrafi opisać własności grafu przedstawionego w sposób graficzny lub za pomocą metod algebraicznych (macierz incydencji, macierz sąsiedztwa, ciąg stopni) (MA2_U13, MA2_U24)
U2: potrafi w sposób precyzyjny omówić złożone problemy grafowe na podstawie wiedzy z zajęć oraz z dodatkowych źródeł (MA2_U13, MA2_U15, MA2_U23, MA2_U24)
U3: potrafi samodzielnie udowodnić wybrane własności grafów, w tym grafów planarnych, grafów prostych i grafów dwudzielnych (MA2_U13, MA2_U14, MA2_U24)
U4: potrafi zastosować metody zaczerpnięte z teorii grafów do rozwiązywania różnych problemów i zadań (MA2_U13, MA2_U23, MA2_U24)
K1: jest gotów stawiać pytania związane z omawianymi na ćwiczeniach zagadnieniami (MA2_K02)
K2; jest gotów wykorzystywać zdobytą wiedzę i umiejętności w innych dziedzinach nauki oraz, w dalszej perspektywie, w pracy zawodowej (MA2_K08)

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:

Strona przedmiotu WM-MA-S2-E3-TG w USOSweb