Kezdőlap / Kidolgozott tételek / DEIK Mérnökinformatikus BSC 2017 / 3. tétel

3. Tétel — Kombinációs logikai hálózatok és a mesterséges intelligencia keresési módszerei

Frissítve: 2026-09-09

Ez a tétel két nagyobb témakört fed le: a kombinációs logikai hálózatok felépítését és típusait, valamint a mesterséges intelligencia általános keresési módszereit és a kényszerkielégítési problémák megoldási technikáit.

Témák

I. Témakör: Digitális rendszerek és kombinációs hálózatok

• Kombinációs logikai hálózatok.
• Multiplexerek/Demultiplexerek.
• Kódolók/Dekódolók.
• Komparátorok.
• Paritásvizsgáló áramkörök.
• Aritmetikai-logikai egységek.

II. Témakör: Mesterséges intelligencia – Keresési módszerek és kényszerkielégítési problémák

• Mutassa be az általános problémamegoldó keresési módszereket, majd ezeket hasonlítsa össze a kényszerkielégítési problémákat megoldó módszerekkel!

I. Témakör: Digitális rendszerek és kombinációs hálózatok

1. A kombinációs logikai hálózatok definíciója és alapvető tulajdonságai

A kombinációs logikai hálózatok olyan memóriamentes digitális áramkörök, amelyek kimeneti jeleinek értéke kizárólag a tetszőleges pillanatban érvényes bemeneti jelek kombinációjától függ. Nincsenek bennük tárolóelemek (regiszterek, flip-flopok) vagy visszacsatolások, így múltbeli információt nem őriznek meg.

• Matematikai leírásuk: Boole-algebrai függvényekkel adhatók meg, ahol a bemenetek X = {x₁, x₂, …, x_n} és a kimenetek Y = {y₁, y₂, …, y_m} között meghatározott hozzárendeléssel kapcsolat áll fenn.
• Fizikai megvalósítás: Alapelemeik az elektronikus logikai kapuk (AND, OR, NOT, NAND, NOR, XOR), amelyek tranzisztoros szinten (pl. CMOS technológiával) valósulnak meg.

2. Multiplexerek és Demultiplexerek

Ezek az áramkörök a digitális adatfolyamok irányításáért felelősek összetett rendszerekben:

• Multiplexer (MUX): Adatválasztó áramkör. 2ⁿ darab adatbemenet közül egyet kapcsol át a kimenetre az n darab címbemenet által meghatározott bináris címnek megfelelően.
• Demultiplexer (DEMUX): Adatelosztó áramkör. Egyetlen bemeneti jelet irányít át a 2ⁿ darab kimeneti vonal valamelyikére a címbemenetek értéke alapján.

A Multiplexelés Főbb Típusai

• FDM (Frequency Division Multiplexing – Frekvenciaosztásos multiplexelés):
  • Működés: Analóg jelekhez használják. A teljes elérhető frekvenciasávot kisebb, egymástól elkülönített frekvenciasávokra (csatornákra) osztják, amelyeken a jelek egyidejűleg haladnak.
• TDM (Time Division Multiplexing – Időosztásos multiplexelés):
  • Működés: Digitális jelekhez használják. A közös csatorna teljes sávszélességét időbeli részekre osztják, és a források sorra, váltakozva kapnak időszeletet az adatátvitelre.
  • Altípusok:
    • Szinkron TDM: minden forrás fix időszeletet kap
    • Statisztikai/Aszinkron TDM: csak az aktuálisan adatot küldő források kapnak időt
• WDM (Wavelength Division Multiplexing – Hullámhossz-osztásos multiplexelés):
  • Működés: Optikai szálas hálózatokban alkalmazott technika, ahol a különböző adatfolyamokat eltérő hullámhosszúságú (színű) fénysugarakként küldik át egyetlen optikai kábelen.
• CDM / CDMA (Code Division Multiplexing – Kódosztásos multiplexelés):
  • Működés: Minden egyes jelhez egyedi, matematikai kódot rendelnek. A jelek ugyanazon a frekvencián és egyszerre utaznak, de a vevő a saját kulcsa (kódja) segítségével ki tudja szűrni a számára szóló adatot a zajból.

3. Kódolók és Dekódolók szerepe és típusai

• Dekódoló (Decoder): n bites bemeneti kódot (2ⁿ lehetséges kombináció) alakít át legfeljebb 2ⁿ különálló kimeneti vonal egyikévé, aktiválva azt. Használhatók címdekódolókként memóriákhoz vagy BCD-hétpontos kijelzők meghajtásához.
  • Bináris dekódoló (n-ről 2ⁿ-re): Az n bites bemeneti kód alapján a lehetséges 2ⁿ kimenet közül pontosan azt az egyet kapcsolja aktív szintre, amelynek sorszáma megegyezik a bemeneti bináris értékkel.
  • Címdekódoló (Address Decoder): Digitális rendszerekben (pl. memóriáknál, mikrokontrollereknél) a megfelelő memóriacella vagy periféria kiválasztására szolgáló áramkör a címbusz alapján.
  • BCD-hétsegmenses dekódoló (BCD-to-7-Segment Decoder): BCD kódolt decimális számokat konvertál olyan kimenetekké, amelyek közvetlenül képesek vezérelni egy 7-szegmenses kijelző (LED) szegmenseit.
• Kódoló (Encoder): A dekódoló fordítottja: 2ⁿ bemenet közül a bekapcsolt vonal sorszámának n bites bináris kódját állítja elő. Prioritásos kódolók kezelik azt az esetet is, amikor egyszerre több bemenet aktív.
  • Egyszerű (bináris) kódoló: Az n bites kimeneten azt a bináris számot adja meg, amelyik bemenet éppen aktív (feltételezi, hogy egyszerre csak egy bemenet aktív).
  • Prioritásos kódoló (Priority Encoder): Olyan kódoló, amely kezeli azt a helyzetet, ha egyszerre több bemenet is aktív; ilyenkor az előre meghatározott prioritás alapján (pl. a magasabb sorszámú bemenetet preferálva) végzi el a kódolást.

4. Komparátorok feladata és megvalósítása

A komparátorok két bináris szám (A és B) nagyságát hasonlítják össze. Logikai kimeneteik jelzik, hogy:

• A = B (egyenlőség)
• A > B (nagyobb)
• A < B (kisebb)

Felépítésükben logikai kapuk (XNOR, AND) kombinációiból állnak, és skálázhatók (több chip összekapcsolásával nagyobb bitmázszámú összehasonlítás is végezhető).

5. Paritásvizsgáló áramkörök a hibadetektálásban

Adatátvitel vagy tárolás közben fellépő 1-es bit hibák feltérképezésére használják.

• Működése: A paritásgenerátor/vizsgáló XOR (kizáró vagy) kapuk láncolatából épül fel.
• Páros paritás esetén a kiegészítő bit úgy alakul, hogy az 1-es bitek száma (beleértve a paritásbitet is) páros legyen; páratlan paritás esetén pedig páratlan. Ha az átvitel során egy bit megváltozik, a paritás hibát jelez.

6. Aritmetikai-logikai egységek (ALU) felépítése

Az ALU a CPU számítási magja, amely a vezérlőegység utasításai alapján végzi el a műveleteket.

• Alapkövek: A kombinációs hálózatok építkezése a félösszeadón (half adder) és a teljes összeadón (full adder) alapul, amelyek a bitenkénti összeadás összeg (S) és átvitel jeleit állítják elő.
• Komplex egység: Ezen összeadó/kivonó blokkok, valamint logikai kapusorok (AND, OR, XOR, biteltolók) multiplexeres vezérléssel történő integrálásával jön létre a többfunkciós, több bites ALU, amely egyetlen egységként kezeli a bináris aritmetikai és logikai feladatokat.

II. Témakör: Mesterséges intelligencia – Keresési módszerek és kényszerkielégítési problémák

1. Általános problémamegoldó keresési módszerek

Az MI-ben a problémákat állapottér-reprezentációval írjuk le: kezdőállapot, operátorok (akciók), célteszt és útköltség.

• Vak (uninformed) keresések: Nem használnak heurisztikát, csak a fa struktúráját járják be.
  • Szélességi keresés (BFS – Breadth-First Search): Mindig a legsekélyebb csomópontot fejti ki először. Garantáltan megtalálja a legrövidebb utat, de nagy memóriát és időt igényel.
  • Mélységi keresés (DFS – Depth-First Search): A fa legmélyebb csomópontját fejti ki először. Kisebb memóriát igényel, de nem garantálja az optimális utat, és végtelen ágakban elakadhat.
  • Költségoptimalizáló keresés (UCS – Uniform Cost Search): A legkisebb halmozott útköltségű csomópontot bővíti ki.
• Tájékozott (informed / heurisztikus) keresések: Heurisztikus függvénnyel (h(n)) (a célig hátralévő távolság becslése) gyorsítják a keresést.
  • Mohó legjobb-első keresés: Mindig a h(n) = min csomópontot választja.
  • A* keresés: Kombinálja az eddigi út költségét (g(n)) és a heurisztikát: f(n) = g(n) + h(n). Megengedett heurisztika mellett teljes és optimális.

2. Kényszerkielégítési problémák (CSP – Constraint Satisfaction Problems)

A CSP-k során a feladatot nem egy eljutási útvonalként, hanem egy korlátozásrendszerként definiáljuk.

• Komponensei: Változók halmaza (X₁, X₂, …, X_n).
  • Minden változóhoz tartozik egy lehetséges értékek halmaza, a domén.
  • Kényszerek (Constraints): Szabályok, amelyek megadják, hogy a változók milyen kombinációvektorokat vehetnek fel.

Főbb megoldási technikák:

• Visszalépéses keresés (Backtracking Search): Egy rekurzív DFS alapú algoritmus, amely egyszerre egy változónak ad értéket, és ha kényszerütközést észlel, visszalép (backtrack).
• Kényszerterjesztés (Constraint Propagation): Az élek konzisztenciájának biztosításával folyamatosan szűkíti a változók doménjeit, kizárva a zsákutcákat még a keresés előtt.

Megoldási módszerek és heurisztikák:

• Visszalépéses keresés (Backtracking search): Rekurzív DFS, amely egyszerre egy változónak ad értéket, és amint kényszerütközést (inkonzisztenciát) érzékel, visszalép.
• Változó- és értékválasztási heurisztikák: MRV (Minimum Remaining Values – legkevesebb fennmaradó érték), fokszám-heurisztika, LCV (Least Constraining Value).
• Előretekintő ellenőrzés (Forward Checking) és kényszerterjesztés: Az AC-3 (Arc Consistency) algoritmus révén a meg nem adott változók domainjéből kigyomlálják az érvénytelen értékeket, drasztikusan szűkítve a keresési teret.

3. Összehasonlítás: Általános keresés vs. Kényszerkielégítési problémák (CSP)