Rendszeroptimalizálás

A mérnök informatikus MSc Felsőbb matematika tárgyblokk egyik tantárgya.

Rendszeroptimalizálás

Tárgykód	VISZMA02
Régi tárgykód	VISZM117
Általános infók
Szak	InfoMsc
Kredit	4
Ajánlott félév	tavasz
Keresztfélév	vizsgakurzus
Tanszék	CS
Követelmények
Jelenlét	nincs, de ajánlott
Minimális munka	ZH + szóbeli vizsga
Labor	nincs
KisZH	nincs
NagyZH	1 db
Házi feladat	nincs
Vizsga	szóbeli
Elérhetőségek
Levlista	sysopt@NO-SPAM.sch.bme.hu
Tantárgyi adatlap
Tárgyhonlap

Követelmények

A szorgalmi időszakban

• Az aláírás feltételei: Az aláírás megszerzésének feltétele a zárthelyi elfogadható (legalább elégséges szintű) megoldása.
• Pótlási lehetőségek:
  • A zárthelyihez a TVSZ előírásai szerint mind a szorgalmi, mind a pótlási időszakban 1-1 pótlási lehetőség áll rendelkezésre.

A vizsgaidőszakban

• Vizsga: szóbeli.
• Előfeltétele: az aláírás megléte.

Anyagrészek

Elméleti anyagrészek (zh-ra és vizsgára is tudni kell mindet):

• lineáris programozás -- Szeszlér Dávid
• matroidelmélet -- Recski András
• közelítő és ütemezési algoritmusok -- Wiener Gábor

Esettanulmányok (zh-ra nem kell; vizsgán ha az esettanulmány tételt húzod, egyet kell választani közülük, de mellette az elméletbe is belekérdezhetnek):

• megbízható hálózatok tervezése -- Wiener Gábor
• nagybonyolultságú hálózatok huzalozása -- Szeszlér Dávid
• hálózatelméleti alkalmazások -- Recski András
• statikai alkalmazások -- Recski András

Segédanyagok

Előkövetelmény

• BSZ1-ből van Fleiner jegyzet, nagyon jó kis összefoglaló, érdemes átolvasni

• BSz-ből és Algel-ből szükséges fogalmak listája, amire szeretnek rákérdezni:
  • test, gyűrű, csoport, félcsoport
  • ponthalmaz, párosítás, feszítőfa, feszítő, Tutte tétel, Gallai tétel
  • Gráfok színezése, síkba rajzolhatóság, gráf izomorfia
  • magyar módszer, Vízing tétel, Hall feltétel
  • NP teljes, NP-beli, NP nehéz, P-beli, coNP
  • Algoritmusok bonyolultsága. NP-beli problémák mely speciális eseteire van P-beli megoldások

Könyv

• Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás. Érdemes törzsvásárlói kártyát igényelni a Typotextől. Csak egy email címet kérnek, amit utána telespamelnek, de cserébe 20% kedvezményt adnak. Évente 3-4 alkalommal akcióznak, olyankor féláron vehetők meg a könyvek.
• A könyvből néhány anyagrész hiányzik, vagy nincs kifejtve:
  • Rangnyi sok lineárisan független sor és oszlop metszete
  • Algoritmus az MPP_k matroid partíciós problémára
  • Matroid orákulumok kapcsolata
  • Részösszeg probléma
• Matematikus hallgatók kézzel írt órai jegyzetei

Hallgatói jegyzet

• Matroidok jegyzet
• Lineáris programozás jegyzet
• Approx és ütemezés jegyzet
• reopt-jegyzet-kombopt-matekosok.pdf
• Lineáris programozás jegyzet 2015

2012 tavaszi félév jegyzetből készített PDF-ek:

• Lineáris programozás
• Matroidelmélet
• Közelítő és ütemező algoritmusok
• Megbízható hálózatok tervezése
• Nagybonyolultságú hálózatok huzalozása
• Hálózatelméleti alkalmazása
• Statikai alkalmazások

Zárthelyi

• 2015/2016
  • tavaszi félév
    • 2016.04.19 ZH - megoldással
    • 2016.04.28 PZH

• 2014/2015
  • tavaszi félév
    • 2015.04.14 ZH - megoldással
    • 2015.04.28 PZH

• 2006/2007
  • őszi félév
    • 2006.12.09 ZH

• 2005/2006
  • őszi félév
    • 2005.11.23 ZH - megoldással
    • 2005.12.20 PótZH

• 2004/2005
  • őszi félév
    • 2004.11.24 ZH - megoldással
    • 2004.12.20 PótZH

• 2003/2004
  • őszi félév
    • 2003.11.14 ZH - megoldással
    • 2003.12.19 PótZH

• 2002/2003
  • őszi félév
    • 2002.11.11 ZH - megoldással
    • 2002.12.16 PótZH

• Zh és pótZH gyűjtemény 2002-től 2014-ig egy PDF-ben: (a sima ZH-k megoldással szerepelnek)
  • ZH_pakk

ZH túlélőcsomag

Felelősséget nem vállalok érte, de kb. ez az összefoglaló mentett meg a tárgyból. Gondoltam feltöltöm, hátha másnak is segít. :)

• Kézzel írt túlélőpakk a legfontosabb dolgokkal (1. oldal)
• Kézzel írt túlélőpakk a legfontosabb dolgokkal (2. oldal)

A 2. oldalon hibás az uniform matroidokra vonatkozó sor.

Helyesen:

U_n,n, U_n,n-1, U_n,1, U_n,0 grafikus.

U_n,0-t reprezentálja például az a gráf, ahol egy pont van és az összes n él hurokél.

Egy másik túlélőcsomag. A legtöbb algoritmust/fogalmat próbáltam minél "konyhanyelvűbben" írni.

https://docs.google.com/document/d/1lMrz5-IYhD-n_JiRiMLAJgYojdMNLzpcRVQKoU8H-Zc/pub

Tételkidolgozás vizsgára

• Vizsga infók

• 2009 (Vigovszky Dániel)
• 2010
• 2011
• 2012 egyik verzió
• 2012 másik verzió (kicsit más)

• Lineáris programozás: 1, 2, 3, 4, 5, 6, 7
• Matroidok: 8, 9, 10, 11, 12, 13, 14, MMP és MPP
• Közelítő és ütemezési algoritmusok: 15, 16, 17, 18, 19
• Esettanulmányok
  • Megbízható hálózatok tervezése: kidolgozás LaTeX-ben
  • Nagybonyolultságú hálózatok huzalozása: 23, 24, 25
  • Statikai alkalmazások: 29, 30
  • Nincs linkelve, csak ezért ide rakom: Rendszeroptimalizálás, 21. tétel

Rendszeroptimalizálás kedvcsináló

Mérnökinformatikus MSc
1. félév (tavasz)	Adatbiztonság  •  Formális módszerek  •  Rendszeroptimalizálás  •  Analízis  •  Tömegkiszolgálás
2. félév (ősz)	Alkalmazott algebra és matematikai logika  •  Információelmélet  •  Nyelvek és automaták  •  Szoftverarchitektúrák  •  Sztochasztika I.  •  Sztochasztika II.
Egyéb	Kötelezően választható tárgyak  •  Mérnöki menedzsment  •  Befektetések  •  Érvelés, tárgyalás, meggyőzés  •  Információs társadalom joga  •  Minőségmenedzsment  •  Projektmenedzsment  •  Vállalati jog  •  Vezetői számvitel
Szakirányok	Alkalmazott informatika  •  Autonóm irányító rendszerek és robotok  •  Hálózatok és szolgáltatások  •  Hírközlő rendszerek biztonsága  •  Intelligens rendszerek  •  Médiainformatika  •  Rendszerfejlesztés  •  Számításelmélet  •  Szolgáltatásbiztos rendszertervezés