Lineáris egyenlőség-, egyenlőtlenségrendszerek. Vektor/mátrix jelölés. Logikai következtetések lineáris egyenlőség-, egyenlőtlenségrendszerek esetén. Fourier-Motzkin ellimináció. Lineáris egyenlőtlenségrendszer megoldhatóságának eldöntése. Farkas-lemma. Farkas-lemma második változata. Farkas-lemma logikai nyelven való kifejezése. Lineáris egyenlőség megoldáshalmaza, hipersík. Lineáris egyenlőtlenség megoldáshalmaza, féltér. Homogén lineáris egyenlőségrendszerek megoldáshalmaza, lineáris altér. Vektorok lineáris kombinációja. Lineáris egyenlőségrendszerek megoldáshalmaza, affin altér. Vektorok affin kombinációja. Homogén lineáris egyenlőtlenségrendszer megoldáshalmaza, poliedrikus kűpok. Kúpok, végesen generált kúpok. Vektorok kúp kombinációja. Farkas-lemma geometriai változat. Poliéderek, politópok. Politópok kétféle leírása [csak tétel kimondás]. Vektorok konvex kombinaációja. Weyl-Minkowski-tétel [fogalmak és csak a tétel kimondása].

Legrövidebb út problémája. A súlyozatlan probléma. Szélességi keresés. IP alapprobléma. A súlyozott probléma és IP megfogalmazása. Irányított gráf pont-él illeszkedési métrixa. Totálisan unimoduláris mátrixok. LP relaxáció. Tétel és bizonyítása [irányított gráf pont-él illeszkedési métrixa totálisan unimoduláris]. Párosítások. Mohó "nagy" párosítást kereső algoritmus. Lefogó ponthalmazok. A mohó algoritmus analízise [bizonyítás]. Javító utak. Javító utas párosítási algoritmusok sémája. Javító utak keresése páros gráfban. Tétel [ha nem talál az algoritmus javító utat, akkor alkalmas lefogó ponthalmaz igazolja, hogy aktuális párosításunk optimális]. Súlyozott párosítási probléma, hozzárendelési feladat. Súlyozott párosítási probléma IP megfogalmazása. Gráf pont-él illeszkedési métrixa. Tétel és bizonyítása [páros gráf pont-él illeszkedési métrixa totálisan unimoduláris]. Hozzárendelési probléma. Egerváry számozás. Az optimalitás A magyar módszer. Fa fogalma, feszítőfa fogalma. Legsúlyosabb feszítőfa problémája, legsúlyosabb körmentes élhalmaz problémája. Mohó/Kruskal algoritmus. Mohó algoritmus helyessége. Legsúlyosabb megengedett halmaz problémája. Edmonds tétel [csak kimondás]. Hamilton kör. Mohó útnövelés. Csavarásos hosszú útnövelés. Tétel és bizonyítása [a minden csúcs legalább az összes csúcs felével összekötött, akkor minden nem Hamilton-út csavarásos módon növelhető]. A súlyozott Hamilton-kör probléma, az utazó ügynök probléma. Háromszög-egyenlőtlenség. Körösítés. Közelítő algoritmusok. Naív közelítő algoritmus és analízise. Christifides közelítő algoritmusa és analízise.

Vizsganapjaim keddenként vannak. A vizsgára Neptunon kell jelentkezni. A vizsganap előtti hétfőn lesz pontosan leírva mikor lesznek vizsgaidőpontok (félórás időszakaszok). Ott jelentkeni kell egyre. A vizsga Jitsi-n lesz. Jelenjünk meg a Jitsi-n a vizsga időpontjában. Csak a saját vizsga időpontunkban kapcsoljuk be mikrofonunkat.

Mindenki húz egy kérdést: 1-10-ig lesznek számozott kérdések. Én egy számot rejtve felírok egy papírra. A papírt láthatja, a számot nem. A vizsgázó mond egy számot. Feltárom a saját számom. A két szám összege mod 10 adja a kidolgozandó tételt.

10 perc gondolkozás, majd 20 perc beszélgetés.

A jegy a neptunban lesz.

A vizsgán az alábbi típusú kérdésekből szerepel kettő. Minden számmal jelölt rész egy kérdés. A részkérdések a válaszát irányítják a helyes irányba. Az első kérdés a tematikában szereplő vonal feletti részből, a másik a vonal alól.

1. • Definiálja a lineáris függvény fogalmát.
   • Definiálja a lineáris egyenlőtlenségrendszer fogalmát.
   • Mikor mondjuk, hogy ez a rendszer homogén?
   • Mi a megoldáshalmaza?

   ---

   • Definiálja a Hamilton-kör fogalmát.
   • Milyen módon növelhetünk egy utat?
   • Milyen feltétel mellett tudja garantálni csavarásos növelésekkel Hamilton-utat találjon?
   • Definiálja a közelítő/approximációs algoritmus fogalmát
2. • Mondja ki a Minkowski-Weyl-tételt.
   • Definiálja a tételben szereplő fogalmakat.
   • Egy egyenlőtlenségrendszer megoldáshalmazából nehéz generálni egy elemet. Miért segít ezen a Minkowski-Weyl tétel?
   • Rajzoljon fel egy megoldást halmazt és azonosítsa a tétel jelölése mögötti

   ---

   • Definiálja az utazó ügynök problémát.
   • Definiálja a közelítő/approximációs alggoritmus fogalmát
   • Ismertessen egy közelítő algoritmust az utazó ügynük problémára.
   • Mliyen "garanciát" tud hozzá adni? Miért?
3. • Adott két lineáris egyenlőtlenség. Milyen logikai következményeket írhatunk fel?
   • Adott több lineáris egyenlőtlenség. Milyen logikai következményeket írhatunk fel?
   • Hogyan tud egy lineáris egyenlőtlenségrendszerből következmények egy rendszerét úgy felírni, hogy a megoldhatósága ekvivalens legyen az eredeti redszer megoldhatóságával.

   ---

   • Definiálja az LP feladat szótár alakját.
   • Mikor tartozik lehetséges bázismegoldás egy szótárhoz?
   • Mikor látjuk, hogy optimális bázismegoldásnál vagyunk?
   • Mikor látjuk, hogy a célfüggvény nem korlátos?
4. • Definiálja a kúp fogalmát.
   • Mikor nevezünk egy kúpot poliedrikus kúpnak? Mikor végesen generáltnak?
   • Adjon meg egy kúpot, amely se nem végesen generált, se nem poliedrikus.
   • Létezik-e olyan kúp, amely végesen generált, de nem poliedrikus? Fordítva?

   ---

   • Definiálja az LP feladat szótár alakját.
   • Mikor tartozik lehetséges bázismegoldás egy szótárhoz?
   • Hogyan dönti el, hogy egy milyen pivotok lehetségesek?
   • Hogyan végzi el a pivotot?
5. • Mondja ki a Minkowski-Weyl-tételt.
   • Definiálja a tételben szereplő fogalmakat.
   • Egy egyenlőtlenségrendszer megoldáshalmazából nehéz generálni egy elemet. Miért segít ezen a Minkowski-Weyl tétel?
   • Rajzoljon fel egy megoldást halmazt és azonosítsa a tétel jelölése mögötti

   ---

   • Mikor nevezünk egy mátrixot totálisan unimodulárisnak?
   • Adjon két példát az előadásról TU mátrixra.
   • Az egyikről lássa be ezt a tulajdonságot. (A vizsgázó választ.)
   • Milyen következmányekkel járt ez a tulajdonság?
6. • Mi egy lineáris egyenlőségrendszer megoldáshalmaza?
   • Mit nevezünk affin kombinációnak?
   • Mikor nevezünk egy lineáris egyenlőségrendszert homogénnek?
   • Mi egy homogén lineáris egyenlőségrendszer megoldáshalmaza?

   ---

   • Adott egy LP feladat. Mit értünk duálisa alatt? (A vizsgázó választhat egy normálformát a válaszához.)
   • Vegyünk egy-egy lehetséges megoldását a primál/duál párnak. Milyen kapcsolat van a két választott helyen kiértékelt két célfüggvény-érték között a két feladatban?
   • Mire következtethetünk, ha egyenlőség áll fenn?
7. • Definiálja a kúp fogalmát?
   • Mikor nevezünk egy kúpot poliedrikus kúpnak? Mikor végesen generáltnak?
   • Adjon meg egy kúpot, amely se nem végesen generált, se nem poliedrikus.
   • Létezik-e olyan kúp, amely végesen generált, de nem poliedrikus? Fordítva?

   ---

   • Adott egy LP feladat. Mit értünk duálisa alatt? (A vizsgázó választhat egy normálformát a válaszához.)
   • Vegyünk egy-egy lehetséges megoldását a primál/duál párnak. Mit értünk komplementáris lazasági tulajdonság alatt?
   • Mire következtethetünk, ha ez a tulajdonság áll fenn?
8. • Adott két lineáris egyenlőtlenség. Milyen logikai következményeket írhatunk fel?
   • Adott több lineáris egyenlőtlenség. Milyen logikai következményeket írhatunk fel?
   • Hogyan tud egy lineáris egyenlőtlenségrendszerből következmények egy rendszerét úgy felírni, hogy a megoldhatósága ekvivalens legyen az eredeti redszer megoldhatóságával.

   ---

   • Definiálja a súlyozott párosítási problémát. Gráfelméleti és mátrix alakban is fogalmazza meg a páros gráf esetét. Mikor mondjuk, hogy egy páros gráf kiegyensúlyozott?
   • Mit neveztem Egerváry számozásnak?
   • Egy párosítás és egy Egerváry számozás mikor bizonyítja a párosítás optimalitását.
   • Vázolja a magyar módszert.
9. • Mi egy lineáris egyenlőségrendszer megoldáshalmaza?
   • Mit nevezünk affin kombinációnak?
   • Mikor nevezünk egy lineáris egyenlőségrendszert homogénnek?
   • Mi egy homogén lineáris egyenlőségrendszer megoldáshalmaza?

   ---

   • Definiálja a párosítás és javító út fogalmát.
   • Ismertesse, milyen algoritmus építhatő a javító út fogalmára.
   • Hogyan kereshetünk javítő utat páros gráfokban (adott párosításhoz)?
   • Ha sikertelen a keresési eljárás, akkor mire következtethetünk?
10. • Mikor nevezünk egy halmazt konvexnek?
    • Definiálja a konvex kombináció fogalmát.
    • Definiálja a politópot két különböző módon.

    ---

    • Definiálja a párosítás és lefogó ponthalmaz fogalmát.
    • Milyen (súlyozatlan) optimalizálási feladat fűződik a fogalmakhoz és mi a kapcsolat közöttük?
    • Ismertesse a mohó algoritmust és analízisét.
    • Milyen javítási módszerrel lehet javítani a mohó algoritmuson?