Badania operacyjne


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia licencjackie
Semestr:5
Wymiar zajęć:20h wykładu + 16h ćwiczeń
Punkty ECTS:4

Program

    Badania operacyjne to nauka zajmująca się teorią podejmowania decyzji. Zadaniem badań operacyjnych jest znalezienie odpowiedniej metody rozwiązywania problemów decyzyjnych, prowadzące do optymalizacji i maksymalizacji zysków. Jest to dziedzina, która pomaga podjąć decyzję najlepszą z możliwych. Obejmuje między innymi programowanie matematyczne, zagadnienia transportowe oraz sieciowe. Celem wykładu jest zapoznanie słuchacza z częścią metod badań operacyjnych oraz przedstawienie zastosowań metod operacyjnych w informatyce.
  • Złożoność obliczeniowa problemów decyzyjnych (klasy złożoności, klasy P i NP, problemy NP-zupełne).
  • Metody optymalizacyjne:
    - programowanie liniowe (metoda graficzna, sympleks, dualna)
    - programowanie całkowitoliczbowe,
    - programowanie dynamiczne,
    - zagadnienia transportowe.
  • Deterministyczne problemy szeregowania zadań
    - procesory równoległe oraz dedykowane (open-, job-, flow-shop)
    - minimalizacja różnych kryteriów (długość uszeregowania, średni czas przepływu, maksymalne opóźnienie, itd.)
    - zadania o różnych parametrach
    - modele szeregowania z uwzględnieniem dodatkowych zasobów.
  • Zastosowania problemów szeregowania zadań.

Sposób zaliczenia

Ćwiczenia: zaliczenie dwóch kolokwiów + praca na ćwiczeniach.
Egzamin pisemny.

Literatura

  • J. Błażewicz, W. Cellary, R. Słowiński, J. Węglarz, Badania operacyjne dla informatyków, WNT 1983.
  • P. Brucker, Scheduling algorithms, Springer 2006.
  • J. Y-T.Leung, Handbook of scheduling: algorithms, models, and performance analysis , Chapman
  • M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej, PWN 1995.