Zápis zápočtu / konzultácie:
12.06.2014 14:00 – 15:00
16.06.2014 10:00 –
17.06.2014 10:00 – 15:00
19.06.2014 10:00 – 15:00
20.06.2014 10:00 – 17:00
Koncom augusta z MFF odchádzam: 1.9. nastupujem v TU Eindhoven. Ak odo
mňa niečo potrebujete, skúste to vyriešiť dovtedy. Ak by niekto niečo
potreboval po tomto termíne, snáď sa mi podarí dohodnúť s Martinom Böhmom, aby
sa vám podpísal do indexu za mňa alebo niečo podobné. Ale ak to je možné,
vyriešte to skôr.
Cvičenie sa koná každý utorok o 14:00 v S10
Kontakt:
Orientačné podmienky zápočtu: budú sa písať dve písomky po 25 bodov, a budú zadané dve (programovacie) domáce úlohy tiež po 25 bodov. Ďalej získate jeden bod za účasť na každom cvičení a 2 body za predvedenie príkladu pri tabuli. Hranica zápočtu bude asi 65 bodov.
Elektronická zbierka príkladov: http://kam.mff.cuni.cz/~sbirka/
Cvičenie 1: Opakovanie LA, ADS a kombagry
Cvičenie 2: Formulácie LP problémov
Cvičenie 3: Afinita
Cvičenie 4: Konvexita
Cvičenie 5: Dokončenie konvexity + steny mnohostenov
Cvičenie 6: Steny mnohostenov
Cvičenie 7: Písomka 1
Cvičenie 8: Simplexová metóda I
Cvičenie 9: Simplexová metóda II + dualita.
Cvičenie 10: Dualita + komplementarita
Cvičenie 11: Komplementarita
Cvičenie 12: Komplementarita + totálna unimodularita
Písomka 2 bude na poslednom cvičení 20.05.2014
Zadanie prvej domácej úlohy: ./du1.html
Deadline je do 08.05.2014 (do polnoci)
Zadanie druhej domácej úlohy: ./du2.html
Deadline je do 31.7.2014 (do polnoci)
TSP applet: http://www.math.uwaterloo.ca/tsp/methods/cpapp/index.html
Začína s LP programom
min ∑uv ∈ E cuv xuv za podmienok
∑uv ∈ E xuv pre každý vrchol v.
Môžeme dostať nesúvislý graf ako riešenie. Podmienku typu
∑_uv, u ∈ S, v ∉ S xuv ≥ 2
pre S podmnožinu vrcholov pridáte poklikaním na vrcholy, ktoré majú patriť do S.
Takto sa dá zbaviť izolovaných cyklov, ale riešenie môže ostať neceločíselné.
Na prvej mape sa dá takto dôjsť aj k celočíselnému riešeniu. Je tam k tomu aj
tutorial.
optimalizačný software: ./sw.html
krátky zoznam software, ktorý je vhodné použiť napr. pri riešení domácich úloh.
Príklad zacyklenia simplexovej metódy: PDF, Maple.
C1 C2 C3 C4 C5 C6 C7 P1 C8 C9 C10 C11 C12 DU1 C13 C14 P2 DU2 Suma
Maximum 5 5 5 5 5 10 15 5 5 5 5 5 5 20 100 Z/N
-----------------------------------------------------------------------------------------------------------------------
? 1 1 3 1 1 1 0 0 4 5 5 1 1 1 1 1 10 15 1 1 5 2.5 2 0 0 2 65.5 Z
Alex 1 1 1 1 1 1 1 1 1 1 1 1 10 15 1 1 5 0 0 3 0 47 N
Beda 1 1 1 1 1 1 1 0 4 4 5 1 1 2 1 10 15 3 1 1 0 4 3.5 0 5 67.5 Z
Citron 1 1 1 1 3 1 1 1 5 5 5 3 3 1 1 10 15 1 1 5 5 4 0 0 74 Z
FIFACZ 1 1 1 1 1 1 0 4 4 1 1 1 1 1 10 15 1 1 5 0 0 0 0 5 12 68 Z
Folwar 3 3 3 3 1 3 1 1 1 9 15 5 20 68 Z
Freeman 1 1 N
FS 3 5 2 3 3 1 1 5 5 4 3 5 3 1 10 15 69 Z
Helgrind 1 3 1 1 1 1 1 1 4 4 0 1 1 2 3 3 10 15 1 1 5 4.5 0 5 0 69.5 Z
Houkl 1 1 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 10 15 2 1 5 2 5 5 0 69 Z
istien 1 3 1 1 5 1 5 4 5 3 1 10 15 1 1 5 2.5 5 0 0 69.5 Z
JB 1 1 1 1 1 1 5 3 4 4 5 1 1 1 3 10 15 1 5 1 65 Z
jon 3 5 1 1 3 1 1 0 5 4 5 1 3 1 3 1 10 15 3 1 5 5 3.5 0 0 80.5 Z
Kiwi 1 1 1 1 1 3 4 1 1 1 1 9 14 1 1 5 0 0 3 0 49 N
kuba 1 1 N
Kung Fu 1 1 1 1 1 1 1 5 4 1 1 1 1 1 10 15 1 1 1.5 0 3 0 0 5 10 67.5 Z
Limetka 1 1 1 1 1 1 1 5 4 5 1 1 1 1 10 15 1 1 5 5 3.5 5 0 70.5 Z
Martin 3 3 2 1 1 1 1 1 1 5 3 5 3 1 1 3 9 15 1 5 0 5 5 0 75 Z
mop 3 1 1 3 1 1 5 5 5 5 5 3 1 1 1 1 10 15 67 Z
Mzetko 1 1 1 1 1 1 6 N
NaplavaJ 1 3 1 1 1 1 1 1 2 4 5 5 3 3 1 1 10 15 1 1 5 0 0 3 0 69 Z
P47QAX 1 1 N
Peťan 1 1 1 1 2 1 1 1 3 5 0 1 1 1 1 1 10 15 1 1 5 2.5 4 5 0 65.5 Z
Pomelo 3 3 1 1 3 1 1 0 2 5 5 5 3 2 1 1 1 10 15 1 1 5 5 3.5 0 0 78.5 Z
Pomeranč 1 1 1 1 1 1 1 0 1 4 2 5 1 1 1 1 1 7 13 1 1 5 2.5 0 0 0 53.5 N
Poolen 3 1 1 1 1 1 0 3 4 0 1 1 1 1 1 10 15 1 5 20 71 Z
p.rosomak 1 1 1 2 1 1 10 15 1 1 5 0 2.5 5 0 46.5 N
Semai 3 1 1 1 3 1 1 1 5 5 5 1 1 1 1 1 10 15 1 1 5 3.5 4 5 5 81.5 Z
TRAN 1 1 1 1 1 1 ? 2 1 3 0 1 13 N
Hranica zápočtu: 65 bodov