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

Programowanie liniowe i całkowitoliczbowe

Informacje ogólne

Kod przedmiotu: 1000-I2PLC Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Programowanie liniowe i całkowitoliczbowe
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., stacjonarne, 3 rok, przedmioty do wyboru
Inf., II st, stacjonarne, 1 rok, przedmioty do wyboru (podstawowe)
Inf., II st, stacjonarne, 1-2 rok, przedmioty do wyboru (podstawowe)
Inf., II st, stacjonarne, przedmioty do wyboru
Mat., sp. zastosowania, II st., stac., przedmioty do wyboru + uzup. stand. kszt.
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: polski
Całkowity nakład pracy studenta:

30 godz. - wykład

4 godz. - egzamin

30 godz. ćwiczenia:

50 godz. praca własna - bieżące przygotowanie do zajęć, studiowanie literatury,

35 godz. praca własna - przygotowanie do egzaminu.


RAZEM: 149 godz.

6 pkt. ECTS

Efekty uczenia się - wiedza:

Po ukończeniu kursu student:


- zna podstawowe własności zbiorów wypukłych w przestrzeniach euklidesowych,

- potrafi sformułować zagadnienie programowania liniowego,

- zna algorytm sympleks,

- zna całkowitoliczbowy algorytm dualny Gomory'ego,

- potrafi sformułować zagadnienie maksymalnego przepływu

- zna algorytm pozwalający na znalezienie maksymalnego przepływu w grafach skierowanych.


Efekty uczenia się - umiejętności:

Po ukończeniu kursu student potrafi zastosować do rozwiązywania konkretnych problemów następujące algorytmy:


- algorytm sympleks,

- całkowitoliczbowy algorytm dualny Gomory'ego,

- algorytm pozwalający na znalezienie maksymalnego przepływu w grafach skierowanych.

Efekty uczenia się - kompetencje społeczne:

Po ukończeniu kursu student:


- potrafi przekazać 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:

Ćwiczenia praktyczne umożliwiające kształtowanie umiejętności zastosowania przyswojonej wiedzy w praktyce, obejmowały będą rozwiązywanie zadań.

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa

Skrócony opis:

Przedmiot do wyboru przeznaczony jest głównie dla studentów specjalności obliczenia naukowe na kierunku informatyka. Celem wykładu jest zapoznanie się z pojęciami matematycznymi oraz metodami obliczeniowymi używanymi do rozwiązywania problemów programowania liniowego i całkowitoliczbowego. Ćwiczenia mają charakter rachunkowy. Ich zadaniem jest pomoc w zrozumieniu materiału wykładu. Przedmiot prowadzony w języku polskim.

Pełny opis:

  • Zbiory wypukłe.
  • Topologiczne własności zbiorów wypukłych.
  • Twierdzenia o rozdzielaniu.
  • Punkty ekstremalne oraz kierunkowe wektory ekstremalne zbioru wypukłego: 
    • charakteryzacja punktów ekstremalnych,
    • charakteryzacja kierunków ekstremalnych, 
    • twierdzenie o reprezentacji.
  • Algorytm sympleks.
  • Problem znalezienia pierwszego punktu ekstremalnego.
  • Dualna metoda programowania liniowego (twierdzenie o różnicach dopełniających, algorytm dualny sympleks).
  • Leksykograficzna postać dualnej metody sympleks.
  • Całkowitoliczbowy algorytm dualny Gomory'ego.
  • Zagadnienie maksymalnego przepływu (twierdzenie Forda-Fulkersona).
  • Algorytm transportowy.
  • Wielościany całkowite, baza Hilberta oraz twierdzenie Doignona.
  • Odległości rozwiązań optymalnych oraz skończony zbiór testów dla ILP.
Literatura:

Literatura podstawowa:

  • M. S. Bazaraa, C. M. Shetty, Nonlinear Programming Theory and Algorithms, 1979 (istnieje tłumaczenie rosyjskie 1982).
  • A. Schrijver, Theory of linear and integer programming, John Wiley & Sons, Chichester 2000.

Literatura uzupełniająca:

  • N. Deo, J. S. Kowalik, M. M. Sysło, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1995.
  • S. I. Gass, Programowanie liniowe, PWN, Warszawa 1980.
Metody i kryteria oceniania:

Egzamin pisemny z wykładu.

Ćwiczenia kończą się zaliczeniem na postawie obecności oraz prezentacji rozwiązań powierzonych zadań.

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, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
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, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
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.