Metody optymalizacji 0800-MOPT

1. Skojarzenia w grafach i ich zastosowania
a. Definicje
b. Twierdzenie Halla i kojarzenie małżeństw
c. Typy skojarzeń
1. Algorytm Christofidesa
2. Algorytm węgierski
3. Algorytmy sieciowe (np. CPM, PERT), szeregowanie zadań, ścieżki krytyczne
4. Algorytmy optymalizacji liniowej z ograniczeniami
5. Zadanie transportowe z kosztami
6. Algorytmy optymalizacji kwadratowej z ograniczeniami
7. Kolorowanie grafów
8. Gradientowe algorytmy dla problemów optymalizacji bez ograniczeń
9. Algorytmy ewolucyjne w problemach optymalizacji
10. Ukryte łańcuchy Markowa

Całkowity nakład pracy studenta

- godziny realizowane z udziałem nauczycieli: 60h (30h wykład + 30h ćwiczenia), - czas poświęcony na pracę indywidualną potrzebny do pomyślnego zaliczenia przedmiotu: 60h - czasy wymagany do przygotowania się i uczestnictwa w procesie oceniania: 30 h - czas wymagany do odbycia obowiązkowych praktyk: 0 h

Efekty uczenia się - wiedza

W1 - ma wiedzę obejmującą: rozwiązywanie układów równań liniowych, metody interpolacji, minimalizacje przy użyciu gradientów, elementy rachunku prawdopodobieństwa (użytecznych przy ukrytych łańcuchach Markowa) (K_W01) W2 - posiada wiedzę dotyczącą optymalizacji przy użyciu grafów, elementów programowania matematycznego, metod gradientowych oraz algorytmów ewolucyjnych (K_W02) W3 -ma podstawową wiedzę o cyklach życia różnego typu systemów informatycznych (K_W06)

Efekty uczenia się - umiejętności

U1 - potrafi zaprojektować oraz stworzyć struktury danych konieczne do realizacji projektu (K_U06)

Efekty uczenia się - kompetencje społeczne

K1 - działa i myśli w sposób kreatywny rozwiązując problemy optymalizacyjne (K_K06)

Metody dydaktyczne podające

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące

- laboratoryjna
- ćwiczeniowa

Wymagania wstępne

Algorytmy i struktury danych I

Koordynatorzy przedmiotu

Rafał Adamczak

Kryteria oceniania

Ocena przedmiotu odbywa się na podstawie egzaminu ustnego.
Kryteria oceniania:
Wykład: egzamin pisemny

60% punktów ocena 3
75% punktów ocena 4
90% i więcej ocena 5

Podczas ćwiczeń implementowane są wybrane algorytmy optymalizacyjne prezentowane na wykładzie. Zaliczenie odbywa się na podstawie oceny poprawności zaimplementowanych algorytmów.
Egzamin oraz ćwiczenia sprawdzają osiągnięcie efektów: W1, W2, W3

Literatura

1. M.M. Sysło, Algorytmy optymalizacji dyskretnej, PWN, 1993
2. D. Rogulska. Programowanie liniowe. Algorytmy i zadania. Wydawnictwo Uniwersytetu Łódźkiego 1991
3. K.I. Majid, Optymalne projektowanie konstrukcji, PWN, W-wa1981
4. David E. Kolberg, Algorytmy genetyczne i ich zastosowania, 2003 WNT
5. D. Rutkowska, Inteligentne systemy obliczeniowe.
6. M. Trocki, B. Grucz, K. Ogonek, Zarządzanie projektami, W-wa 2002
7. A. Stachurski, A. Wierzbicki, Podstawy optymalizacji, Oficyna Wydawnicza PW, Warszawa 1999

Więcej informacji

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

Strona przedmiotu 0800-MOPT w USOSweb