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

Grafowe algorytmy optymalizacyjne

Informacje ogólne

Kod przedmiotu: 1000-M1GAO
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: Grafowe algorytmy optymalizacyjne
Jednostka: Wydział Matematyki i Informatyki
Grupy: Mat, spec. MEF, I st, stacjonarne, 3 rok, przedmioty specjalizacyjne
Mat, spec. MEF, II st, stacjonarne, przedmioty specjalistyczne
Mat. I st., stacjonarne, przedmioty do wyboru (podstawowe)
Mat., sp. nauczycielskie, II st., stacjonarne, przedmioty do wyboru + uzup. stand. kszt.
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:

Student powinien mieć wiedzę z zakresu przedmiotu Wstęp do informatyki, 1000-M1WDIl

Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30 godz. – wykład

15 godz. - ćwiczenia

15 godz. - laboratorium

50 godz. - praca własna - bieżące przygotowanie do zajęć, przygotowanie referatów, przygotowanie programów komputerowych, studiowanie literatury, konsultacje z prowadzącymi zajęcia

35 godz. praca własna - przygotowanie do egzaminu.

5 godz. - zaliczenie laboratorium, ćwiczeń i egzamin


RAZEM: 150 godz.


6 pkt. ECTS

Efekty uczenia się - wiedza:

W1: zna podstawowe pojęcia teorii grafów i sieci, m.in. pojęcia najkrótszej drogi w grafie, minimalnego drzewa rozpinającego, maksymalnego przepływu w sieci, pokrycia wierzchołkowego grafu, skojarzenia w grafie, grafu dwudzielnego (K_W03,s1)

W2: zna podstawowe algorytmy optymalizacyjne: m.in. wyznaczający minimalne drzewo rozpinające, wyznaczający maksymalny przepływ w sieci, znajdujący maksymalne skojarzenie w grafach dwudzielnych, rozwiązujące problem plecakowy, problem komiwojażera, problem chińskiego listonosza (K_W07, s1)

W3: zna przykłady zastosowań omawianych algorytmów (K_W01, K_W02, s1)


Na drugim stopniu kierunku matematyka (s2) efekty powiązane są z: K_W01

Efekty uczenia się - umiejętności:

U1: umie podać przykłady grafów, grafów dwudzielnych, skojarzenia w grafie, pokrycia wierzchołkowego grafu (K_U01, s1)

U2: umie zastosować podstawowe algorytmy optymalizacyjne na prostych przykładach (K_U20, s1)

U3: potrafi samodzielnie wyszukać (w internecie lub literaturze) oraz zastosować na odpowiednich przykładach algorytmy rozwiązujące zadane problemy (K_U26, s1)

U4: potrafi utworzyć prostą aplikację w programie Visual Basic for Applications. (K_U20, s1)


Na drugim stopniu kierunku matematyka (s2) efekty powiązane są z: K_U05, K_U14

Efekty uczenia się - kompetencje społeczne:

K1: przekazuje innym swoją wiedzę i przemyślenia w zrozumiały sposób; właściwie rozumie sformułowania pytań i problemów, poprawnie posługuje się terminologią fachową (K_K02)

K2: rozumie potrzebę ciągłego doskonalenia się (K_K03)


Na drugim stopniu kierunku matematyka (s2) efekty powiązane są z: K_K02, K_K03

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- laboratoryjna
- referatu

Skrócony opis:

Celem przedmiotu jest przedstawienie podstawowych zagadnień związanych z algorytmami optymalizacyjnymi. W trakcie zajęć będzie można zapoznać się z zastosowaniem programowania liniowego oraz grafów do rozwiązywania pewnych problemów ekonomicznych. W trakcie ćwiczeń studenci będą analizować omawiane na wykładzie algorytmy oraz stosować je w rozwiązywaniu przykładowych praktycznych problemów. Na laboratorium będą implementowane podstawowe algorytmy (w VBA).

Przedmiot przeznaczony jest głównie dla studentów matematyki. Mogą w nim również uczestniczyć studenci informatyki.

Pełny opis:

  • Krótkie wprowadzenie do VBA (Visual Basic for Applications)
  • Metody zachłanne i dynamiczne rozwiązywania problemów
    • Optymalny wybór zajęć
    • Problem plecakowy
  • Grafy i ich podstawowe własności
  • Przeszukiwanie grafu wszerz
  • Minimalne drzewa rozpinające - sposoby ich wyznaczania oraz zastosowania
  • Najkrótsze drogi - sposoby ich wyznaczania oraz zastosowania
  • Podstawowe własności sieci
  • Maksymalny przepływ w sieciach
    • Przekroje w sieciach
    • Sieci residualne
    • Algorytm Forda-Fulkersona
  • Zagadnienie transportowe
  • Skojarzenia w grafach dwudzielnych i ich zastosowania
  • Pokrycia wierzchołkowe w grafach
  • Grafy eulerowskie oraz problem chińskiego listonosza
  • Grafy hamiltonowskie oraz problem komiwojażera
  • Algorytmy aproksymacyjne
Literatura:

Literatura podstawowa

  • M. S. Bazaraa, C. M. Shetty, Nonlinear Programming Theory and Algorithms , New York 1979.
  • T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów , WN-T, Warszawa 2001.
  • J. Kosakowska, P. Malicki, Badania operacyjne - programowanie liniowe , skrypt, WMiI 2009.
  • M. M. Sysło, Algorytmy, WSiP, Warszawa 1997.
  • M. M. Sysło, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1995.

Literatura uzupełniająca

  • N. Deo, Teoria grafów i jej zastosowania w technice i informatyce, PWN 1980.
  • R. Faure, J.-P. Boss, A. Le Garff, Badania operacyjne, PWN, Warszawa 1982.
  • S. I. Gass, Programowanie liniowe, PWN, Warszawa 1980.
  • B. Korzan, Elementy teorii grafów i sieci (metody i zastosowania), WN-T, Warszawa 1978.
  • K. Manteuffel, E. Seiffart, Wstęp do algebry liniowej i programowania liniowego, PWN, Warszawa 1975.
Metody i kryteria oceniania:

Zaliczenie wykładu: egzamin pisemny i/lub ustny. Studenta obowiązuje materiał prezentowany w trakcie wykładu; weryfikacja efektów: W1, W2, W3, K1, K2

Ćwiczenia kończą się zaliczeniem na ocenę. Ocena będzie wystawiana na podstawie sprawdzianu i/lub referatu; weryfikacja efektów: U1, U2. U3, K1, K2

Laboratorium kończy się zaliczeniem. Student będzie zobowiązany do przedstawienia aplikacji stworzonej w VBA (Visual Basic for Applications); weryfikacja efektów: U4

Praktyki zawodowe:

Nie dotyczy

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

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 16 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Justyna Kosakowska
Prowadzący grup: Justyna Kosakowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin

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ęć:
Ćwiczenia, 15 godzin, 16 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Justyna Kosakowska
Prowadzący grup: Justyna Kosakowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Justyna Kosakowska
Prowadzący grup: Justyna Kosakowska, Anna Kwiatkowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie
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)