Algorytmy optymalizacji dyskretnej 1000-MS1AlgOpDys

30 godz. – wykład 30 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 i egzamin RAZEM: 150 godz. 6 pkt. ECTS

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 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 W3: zna przykłady zastosowań omawianych algorytmów

U1: umie podać przykłady grafów, grafów dwudzielnych, skojarzenia w grafie, pokrycia wierzchołkowego grafu U2: umie zastosować podstawowe algorytmy optymalizacyjne na prostych przykładach U3: potrafi samodzielnie wyszukać (w internecie lub literaturze) oraz zastosować na odpowiednich przykładach algorytmy rozwiązujące zadane problemy

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ą K2: rozumie potrzebę ciągłego doskonalenia się

- wykład informacyjny (konwencjonalny)

- laboratoryjna
- referatu
- projektu
- ćwiczeniowa

Student powinien mieć podstawową wiedzę z zakresu programowania i algorytmiki.

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

Laboratorium kończy się zaliczeniem na ocenę. Student będzie zobowiązany do przedstawienia aplikacji implementującej omawiane algorytmy; weryfikacja efektów: U1, U2. U3, U4, K1, K2

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.

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

• Strona przedmiotu 1000-MS1AlgOpDys w USOSweb