Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Teoria grafów

Informacje ogólne

Kod przedmiotu: 1000-MS1-TeoGraf Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Teoria grafów
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., stacjonarne, 2 rok, przedmioty do wyboru
Inf., I st., stacjonarne, 3 rok, przedmioty do wyboru
Inf., II st, stacjonarne, przedmioty do wyboru
Przedmioty z polskim językiem wykładowym
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
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.

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 godzin, do egzaminu: 20 godz.

egzamin: 3 godz.


Efekty uczenia się - wiedza:

W1: Zna pojęcia, definicje i twierdzenia teorii grafów oraz dowody twierdzeń - K_W02

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_W6


Efekty uczenia się - umiejętności:

U1: Potrafi konstruować modele teoretyczne dla problemu decyzyjnego w postaci grafu, potrafi dowodzić własności i twierdzeń dotyczące omawianych zagadnień teoretycznych - K_U01

U2: Potrafi dokonać analizy problemu decyzyjnego, dobrać odpowiednie struktury dla reprezentacji danych i metody sprzyjające znalezieniu optymalnego rozwiązania problemu decyzyjnego - K_U02

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 - K_K01

K2: Pracuje sumiennie, dotrzymując terminów przekazywania swoich prac, systematycznie zapoznaje się materiałem wykładu i dodatkowymi materiałami elektronicznymi - K_K02

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_K03


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:

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

Metody dydaktyczne podające:

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

Metody dydaktyczne poszukujące:

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

Metody dydaktyczne w kształceniu online:

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

Skrócony opis:

Teoria grafów jest nauką interdyscyplinarną. Prowadzi do umiejętności tworzenia abstrakcyjnego modelu dla sytuacji problemowej i przez badanie jego własności, pomaga znaleźć efektywne rozwiązanie. Ma zastosowanie we wszystkich dziedzinach życia, a szczególnej rangi nabiera w czasach, gdy rozwój sieci komputerowych powoduje konieczność analizy dużych zbiorów danych, często przy zastosowaniu sztucznej inteligencji. Konstruowanie abstrakcyjnego modelu w postaci grafu i teoretyczne rozważania są ważnym elementem całego procesu twórczego poszukiwania rozwiązania od specyfikacji problemu, przez zdefiniowanie pojęć, modelowanie sytuacji problemowej, aż do znalezienia rozwiązania, udowodnienia jego poprawności i oszacowania złożoności oraz praktycznej efektywności. Wykład wzbogacony przykładami konkretnych zastosowań omawianych aspektów teoretycznych i algorytmów, połączony z zajęciami laboratoryjnymi, jest ważnym elementem procesu kształcenia absolwenta informatyki i matematyki stosowanej.

Pełny opis:

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.

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.

Metody i kryteria oceniania:

Wykład:

Egzamin teoretyczny.

Z egzaminu są zwolnione osoby, które na zaliczenie otrzymaja ocenę końcową bdb lub +db. Wtedy ocena z egzaminu jest taka jak ocena z ćwiczeń.

Ćwiczenia:

Na ocenę końcową składają się:

kolokwium: praktyka 30%, teoria 30% razem 60%

rozwiązywanie zadań i znajomość wykładu 40%

Aby otrzymać zaliczenie, za każdą ze składowych oceny trzeba zdobyć co najmniej 50% punktów. Dopuszczalne są tylko dwie nieobecności nieusprawiedliwione w semestrze.

Oceny końcowe (%):

90-100 - bdb

80-89 +db

70-79 db

60-69 +dst

50-59 dst

poniżej 50% ndst

Praktyki zawodowe:

nd

Zajęcia w cyklu "Semestr letni 2019/20" (w trakcie)

Okres: 2020-02-29 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska
Prowadzący grup: Anna Kwiatkowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Jak w podstawowej informacji o przedmiocie.

Pełny opis:

Jak w podstawowej informacji o przedmiocie.

Literatura:

Jak w podstawowej informacji o przedmiocie.

Uwagi:

Jak w podstawowej informacji o przedmiocie.

Zajęcia w cyklu "Semestr letni 2020/21" (jeszcze nie rozpoczęty)

Okres: 2021-03-01 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska
Prowadzący grup: Anna Kwiatkowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Jak w podstawowej informacji o przedmiocie.

Pełny opis:

Jak w podstawowej informacji o przedmiocie.

Literatura:

Jak w podstawowej informacji o przedmiocie.

Uwagi:

Jak w podstawowej informacji o przedmiocie.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.