Rendszeroptimalizálás

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

Rendszeroptimalizálás

Tárgykód	VISZM117
Általános infók
Szak	InfoMsc
Kredit	4 igen kemény kredit
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. Sok.
Labor	nincs
KisZH	0
NagyZH	1
Házi feladat	nincs
Vizsga	szóbeli, cs style
Elérhetőségek
Levlista	sysopt@NO-SPAM.sch.bme.hu
Tantárgyi adatlap
Tárgyhonlap

A tárgyról

• Ajánlott rövidítés: ReOpt, Ropi
• Levlista:
  • sysopt@NO-SPAM.sch.bme.hu -> feliratkozás
• Megj.: (Matek szakon: Kombinatorikus optimalizálás és alkalmazásai, BMETE935008)
• Rendszeroptimalizálás kedvcsináló

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

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

• ZH megoldásokkal, 2002. november 11.
• PótZH, 2002. december 16.
• ZH megoldásokkal, 2003. november 14.
• PótZH, 2003. december 19.
• ZH megoldásokkal, 2004. november 24.
• PótZH, 2004. december 20.
• ZH megoldásokkal, 2005. november 23.
• PótZH, 2005. december 20.
• ZH, 2006. december 9.

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

-- Peti - 2006.12.28.

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