Teoria grafów 1000-MS1-TeoGraf

https://plas.mat.umk.pl

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.

W cyklu 2022/23Z:

Jak w podstawowej informacji o przedmiocie.

Całkowity nakład pracy studenta

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

Efekty uczenia się - wiedza

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

Efekty uczenia się - umiejętności

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

Efekty uczenia się - kompetencje społeczne

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

Metody dydaktyczne

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.

Metody dydaktyczne eksponujące

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

Metody dydaktyczne podające

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

Metody dydaktyczne poszukujące

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

Metody dydaktyczne w kształceniu online

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

Rodzaj przedmiotu

przedmiot pomocniczy (atrybut wycofany)

Wymagania wstępne

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.

Koordynatorzy przedmiotu

Anna Kwiatkowska

Kryteria oceniania

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

Praktyki zawodowe

Literatura

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.

W cyklu 2022/23Z:

Jak w podstawowej informacji o przedmiocie.

Uwagi

W cyklu 2022/23Z:

Jak w podstawowej informacji o przedmiocie.

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 1000-MS1-TeoGraf w USOSweb