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

Badania operacyjne - programowanie liniowe

Informacje ogólne

Kod przedmiotu: 1000-M1BOP
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: Badania operacyjne - programowanie liniowe
Jednostka: Wydział Matematyki i Informatyki
Grupy: Mat, spec. MEF, I st, stacjonarne, 2 rok, przedmioty specjalizacyjne
Mat, spec. MEF, I st, stacjonarne, 3 rok, przedmioty specjalizacyjne
Mat. ogólna, I st., stacjonarne, 2 rok, przedmioty do wyboru
Mat. ogólna, I st., stacjonarne, 3 rok, przedmioty do wyboru (matematyczne)
Mat., sp. nauczycielskie, II st., stacjonarne, przedmioty do wyboru + uzup. stand. kszt.
Mat., sp. zastosowania, II st., stac., przedmioty do wyboru + uzup. stand. kszt.
Punkty ECTS i inne: (brak) 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.

zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30 godz. – wykład

15 godz. - ćwiczenia

15 godz. - laboratorium

20 godz. - konsultacje z prowadzącymi zajęcia

30 godz. - praca własna - bieżące przygotowanie do zajęć, przygotowanie referatów, przygotowanie programów komputerowych, studiowanie literatury,

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:


  • 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

  • zna następujące algorytmy: przeszukiwania grafu wszerz, wyznaczający minimalne drzewo rozpinające, wyznaczający maksymalny przepływ w sieci, znajdujący maksymalne skojarzenie w grafach dwudzielnych, algorytmy zachłanne rozwiązujące problem plecakowy

  • zna przykłady zastosowań omawianych algorytmów


Efekty uczenia się - umiejętności:


  • umie podać przykłady grafów, grafów dwudzielnych, skojarzenia w grafie, pokrycia wierzchołkowego grafu, ,

  • umie zastosować następujące algorytmy na prostych przykładach: przeszukiwania grafu wszerz, wyznaczający minimalne drzewo rozpinające, wyznaczający maksymalny przepływ w sieci, znajdujący maksymalne skojarzenie w grafach dwudzielnych, algorytmy zachłanne rozwiązujące problem plecakowy

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

  • potrafi utworzyć prostą aplikację w programie Visual Basic for Applications.


Efekty uczenia się - kompetencje społeczne:

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ą

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- referatu

Skrócony opis:

Celem wykładu jest przedstawienie podstawowych zagadnień związanych z badaniami operacyjnymi. W trakcie zajęć będzie można zapoznać się z zastosowaniem programowania liniowego oraz grafów do rozwiązywania pewnych problemów ekonomicznych. Wykład 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.

Ćwiczenia kończą się zaliczeniem na ocenę. Ocena będzie wystawiana na podstawie sprawdzianu i/lub referatu.

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

Praktyki zawodowe:

nie dotyczy

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
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)