Számítástudomány alapjai 2. - Vizsgatételek

(Milton Friedman Egyetem - Horák László jegyzetei alapján)

Ez a dokumentum a "Számítástudomány alapjai 2" tantárgy legfontosabb témaköreit és vizsgatételeit tartalmazza strukturált formában.

1. Gráfelméleti algoritmusok

1.1. Gráfok ábrázolása és alapfogalmak

A gráfok számítógépes tárolására többféle modell létezik, a választás a gráf sűrűségétől (élek számától) függ.

• Szomszédossági (Adjacencia) mátrix: n × n-es mátrix, ahol A[i,j] = 1, ha van él i-ből j-be. Előnye a gyors él-lekérdezés, hátránya a nagy memóriaigény ritka gráfoknál.
• Illeszkedési mátrix: n (csúcsok) × m (élek) méretű mátrix. A[i,j] = 1, ha az i-edik csúcs illeszkedik a j-edik élre.
• Szomszédossági lista: Minden csúcsra egy láncolt listát tartunk fenn a szomszédos csúcsokról. Memóriahatékony ritka gráfok esetén.

1.2. Gráfok bejárása (BFS és DFS)

A gráfok szisztematikus feltérképezésére szolgáló eljárások.

• Szélességi bejárás (BFS - Breadth-First Search):
  • Lépései: Egy kezdőcsúcsból indulva először az összes közvetlen szomszédot látogatjuk meg, majd azok szomszédait.
  • Adatszerkezete: Sor (Queue - FIFO).
  • Alkalmazása: Legrövidebb út keresése súlyozatlan gráfokban.
• Mélységi bejárás (DFS - Depth-First Search):
  • Lépései: Egy csúcsból elindulva a lehető legmélyebbre megyünk a gráfban egy szomszédon keresztül, majd ha elakadunk, visszalépünk (backtracking) és új irányt választunk.
  • Adatszerkezete: Verem (Stack - LIFO), gyakran rekurzív módon implementálva.

1.3. Legrövidebb utak keresése (Dijkstra algoritmus)

Súlyozott gráfokban (ahol az éleknek költsége/súlya van) keresi meg egy kezdőcsúcsból az összes többi csúcsba vezető legolcsóbb utat.

• Feltétel: Csak nemnegatív élsúlyok esetén működik megbízhatóan.
• Algoritmus lépései:
  1. Távolságok inicializálása: kezdőcsúcs = 0, többi = ∞.
  2. Választunk egy még nem fixált csúcsot, amelynek a távolsága minimális.
  3. "Relaxáció": Megvizsgáljuk a választott csúcs szomszédait, és ha rajta keresztül rövidebb út vezet hozzájuk, frissítjük a távolságukat.
  4. A csúcsot fixáltnak (késznek) jelöljük.
  5. Ismételjük, amíg minden elérhető csúcsot fixáltunk.

1.4. Minimális feszítőfák (Kruskal algoritmus)

Összefüggő, súlyozott gráfban olyan összefüggő, körmentes részgráfot (fát) keresünk, amely minden csúcsot tartalmaz és az éleinek összsúlya minimális.

• Algoritmus lépései:
  1. Sorba rendezzük az összes élet súly szerint növekvő sorrendbe.
  2. Egyenként vesszük az éleket a legkisebbtől kezdve.
  3. Ha az adott él behúzása nem hoz létre kört a már meglévő élekkel, akkor hozzáadjuk a feszítőfához.
  4. Addig folytatjuk, amíg n-1 élet ki nem választottunk (ahol n a csúcsok száma).

1.5. Huffman-kódolás (Bináris fák alkalmazása)

Optimális prefix kódolás adattömörítéshez.

• Prefix tulajdonság: Egyik betű kódja sem kezdőszelete (prefixe) egy másiknak, így az üzenet egyértelműen dekódolható.
• Konstrukció lépései:
  1. Betűk gyakoriságának meghatározása.
  2. Levelek létrehozása a betűkhöz, gyakoriság szerint rendezve.
  3. A két legkisebb gyakoriságú csúcsot összevonjuk egy új szülőcsúccsá, melynek értéke a kettő összege.
  4. Ismétlés, amíg egyetlen gyökerű fát nem kapunk.
  5. Élek címkézése (bal=0, jobb=1), a betű kódja a gyökértől a levélig vezető út.

2. Hálózati folyamok

2.1. Szuperforrás és szupernyelő

Speciális csúcsok az irányított gráfokban, amelyek fontos szerepet játszanak a hálózati modellezésben.

• Szuperforrás (s): Olyan csúcs, amelyből minden más csúcsba vezet él, de belé sehonnan nem érkezik él.
• Szupernyelő (n): Olyan csúcs, amelybe minden más csúcsból vezet él, de belőle sehonnan nem indul ki él.
• Keresési algoritmus: Az adjacencia mátrix vizsgálatával lineáris időben (O(n)) eldönthető a létezésük, ami sokkal hatékonyabb a naiv O(n²) megoldásnál.

2.2. Hálózati folyam definíciója

• Hálózat: Irányított gráf, ahol minden élnek van egy nemnegatív kapacitása (c(u,v)).
• Folyam (f(u,v)): Az éleken áramló mennyiség, amelyre teljesül:
  1. Kapacitáskorlát: 0 ≤ f(u,v) ≤ c(u,v).
  2. Folyamkonzerválás: A forráson és nyelőn kívül minden csúcsba amennyi befolyik, annyinak ki is kell folynia.

2.3. Ford-Fulkerson algoritmus és Max-Flow Min-Cut

A maximális hálózati folyam meghatározására szolgáló eljárás.

• Javítóút: Olyan út a forrástól a nyelőig a maradék gráfban (residual graph), amely mentén még növelhető a folyam.
• Algoritmus: Addig keresünk javítóutakat (pl. BFS-sel - Edmonds-Karp változat), amíg létezik ilyen. Minden út megtalálásakor annyival növeljük a forrásból kilépő folyamot, amennyit az út legszűkebb keresztmetszete megenged.
• Max-Flow Min-Cut tétel: Egy hálózatban a maximális folyam értéke megegyezik a forrást a nyelőtől elválasztó minimális vágás (kapacitásösszeg) értékével.

3. Formális nyelvek és automaták

3.1. Alapfogalmak

• Alfabéta (Σ): Véges szimbólumkészlet (pl. {0, 1} vagy {a, b, c}).
• Szó/Mondat: Szimbólumok véges sorozata. ε jelöli az üres szót.
• Nyelv (L): Σ* (összes lehetséges szó) egy részhalmaza.

3.2. Chomsky-féle nyelvhierarchia

A nyelveket a generáló nyelvtanuk (grammatikájuk) szabályainak bonyolultsága alapján osztályozzuk:

1. 3-as típus (Reguláris nyelvek): A → aB vagy A → a alakú szabályok. Felismerőjük a véges automata.
2. 2-as típus (Környezetfüggetlen nyelvek - CF): A → α alakú szabályok (baloldalon csak egy nemterminális). Felismerőjük a veremautomata.
3. 1-es típus (Környezetfüggő nyelvek): α A γ → α β γ alakú szabályok (a helyettesítés környezettől függ). Felismerőjük a lineárisan korlátos automata.
4. 0-ás típus (Mondatszerkezetű nyelvek): Nincs megkötés. Felismerőjük a Turing-gép.

3.3. Véges automaták (DFA és NFA)

A reguláris nyelvek felismerésére szolgáló absztrakt gépek.

• DFA (Determinisztikus Véges Automata): Minden állapot-karakter párhoz pontosan egy átmenet tartozik.
• NFA (Nemdeterminisztikus Véges Automata): Egy állapotból egy karakter hatására több állapotba is juthat, vagy ε-átmenettel karakter olvasása nélkül is válthat állapotot.
• Elfogadás: Az automata akkor fogad el egy szót, ha a végigolvasása után elfogadó állapotba (F) kerül.

3.4. Automata determinisztikussá tétele és minimalizálása

• Determinisztikussá tétel (NFA → DFA): Részhalmaz-konstrukcióval (subset construction) minden NFA-hoz készíthető vele ekvivalens DFA.
• Minimalizálás: Olyan DFA létrehozása, amely a legkevesebb állapottal rendelkezik, de ugyanazt a nyelvet ismeri fel. Az összeférhetetlen állapotok összevonásával történik.

4. Bonyolultságelmélet

4.1. Algoritmusok hatékonysága és futásideje

Az algoritmusok teljesítményét a bemeneti adatok méretének (n) függvényében mérjük.

• Lineáris idő (O(n)): Pl. szuperforrás keresése a 2. algoritmussal.
• Négyzetes idő (O(n²)): Pl. szuperforrás keresése az összes él vizsgálatával, vagy buborékrendezés legrosszabb esetben.
• Logaritmikus idő (O(log n)): Pl. bináris keresés rendezett tömbben.

4.2. Eldönthetőség

• Algoritmusilag eldönthető: Ha létezik algoritmus, amely véges lépésben választ ad (igen/nem). (Pl. tartalmazás kérdése 1-3 típusú nyelveknél).
• Algoritmusilag eldönthetetlen: Nincs olyan algoritmus, amely minden esetben véges idő alatt megállna a válasszal. (Pl. a Megállási probléma vagy a tartalmazás kérdése 0-ás típusú nyelveknél).

4.3. P és NP osztályok

• P osztály: Azok a problémák, amelyek determinisztikus Turing-géppel polinomiális időben (O(nᵏ)) megoldhatóak. Ezek a "hatékonyan megoldható" feladatok.
• NP osztály: Azok a problémák, amelyek megoldása nemdeterminisztikus Turing-géppel polinomiális időben megtalálható, vagy (determinisztikusan) egy javasolt megoldás polinomiális időben ellenőrizhető.
• P vs NP probléma: A számítástudomány egyik legnagyobb nyitott kérdése: vajon minden NP-beli probléma megoldható-e polinomiális időben?

Készítette: Gemini CLI autonóm ágens a megadott oktatási anyagok alapján.