Csia Klaudia Kitti: Tárgy kibővítése.

2022-02-14T21:01:28Z

Tárgy kibővítése.

Új lap

{{Tantárgy
| név = Gráfok és algoritmusok
| tárgykód = VISZA028
| szak = villany és infó
| kredit = 4
| tanszék = SZIT (CS)
| jelenlét = gyakorlati jelenlét
| labor = nincs
| kiszh = nincs
| nagyzh = 2 db
| hf = nincs
| vizsga = szóbeli
| tad = https://portal.vik.bme.hu/kepzes/targyak/VISZA028/
| tárgyhonlap = https://www.cs.bme.hu/grafalg/
}}

A tantárgy néhány olyan, a gráfelmélethez szorosan kapcsolódó területet igyekszik bemutatni, amelyekre egy bevezető kurzuson rendszerint nem jut idő. Az vizsgált problémák megoldásában az algoritmikus megközelítés kiemelt szerepet kap.

== Követelmények ==

=== Előtanulmányi rend ===
* '''Ajánlott: ''' [[Bevezetés a számításelméletbe II. | Bevezetés a számításelméletbe 2.]] vagy [[A számítástudomány alapjai]].

=== A szorgalmi időszakban ===
* Az '''aláírás''' feltételei:
** A '''gyakorlat'''okon való részvétel.
** '''ZH'''-k teljesítéséhez elérhető 50 pont 40%-át, tehát legalább 20 pontot kell elérni. 5 feladatból áll a ZH, és 90 perces.
* '''Pótlási lehetőségek:'''
** Mindkét '''ZH''' pótolható egyszer a félév közben, egyszer meg pótlási héten (pótpótzárthelyi), viszont a pótpótZH már különeljárási díj fejében írható meg. A pZH-t a ZH-val azonos anyagrészből van, és a ZH-val azonos nehézségű. A pZH-n elért eredmény felülírja az adott számonkérés korábbi eredményét, kivéve egy sikeresen megírt ZH sikertelen javításának esetét: ilyenkor az adott ZH pontszáma a sikeres számonkérés minimális pontszáma, azaz 20 lesz.

=== A vizsgadőszakban ===
* '''Vizsga''': szóbeli előre kiadott tételekből.

=== Félévvégi jegy ===
* A ZH-ról hozott pontok 40%-ban, a vizsga 60%-ban számít bele az évvégi jegybe.
* Ponthatárok:
:{| class="wikitable" style="text-align: center; width: 120px; height: 40px;"
!Pont!!Jegy
|-
|0 - 39|| 1
|-
|40 - 54|| 2
|-
|55 - 69|| 3
|-
|70 - 84|| 4
|-
|85 - 100|| 5
|}

== Segédanyagok ==

* Az előadások videói/diasorai megtalálhatóak [https://login.microsoftonline.com/6a3548ab-7570-4271-91a8-58da00697029/oauth2/authorize?client_id=00000003-0000-0ff1-ce00-000000000000&response_mode=form_post&protectedtoken=true&response_type=code%20id_token&resource=00000003-0000-0ff1-ce00-000000000000&scope=openid&nonce=6ACB710DB13C7BA0BAFA9BE453E2C0A2C909C437E4DA48ED-6CDEA48479C69FCB24250857BA122B51E38F11B11BD9FAF196A6C5D9E3C9BE17&redirect_uri=https%3A%2F%2Fbmeedu.sharepoint.com%2F_forms%2Fdefault.aspx&state=OD0w&claims=%7B%22id_token%22%3A%7B%22xms_cc%22%3A%7B%22values%22%3A%5B%22CP1%22%5D%7D%7D%7D&wsucxt=1&cobrandid=11bd8083-87e0-41b5-bb78-0bc43c8a8e8a&client-request-id=dec220a0-80a2-c000-c257-a79ecde3ddf9 itt] bejelentkezést követően.

=== Előadás (2022) ===
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0215mohotech.pdf 1. Előadás]
* 2. Előadás
* 3. Előadás
* 4. Előadás
* 5. Előadás
* [https://www.cs.bme.hu/%7Efleiner/grafalg/slide0324maxbackchordal.pdf 6. Előadás]
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0331GomoryHu.pdf 7. Előadás]
* 8. Előadás
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0414Edmonds.pdf 9. Előadás]
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0421Leemeles.pdf 10. Előadás]
* 11. Előadás
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0505MInKtgFolyam.pdf 12. Előadás]
* [https://www.cs.bme.hu/~fleiner/grafalg/slide0512Baranyai.pdf 13. Előadás]

=== Gyakorlat (2022) ===
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak1.pdf 1. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak2.pdf 2. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak3.pdf 3. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak4.pdf 4. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak5.pdf 5. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak6.pdf 6. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak7.pdf 7. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak8.pdf 8. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak9.pdf 9. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak10.pdf 10. Gyakorlat]
* [https://www.cs.bme.hu/%7Efleiner/grafalg/gyak11.pdf 11. Gyakorlat]

=== Összefoglaló ===
* [https://www.cs.bme.hu/%7Efleiner/grafalg/tematika.pdf Tételsor címek]

=== Ajánlott könyvek ===
* [https://web.cs.elte.hu/%7Efrank/jegyzet/disopt/dopt13.pdf Frank András - Diszkrét optimalizálás]
* [https://web.cs.elte.hu/%7Efrank/jegyzet/graf/graf.2014.pdf Frank András - Gráfelmélet]
* [https://web.cs.elte.hu/%7Efrank/jegyzet/kombal Frank András - Kombinatorikus algoritmusok II.]

== Zárthelyi ==
* 2021
** [[Media:zhjav.pdf | ZH + megoldása]]

== Vizsga ==
* A vizsga megkezdésekor a vizsgázónak kisorsolunk egy tételt a tárgyhoz tartozó, a vizsgatételsorból. Ennek a kidolgozására (vagyis a szóbeli felelethez egy vázlat vagy bő jegyzet elkészítésére) legalább 45 percet biztosítunk. Negyvenöt perc felkészülési idő letelte után a vizsgáztató abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem jelezte, hogy elkészült. A felelet abból áll, hogy a vizsgázó egyrészt a jegyzeteire támaszkodva részletesen beszámol a húzott tételben található tananyagról, másrészt a vizsgáztató néhány szúrópróbaszerű, a tananyag további részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az fent említett további kérdésekre is kell tudni válaszolni.)
* '''Az elégséges''' megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden lényeges (a tételsorban félkövéren szedett) definíciót és tételt pontosan ki tudjon mondani, illetve tudjon értelmezni. Ugyancsak szükséges, hogy a nem vastagon szedett részek esetében is legfeljebb egy-két hiányossága legyen a vizsgázónak.
* A tételsorban szereplő tételek bizonyításainak ismerete csak a '''közepes''' vagy jobb jegy megszerzéséhez szükséges. Ha valaki az egyszerűbb bizonyításokat is tudja, akkor jók az esélyei a hármas szóbeli feleletre.
* A '''négyes vagy ötös''' felelethez (esetleg kisebb-nagyobb segítséggel) már a nehéz bizonyításokat is el kell tudni mondani (és persze érteni is kell azokat). A vizsgán számítani kell arra is, hogy a zárthelyik által le nem fedett anyagrészből bizonyosan kap kérdést a vizsgázó.

[[Kategória:Valaszthato]]

Gráfok és algoritmusok - Laptörténet

Csia Klaudia Kitti: Tárgy kibővítése.