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

Badania operacyjne - programowanie liniowe

Informacje ogólne

Kod przedmiotu: 1000-M1BOP Kod Erasmus / ISCED: (brak danych) / (0541) Matematyka
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.
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
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

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-02-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 15 miejsc więcej informacji
Laboratorium, 15 godzin, 15 miejsc więcej informacji
Wykład, 30 godzin, 15 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 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-02-24
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 16 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 16 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 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 16 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 16 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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.