Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Teoria grafów

Informacje ogólne

Kod przedmiotu: 1000-MS1-TeoGraf
Kod Erasmus / ISCED: (brak danych) / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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
Strona przedmiotu: https://plas.mat.umk.pl
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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.

Rodzaj przedmiotu:

przedmiot pomocniczy

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:

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

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:

nd

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 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 zimowy 2022/23" (zakończony)

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska
Prowadzący grup: Anna Kwiatkowska
Strona przedmiotu: https://plas.mat.umk.pl
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 2023/24" (w trakcie)

Okres: 2024-02-20 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 16 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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)