Miskolci Egyetem - Programtervező informatikus BSc


Tartalomjegyzék

Nyári szakmai gyakorlat

Minden információ itt található: www.mediamulti.net/hu/karrier/szakmai-gyakorlat/


LaTeX -> TeX generátor


A diákigazolvány igénylésének folyamata

A felsőoktatásban nem egyszerű hozzájutni az új diákigazolványhoz, melyet 2012. szeptemberében vezettek be hivatalosan, gyakorlatilag - bár a diákok elvégezték a nem kevés feladatikat, mégis - fél éves késéssel érkeztek meg az új azonosítók.

Tehát a sikeres igénylés lépései:

  • bruttó 1.400,- forint átutalása a gyűjtőszámlára (közlemény rovatban kötelező feltüntetni a neptun-kódot NK-ABC123 formátumban)
  • bármelyik okmányirodában az aláírás és a fénykép rögzítése
  • az okmányirodától kapott dokumentumon található NEK-azonosítóval a Neptun/Ügyintézés/Diákigazolvány igénylés menüpontban új igénylés leadása (a NEK-azonosítót kötőjel nélkül szükséges feltüntetni az űrlap első sorában)
  • a Neptun/Pénzügyek/Befizetés/Befizetendő kiírt tételek sorában megjelenő új tétel kiegyenlítése a Neptun-számláról. Amennyiben az 1.400,- forint levonódik a számláról, az igénylés sikeresen végbement.

Az új diákigazolványt hivatalosan 45 napon belül postázzák a megadott címre. A 16-os szobában iskolalátogatási igazolás igényelhető.


Neptun

Az alábbi rövid script segítségével a Mozilla Firefox böngésző megjegyzi a Neptun-jelszót. Mindössze három lépést kell véghezvinni:

  1. A Greasemonkey kiegészítő hozzáadása a böngészőhöz.
  2. A telepítés után megjelenő ikonra kattintva új parancsfájl készítése, ott bármilyen név megadása, például: Neptun-jelszó
  3. OK, majd a következő kód hozzáadása a NEPTUNKÓD és JELSZÓ adatok átírásával természetesen:
// ==UserScript==
// @name Neptun Jelszóőrző
// @ver 1.0
// @grant none
// @include https://neptun32.uni-miskolc.hu/hallgato/Login.aspx
// ==/UserScript==
user.value="NEPTUNKÓD";
pwd.value="JELSZÓ";

Amennyiben a Greasemonkey engedélyezve van, úgy már működik is a script.


Fájl feltöltése (multiupload változat)

<h3>Fájl feltöltése</h3>
<?php
// install: mkdir tmp + chmod 777 tmp
	if(isset($_FILES['uploaded']))
	{
		foreach($_FILES['uploaded']['name'] as $n => $name) 
		{
			if(!empty($name))
			{
				$target_path = "tmp/" . $name;
				if(move_uploaded_file($_FILES['uploaded']['tmp_name'][$n], $target_path)) 
				{
					echo 'OK: '.$_FILES['uploaded']['name'][$n].' ('.($_FILES['uploaded']['size'][$n]/1024).'kB, '.$_FILES['uploaded']['type'][$n].')
'; } } } } ?> <form enctype="multipart/form-data" action="index.php" method="post" target="_self"> <input type="file" name="uploaded[]" multiple /> <input type="submit" value="OK" /> </form>

PHP

Ékezetes karakterek probléma

Ha nem jól jelennek meg az ékezetes karakterek a php fájlban, amellett, hogy utf-8-ban mentitek le, még legfelülre ezt kell beszúrni:

<?php header('Content-Type: text/html; charset=UTF-8'); ?>

Formból megkapott adatok mentése fájlba:

// mentés file-ba
// átvett tartalom eltárolása egy változóba (GET átadásnál át kell írni!)
$data='Név: '.$_POST['name'] . ', neptun: '.$_POST['neptun'] . "\n";
// melyik fájlba akarom menteni? a fájl kiterjesztése bármi lehet
$file='regisztraciosurlap.txt';
// megnyitom az előbb megadott fájlt tartalom hozzáfűzésre
$handle=fopen($file,'a');
// megadom, hogy a megnyitott fájlba a data változót szeretném írni
fwrite($handle,$data);
// bezárom a fájlt
fclose($handle);

Selenium

A Selenium Firefox plugin telepítése után elindítjuk az alkalmazást, majd a felső sáv jobb szélén található piros/rózsaszín gomb lenyomása után elkezdi rögzíteni a böngésző eseményeit. Töltsük ki az űrlapot, majd ha készek vagyunk, nyomjunk ismét a rögzítés gombra, amely így befejezi a cselekvés-figyelést. Ezzel együtt lényegében automatikusan létre is jött egy új Selenium fájl, melyet a zöld nyílak egyikével le is játszhatunk, illetve Fájl->Mentés másként lehetőséggel le is menthetünk html fájlként. Ezt a html fájlt kell az SVN-re is feltölteni.


SVN

Külön SVN alkalmazással lehet feltölteni a saját SVN tárhelyre, amely így érhető el: https://jerry.iit.uni-miskolc.hu/svntzs/webtech/2014/LDAPFELHASZNALONEV/. Hogy vindózon mely szoftver jó rá, linuxosként nem tudom megválaszolni.


HTML

A HTML (HyperText Markup Language = hiperszöveges jelölőnyelv) egy leíró nyelv, melyet weboldalak készítéséhez fejlesztettek ki, és mára már internetes szabvánnyá vált a W3C (World Wide Web Consortium) támogatásával. Jelenleg az ötödik generációnál tart (HTML 5).

A HTML általában szöveges állományokban található meg olyan számítógépeken, melyek az internethez kapcsolódnak. A dokumentum tetszőleges szövegszerkesztővel elkészíthető. Ezek az állományok tartalmazzák azokat a szimbólumokat, amelyek a megjelenítő programnak leírják, hogyan is kell megjeleníteni, illetve feldolgozni az adott állomány tartalmát. Megjelenítő program lehet egy webböngésző, aural böngésző (olyan, amelyik a felhasználónak felolvassa a megjelenítendő szöveget), braille olvasó, amely konvertálja a szöveget braille "formátumba", levelező program (mint például: Mozilla Thunderbird, Microsoft Outlook, Eudora stb.), valamint egyéb eszközök, például mobiltelefon.

Annak érdekében, hogy részleteiben is megismerkedhessen e nyelv működésével, kérem, az alábbi leckéket is tekintse meg:

Egy honlap alapvető felépítése:

<html>
<head>
A látogató számára alapvetően nem jelentős információkat tartalmazza, például a meta tagokat.
</head>
<body>
A felhasználó által látott, használt felület, terület.
</body>
</html>
<a>: hivatkozás
  • href: a hivatkozás célja, például href="http://www.domain.tld"
  • rel: referencia, azaz milyen viszonyban áll a hivatkozott oldal a jelenlegivel, például rel="támogatás"
  • style: hivatkozás stílusának meghatározása, például style="text-decoration:underline"
  • target: meghatározza, hogy az adott link hol nyíljon meg, például target="_blank"
    • _blank: új lapon
    • _self: ugyanabban a keretben (frame-ben)
    • _parent: az adott frame-et tartalmazó frame-ben
    • _top: a legmagasabb, elsődleges frame-ben

Szöveg formázása

<h1,...,h6> (header): fejléc, cím kiemelése, például:

<h1>szöveg<h1>

<h2>szöveg<h2>

<h3>szöveg<h3>

<h4>szöveg<h4>

<h5>szöveg<h5>
<h6>szöveg<h6>
<b/strong> (bold/strong): adott szövegrész kiemelése, "vastagítása", például:

<b>szöveg<b>

<strong>szöveg<strong>

<i> (italic): adott szövegrész dőlté váltása; például:

<i>szöveg<i>

<u> (underline): adott szövegrész aláhúzása; például:

<u>szöveg<u>

<small> (small): adott szövegrész megjelenítése kisebb betűmérettel, például:

© 2014 Minden jog fenntartva!

<p> (paragraph): összetartozó szövegrészek elválasztása, például:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Táblázatok elkészítése

<table>
    <tr>
        <td>tartalom</td>
    </tr>
</table>
<td> elem tartalmának igazítása
align="left" align="right" valign="top" valign="bottom" align="center"
szöveg/kép szöveg/kép szöveg/kép szöveg/kép szöveg/kép
Miskolci Egyetem térképe

Programok

Online ingyenes tárhely

Könyv

Ösztöndíj

Rendezvény/Verseny

Hasznos

Linkgyűjtemény


Objektum orientált programozás - Java

Tételek

  1. OOP alapelvei
  2. Java jellemzői, java platform, java program felépítése, fordítás, futtatás menete. Csomagok. Import.
  3. Osztálydefiníció, adattag, metódustag definíció. Egységbezárás alapelvének implementálása. Információ rejtés alapelvének implementálása.
  4. Hivatkozás típusú (referencia) változók fogalma, jellemzői. Elemi tipusú és referencia változók összehasonlítása.
  5. Műveletek referencia változókkal. Referencia statikus és dinamikus típusa. Referencia konverziók.
  6. Példányosítás, Szintaktikája, menete. Példány élettartama. Szemétgyűjtő. A final módosító.
  7. Konstruktorok fogalma, definíciója, használatának szabályai.
  8. A this fogalma, szerepe. Osztályszintű adattagok, metódusok.
  9. Öröklődés fogalma, használatának előnyei, hátrányai, jellemzői. Öröklődés szintaktikája. Tagok öröklődése.
  10. Függvény túlterhelés, metódus felüldefiniálás, operátor túlterhelés.
  11. Absztrakt metódusok, osztályok. Interface fogalma szerepe. Interface definíció, implementálás.
  12. Speciális szintaktikával definiálható osztályok: tömb, enum. Generikus osztályok.
  13. Kivételkezelés
  14. A lang csomag osztályai: Object, Comparable, System, String, StringBuilder, csomagoló osztályok.
OOP alapelvei

Osztály, objektum: Egy OOP nyelvben két új nyelvi elemre van szükség: osztály és objektum. Az osztály egy programozó által definiálható típus, amely tartalmazhat adatokat az objektum struktúrájának modellezésére és metódusokat az objektum viselkedésének modellezésére. Az objektum egy osztály egy példánya. Egy osztály általában többször is példányosítható. A példányok ugyanazzal a viselkedésfajtákkal rendelkeznek, de minden példány más állapottal rendelkezhet.

Osztály definíció: módosítók class osztálynév { tagok definíciói }. A módosítók (public, protected, private), az osztálynév tetszőleges azonosító.

Az osztály tagjai lehetnek:

  • adattag (mező)
  • metódus tag
  • konstruktor
  • inicializáló blokk
  • tag osztály (interfész)

A tagok definiálásának sorrendje tetszőleges, bár szokások vannak, például adattagok, inicializáló blokkok, konstruktorok, metódusok, tagosztályok.

Az adattag hasonlít egy lokális változó definíciójához, de lehetnek módosítók előtte: módosítók típus azonosítólista;, a típus lehet elemi vagy referencia, az azonosítólista elemek listája vesszővel elválasztva, ahol egy elem azonosító vagy azonosító=inicializálókif.

Az adattagokat a lokális változókkal ellentétben szokás külön-külön definiálni. A lokális változókkal ellentétben az adattagok alapértelmezetten is inicializálódnak (numerikus 0-val, char 0 kódú karakterrel, boolean false-sal, referencia null-lal).

A metódus a C-beli függvények definíciójához hasonlít: módosítók típus név(paraméterlista) { utasítások }. A típus tetszőleges típus lehet vagy void, a név egy szokásos azonosító, a paraméterlista pedig a C-beli paraméterlista szintaktika.

Egységbezárás (encapsulation): Az osztály egy egységbe zárja az objektum adatait és az azokkal dolgozó műveleteket. Az osztály saját névteret képez, azaz több osztályban is lehet ugyanolyan nevű adat vagy művelet. Valamint az osztályon belül az adatok és műveletek korlátlanul elérik egymást.

Üzenet (message): Az üzenet az objektumok között kommunikáció formája. Technikailag az objektum metódusainak meghívását jelenti.

Adatrejtés (information hiding): Az osztály műveleteinek implementációja osztályon kívülre nem látható, az osztály adatai, és műveletei csak szabályozottan legyenek elérhetőek. Kell egy mechanizmus, amellyel a programozó szabályozhatja az adatok, műveletek elérését, figyelembe véve a szabályokat.

Betartandó szabályok:

  • az adatok ne legyenek közvetlenül elérhetőek a külvilág számára, legfeljebb metódusokon (függvényeken) keresztül. Ennek előnyei, hogy
    • szabályozható, hogy csak olvasás, írás vagy mindkettő biztosított
    • független lesz az adat elérése a tényleges ábrázolástól
    • az adatok beállításakor megtehető, hogy csak bizonyos értékeket lehessen beállítani
  • A metódusok közül csak azok legyenek a többi objektum számára elérhetőek, amelyek az objektum kommunikációs felületéhez tartoznak.

Öröklődés (inheritance): Egy osztály létrehozható egy másik osztály leszármazottja. Ilyenkor az osztály örökli a szülője adatait, metódusait, de lehet újakat is definiálni, illetve lehet örökölt metódusokat módosítani. Az öröklődés jelentősége egyrészt valós életbeli osztályozás (leszármazás) modellezése, másrészt a kód újrafelhasználása.

Polimorfizmus: Bizonyos viselkedések működése függ a környezettől, ahol alkalmazzuk.


Mesterséges intelligencia

Jelen tananyag dr. Dudás László, a Miskolci Egyetem oktatójának anyaga alapján készült a Mesterséges intelligencia alapok (GE) tárgy keretein belül.

Bevezetés

Az ember ősidőktől törekedett arra, hogy a természettől kapott adottságait, képességeit mesterségesen megalkotott eszközök segítségével kibővítse, kiváltsa, és új, számára meg nem adatott képességekkel folyamatosan javítsa. Ezt a törekvését mindig az adott kor technikai színvonalán tudta megvalósítani.

A technika fejlődése a 20. század közepére a számítógép megjelenésével megteremtette a lehetőséget arra, hogy az ember legtöbbre értékelt tulajdonságát, az intelligenciáját mesterséges eszközökkel részben helyettesítse.

Intelligencia definíciók

Arisztotelész:

"Az intelligencia az igazságot megragadó megállapítás, beleértve a következtetést, amely ahhoz a tevékenységhez kapcsolódik, amely jó, vagy rossz egy ember számára. ... és ez megfelelőnek tűnik azután egy intelligens személy számára arra, hogy képes legyen finoman megítélni, mi a jó és előnyös számára; nem néhány korlátozott területre vonatkozóan (például ami jó az egészség, vagy az erő számára), hanem amely általában támogatja a jólétet."

Henri Bergston:

"Az intelligencia ... képesség mesterséges objektumok készítésére, különösen eszközöket előállító eszközök készítésére."

Martin A. Fischler és Oscar Firschein:

"Egy intelligens képződménytől elvárjuk, hogy legyenek lelki attitűdjei (magatartásformái), legyen képes tanulni, problémákat megoldani, megérteni, tervezni és megjósolni, ismerni saját korlátait, megkülönböztetéseket tenni, legyen eredeti, általánosítson, legyen felfogóképessége és használjon nyelvet."

F. Scott Fitzgerald:

"Egy elsőrendű intelligencia mércéje az, hogy legyen képes két ellentétes gondolatot, elképzelést hordozni a tudatában egyidejűleg, és ezzel együtt legyen működőképes."

Marvin Minsky:

"Az intelligencia egy gyakran használt fogalom annak a rejtélynek a kifejezésére, hogy néhány önálló elem, vagy elemek felelősek a személy következtetési képességéért. Én jobban szeretem úgy elképzelni ezt, mint amely nemcsak valami különös erőt, vagy tüneményt reprezentál, hanem egyszerűen az összes mentális képességet, amelyet mi minden pillanatban megcsodálhatunk, de még nem értettünk meg."

Allen Newell:

"Egy rendszer intelligenciája az a fok, amelyhez a tudásszintje közelít, vagy az a tartomány, amelyhez használja a tudását; nem hibáztathatunk egy olyan rendszert, amely kevés tudással bír, de azt jól alkalmazza."

Elaine Rich:

"Az intelligencia az az egyetlen általános, közös jellemző, minőség az emberi tevékenységben, amely lehetővé teszi, hogy bármikor jobbak legyünk a számítógépnél."

Robert Sternberg:

"Az a lény (képződmény) intelligens, amely célirányos adaptív (alkalmazkodó) viselkedést végez."

Webster's Dictionary (szótár):

"Az a képesség, hogy hatékonyan tudjon a tapasztalásból tanulni, vagy megérteni, kinyerni és megőrizni a tudást; mentális (szellemi) képesség; egy új szituációhoz való gyors és sikeres alkalmazkodás képessége; a következtetés használatának a képessége a problémamegoldásban, a viselkedés irányítása, stb."

Christopher F. Chabris:

"Mondhatnánk azt: Nem tudom megmondani, mi az intelligencia, de megismerem, ha találkozok vele. Az intelligencia olyan fogalom, amely jelentését a kontextusból, alkalmazási környezetéből nyeri, nem pedig egy felállított modellből, vagy kritériumrendszerből."

E.L. Thorndike:

"Az intelligencia az a tulajdonság, melyben az olyan zsenik, mint Newton, Einstein, Leonardo da Vinci, Shakespeare csoportja leginkább eltér egy értelmi-fogyatékos otthon lakóitól."

David Wechsler:

"Az intelligencia az egyénnek az az összesített, vagy globális képessége, amely lehetővé teszi, hogy célszerűen cselekedjen, hogy racionálisan gondolkodjon és eredményesen bánjon a környezetével."

Alfred Binet és Teophile Simon:

"Úgy tűnik, hogy az intelligenciában van egy alapvető tényező, amelynek megléte, illetve hiánya oly döntő a mindennapi életben. Ez az ítéletek, a józan ész képessége, a gyakorlati érzék, a kezdeményezőkészség és a körülményekhez való alkalmazkodás képessége. A jó döntés, a jó felfogás és a jó okfejtés az intelligencia lényege."

Az intelligencia mérése

  • Egzakt mérés igénye » tesztek
  • Tesztek fajtái
  • Teljesítménytesztek: jelenleg mit tudunk teljesíteni
  • Képességtesztek: gyakorlás után mire leszünk képesek, jóslás
    • Az intelligencia teszt is képességteszt
  • Érvényesség: azt mérje, amit mérni szeretnénk
  • Megbízhatóság: ismételve közel ugyanolyan eredményt adjon.
  • Kortól, kultúrától való függés

Intelligencia tesztek készítése

Sir Francis Galton

  • Öröklött észlelési, érzékelési képességek? » Nem.
  • Mérésekkel összekötött vizsgálatok
  • Érdeme: a korrelációs együttható alkalmazásának bevezetése.
    Korreláció: egymást kölcsönösen feltételező dolgok, vagy fogalmak viszonya, dolgoknak egymástól való függése, ill. egymásnak való megfelelése.

J. Cattel:

  • Első intelligenciateszt, 1890.
  • Ő a tesztmódszerek atyja.

Alfred Binet, Teophile Simon

  • Teszt gyerekek iskolaérettségének vizsgálatára, 1905.
  • Gondolkodási és problémamegoldási feladatok.
  • Mentális kor fogalma, mentális kor skála.
  • MK - ÉK különbség.
  • A legelterjedtebb tesztek egyike

Lewis Terman

  • A Binet teszt átdolgozása amerikai gyerekekre, 1916.
  • William Stern javaslatára bevezette az IQ hányadost:
    IQ = MK/ÉK *100
  • Átlagos intelligencia érték: 90 - 110, értelmi fogyatékosság: 70 alatt, zsenialitás 140 feletti értéknél. Egyetemi hallgatók: IQ ~ 120.
  • Külön pontozott területek:
    • verbális gondolkodás,
    • absztrakt-vizuális gondolkodás,
    • számolás,
    • rövidtávú memória.

David Wechsler

  • A másik legismertebb teszt, 1939.
  • Felnőttek tesztelésére: WAIS
  • "Az IQ globális képesség"
  • Verbális skála, performációs skála.

Charles Spearman

  • A faktoranalízis kidolgozója, 1904
  • g - general, általános intelligencia: összefüggések felfogása, értékelése
  • s - specific, speciális intelligencia faktorok: logikai, térbeli, tájékozódási, matematikai, zenei, stb.

Louis Thurstone

  • Elveti a g-general faktor létezését, 1938
  • Az intelligencia számos elsődleges képesség együttese
  • Hét faktort talált: verbális megértés, beszédfolyékonyság, számolás, téri képességek, emlékezet, észlelési sebesség és következtetés.

Howard Gardner

  • Többszörös intelligencia elméletében 6 elkülönült agyi modult talált: nyelvi, logikai-matematikai, téri, zenei, kinetikus (mozgási) és személyes (intraperszonális és interperszonális).
  • Információfeldolgozási megközelítés az IQ tesztek készítésében
  • Indíték:
    • kognitív pszichológia
    • információfeldolgozás kutatása.
  • Lényege: milyen kognitív (megismerési) műveleteket igényelnek az egyes intellektuális tevékenységek.

Hunt; Carpenter+Just+Shell, 1990

  • Feltett kérdések:
    • Milyen mentális folyamatokat igényelnek a tesztek?
    • Ezek milyen gyorsan működnek?
    • Hogyan rögzítjük a szükséges információkat?
  • Azokat a mentális folyamatokat keresi, amelyek az intelligens viselkedésért felelősek.

Sternberg

  • A gyakorlati intelligencia is fontos a "tudományos" intelligencia mellett.
  • Összetevőmodellje:
    • Mentális folyamatok készlete = összetevők
    • Összetevők szervezett működése = intelligencia.
  • Összetevők:
    • Metaösszetevők: felsőszintű vezérlő folyamatok
    • Teljesítmény-összetevők: végrehajtó folyamatok
    • Tanulási összetevők: tanulási folyamatok
    • Megőrzési összetevők: információ előhívó folyamatok
    • Átviteli összetevők: folyamatok az ismereteknek más problémákra való adaptálásához.
  • Gazdag összetevőkészlet létezhet
  • Az intelliganciához szükséges képességek:
    • Tapasztalatokból való tanulás és azok alkalmazása
    • Absztrakt gondolkodás és következtetés
    • A változó és bizonytalan világ szeszélyeihez való alkalmazkodás
    • Önmotiválás...

Részlet egy intelligencia tesztből

  1. Írja be a hiányzó számot! 2, 5, 8, 11, __
  2. Húzza alá az oda nem illő szót! ház kunyhó bungaló hivatal
  3. Találja ki a hiányzó számokat! 7, 10, 9, 12, 11, __, __
  4. Húzza alá az oda nem illő szót! hering bálna cápa ponty harcsa

Az intelligencia három kulcsfontosságú jellemvonása Aaron Sloman szerint

  • szándékosság (intentionality)
  • rugalmasság (flexibility)
  • produktív lustaság (productive lazyness)

Szándékosság

Olyan belső állapotokkal való rendelkezés képessége, melyek időben, vagy térben többé-kevésbé távoli, vagy teljesen elvont objektumokra, vagy szituációkra vonatkoznak, illetve utalnak.

  • A szándékos állapotok magukban foglalják például:
    • az elmélkedést
    • álmodozást arról, hogy herceg vagyok
    • egyenletek vizsgálatát
    • tűnődést egy lehetséges akción
    • egy kígyó elképzelését
    • valaki kegyei elnyerésének kívánását
    • stb.
  • A szándékossághoz tartozik az öntudat is: az agy gondolatai önmagáról
  • A szándékosság részkategóriái:
    • megértés
    • hit
    • ismeret
    • akarás
    • célkitűzés
    • elképzelés
    • kérdésfeltevés
    • terv
    • stratégia
  • Következtetési eljárás: implicit ismeretekből &raqou; explicit ismeret

Rugalmasság

Kezeli a széles és változatos szándékos agyi tartalmakat, például a célok, objektumok, problémák, tervek, akciók, környezetek, stb. típusainak választékát, ez foglalkozik az új szituációkkal, felhasználva a régi ismereteket, új módon kombinálva és transzformálva azokat. A rugalmasságból eredő képességek:
  • Kérdések sokaságának felvetése
  • Összetett problémák leegyszerűsítése

Produktív lustaság

Nem elegendő elérni egy eredményt: az intelligencia lényege abban is van, hogy hogyan értük el. A produktív lustaság a felesleges munka elkerülését jelenti. Másként számolja ki az emberi agy a 200! - 200! = ? feladatot, mint a számítógép.
  • Előny: a kombinatorikus robbanás elkerülése
  • Magába foglalja:
    • szimmetriák, viszonylatok, egyszerűsítő összefüggések felfedezését
    • általánosítás képességét
  • Igényli a tanulás képességét: azt a képességet, hogy új koncepciókat formáljunk.

Mesterséges intelligencia

Az emberi intelligencia körüljárása után nézzük meg, mit jelent, mi a célja a mesterséges intelligencia kutatásnak! Az AI (Artificial Intelligence = Mesterséges Intelligencia) elnevezést McCarthy alkalmazta először 1956-ban. Elterjedése Marvin Minsky 1961-ben megjelent "Steps towards artificial intelligence" című cikkének köszönhető.

Mesterséges intelligencia definíciók

Cihan H. Dagli (idézi Barr-t és Feigenbaum-ot):
"A gépi intelligencia emulálja, vagy lemásolja az emberi ingerfeldolgozást (érzékletfeldolgozást) és a döntéshozó képességet számítógépekkel. Az intelligens rendszereknek autonóm tanulási képességekkel kell bírniuk és alkalmazkodniuk kell tudni bizonytalan, vagy részlegesen ismert környezetekhez."
Aaron Sloman:
"A számítógéptudomány egy alkalmazott részterülete. A mesterséges intelligencia egy nagyon általános kutatási irány, mely az intelligencia természetének kiismerésére és megértésére, valamint a megértéséhez és lemásolásához szükséges alapelvek és mechanizmusok feltárására irányul."
Yoshiaki Shirai - Jun-ichi Tsujii:
"A mesterséges intelligencia kutatásának célja az, hogy a számítógépeket alkalmassá tegyük az emberi intelligenciával megoldható feladatok ellátására."
Sántáné Tóth Edit:
"A mesterséges intelligencia a számítástudomány azon részterülete, amely intelligens számítógépes rendszerek kifejlesztésével foglalkozik. Ezek pedig olyan hardver/szoftver rendszerek, amelyek képesek "emberi módon" bonyolult problémákat megoldani: az emberi gondolkodásmódra jellemző következtetések révén bonyolult problémákra adnak megoldást, a problémamegoldást teljesen önállóan végzik, vagy közben kommunikálnak környezetükkel, tapasztalataikból tanulnak, stb."
Peter Jackson:
"A mesterséges intelligencia a számítógéptudomány azon részterülete, amely az ember olyan kognitiv (megismerő) képességeit emuláló számítógépi programok tervezésével és alkalmazásával foglalkozik, mint a problémamegoldás, vizuális érzékelés és a természetes nyelvek megértése."

A mesterséges intelligencia osztályozása

  • alkalmazási területek szerint:
    • logikai játékok (logical games)
    • tételbizonyítás (theorem proving)
    • automatikus programozás (automated programming)
    • szimbolikus számítás (symbolic algebraic computation)
    • látás, képfeldolgozás (vision)
    • robotika (robotics)
    • beszédfelismerés (voice recognition)
    • természetes nyelvek feldolgozása (natural language processing)
    • korlátozás kielégítés (constraint satisfaction)
    • cselekvési tervek generálása (planning)
    • szakértőrendszerek (expert systems)
    • mesterséges neurális hálózatok (artificial neural nets).
    • adatbányászat (data mining)
    • ágensek, multi-ágensek (agents, multi-agents).
  • alkalmazott módszerek alapján:
    • problémareprezentáció
    • tudásreprezentáció
    • tudás kinyerés
    • tanulási technikák
    • következtetési technikák
    • keresési technikák
    • evolúciós technikák
    • bizonytalanság kezelés
    • szimbolikus programozás
    • tudáshasznosítás

Történeti előzmények

1936 - Turing vázolja az általános célú számítógép alapelvét 1945 - Neumann kigondolja a tárolt programú kialakítást a szekvenciális digitális számítógép számára 1946 - ENIAC : az első általános célú számítógép 1950 - Turing tesztje a mesterséges intelligencia számára 1955 - Bernstein kifejleszti az első működő sakkprogramot 1956 - McCarthy bevezeti a mesterséges intelligencia (artificial intelligence) elnevezést 1957 - McCarthy kifejleszti a LISP (LISt Processor) programozási nyelvet. Newell, Shaw és Simon belekezd az ambíciózus General Problem. Solver program kidolgozásába 1957 - Chomsky bevezeti a transzformációs nyelvtant a természetes nyelv modellezésére 1965 - Feigenbaum kifejleszti a DENDRAL-t, az első szakértői rendszert 1966 - Quillian kifejleszti a szemantikus hálót 1967 - Greenblatt kifejleszti MacHack-et, az első versenyző sakkprogramot 1970 - Winston úttörő gépi tanuló programja: "Learning Structural Descriptions from Examples" - Colmerauer elkészíti a Prolog (PROgramming in LOGic) programozási nyelvet 1972 - MYCIN: az első gyakorlati szakértőrendszer, amely produkciós szabályokat használt - Winograd befejezi a természetes nyelvet feldolgozó SHRDLU programját 1974 - Minsky publikálja a "Tudásfeldolgozás kerettel" című cikkét 1975 - Elkészül az első LISP-hardveres számítógép 1982 - Marr publikálja forradalmi, átfogó elméletét a látásról - Elkezdődik az 5. generációs számítógép fejlesztése Japánban 1986 - A Thinking Machines Corporation bemutatja a Connection Machine-t - Berliner HiTech sakkprogramja elnyeri a nagymesteri címet 1994 - A sakkszámítógép legyőzi Garri Kaszparov világbajnokot. Megjegyzés: A mesterséges neurális hálók történetét lásd később, a témához kötötten Lásd továbbá: http://128.174.194.59/cybercinema/aihistory.htm

A Turing teszt

A tesztet Alan Turing fogalmazta meg a(z igazi) mesterséges intelligencia minősítésére. Turing a COMPUTING MACHINERY AND INTELLIGENCE című cikkében tette fel a kérdést: "Can machines think?" , azaz "Tudnak a gépek gondolkodni?" A gondolkodó gép címre pályázó számítógép megítélésére alkotta meg tesztjét. A tesztet általánosították az emberhez hasonlóan gondolkodó gépből kiindulva az emberhez hasonlóan cselekvő gép irányába.

Az ágens

Bővebb értelmezés: valami, aminek
  • környezete van, önállósága van,
  • érzékeli környezetét,
  • beavatkozik a környezetébe.
Szűkebb értelmezés: az ágens olyan rendszer, amely
  • környezetbe ágyazott,
  • reaktív: érzékel és reagál,
  • autonóm: emberi beavatkozás nélkül működik, önkontrollja van,
  • helyzetfüggő: helyzethez és szerephez kötötten ágens csak,
  • kezdeményező: nem csak reagál, hanem kezdeményez is,
  • célvezérelt,
  • huzamosabb ideig működik.
Még szűkebb (erős) definíció: Jellemzői az előzőek, továbbá:
  • Racionális: nem cselekszik tudatosan a céljai ellen, igyekszik a legjobb alternatívát választani,
  • Mentális állapotváltozókkal bír: tudás, vélekedés, szándék, stb.
További, kívánatos antropomorf jellemvonások, az intelligencia szükséges elemei:
  • A nyelv és a kommunikáció
  • Tanulás, adaptivitás.
    • Új ismeret gyűjtése, tárolása, alkalmazása.
    • Alkalmazkodás valamihez
      • Hosszú távú (evolúciós, genetikai jellegű)
      • Középtávú, megerősítéses: gyakorlással, tapasztalással
      • Kognitív, következtetéses: gondolkodással, következtetési eljárással.
A mesterséges személyiség további jellemzői:
  • Személyisége van: más ágensektől megkülönböztető jegyek,
  • Érzelmei vannak: speciális mentális állapotok,
  • Arc, mimika (mesterséges): virtuális emberek.

Csoportos ágensek - multi-ágens rendszerek (MAS)

  • Kölcsönhatásban állnak egymással
    • direkt : kommunikálnak,
    • indirekt : cselekedeteik által hatnak egymásra,
    • fizikailag : érintkeznek egymással.
  • Együttműködnek: közös cél
    • kommunikáció + kollaboráció (együtt tevékenykedés).
  • Struktúra, hierarchia van az ágensek között.

Elosztott mesterséges intelligencia (DAI)

Az elosztott mesterséges intelligencia (Distributed AI) azt vizsgálja, hogyan lehet a feladatokat több, önálló problémamegoldó egység segítségével megoldani.
  • A multi-ágens rendszerek és az elosztott MI viszonya: a multi-ágens rendszer és az elosztott MI jelentősen átfedi egymást
    • Koordináció: tevékenységek összehangolása a csoport feladatainak megoldása, illetve a csoporttal szembeni korlátozások betartása érdekében.
    • Kooperáció: a csoport egy ágensének tevékenysége segíti a másik ágenst célja elérésében és megfordítva.
Ágensek alkalmazása
  • Információs ágensek: az információs robbanás megoldására. Önállóan gyűjtik, szelektálják, dolgozzák fel az adatokat.
  • Internet és WWW ágensek: pl. kereső szerverek, Google, Alta Vista, Yahoo, stb. News-figyelő ágensek. Elektromos kereskedelmi ágensek: felderítik az árut, alkudoznak, vásárolnak.
  • Interfész-ágensek: számítógép felhasználók támogatására. Figyelik és modellezik a felhasználó tudását és igényei, ezekre reagálva önállóan ajánlanak fel funkciókat, végeznek el feladatokat. Tulajdonságuk: perszonalizáció = alkalmazkodás a felhasználó igényeihez. Pl. WORD iratkapocs--súgója. Lehet szimulált személyiségük is.
  • Asszisztensek: hasonlóak az előzőhöz. Pl. Elektromos levelek kezelésére, osztályozására, megválaszolására. Intelligens határidőnaplók: találkozók egyeztetésére. Web-asszisztensek: az ember ellesett preferenciái alapján ajánlanak új web-lapokat.
  • Oktató ágensek: a tanuló tudásához, szintjéhez alkalmazkodnak.
  • Ágens alapú szimulátorok: pl. Mesterséges élet (Artificial life) célja olyan ágensek, rendszerek (szimulációk, robotok, hardvereszközök) létrehozása, melyek valamilyen szempontból hasonlóak az élet egyes aspektusaihoz, például alkalmazkodás, reprodukció, evolúció. Ide tartoznak a genetikus algoritmusok, neurális hálók, sejtautomaták is.
  • Szintetikus karakterek: a virtuális valóság igényeinek kielégítésére. Cél: illúziókeltés (mozifilm, reklám, interfészek).
  • Intelligens épületek: érzékelő és szabályozó elemek segítségével automatikus és hatékony erőforrásgazdálkodást végeznek.
  • Szoftvertechnológiai alkalmazások: az ágens alapú programozás egyenes továbbfejlődése a strukturált és az objektum orientált programozásnak. Különösen nagy bonyolultságú nyílt rendszerek esetében előnyös. Mobil ágensek: a szoftverágens mozog a hálózaton a nagymennyiségű adatban a keresett adathoz.

A mesterséges intelligencia alkalmazási területei

Az ötödik generációs számítógép projekt

A mesterséges intelligencia alkalmazási területei:
  • logikai játékok (logical games)
  • tételbizonyítás (theorem proving)
  • automatikus programozás (automated programming)
  • szimbolikus számítás (symbolic algebraic computation)
  • látás, képfeldolgozás (vision)
  • robotika (robotics)
  • beszédfelismerés (voice recognition)
  • természetes nyelvek feldolgozása (natural language processing)
  • korlátozás kielégítés (constraint satisfaction)
  • cselekvési tervek generálása (planning)
  • szakértőrendszerek (expert systems)
  • mesterséges neurális hálózatok (artificial neural nets).
  • adatbányászat (data mining)
  • ágensek, multi-ágensek (agents, multi-agents).

Logikai játékok (logical games)

Mottó: "A játék nem játék!"

  • A játék lényege:
    • Ellenérdekűű résztvevők felváltva érvényesített stratégiái a végső nyerés érdekében
    • Gazdasági, katonai vetület
    • A véletlennek nincs szerepe
  • Motiváció: az ember szereti a szellemi kihívásokat (különösen a férfiak szeretnek versenyezni)
  • Fő kérdés: Lehet-e a gépnek esélye az ember ellen?

Játékkal foglalkozó gondolkodók

  • Kempelen Farkas: sakkautomatája , a Török (csalás) 1769
  • Leonardo Torres y Quevedo: működő mechanikus sakkvégjátékautomata 1890!
  • Neumann és Morgenstern: Theory of Games and Economic Behavior című könyv
  • Nemes Tihamér: cikk sakkozó gépről, 1949
  • Claud Shannon: tanulmány, 1950
  • Alan Turing: sakkalgoritmus, 1951
  • A játékelmélet alkalmazásának kiteljesedését a számítógép teremtette meg

Kétszemélyes zérusösszegű játékok

  • Egyik nyer, másik veszít, egyes játékokban döntetlen is.
  • MAX, MIN, a két játékos elnevezése
  • Teljes információjú
    • táblás játékok: igen
    • kártyajátékok: nem
  • Diszkrét: elméletileg véges számú játékállás, lépés
  • Végteszt: nyert-e valamelyik? Döntetlen?
  • Nyerő stratégia: kényszerítve nyer
  • Tökéletes definiáltság és kevés szabály miatt ideális MI tesztterületnek

A játék szemléltetése

  • A játék szemléltetése: irányított gráffal
  • Gráf-fajták:
    • Hálós gráf: egyféle állás - ugyanazon csomópont
    • Fagráf: ugyanazon állásnak több csomópont felel meg (leggyakoribb, jól kezelhető)
    • ÉS/VAGY gráf: az egyik játékos szemszögéből. (Saját lépések között: VAGY, ellenfélé között: ÉS.) Csomópontban kell: legalább egy nyerőcímkés VAGY, ill. ÉS esetén mind legyen nyerőcímkés.

Gráfjellemzők

  • Csomópont « » játékállás
  • Élek « » legális lépések
  • Fagráf-jellemzők:
    • Gyökér csomópont ó a játék kezdete (elemzés kezdete)
    • Szintek, mélység, depth, d, váltakozva MAX, MIN, gyökér: d=0
    • Levél csomópontok: az egyes játszmák vége, valaki nyer, vagy döntetlen; nyereségérték.
    • Elágazási tényező: a csomópontnak megfelelő állásból tehető legális lépések száma, branching factor, b
    • Átlagos elágazási tényező: több, n csomópontra:

    A legjobb stratégia meghatározása

    A legjobb lépés kiválasztása az adott csomópontból megtehetők közül: • Minimax algoritmus: Neumann János, 1928 • Stratégiamátrix 3 5 5 1 9 2 4 MAX MIN (MAX a 2. sort választja, mert annak a minimuma nagyobb= 2, nyeregpont) • Az algoritmusban: MAX a kiinduló éleken visszakapott értékek maximumát, MIN a minimumát rendeli a csomóponthoz. • Az értékek számítása a fa leveleitől a gyökér irányába. 2/ 8 . dr.Dudás László n A játék értéke • A játék értéke: A teljes játékfára elvégzett minimax algoritmus eredménye. Egyértelműen megmondja, a kezdő játékos nyeri-e a játékot hibátlan lépésvezetés esetén, és ha igen, azt milyen lépések választásával teheti meg. A nyerés független az ellenérdekű játékos lépéseitől ilyenkor. Ez az algoritmus NEM épít a játékosok szerencséjére, azaz az ellenfél hibázására. • A játék teljes fája és a játék értéke csak kis egyszerű játékok (pl. TicTacTo) esetén határozható meg a gyakorlatban. • Gond: a játék állásainak száma a mélységgel exponenciálisan nő, közelítőleg= • Kombinatorikus robbanás: sok a lehetőség, illetve kis teljesítményű a fa kiértékelése. 2/ 9 . dr.Dudás László n A hatékonyság növelése • Alfa-béta lenyesés: a fa egyes ágainak levágása. A játék értékére nincs kihatással, de a számításigényt csökkenti. Nem kell kimerítő keresés. Általános esetben kb. 33%-kal mélyebb fa elemezhető ki. • Gyakorlatban sokszor még ez is kevés. • Gyakorlati megoldás összetett játékok esetében: az elemzés mélységének egy adott szintre korlátozása. • Gond: a játéklefolyások teljességükben ismeretlenek, a végződések elvesznek, nincs a minimax algoritmussal felterjeszthető érték. • Megoldás (közelítő, nem ad feltétlenül azonos eredményt, mint a minimax)(Shannon): • Az elvágással keletkezett leveleknek megfelelő állásokhoz tapasztalati nyerési esélyértékek rendelése, heurisztikus kiértékelő függvények (HKF) révén. n A heurisztikus kiértékelő függvény • Heurisztikus kiértékelő függvény (HKF): a játékot jól ismerő, nagy tapasztalatú emberek által megadott függvény, mely az állás jellemzőiből számít egy, az állás jóságát megítélő értéket. • A minimax algoritmus (és az alfa-béta lenyesés) alkalmazása a HKF értékekre alapozva: a kapott játékérték, ill. közbenső érték annyira lesz jó, közelíti a teljes fa esetére adódó pontos értéket, amennyire jó, kifinomult a HKF. • Problémák a fa elvágása miatt: • horizont effektus: az elvágás alatti részen bekövetkező kedvező, vagy kedvezőtlen hatások nem látszanak (pl. sorozatos sakkadással lemehetünk a horizont alá és nem láthatjuk, hogy a játék a sakkot kapó számára kedvezőbb állású). horizont 2/ 10 . dr.Dudás László 2/ 11 . dr.Dudás László n A heurisztikus kiértékelő függvény .. • A HKF jóságának és a keresésigénynek az összefüggése 2/ 12 . dr.Dudás László n További hatékonyságnövelő technikák • B* algoritmus, intervallumkorlátok a csomóponti értékekre a lenyeséshez • SSS* algoritmus, az alfa-béta lenyeséstől is több ág elhagyása (játékspecifikus) • Intervallumtechnika helyett valószínűségi eloszlás • Iteratív mélyítés: jó az alfa-béta lenyesés rendezettségi igényének részbeni kielégítésére és az időkorlátos játékokhoz is • Legalább részleges rendezettség elérése az alfa-béta lenyesés hatékonyságának növelésére • Célhardver és párhuzamos számítás alkalmazása 2/ 13 . dr.Dudás László n Híres programok, hardver implementációk • Legeredményesebbek: • Belle, első sakkcélhardver, 1982 • Chinook, első ember ellen világbajnok játék (dáma) http://web.cs.ualberta.ca/~chinook/ 2/ 14 . dr.Dudás László n Híres programok, hardver implementációk .. • Legeredményesebbek: • DeepBlue, sakk, (Feng Hsu, Joseph Hoane and Murray Campbell), 1998 Garri Kaszparov ellen nyert. (200millió állás/sec) – Okok: » Egycsipes keresőgép » Párhuzamos hardver több szinten párhuzamosítva » Javított kereső algoritmus » Komplex HKF » Nagymesterek játszmáit tartalmazó adatbázis. • Fritz7, sakk: a Kaszparovtól a világbajnoki címet elhódító Vlagyimir Kramnyik kihívója, 2002 2/ 15 . dr.Dudás László n Híres programok .. • Legeredményesebbek: • Othello: – Logistello, Michael Buro, a legjobban játszó embernél jobb. • Backgammon: – TD-gammon, Gerald Tesauro, világbajnok szintű. • Go: – A legerősebb programok is még csak kissé jobbak a kezdő szintű emberjátékosoktól 2/ 16 . dr.Dudás László n Tételbizonyítás • Matematikai tételek bizonyítása az alapaxiómákból kiindulva, pl. kijelentés (propozíciós, nulladrendű predikátum-) kalkulust, illetve elsőrendű predikátumkalkulust használó MI programokkal, a rezolúció módszerével. A rezolúció lényege: lássuk be, hogy a tényekből, szabályállításokból és a bizonyítandó állítás negáltjából álló halmaz kielégíthetetlen, ellentmondásos. Ha sikerül, akkor a bizonyítandó állítás csak igaz lehet. • A tételbizonyítók automatikus következtetések levonására alkalmasak alapaxiómákból, alapinformációkból kiindulva, következtetési szabályokat alkalmazva. • A tételbizonyítók esetében, szemben a logikai programozási nyelvekkel (pl. Prolog) , nem csak a logika, azaz a kiinduló ismeretek, tények és a szabályok megadása hárul a felhasználóra, hanem a vezérlést, azaz a következtetés, bizonyítás menetének módszerét is nyújtania kell. A tételbizonyítók kutatása elsősorban általánosan alkalmazható vezérlők megtalálását célozza. • Konkrét alkalmazások: QA1, QA2, QA3 programnyelvek, programnyelv procedurális reprezentációt is alkalmaz. a QA4 2/ 17 . dr.Dudás László n Isabelle • Egy másik professzionális szoftver az Isabelle. Tekinthető a következtető rendszerek gyors kreálására alkalmas környezetként, valamint egy komplett tételbizonyítóként. • Az Isabelle az alábbi módszereket támogatja: • elsőrendű logika • magasabbrendű logika • Zermelo-Fraenkel féle halmazelmélet • a Martin-Löf féle típusemélet egy bővített verziója • modális logika • a Kiszámítható Függvények logikája. http://www.cl.cam.ac.uk/Research/HVG/Isabelle/ 2/ 18 . dr.Dudás László n A tételbizonyítók eredményei • Matematikai tételek, sejtések bebizonyításában • Szoftver és hardvereszközök helyességellenőrzésében és szintézisében • Áramkörök tervezésében • stb. 2/ 19 . dr.Dudás László n Automatikus programozás • Cél: a szoftverkészítés munkájának automatizálása, olyan eszközök létrehozásával, melyeknél elegendő a megoldandó feladatot specifikálni, a megoldás algoritmusa és programja automatikusan készül el. • Az automatikus programozás esetén a szoftver specifikációja értelemszerűen kisebb és könnyebben megadható, mint maga a program lenne valamilyen programnyelven 2/ 20 . dr.Dudás László n Automatikus programozás generikus algoritmusokkal • Az automatikus programozás egyik módszere az általános algoritmusokra (generic algorithms) épít. Az általános algoritmusok egyszerű programozási feladatokra adnak megoldást, például egy sorozatot rendeznek. • A felhasználó feladata a konkrét programozási feladat és a generikus algoritmusok közötti kapcsolat megadása, pl. hogyan feleltethető meg a generikus algoritmus valamelyik absztrakt adata a konkrét probléma egy jellemzőjének. • Ha a megfeleltetés adott, egy fordítási folyamat eredményeként egy specifikus algoritmust kapunk, amely már konkrétan megoldja a kitűzött feladatot. • A generikus algoritmusok és a feladatok egymáshoz rendelése grafikus segédlettel is történhet. Lásd: http://www.cs.utexas.edu/users/novak/autop.html 2/ 21 . dr.Dudás László n Automatikus programozás evolúciós algoritmusokkal • Az ADATE (Automatic Design of Algorithms Through Evolution) rendszer nem genetikus algoritmussal állítja elő a feladatot megoldó programokat • Az algoritmusok nagyméretű kombinációs keresés révén születnek, mely keresés kifinomult program-transzformációkat alkalmaz • Az ADATE rendszer különösen szimbolikus, funkcionális programok származtatására előnyös • Windows-os demo program elérhető az alábbi lapról: http://www-ia.hiof.no/~rolando/adate_intro.html 2/ 22 . dr.Dudás László n Mintapélda: • lista rendezése A feladatspecifikáció, melyet nekünk kell megadni, a következőket tartalmazza: 1. Az input és az output típusa. Mindkettő céljára egészek listája választható. 2. Az előredefiniált konstansok és függvények, azaz a primitívek. Ezek vannak kiválasztva az üres listára, egy függvény, amely előre szúr be egy elemet a listába és a < függvény egészekre értelmezett alakja. 3. Input-output párok. Ezek többféle különböző módon választhatók. Pl: ( [], [] ) ( [0], [0] ) ( [0,1], [0,1] ) ( [1,0], [0,1] ) ( [0,1,2], [0,1,2] ) ( [0,2,1], [0,1,2] ) ( [1,0,2], [0,1,2] ) ( [1,2,0], [0,1,2] ) ( [2,0,1], [0,1,2] ) ( [2,1,0], [0,1,2] ) 2/ 23 . dr.Dudás László n Mintapélda: lista rendezése .. • Az eredmény: Az ADATE számtalan, a specifikációt kielégítő programot generál. A legrövidebb, mely feltehetően a legáltalánosabb is, az alábbi: fun f (V1_0) = case V1_0 of nil => V1_0 | (V60_0 :: V61_0) => let fun g471891_0 (V471892_0) = case V471892_0 of nil => (V60_0 :: nil) | (V471883_0 :: V471884_0) => case (V60_0 < V471883_0) of true => (V60_0 :: V471892_0) | false => (V471883_0 :: g471891_0( V471884_0 )) in g471891_0( f( V61_0 ) ) end • Ez a program a Standard ML programnyelven íródott. • A g471891_0 rekurzív segédfüggvényt az ADATE rendszer találta fel. Ez a függvény egy elemet szúr be a rendezett listába. 2/ 24 . dr.Dudás László n Automatikus programelőállítás genetikus algoritmussal • A genetikus programozás a probléma egy magasszintű meghatározásából kiindulva képes automatikusan előállítani működő számítógépi programokat. • Véletlenszerűen generált ezernyi ősprogram halmazából indulva, a programok populációja folyamatosan javulva fejlődik sok generáción át. Az evolúciós keresés a legrátermettebb és természetesen felbukkanó mintázatokkal rendelkező műveletek túlélésének darwini elméletét alkalmazza, köztük a keresztezést (szexuális rekombinációt), a mutációt, génduplikációt, géntörlést, valamint bizonyos fajtáit a fejlődési folyamatnak amelyek által az embriók kifejlett organizmusokká váltak. Forrás: http://www.genetic-programming.com/ 2/ 25 . dr.Dudás László n Szimbolikus számítás • Matematikai levezetések, algebrai manipulációk, deriválás, integrálás azonosságainak, trigonometrikus, logaritmikus, stb. azonosságoknak az alkalmazása szimbolikus alakban adott feladatok megoldására. • Ismertebb szimbolikus algebrai szoftverek: MACSYMA, REDUCE, CAMAL, LAM, ALTRAN, FORMAC, SYMBOL, MATHEMATICA 2/ 26 . dr.Dudás László n A MATHEMATICA szimbolikus számítási program • Egyaránt végez numerikus és szimbolikus számításokat • Automatikusan végzi az alapvető egyszerűsítéseket: • Összetett kifejezésekre addig alkalmazza az átalakítási szabályokat, amíg a kifejezés tovább nem változik, egyszerűsödik 2/ 27 . dr.Dudás László n A MATHEMATICA további jellemzői • • • • • • • • • • A problémák definiálására fordíthatjuk az időt, nem a levezetések és számítások elvégzésére A világ legnagyobb matematikai eszközkészletét, tudását nyújtaj Az eredményeket grafikusan is szemlélteti Numerikusan pontos Szimbolikusan kezeli a feladatokat Automatikusan megválasztja a legjobb megoldási módszert a megadott feladathoz Jegyzőkönyvbe szervezi a megoldás útját a megadástól a megoldásig Nyomdai minőségben prezentálja a kimeneteket Többféle formátumban kommunikálhatunk vele, akár a web-en keresztül is Gyors alkalmazásfejlesztést tesz lehetővé http://www.wolfram.com/products/ mathematica/newin42/M e s t e r s é g e s n A MATHEMATICA további jellemzői .. • Hatalmas mennyiségű integrálból, differenciálegyenletből, összegzésekből és transzformációkból álló kifejezések kezelésére képes, mely ember számára megterhelő lenne, nem beszélve a hibalehetőségről. 2/ 28 . dr.Dudás László http://www.wolfram.com/products/mathematica/newin42/M e s t e r s é g e s n A MATHEMATICA további jellemzői .. • Parciális differenciálegyenletek megoldására, az eredmények szemléltetésére képes. 2/ 29 . dr.Dudás László http://www.wolfram.com/products/ mathematica/newin42/ 2/ 30 . dr.Dudás László n Gépi látás, képfeldolgozás • Az ember a külvilágból szerzett információknak a legnagyobb részét látással szerzi meg. Ezért fontos az MI számára a mesterséges látás. 1. • A feladat: Adott egy kétdimenziós bit-térkép, ebből kiindulva meg kell adni a kép leírását, beleértve az alakzatok, méretek, színek, helyzetek paramétereit. Lényegében a nagyon alacsony szintű vizuális adatból egy magas szintű absztrakciót kell elérni, mely megfelel a képen látható objektumoknak. • Fontos mozzanatok: az emberi látás jellegzetességeinek modellezése, pl.: élek, kontúrok detektálása. A legjobb eredményekkel a neurális hálók kecsegtetnek (pl. PERCEPTRON, Rosenblatt kísérlete; karakterfelismerő programok). • Az elért eredmények magukba foglalják az elektronikus recehártyát is, mely a recehártya sok funkcióját, köztük a látvány elsődleges feldolgozását is modellezi. Létrehozása megkönnyíti a mesterséges neurális hálók bemenőjeleinek előállítását. 1. www.cnn.com/TECH/9604/10/ t_t/darts_eyes_lg.jpg 2/ 31 . dr.Dudás László n Gépi látás, képfeldolgozás .. • • Input: kétdimenziós bitmap fájl alakjában a látvány, a kép. Output: a felismert objektumok és térbeli viszonyuk, fizikai jellemzőik. • A képfeldolgozás lépései: • • • • • Élek detektálása Mélység meghatározása Alak meghatározása az árnyékoltságból Vonalak címkézése Objektum beazonosítás, helyzet meghatározás www.toytent.com/1140.html 2/ 32 . dr.Dudás László n Gépi látás, képfeldolgozás .. Élek detektálása: • Az élek fontossága: objektumhatárok, körvonalak, változások a fényvisszaverésben, világításban, mélységben és felületorientációban • A zaj problémája: ál-élek, melyeket előbb el kell simítani • Simítás egy pont-szórás függvénnyel (konvolúció) • Él megtalálása a fényességváltozás változásának (második derivált) nullát metsző helyeit keresve • A simítás és az éldetektálás kombinálása végrehajtva egy pont-szórás függvénnyel való módosítás révén, amely átlagol és megtalálja a fényességváltozások változásait • Az éldarabkák megcímkézése orientáció szerint egy együttműködési algoritmussal • Elemek halmazait és szomszédos elemek közötti kapcsolatokat értelmezzük • Az algoritmus ismétlése változtatja az értelmezését minden egyes elemnek, hogy a legnagyobb harmóniában legyen a szomszédos elemekkel (korlátozás kielégítés/kiterjesztés) • Párhuzamos feldolgozás: egy processzor elemenként: a processzorok csak a szomszédukkal kommunikálnak. 2/ 33 . dr.Dudás László n Gépi látás, képfeldolgozás .. Mélység meghatározása: • Sztereo egyenlőtlenség: igényli az egymásnak megfelelő pontok megtalálását a képeken • Objektumok mozgása • Szem mozgása Alak meghatározása az árnyékoltságból • Árnyékoltság • Ismeretek a fényelnyelésről • Ismeretek a relativ méretekről 2/ 34 . dr.Dudás László n Gépi látás, képfeldolgozás .. Vonalak címkézése : • Valós élek problémája: konvex, konkáv, kontur: két “irány” • Pszeudo élek: jelek, árnyék “élek”, -törések • Kapcsolódás típusok: három sík lehetséges csúcsalkotásai • Érkezés egy lehetséges címkézett kapcsolódáshoz a következő alakzatok egyikéből észlelhető: egy, három, öt, vagy hét kockából tevődnek össze, melyek különböző irányokból érkeznek • Lehetséges kapcsolódásfajták: 18 • A címkézést a határoknál kezdjük, felhasználva a megszorításokat melyek a nyíl és villa alakú kapcsolódásokra vonatkoznak. 2/ 35 . dr.Dudás László n Gépi látás, képfeldolgozás .. Objektum meghatározás Mintaegyezés vizsgálattal : • A régi módszer: néző-központútól az objektum-központú felé haladó reprezentációkkal • Éldetektálás, élkapcsolás. • Alakmeghatározás az árnyékoltságból, vonalcímkézés • A kiterjedés leírást az ismert objektumok könyvtárában található leírásokkal összevetik • Az új módszer: az objektumleírás kerülése; az alak implicite benne van az objektum nézeteinek halmazában • Minden egyes ismert objektumra a könyvtár tartalmaz egy modellt, képek halmazát, melyek mindegyike beazonosítható jellemző pontokat tartalmaz • Minden egyes ismeretlen objektumhoz minden egyes modellt párosítva megvizsgálják a jellemző pontok illeszkedését • Az illeszkedéseken alapulva, jóslásokat végeznek arra nézve hogy további pontoknak hol kellene megjelenniük az ismeretlen objektumon, elkészítve így egy testreszabott mintát minden egyes modellhez • Az ismeretlen objektumot úgy azonosítják, mint egy egyedét annak a modell mintához tartozó kategóriának, amelynek a testreszabott mintájához a legjobb egyezést mutatta az objektum. 2/ 36 . dr.Dudás László n Gépi látás, képfeldolgozás .. Felfogás (Felismerés, Megismerés, Megértés) • Szegmentálás Hogyan tagolható a látvány régiókra vagy objektumokra? • Aggregáció Hogyan kapcsolhatók egybe a részek? • Bizonytalanság Hogyan értelmezhetők a bizonytalan részei a látványnak? • Változatlanság és kategóriák Minden egyes absztrakt kategóriának számtalan megjelenési formája lehet a látványban. Hogyan lehet az egyformákat, melyek a kategóriát jellemzik, elkülöníteni? 2/ 37 . dr.Dudás László n Robotika • Ipari robotok érzékelő rendszereinek, beavatkozó szerveinek, tanítási lehetőségeinek, adaptív képességeinek fejlesztése tartozik ide, szoros kapcsolatban a mesterséges látással. • A robot témakör azért fontos a mesterséges intelligencia számára, mert a robot rendelkezik az ágenstől is elvárt érzékelés, beavatkozás képességekkel a szenzorai, manipulátor-karjai, kezei révén. • A robotvezérlő intelligenciájának növelésével nemcsak emberhez hasonlóan gondolkodó, Turing tesztet teljesítő gépi intelligencia jöhet létre, hanem az emberhez hasonlóan cselek- vő, humanoid, emberszerű gépi intelligencia is. • Az ily módon létrejövő gépi intelligencia hasz- nosíthatósága (és veszélyessége) is megnő. Boilerplate, mechanikus robot, 1879 http://www.bigredhair.com/boilerplate/soldier/index.htmlM e s t e r s é g e s n Sprawlita • Lépegető bogár-robot 6 lábbal • Három testhossz/másodperc sebességgel mászik, akár akadályokon át is. 2/ 38 . dr.Dudás László http://www-cdr.stanford.edu/biomimetics/documents/sprawlita/sprawlita.htmlM e s t e r s é g e s n Boadicea • Kisméretű pneumatikus mászó robot • Hat lába egyenként három szabadságfokú. http://www.ai.mit.edu/projects/boadicea/boadicea.html 2/ 39 . dr.Dudás László 2/ 40 . dr.Dudás László n CONRO • Miniatűr újrakonfigurálható robot • Azonos modulokból áll, amelyeket arra lehet programozni, hogy megváltoztassák a topológiájukat a környezetben adódó olyan kihívásokhoz, mint például egy akadály. • Az alaptopológia egyszerű kígyó alak, de a rendszer képes újrakon- figurálni magát hogy lábakat növesszen, vagy egyéb speciális nyúlványokat. Minden egyes modul tartalmaz egy CPU-t, memóriát, elemet, micro-motort és változatos szenzorokat és képességeket, köztük látást, huzalnélküli kapcsolatot és a dokkolás szenzorait. http://www.isi.edu/conro/ 2/ 41 . dr.Dudás László n GRACE: A Társasági Robot • GRACE egy mobil robot, kifejező arccal és hatalmas mennyiségű szenzorral. A szenzorok között találunk mikrofont, tapintó szenzorokat, infravörös érzékelőket, hangérzékelőt, letapogató lézert, sztereo kamerapárt és egy színes zoom-olható kamerát. Tud beszélni egy kiváló beszédszintetizátorral és megérti a válaszokat a mikrofonja és beszédfelismerő szoftvere révén. • GRACE elment egy konferenciára, sorban állt (egy előtte álló hölgyet kitúrt), regisztráltatta magát, majd megtartotta a magáról szóló előadást. http://www.palantir.swarthmore.edu/GRACE/M e s t e r s é g e s n BIP a lépegető robot • A 15 szabadságfokú robot két lábon jár. 2/ 42 . dr.Dudás László http://www.inrialpes.fr/iramr/Orccad/Presentation/frame-eng.htmlM e s t e r s é g e s n A HONDA humanoid robotja • A honda robot igen fejlett mozgásképességgel bír. • Indul a humanoid robotok labdarúgó világbajnokságában is. 2/ 43 . dr.Dudás László http://world.honda.com/robot/ n Autonóm jármű • Jellemzők: • A vezető ébrenlétének figyelése • Automatikus útkövetés • Automatikus akadályérzékelés és kikerülés • Autonóm vezérlés egy úttalan vidéken. http://www.syseng.anu.edu.au/rsl/car/ 2/ 44 . dr.Dudás LászlóM e s t e r s é g e s n Rubik kocka kitekerő robot • Jellemzők: • Lego robot alkatrészekből készült. • Maximum 40 lépésből megoldja a feladatot. http://jpbrown.i8.com/cubesolver.html 2/ 45 . dr.Dudás László 2/ 46 . dr.Dudás László n Beszédfelismerés • Cél: Az emberi beszéd gép által kezelhető, szöveges formára alakítása, végső célként, a nyelvfeldolgozással egyesítve a beszélt nyelv gépi megértése céljából. • Kezdeti eredmények: szűk szókincs, vagy ugyanazon beszélő esetén nagyobb szókincs felismerése. • Az emberi nyelvek kb. 50 fonémát, beszédhangot különböztetnek meg. • Szegmentálás, szavakra bontás à gond: a beszéd szavai egybefolynak. • A fonémák és a szavak leírására használt betűk között nincs teljesen egyértelmű megfeleltetés à gond. (Pl: eltérő fonémák, azonos betűk: Mondd, Zsanett, kell findzsa? Vagy: azonos fonémák, eltérő betűk: Mi hájjal kenjük a kenyeret, Mihály.) 2/ 47 . dr.Dudás László n A hangjel feldolgozása Cél: az információ csökkentése és a jellemzők kiemelése. Lépések : • Mintavételezés, kvantálás • Jellemzők kinyerése, keretekben, azonos időintervallumokban • Vektorkvantálás: a jellemzők hiperterének régióihoz rendelése a keretek jellemzővektorainak. 2/ 48 . dr.Dudás László n A hangjel feldolgozása .. • A beszédfelismerés célja a beszélőktől független, de a beszédre jellemző paraméterek kinyerése • A beszélőfelismerés ezzel szemben éppen a beszélőkre jellemző paraméterek kinyerését jelenti. • A szavak egyértelmű felismerése további statisztikai, illetve valószínűségi adatok felhasználását kívánja meg. • A legjobb rendszerek a szavak több, mint 95%-át jól ismerik fel. • A beszédfelismerő rendszerek statisztikai, valószínűségi adatait általában betanítással adják meg. n A legjobb beszédfeldolgozó rendszerek • A SpeechStar programcsomag, benne a Dragon NaturallySpeaking beszédfelismerővel • Az IBM ViaVoice programja • Lemut & Hauspie Voice Xpress programja Http://www.dragonsys.com/ http://www-3.ibm.com/software/speech/desktop/w8-win.html 2/ 49 . dr.Dudás László 2/ 50 . dr.Dudás László n Természetes nyelvek feldolgozása • Cél: Az emberi nyelv (írott formájának) megértése. Szükséges az MI eszközök és az ember közvetlen kapcsolatához. Idetartoznak a természetes nyelvű interfészek és a gépi fordítás is. Dan Jurafsky, James H. Martin, Keith Vander Linden, Daniel Jurafsky: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition 2/ 51 . dr.Dudás László n Természetes nyelvek feldolgozása .. • Példák: ELIZA (Joseph Weizenbaum, MIT, 1966) • Ember - gép párbeszédet valósított meg. A gép egy pszichológust utánoz, aki megpróbálja megérteni az ember problémáit. Valójában az ember válaszainak kulcsszavait érzékelve típusszöveget, egyszerű mintaillesztésen alapuló szövegrész-cserét alkalmazott. Hasonló programot írt K.M.Colby az 1960-as évek közepén. Valódi célja a Turing teszt teljesítésének megpróbálása volt, sikertelenül. A terminálokon folytatott párbeszéd például így festett: Orvos: Hogyan tudnék segíteni? Páciens: Nem tudom. Orvos: Próbáljon mondani róla valamit! Páciens: Nem tudok. Orvos: Ki tudná ezt fejteni részletesebben? Páciens: Beteg vagyok és fáradt. Orvos: Van elképzelése, hogy miért? Páciens: Igen, öreg vagyok. Orvos: Folytassa, kérem! Páciens: Úgy érzem, elvesztettem minden érdeklődésemet. Orvos: Mondjon többet ezekről az érzésekről! Páciens: Van arról is elképzelésem, miért érzek így. Orvos: Biztosan van. 2/ 52 . dr.Dudás László n Természetes nyelvek feldolgozása .. • Példák: SHRDLU (Terry Winograd, 1972) • Egy mértani testekből (kockák, gúlák, stb.) álló mikrovilágot hozott létre, melynek elemeit egy robot az ember írásos parancsainak megfelelően manipulálhatta. pl.: Ember: "Keress egy hasábot, amelyik magasabb, mint az, amelyiket a dobozba raktál !" Robot: "Rendben." Ember: "Megérintettél egy gúlát, mielőtt a zöld hasábot a kis kockára tetted ?" Robot: "Igen, a piros színűt." . . A rendszernek a kockák mikrovilágáról egy belső leképezése volt, és azt felhasználva, látszólag megértette az ember mondatait. 2/ 53 . dr.Dudás László n Természetes nyelvek feldolgozása .. • A Loebner - díj • Hugh Loebner 1990-ben 100 000$-os díjat és egy arany medált tűzött ki annak a nyertesnek, akinek a beszélgetőprogramja elsőként teljesíti a Turing tesztet. Egy 2000$-os kisebb díjat és egy bronz medált minden évben elnyer az a program amely a legszínvonalasabb párbeszédet folytatja emberrel. • A nyertes 2001-ben (is) Richard Wallace amerikai programozó volt. Beszélgető- robotja kipróbálható az Interneten. • További chat-robotok találhatók a http://alice.sunlitsurf.com/live.html címen. 2/ 54 . dr.Dudás László n Számítógépes fordítás .. • A természetes nyelvek feldolgozása nagy jelentőségű a számítógépes fordítás, tolmácsolás megoldásához is. Az emberi nyelv összetettsége miatt a megoldást csak az emberi intelligenciával, tudással összemérhető képes- ségű géptől várhatjuk a jövőben. Szűk területeken biza- lomkeltő részeredmények vannak. • Néhány on-line elérhető fordítóprogram címe: http://babelfish.altavista.com http://www.babylon.com http://www.freetranslation.com A hazai Morphologic cég is elkészítette fordítóprogramját, melynek előnye, hogy a magyar nyelvet is ismeri. • A természetes nyelvek megértésének problematikájára jól rávilágít egy mondat értelmezésének 4 szintje: » » » » Szintaktikai Szemantikai Pragmatikus Intencionális. 2/ 55 . dr.Dudás László n Számítógépes fordítás .. • A mondat jelentésének négy szintje Az egyes szintek tartalmát legjobban egy példa kapcsán mutathatjuk be: – Éva: Tudod, hogy Viktor ugyanúgy dohányzott, mint te? – Imre: Nem. Miért, mi van vele? – Éva: Tüdőrák. Feldobta a bocskorát. – Imre: Szomorúan hallom. • Figyeljük azt a mondatot: "Feldobta a bocskorát." – Szintaktikailag (formailag) egy múlt idejű állítmányt és egy tárgyat figyelhetünk meg. – Szemantikailag (tartalmilag) azt jelenti: Felhajította a lábbelijét. – Pragmatikus (valóságos) jelentése: Meghalt. – A mondat intencionális (szándékolt) jelentése, célja a szövegkörnyezettel együtt Imre figyelmét felhívni, hogy ne dohányozzon annyit. • Az ELIZA program gyakorlatilag csak a szintaktikai szinten értette a páciens válaszait. 2/ 56 . dr.Dudás László n Számítógépes fordítás .. • A gépi fordítás szintjei a fordítás minősége szerint a következők: – tájékozódó fordítás (information acquisition) – tényszerű közlésekre vonatkozó fordítás (denotative translation) – igényes fordítás (connotative translations). • A gépi fordítás az automatizáltság szintje szerint lehet: – teljesen automatikus (fully automatic machine translation) – emberi segítséggel készülő (human assisted machine translation) – gépi segítséggel készülő (machine assisted human translation) • Természetes nyelvű interfészek • A természetes nyelvű interfészek különféle számítógépes alkalmazások kezelését könnyítik meg azáltal, hogy a kezelő a megszokott szavakkal, mondatokkal kommunikálhat a szoftverrel. Természetes nyelvű interfészeket fejlesztettek ki: jól strukturált adatbázisokhoz, szimulációs modellekhez, szakértői rendszerekhez, helybiztosító rendszerekhez és szöveges adatbázisokhoz. 2/ 57 . dr.Dudás László n Korlátozás kielégítés • A korlátozás kielégítési feladat a benne szereplő változók értékeit korlátozza. A korlátok megadhatók az értékek felsorolásával, explicit módon, vagy egy kifejezéssel, implicit módon. A változók által felvehető értékek száma véges. • A feladat megoldása alatt a változók olyan értékhalmazát értjük, melyek kielégítik az összes korlátozást. • Megelégszünk egyetlen megoldással, bár gyakran több megoldás is lehetséges. Egyes esetekben az összes megoldást meg kell találnunk. • A korlátozás kielégítés kedvenc feladata volt a 8 vezér probléma: úgy helyezzünk el a sakktáblán 8 vezért, hogy ne üssék egymást. • A megoldó módszerek egyike a lehetőségtér állapotait tartalmazó fagráf „mélységben először” technikával történő bejárása. • A megoldáskeresés gyorsítható a korlátozás propagáló, azaz a korlátokon kívül eső, megoldást biztosan nem adó pontok kizárásával. 2/ 58 . dr.Dudás László n Cselekvési tervek generálása • A cselekvéstervezés lényege hatékony célirányos tevékenységsorozat generálása valamilyen, a világban felmerülő feladat megoldására. • A megoldás meghatározására általános, azaz a problémától független valamint alkalmazás-specifikus módszerek közül választhatunk. • Megoldási módszerek: • keresés - nehezíti a nagy elágazási tényező, s a talált megoldások a cselekvések egyszerű szekvenciái lehetnek csak. • Szituációkalkulus - nehezen irányítható és könnyen adódnak nem megfelelő lépések is. (A szituációkalkulus az elsőrendű logika módszerét alkalmazza a világ egy adott állapotára, azaz egy szituációra.) • A cselekvési terv a két módszer együttes alkalmazásával áll elő, a finomító tervezési szakasz előre/hátra láncoló technikájánál a keresés jut szerephez. • Végeredményként egy olyan cselekvésegyüttes jön létre, amely végrehajtható és a világot a megadott korlátokat kielégítő új állapotba viszi át. 2/ 59 . dr.Dudás László n Szakértőrendszerek • Egy szakértőrendszer olyan eszköz, amely probléma specifikus ismeret megértésére képes és intelligensen használja a tématerület ismeretanyagát egy tevékenység különböző megvalósítási útjainak felvetéséhez. A szakértőrendszerek nem csak az ismeretátadás technikáit alkalmazzák, hanem analitikus, elemző eszközöket is az ismeret kiértékelésére, valamint tanulási technikákat. Példák olyan területekre, ahol szakértőrendszert alkalmaznak: • Repülés: repülőgépmotor-diagnosztika: helikopter javítás, Pl.: NAVEX, • Mezőgazdaság: Almáskertek gondozása (POMME), • Kémia: Kémiai reakciók tervezése (SYNCHEM), Szerkezetértelmezés (DENDRAL), • Számítógépek és kommunikáció: VMS dump fájlok elemzése rendszerkiakadás után (CDX), • Oktatás: Tervezők oktatása konstrukciós tervezés ellenőrzésére (DECGUIDE), • Vállalatvezetés: Üzlet hatékonyságelemzése (GURU), • Egészségügy: Fertőző betegségek diagnózisa (MYCIN), • Mérnöki technika, gépészet: Motoralkatrészek tervezése, stb. 2/ 60 . dr.Dudás László n Szakértőrendszerek: a DENDRAL • Ma is használt szakértőrendszer, több, mint 50 tudományos cikket írtak a vele elért felfedezésekről. • Célja: Hipotézis felállítása egy vegyület lehetséges molekuláris felépítésére, atomszerkezetére. • Ha egy vegyész egy ismeretlen vegyülettel találkozik, első feladata, hogy meghatározza az összetevő atomokat és azok relatív arányát. Ehhez analitikai tesztekre és kísérletekre van szüksége. Az egyik gyakran alkalmazott műszer a tömegspektrométer. A DENDRAL is felhasználja a vegyület tömegspektrumát. • Egy vegyület kémiai képletét egyszerű megtalálni, de szerkezeti képletének meghatározása speciális tudást igényel. 2/ 61 . dr.Dudás László n Szakértőrendszerek: a DENDRAL .. • A DENDRAL három részből áll: • Szerkezetgeneráló rész, az összegképletből a lehetséges szerkezeti képletet generálja; • Spektrumjósló, a szerkezeti képletből a megfelelő jósolt tömegspektrumot származtatja, és összehasonlítja az aktuális adatokkal; • Szerkezetjósló, amely résszerkezeteket származtat le az adatokból és lehetetlen szerkezeteket kizár. Ez a rész felel meg a szakértő tudásának ( 1. + 2. elvileg elég, de kombinatorikus robbanás miatt nem lehet az összes szerkezetet generálni és vizsgálni. pl.:C 6 H 13 NO 4 kb.10000 lehetséges szerkezettel rendelkezik.). 2/ 62 . dr.Dudás László n Szakértőrendszerek: a DENDRAL .. Relatív frekvencia Tömegspektrum 0 20 40 60 80 tömeg/töltés i. szabály: ha létezik egy magas csúcs a 71 tömeg/töltés helyen és ha létezik egy magas csúcs a 43 tömeg/töltés helyen és ha létezik egy magas csúcs a 86 tömeg/töltés helyen és ha van néhány csúcs az 58 tömeg/töltés helyen akkor az N-propil-keton 3 szerkezet jelenlévőnek feltételezhető. n Mesterséges neurális hálózatok • Az MI egyik nem új, de egyre nagyobb jelentőségű területe az emberi agy neuronjainak modellezésével létrehozott neurális hálók kutatása, ill. alkalmazása. • A neurális hálózatot szokták kapcsolati modellnek (connectionist model) nevezni a működésben domináló kapcsolatok és nagyon erős párhuzamos működés miatt. 3 fő részük: – a neuronok – a hálózati topológia (kapcsolódások) – a tanulási algoritmus. 1. http://ei.cs.vt.edu/~history/NEURLNET.HTML 2/ 63 . dr.Dudás László 1. 2/ 64 . dr.Dudás László n Mesterséges neurális hálózatok .. képességei alkalmazására példa [17] • mintafelismerés • • általánosítás trendek megjóslása • viselkedés, kimenetel megjóslása • kiértékelés • • • • • • • • nem pontos adatok elfogadása szűrés gyors működés szövevényes viszonylatok felfogása előnyös leegyszerűsítés optimalizáló képesség hatalmas adatmennyiség elemzése extrapolálás tengeralattjárók felismerése sonar-jelek alapján a valós állapot felbecsülése döntés részvényvásárlásról, vagy eladásról a műtét kimenetelének megjóslása kölcsönigények elfogadása, elutasítása optikai karakterfelismerés videojelek zavarmentesítése robotkar vezérlése gyógyászati "szakértőrendszer" vezérlés az űrben repülőjáratok ütemezése biztosítási igények összevetése termelési problémák diagnózisa. n Mesterséges neurális hálózatok .. Egy konkrét neuronháló alkalmazás: Alkatrészcsaládok kialakítása [18] • • • Adott m gép és n alkatrész, valamint egy mxn méretű mátrix, melyben 1 áll az ij helyen, ha az i. gépen meg kell munkálni a j. alkatrészt. A neuronhálónak a feladata egy ilyen mátrixhoz, mint input mintához egy olyan output mintát rendelni, melynek elemei megfelelnek egy-egy alkatrészcsaládnak. Egy család alkatrészeit az jellemzi, hogy ugyanazon a néhány gépen - azaz egy gépcsoporton - minden műveletük elkészíthető. Műveleti mátrix 2/ 65 . dr.Dudás László 2/ 66 . dr.Dudás László n Mesterséges neurális hálózatok .. Egy konkrét neuronháló alkalmazás: Alkatrészcsaládok kialakítása .. • A megoldás kihasználja a versengő neuronhálók azon tulajdonságát, hogy a neuronokat képesek osztályokba rendezni, ezzel gyakorlatilag megoldva a csoporttechnológia (Group Technology) alapfeladatát. • Előnyök: • könnyű alkalmazhatóság, • új alkatrész könnyen bevonható, • nagy méretű feladatok időigénye nem nő exponenciálisan. http://www.e-orthopaedics.com/sakura/neusak.htm Ez a háló nem versengő háló. 2/ 67 . dr.Dudás László n Adatbányászat Az adatbányászat az adatbázis alkalmazások egyik területe amely rejtett összefüggések, mintázatok után kutat nagy adathalmazokban. Például, segíti a szolgáltató vállalatoknak megtalálni az azonos érdeklődésű vevőket. Az adatbányászat kifejezést rendszerint helytelenül használják olyan szoftverek meghatározására, amelyek új módon prezentálják az adatokat. Az igazi adatbányászati szoftverek nem csak az adatok prezentálását változtatják meg, hanem korábban nem ismert összefüggéseket is feltárnak az adatok között. • Az adatbányászat csak pár évtizedre visszatekintő múlttal bíró, dinamikusan fejlődő új kutatási irányzat. Célja az adatbázisokban található ismeretekből a tudás kinyerése, ezáltal konvergál a mesterséges intelligencia tudománya felé. • Az adatbányászat kezdetben az általánosan alkalmazott statisztikai módszerek egyszerűsítésére és automatizálására fektette a hangsúlyt. Ez az irányultság az évek folyamán megváltozott. Sok új adatbányászó algoritmus és eszköz keletkezett. Ezek összevetéséhez komoly statisztikai felkészültség kell. • Egyre több intelligenciát építettek be a programokba a mesterséges intelligencia többnyire jól ismert módszereit alkalmazva. 2/ 68 . dr.Dudás László n Adatbányászat Alkalmazott módszerek: • Felügyelt • Regressziós technikák • Legközelebbi szomszéd módszere • Mesterséges neurális hálók • Következtető (indukciós) szabályok • Döntési fák • Felügyelet nélküli • Klaszterezés • Önszervező neurális hálókM e s t e r s é g e s n Adatbányászat Kiemelkedő alkalmazásszállítók: • SAS • SPSS 2/ 69 . dr.Dudás László • Oracle • Angoss • HNC • Unica. SPSS Clementine 2/ 70 . dr.Dudás László n Az ötödik generációs számítógép projekt • Az MI és a szoftverfejlesztés területén végzett kutatások előrehaladásával világosabbá váltak az okok, hogy eddig (1970) miért nem tudtak megbirkózni a számítógépek az olyan feladatokkal, mint a mesterséges intelligencia tárgykörébe tartozó feladatok, ill. a párhuzamos feldolgozást igénylő feladatok. • Maguk a feldolgozási módszerek is világosabbak lettek. Felmerült annak a lehetősége, hogy további kutatásukkal olyan számítógép építhető, amely a felhasználó számára már természetesebben megközelíthető. • A japánok hirdették meg az 5. generációs számítógép létrehozására irányuló projektet. Ebben célul tűzték ki, hogy az 5. generációs számítógépnek az átlagos emberi tudást kell tárolnia . 2/ 71 . dr.Dudás László n Az ötödik generációs számítógép projekt .. • Az eredmények amelyekre támaszkodtak: • VLSI technológia, mint lehetőség: szilícium alapú logikai kapuk néhány száz picosecundum alatti jeltovábbítással ( 1 picosec = 1 sec / 1000millió; a fény 100 picosec alatt 3 cm-t tesz meg.); • szupravezetők; • optikai technológia (képfeldolgozáshoz természetes); • párhuzamos feldolgozás, pl. a J.B.Dennis által kidolgozott adatvezérelt működés, mely lehet: • adatmeghajtású (ha van input, elvégzi a számítást), • igénymeghajtású (a számítást akkor végzi el, ha már szükség van az outputra); • párhuzamos számítási algoritmusok, -programozás; • tudásszemléltető és feldolgozó nyelvek: LISP, PROLOG. 2/ 72 . dr.Dudás László n Az ötödik generációs számítógép projekt .. 1. természetes nyelv, nyelvi és grafikai alkalmazás 2. magasszintű elemzőnyelv 3. tudásbázist kezelő rendszer 4. intelligens interfészkezelő rendszer 5. belső nyelv 6. problémamegoldó és következtető rendszer 7. külső interfész az alap szoftverrendszerhez 8. tudásbázist kezelő rendszer 9. problémamegoldó és következtető rendszer 10. intelligens interfészrendszer 11. alap szoftverrendszer 12. tudásbázisú gép 13. relációs algebra 14. relációs adatbázisrendszer 15. problémamegoldó és következtetőgépek 16. predikátumkalkulus típusú nyelv 17. absztrakt adattípust támogató rendszer 18. párhuzamos adatáramlásos rendszer 19. fejlett Neumann- rendszer 20. intelligens interfész gép 21. hardverrendszer 22. elosztott funkciójú hálózati rendszer 23. VLSI architektúra. T.Moto-oka - M.Kitsuregawa: Az ötödik generációs számítógép Műszaki Könyvkiadó Budapest, 1987. p68. 3/ 1 . dr.Dudás László n A tudás, mint központi fogalom A tudás formalizálásának szükségessége Tudásszemléltetési modellek Tudásfeldolgozás Szabályalapú tudásszemléltetés • A tudás, mint központi fogalom Christopher F. Chabris: tudás = az elvégzendő feladat végrehajtásában hasznosnak bizonyuló bármely ismeret • Bár az intelligenciát a vele foglalkozó tudósok sokféleképpen definiálják, abban egyetértenek, hogy az emberi intelligenciával összemérhető képességű gépi intelligenciának rendelkeznie kell az ember általános tudásával. • Az ilyen tudással, ismerethalmazzal bíró mesterséges rendszer intelligenciája ezen ismerethalmaz szervezésétől függ. n A tudás, mint központi fogalom .. • A tudás szervezésének, reprezentálásának lényege: azok a formai (szintaktikai) és tartalomra vonatkozó (szemantikai) szabályok, melyeket az adott tudásszemléltetési forma rögzít. • Szintaktika = • formai szabályok, a formalizáláshoz alkalmazható elemek, szimbólumok készlete, • a formailag helyes összetett egységek szerkezete. • Szemantika= • a tartalomra vonatkozik, • megadja a formai elemek, egységek kezelésének tudnivalóit, az alkalmazásukra vonatkozó szabályokat. • Ezek a szabályok a természetes formában rendelkezésre álló tudáselemek gépi ábrázolásához is fontosak. 1. http://www.workonenw.com/ets.htm 3/ 2 . dr.Dudás László 1. 3/ 3 . dr.Dudás László n A tudásszemléltetés szükségessége • A valós világ objektumairól, azok viszonyáról, kapcsolataikról rendelke- zésre álló ismeret ritkán adódik a számítógép által kezelhető formában. • Ahhoz, hogy a számítógép az ismereteket tárolni, kezelni tudja, azok kódolására van szükség. • A kódolás módja nagyban kihat a gép általi feldolgozás gyorsaságára, hatékonyságára, a tárolt tudáson alkalmazható gépi műveletekre, mint pl. keresések, illesztések, összehasonlítások, láncolások, kapcsolatok kialakítása, stb. • A megfelelő ismeretstruktúrát alkalmazó tudásszemléltetés az MI kulcskérdése. Oka: korlátos gépidő és tárkapacitás. 3/ 4 . dr.Dudás László n A tudásszemléltetés szükségessége .. • Megfelelő színvonalú működés reálisan csak párhuzamos hardverrendszerektől remélhető. • Súlypontáthelyeződés Statikus ismeretek gyűjtése önszervező ismeretábrázoló modellek • Tanulóképesség fontossága • Előtérbe kerül a szimbolikus jelleg • A fogalom jelentése: mindaz, ami hozzá asszociálódott • Asszociáció létrejöttének feltétele: térbeli, időbeli közelség. 3/ 5 . dr.Dudás László n A tudásszemléltetés szükségessége .. • A tudatalatti működés modellezése. • Ideális esetben az MI öntudatra ébredését megelőző szintű működése ugyanannak az öntanuló rendszernek a kevesebb ismeret birtokában megtestesített fejlődési szintje. • A mai MI még a tudatalattijában létezik csak. 3/ 6 . dr.Dudás László n A tudásszemléltetés elvárt jellemzői Patrick Winston szerint A jó tudásszemléltetés az MI feladatok megoldásánál fél siker. 1. A fontos dolgokat világosan adja meg. 2. Fedje fel a természetes korlátokat, megkönnyítve a számítások néhány fajtáját. 3. Legyen teljes. 4. Legyen tömör. 5. Legyen átlátható számunkra. 6. Legyen alkalmas gyors feldolgozásra. 7. Rejtse el a részleteket, de tegye elérhetővé azokat szükség esetén. 8. Létezzen rá számítógépi eljárás. 3/ 7 . dr.Dudás László n Tudásszemléltetési módszerek • • • • • • • Szimbolikus logika Szabályalapú rendszerek Szemantikus hálók Keretek, script-ek Neurális hálózatok Modellalapú Hibrid. • Hibrid rendszerekre példa a KEE, BABYLON, SRL+, ART fejlesztő környezet ftp://ftp.gmd.de/gmd/ai- research/Software/Babylon/doc/overview.pdf 3/ 8 . dr.Dudás László n A tudásfeldolgozási folyamat vízesésmodellje Beazonosítás Probléma- jellemzők beazonosítása Koncepciókészítés Elvárások Koncepció- keresés a tudás reprezentálására Újraformulázás Formalizálás Koncepciók Újratervezés A struktúra megtervezése a tudás szervezésére Implementálás Struktúra A tudásábrázoló szabályok megalkotása Finomítás Tesztelés Christopher F. Chabris: Artificial Intelligence & Turbo Pascal Dow Jones-Irwin, Illinois,1987. p395. Szabályok A tudást szervező szabályok tesztelése 3/ 9 . dr.Dudás László n Tudásfeldolgozás A tudásfeldolgozás az a folyamat, amelyben a szintetizált tudást a számítógépbe juttatjuk 1. abból a célból, hogy a problémákat a tudásbázison végzett elektronikus szimbolikus manipulációval és következtetéssel megoldjuk. Egyben az a tudomány, mely a szakértőrendszerek készítésével foglalkozik. • A tudásfeldolgozással (Knowledge Engineering) a tudástechnológus (Knowledge Engineer) foglalkozik. • A gazdaságos és hatékony ismeretalapú rendszer létrehozásának kulcskérdése a megfelelő tudásfeldolgozás. • A tudásalapú rendszerek fejlesztésének egyik első teendője a tudásgyűjtés (Knowledge Acquisition). Egyben ez a tudástechnológus munkájának egyik legfelelősségteljesebb része is. 1. www.postmodern.com/~fi/morbid/ doc/amman_death-tree.htm A fejezethez felhasznált irodalom: Deborah D. Wolfgram - Teresa J Dear - Craig S. Galbraith: Professional John Wiley & Sons,New York, 1987. Expert Systems for the Technical 3/ 10 . dr.Dudás László n Tudásgyűjtés, tudáskinyerés Tudásgyűjtés, tudáskinyerés az a folyamat, amelynek feladata beazonosítani, kinyerni, dokumentálni és elemezni a szakterület szakértőjének információ- feldolgozó tevékenységét abból a célból, hogy meghatározásra kerüljön egy szakértőrendszer tudásbázisa és következtető automatája. • A tudáskinyerés négy fő szakasza: 1. Az előzetes tudás és problématartomány feltárása 2. Az információforrások beazonosítása 3. A részletes tudás kinyerése a forrásokból 4. A kinyert tudás elemzése, kódolása és dokumentálása. 3/ 11 . dr.Dudás László n Előzetes tudásfeltárás Célja: • • • • • • • a rendszer által kezelendő problémák tartományának, a problématartomány jellemzőinek, a tématerület tudásmennyiségének behatárolása, a felhasználók elvárásainak megismerése, néhány tipikus következtetési fordulat megismerése, a szakértők szakterülettel kapcsolatos elképzeléseinek megismerése, fő szabályok és koncepciók definiálása. Eszközei: • • előzetes archívum-kutatások, konzultációk szakértőkkel. 3/ 12 . dr.Dudás László n Előzetes tudásfeltárás .. • A háttér felkutatása • A tudáskinyerésnek előfeltétele • Célja: • A szakterület – háttértudásának – szókincsének – szokásos elveinek megismerése. • Források: • szaklapok, • könyvek, • kezelési leírások, • egyéb dokumentumok, • konzultációk szakértőkkel, felhasználókkal. 3/ 13 . dr.Dudás László n Előzetes tudásfeltárás .. • A problématartomány behatárolása • Az alkalmazási tartomány felosztása alterületekre: „Oszd meg és uralkodj!” • Egy alterület a problémák, adatbázisok, szakértelem független rendszere • Minden alterületre meghatározandó a problémák elsődleges típusa, az alkalmazás jellegzetességei, stb. • Prototípus-tartomány választása • Célja: bizalomszerzés és tapasztalatszerzés • Oka: a szakértőrendszerek kifejlesztése bonyolult és időigényes. • Előnyös: olyan alterület kiválasztása, amely – viszonylag független, – a felhasználó számára hasznos. 3/ 14 . dr.Dudás László n Előzetes tudásfeltárás .. • A dokumentálás szükségessége: A Tudás Kézikönyv A kezdeti feltáró munka végén a tudástechnológusnak egy dokumentummal kell rendelkeznie, egy kézikönyv formájában, melynek a következőket kell tartalmaznia: • Az általános problémaleírást • Kik a felhasználók és milyen elvárásokkal • Alproblémákra és résztartományokra való lebontást a későbbi tudáskinyeréshez • Egy részletesebb leírást a résztartományokról, melyet fel lehet használni a prototípusfejlesztésben • A referencia dokumentumok nyilvántartását • A szakterület terminológiájának, elveinek, szakkifejezéseinek listáját • A prototípus kifejlesztésében közreműködő szakértők nevét • Néhány ésszerű teljesítménymutatót a rendszer számára • A tipikus következtetési módszer leírását. 3/ 15 . dr.Dudás László n Információforrások • A szakterület szakértőjének kiválasztása A szakértő az, aki speciális szakértelmet birtokol, hordoz magában, vagy mutat, illetve olyan tudást, melyet gyakorlással, vagy tapasztalással szerzett. • A tartomány szakértőjének hitelessége A szakértőnek hitelesnek kell lennie – a felhasználók előtt, – a projekt team előtt, – a szakértők közössége előtt, – a szervezet vezetése előtt. • A szakértő motiválása • A sikeres tudáskinyerés záloga: „ a tudás hatalom” à elvesztése... • Helyi és kozmopolita szakértő à eltérő motiválást igényelnek. 3/ 16 . dr.Dudás László n A tudáskinyerés • A tudáskinyerés tárgya A tudáskinyerés tárgyát • előzetes tudásra és • részletes tudásra bontjuk. Az előzetes tudás kinyerése • Az előzetes tudáskinyerés tárgya a bevezető interjúk és konzultációk alatt a következő: • Az alap-, gyakran primitívnek nevezett terminusok és elvek beazonosítása • A rendszer tipikus inputjainak és outputjainak behatárolása • A tipikus megoldások, vagy megoldási osztályok behatárolása • A rendszer kezdeti implementációjához problémakezelő stratégiák találása. 3/ 17 . dr.Dudás László n A tudáskinyerés .. A részletes tudás kinyerése • A részletes tudás kinyerésének tárgya a terület szakértőjétől a "privát" tudásának megszerzése, mely tudás több éves tanulást és tapasztalatot tükröz. Ez magába foglalja: • A változatos adatok és szabályok közötti viszonyok beazonosítását • A szabályok hierarchiájának beazonosítását • Az adatok relatív értékének és fontosságának megítélését • Az adatok bizonyosságának és relatív valószínűségének megítélését • A szakértő közelítései alapjának meghatározását • A feladatok prioritásának és sorrendjének megítélését • A szabályok és a következmények közötti konfliktusok megoldásának meghatározását 3/ 18 . dr.Dudás László n A tudáskinyerés .. A részletes tudás kinyerése .. Ez magába foglalja továbbá: • A problémamegoldás alternatív lehetőségeinek felismerését • A következtetésekben elvégezhető ésszerűsítések meghatározását • Részletes válaszokat a várt és a váratlan szituációkra • A különféle szabályokban, eredményekben és adatokban való hit fokának megadását • A különféle célok és részcélok input követelményeinek megértését • Megfelelő teljesítménymércék meghatározását. n A tudáskinyerés .. Tudáskinyerési technikák A technikák öt fő osztályát alkalmazhatjuk: interjú, protokoll elemzés, végigvezetés, kérdőív és szakértői beszámoló. • Interjú Különösen az előzetes információ kinyerésére előnyös. Két típusa: strukturálatlan és nyitott-végű. • A strukturálatlan interjúnál a tudástechnológus engedi a szakértőnek, hogy elveket, terminológiát mutasson be és meg- határozza az interjú menetét. A tudástechnológus csak rögzít. 1. • A nyitott-végű interjú feltételezi, hogy a tudástechnológus rendelkezik előzetes háttér-információkkal. A tudástechnológus irányítja az interjú menetét kérdésekkel, de a szakértő szabadon válaszolhat, vagy kitérhet a válaszadás elől. Egyéb: csoportos interjú. 3/ 19 . dr.Dudás László 1. www.udel.edu/PR/UpDate/ 01/12/whatsup.html 3/ 20 . dr.Dudás László n A tudáskinyerés .. Tudáskinyerési technikák .. • Protokoll elemzés Ez a leggyakrabban alkalmazott tudáskinyerési módszer a részletes tudás kinyerésére. A protokoll a szakértő információ-feldolgozó tevékenységének és döntéshozó viselkedésének lépésről - lépésre történő rögzítése. Számtalan speciális formája létezik. • Végigvezetés A végigvezetés is a tudáskinyerés általánosan alkalmazott formája. A tudástechnológus megkéri a szakértőt, hogy vezesse őt végig a feladat megoldásában és felügyelje. • Kérdőívek – szabad-végű, – rövid válaszos – erőltetett válaszos. 3/ 21 . dr.Dudás László n A tudáskinyerés .. Tudáskinyerési technikák .. • Szakértői beszámoló A szakértő saját írásos összegzése a problémamegoldó viselkedéséről. Kétféle forma: • A szakértő megadja: - feladat megközelítési módszerét, - stratégiáját, - a szabályokat, melyeket használ, - a szükséges adatokat, - az eredményt. A tudástechnológus: - feldolgozza a beszámolót, - kinyeri az ismereteket. • A szakértő formálisan, például folyamatábra alakjában adja meg az általa követett döntéshozás lépéseit, mentesítve ezen feladat alól a tudástechnológust. A szakértői beszámolók alkalmazása korlátozott. 3/ 22 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása Ebben a fázisban a következőket kell elvégezni: formális módsze- rekkel elemezni kell a kinyert tudást, dokumentálni kell a probléma- területet érintő szabályokat, hálózatokat, viszonylatokat, jellemzőket. A dokumentálás helye a Tudás Kézikönyv. • Az elemzés négy tipikus lépése a következő • Átírás A szóbeli információk első írásos alakjának letisztázása, minden egyéb járulékos információt, például a technikai segédszemélyzet által rögzített vizuális anyagokat is beleértve. • Szövegrész-indexelés Lényege az átirat tagolása rövid szövegrészekre, melyeket indexekkel látnak el. Egy ilyen egység célszerűen megfelel egy tudáselemnek, azaz egy elemi feladatnak, állításnak, vagy adategyüttesnek. 3/ 23 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. Az elemzés további lépései: • Tudáskódolás Ebben a fázisban a tudást aszerint elemzik, hogy mivel foglalkozik, milyen típusú operátorokat, kiértékelési kritériumot és a választásokat és döntéseket megalapozó következtetéseket tartalmaz. Két fő kategória: a descriptív (leíró) és a procedurális (eljárásokra vonatkozó) tudás. – Descriptív tudás tagolása: Jelentések: Definíció; Axióma; Zsargon; Feltételezés; Hipotézis, elmélet; Modell; Analógia; Koncepció, elképzelés. Környezetek: Fizikai beállítás, elhelyezkedés; Alak, méret; Hely, pozíció; Időpont, időtartam, ütemezés; Szabályosság, periodikusság. 3/ 24 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. – Descriptív tudás tagolása .. Szabályok Függvény; Jellemző; Rendszerállapot; Korlát; Esemény; Operátor. Asszociációk Összefüggés, viszonylat; Egymásrahatások; Hierarchia; Hálózat, kapcsolódás; Megoldás. Erőforrások Adat; Eszköz; Tájékoztató. Tevékenységek Akció; Akció következménye; Akció következmény-visszacsatolás; Az akció tárgya; Az akció fogadója. 3/ 25 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. – Descriptív tudás tagolása .. Eredmények Cél; A hatékonyság mértéke; A siker kritériuma; Diagnózis. – Procedurális tudás Az ilyen tudás a problémamegoldásban alkalmazott eljárásokra, tevékenységekre vonatkozik. Tagolása: Problémadefiniálás A rendszermodell megfelelőségének kiértékelése A feladat alkalmasságának ellenőrzése Problémaelemzés/újrafogalmazás/analógiakeresés. Adat- és erőforrásgyűjtés Erőforrás-, ismeret-meghatározás Adatgyűjtés. 3/ 26 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. – Procedurális tudás tagolása .. Feladattervezés A probléma megoldásának tervezése, a lépések felsorolása Szakaszok/erőforrások a problémamegoldásban Rangsorolás, célfelállítás Keretek/korlátok felállítása Elképzelések körvonalazása Becslés/közelítés/előfeltétel meghatározása Előfeltételek egyszerűsítése Megoldáskereső technikák (előre, vagy hátraláncolás). Megoldóeljárás Feladat számbavétel/sorberendezés/megoldás Eszközhasználat/mérés Adatszelektálás/kiértékelés Hiányzó adatok helyettesítése Valószínűség beállítás Induktív/deduktív problémamegoldás Heurisztikus szabály, ökölszabály, emlékeztető szabály megfontolás; 3/ 27 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. Megoldóeljárás .. Szabály megbízhatóság/megfelelőség kiértékelés Szabály egymásrautalás, kihatás Szabályelőhívási-igény meghatározás Szabályelőhívási hatás, kővetkezmény meghatározás Állapotváltoztató akciók megfelelőségének/előfeltételének meghatározása Állapotváltoztató eljárás Megváltoztatott állapot felismerése Megítélés Konklúzió/megoldás/következmény meghatározás. Megoldás-kiértékelés Hatékonyságbeállítás mértéke Kritériumbeállítás (konfidenciaszint) Kritériumbeállítás (megbízhatósági szint) Kritériumbeállítás (valószínűségi szint) Kritériumkielégítés meghatározása. 3/ 28 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. Megoldás-beszámoló Döntés/ konklúzió igazolás A probléma megoldásának/az eredménynek bemutatása/igazolása. Példa tudáselem indexelésre: " A sikerre 75% esély van." tudáselemhez a 'Megoldás kiértékelés/kritériumbeállítás(valószínűség) ' megjegyzés kerül feljegyzésre a Tudás Kézikönyvbe. 3/ 29 . dr.Dudás László n A kinyert tudás elemzése, kódolása és dokumentálása .. • Dokumentálás Helye: a Tudás Kézikönyv. Részei: átfogó tartománylista, descriptív (leíró) tudás, procedurális (eljárásokra vonatkozó) tudás, szójegyzék. 3/ 30 . dr.Dudás László n Tudáskinyerési eszközök • A "tudáskinyerés szűk keresztmetszete” • Kimarad a tudástechnológus. • Példák alapján való következtetés Eszköze egy tanulóprogram elven működő szoftver, amely a szabályokat a szakértő által megoldott példafeladatokból nyeri. Szoftverek: RULEMASTER, EXPERT EASE, WIZARD. 3/ 31 . dr.Dudás László n Tudáskinyerési eszközök .. • Ismeretmegszerző eszközök Ezek következtetés alkalmazása nélkül, a szakértővel közvetlenül, interaktív módon együttműködve szerzik meg és strukturálják a tudást. Ismertebb rendszerek: ROGET, MORE, ETS. Egy ilyen rendszerrel kapcsolatos elvárások Richard Hill szerint a következők: • Közvetlen interaktív együttműködés a szakértővel tudástechnológus segítsége nélkül a teljes fejlesztési folyamat alatt • Korlátlan,vagy legalább a problémák egy tág köréhez való alkalmazhatóság • Betanító képesség, mely kiváltja a szakértő előzetes kiképzését, tájékoztatását • Elemzőképesség, mellyel a rendszer bővülése közben feltárhatók az inkonzisztenciák, ellentmondások, tudáshiányok • Sok tudásforrás egyesítésének képessége • Emberközeli interfész, pl. természetes nyelv használata, mely révén a rendszer használata élvezetessé válik • Képesség másféle, a szakterülethez megfelelő szakértőrendszer- eszközökkel való kapcsolódásra. 3/ 32 . dr.Dudás László n Gépi tanulás • Feleslegessé válik a szakértő is. • A szakértőrendszerek on-line adatbázisokat fognak letapogatni, könyveket, folyóiratokat és magazinokat fognak digitalizálni. Más számítógépes rendszereken tárolt adatokat elektronikus vonalon lehívnak, hogy származtassák, vagy aktualizálják az ismeretbázist, mindezt emberi közreműködés nélkül. (Vesd össze a korszerű keresőszerverek működésével, pl. Google.) • Az automatikus tudáskinyerés potenciális előnyei a következők: • Jobb eredményeket érhetnek, mint az emberek, különösen amiatt, hogy az információkeletkezés egyre nagyobb méretű és az információ egyre komplexebb, és ilymódon nagyobb szakértőrendszereket hozhatnak létre. • Csökkentik a magas költségű emberi munkaerő iránti igényt és a tudásbázisok kifejlesztéséhez szükséges időt. 3/ 33 . dr.Dudás László n Gépi tanulás .. • Napjaink tanuló algoritmusai: – AQ - Egy korai DNF tanulóalgoritmus. – Backprop - A szabványos multi-layer neurális háló algoritmus. – Bayes Indp - Egy egyszerű naív, vagy ”idióta" Bayes osztályozó. – Cobweb - Egy valószínűségi klaszterező. – FOIL - Egy első rendű Horn-klauza tanuló (Prolog és Lisp verzió). – ID3 - Egy döntési-fa tanuló számos sajátossággal. – KNN - Egy legközelebbi szomszéd (eset-alapú) algoritmus. – Perceptron - A korai egyréteges neurális háló algoritmus. – PFOIL - A FOIL propozíciós logikát használó verziója DNF tanulására. – PFOIL-CNF - A FOIL propozíciós logikát használó verziója CNF tanulására. – DList - A PFOIL-on alapú egyszerű döntési lista tanuló algoritmus. 3/ 34 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés • • Előállító szabály (production rule): egy IF-THEN, feltétel-következmény szerkezet, melyet egyaránt alkalmaznak a problémák megoldásához szükséges deklaratív (leíró) és procedurális (eljárásokon alapuló) tudás ábrázolására. α, α à β A logikában neve: implikáció, modus ponens: β Deklaratív következmény: kikövetkeztetett tény • Procedurális következmény: • Szabályláncolás - a következtetési folyamat megvalósulása akció. szabályláncolódás = a szabály következményrésze illeszkedik más szabály feltételrészére • Ha az összes kapcsolódást megvalósítanánk, előállna a szabálybázis által reprezentált összes következtetési fa, melyek egymáshoz rendelnék a leveleiken szereplő tényeket és a fák csúcsán szereplő végkövetkeztetéseket. • A következtetési fa teljes előállítása gyakorlatilag lehetetlen, ezért egy konkrét esetre a következtetési feladat végigvitele a következtető automatára hárul. 3/ 35 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés .. • Előrehaladó láncolás (forward chaining): a végkonklúzió megtalálása a feladat, a megadott tényekből kiindulva ! • Hátrafelé haladó láncolás (backward chaining): az elérendő cél adott és a szükséges előfeltételek megtalálása, ill a megadottak elégséges voltának megállapítása a cél. ? n Előállító szabályok, szabályalapú tudásszemléltetés .. • Előnyös alkalmazási terület (Christopher Chabris): • Előrehaladó láncolás: ha a megoldandó problémával kapcsolatosan nagyszámú összegyűjtött adattal rendelkezünk, de a megoldást illetően nincs jó elképzelésünk. A szabályalapú rendszer el fogja végezni az összes végrehajtható következtetést és elő fogja állítani a megadott tényekből következő összes szóbajöhető megoldást. • Hátrafelé haladó láncolás: amikor egy, vagy több hipotézissel rendelkezünk a problémánk megoldására vonatkozóan és azt kívánjuk, hogy a szabályalapú rendszerünk tesztelje ezeket. A hipotézistől visszafelé indulva a rendszer bekéri a hipotézis teljesüléséhez szükséges adatokat. • Az előreláncolást alkalmazó rendszert deduktív rendszernek is szokták nevezni utalva a sorozatban végzett deduktív logikai következtető műveletre (modus ponens). 3/ 36 . dr.Dudás László www.princeton.edu/~ds/Dining_on_Campus/ Frist/thought.html 3/ 37 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés .. • Szabályláncolás Tények a b Szabályok IF a and b THEN e IF e or f THEN g c d IF c and d THEN f 3/ 38 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés .. • Szabályalapú tudásszemléltetést és következtető automatát alkalmazó szakértőrendszer felépítése n Előállító szabályok, szabályalapú tudásszemléltetés .. • Szabályalapú következtetés működése előrehaladó láncolásnál • Feladat: A szabálybázist és az aktuális feladat tényeit felhasználva meg kell próbálni elérni a célállapotot, mely a problémára adott válasz, vagy egy elfogadható választ reprezentáló részcél elérése lehet. • Lépések: 1. Mintaillesztés: ki kell keresni a szabálybázisból az összes olyan szabályt, melynek a feltételrésze a ténybázisbeli tényekkel igaz. 2. Konfliktusfeloldás: az 1. lépésben megtalált szabályok alkotják a konfliktus-halmazt, mert bármelyik felhasz-nálható, de csak egyet alkalmazhatunk. 3. Szabályalkalmazás: végre kell hajtani a kiválasztott szabály következmény-részében szereplő tevékenysé-get, ill. fel kell használni az új tényt. (Új tény: az adott feladatra nézve igaz, kikövetkeztetett.) 4. A célállapot tesztelése: meg kell vizsgálni, eljutottunk-e a célállapotba, ha nem, folytatni kell 1.-től. 3/ 39 . dr.Dudás László Tilly Károly - Tóth Endre: Számítógépek Kézirat BME Villamosmérnöki Kar, Műszer- és Méréstechnikai Tanszék, Budapest, 1992. p115. n Előállító szabályok, szabályalapú tudásszemléltetés .. • A következtető automata konfliktusfeloldó működésének vezérlése • Lokális: lokális információkat, speciális, tartománytól függő szabályokat, metaszabályokat alkalmaz. A programozó bizonyos hatások kiváltására közvetlenül megadhat szabályokat. • Globális: globális információkra alapoz, a teljes szabálytartományban egyformán működik. • Globális konfliktusfeloldási módszerek jellemzői: • érzékenység, • stabilitás • Globális konfliktusfeloldási módszerek fajtái: • Megakadályozás • Újdonság • Specifikusság. 3/ 40 . dr.Dudás László Peter Jackson : Introduction to Expert Systems Addison-Wesley,New York, 1990. p526.. 3/ 41 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés .. • A szabályalapú rendszerek előnyei • Modularitás: egyedi előállító szabályok hozzáadhatók, törölhetők, megváltoztathatók • Egyöntetűség: homogén ábrázolás, könnyű megértés • Természetesség: emberi problémamegoldáshoz hasonló. • A szabályalapú rendszerek hátrányos tulajdonságai • Merevek: nem nyújtanak különféle absztrakciós szinteket • Nem hatékonyak: ténybázis-szabálybázis illesztés, kombinatorikus robbanás. A szabályalapú tudásszemléltetés rendkívül elterjedt és számtalan szakértőrendszernek és szakértőrendszer-váznak alkotja az alapját. 3/ 42 . dr.Dudás László n Előállító szabályok, szabályalapú tudásszemléltetés .. • Előnyös alkalmazási területek (Barr, Feigenbaum) • Elosztott tudás esetén. Ilyen esetben a tények aránya a szabályokhoz képest jelentős. Példaként a klinikai gyógyászati rendszereket említhetjük. • Olyan esetekben, amikor a szemléltetett tudás és a vezérlő szerkezetek jól elkülöníthetők. Olyan tudásterületeknél áll ez fenn, amelyek könnyen elkülöníthetők a felhasználásukra szolgáló módszerektől, mint például a biológiai osztályozás. • Független tevékenységek esetén. Olyan területek ezek, amelyeknek a folyamatai egymástól elkülönülő tevékenységek halmazaként állnak elő, mint például a gyógyászatban a betegmegfigyelő rendszerek. Deborah D. Wolfgram - Teresa J Dear - Craig S. Galbraith: Expert Systems for the Technical Professional John Wiley & Sons,New York, 1987. 4/ 1 . dr.Dudás László n Tudásszemléltetés formális logikával • A logikáról A logika a bölcselés tudománya, a helyes gondolkodás művészetének tana. • A logika osztályozása Logika Arisztotelészi (hagyományos) Szimbolikus (formális) Propozíciós logika Predikátum logika Nem klasszikus szimbolikus logika - modális - temporális - többértékű - intuicionista - valószínűségi. Fuzzy n A szimbolikus logika kifejlődése • Petrus Ramus (1515-1572) • Bírálta az arisztotelészi logikát. • "A logika: a helyes érvelés eszköze." • Francis Bacon (1561-1626) • "A logika az új ismeretek megszerzésének eszköze." • Kísérletek, mérések fontossága. 1. 2. 2. • René Descartes (1596-1650) • "Értekezés a módszerről" c. műve – A problémákat osszuk független, vagy kevéssé összefüggő részekre – Az egyszerűtől haladjunk a bonyolultabb felé – Csak olyan dolgokat fogadjunk el igaznak, melyek igazsága megkérdőjelezhetetlen – Törekedjünk a teljes felsorolásokra. 3. 4/ 2 . dr.Dudás László 1. www.phil-fak.uni-duesseldorf.de/ .../neuzeit/ramus.htm 2. "www.amorc.no/images/bacon.jpg" 3. www.homeoint.org/seror/ articles/raison.htm n A szimbolikus logika kifejlődése .. • Gottfried Wilhelm Leibniz (1646-1716) • A szimbolikus logika előfutára. • "Logika ≅ matematika." • Azonosság definíciója: 1. "Azok a terminusok tekintendők azonosnak, vagy egybeesőnek, amelyek egymással tetszés szerint felcserélhetők anélkül, hogy ezáltal bármelyik állítás igazsága megváltozna." • George Boole (1815-1864) • A szimbolikus logika megalapítója. • "A logika matematikai analízise" című műve. • A logikai szorzás és logikai összeadás műveletének bevezetése. • 2. John Venn (1834-1923) • "Symbolic Logic" című műve • Diagramok: teljes esemény = téglalap; körök: mindenféle egymásbametszés 3. 4/ 3 . dr.Dudás László 1. http://usuarios.lycos.es/Cantemar/Leibniz.html 2. powerreporting.com/ altavista.htm 3. lawrence.lancour.students.noctrl.edu/ mathematicians.htmlM e s t e r s é g e s n A szimbolikus logika kifejlődése .. • William S. Jevons (1835-1882) • "megengedő vagy" • Első logikai gép (a logikai zongora) 1. 4/ 4 . dr.Dudás László • • Charles S. Peirce (1839-1914) • Boole összes logikai művelete kiváltható egyetlen művelettel, a "sem...., sem' művelettel. 2. Augustus de Morgan (1806-1871) • Reláció-azonosságok. 3. 1. "pierre.mf.free.fr/tpe/ partie2/pasclin2.gif" 2. www.macalester.edu/~warren/ courses/P50-01_timeln.htm 3. www.din.uem.br/ia/precursores/ morgan.htmlM e s t e r s é g e s n A szimbolikus logika kifejlődése .. • Gottlob Frege (1848-1925) • Kimagasló teljesítménye • "A szimbolikus logika atyja" • "Fogalomírás, a tiszta gondolkodás aritmetika mintájára megalkotott formanyelve" c. műve 4/ 5 . dr.Dudás László Részlet a Begriffschrift-bőlM e s t e r s é g e s n A szimbolikus logika kifejlődése .. • Bertrand Russell (1872-1970) • Frege-től függetlenül ugyanoda eljutott • Hézagok az elődök munkáiban: logikai paradoxonok. • "Az osztályok osztálya eleme-e önmagának ?" • Típuselmélete: magyarázat a paradoxonokra. 4/ 6 . dr.Dudás László 1. 1. www.univie.ac.at/bvi/photo-gallery/ photo_gallery.htm 4/ 7 . dr.Dudás László n Új irányzatok a logikában • • • A modális logikákkal olyan terminusok is kifejezhetők, mint a "lehetséges", "szükségszerű" és ezek változatai. A modális logika a klasszikus logika kiterjesztése. A deontikus logika olyan etikai és jogi kifejezések elemzésével foglalkozik, mint a "Megtiltott, hogy...", "Megengedett, hogy...", stb. Jan Lukasiewicz (1878-1956) • Háromértékű logika: 0, 1/2, 1 • Az 1/2 érték a bizonytalanságot fejezi ki. • Eljutott a végtelenértékű logikáig. . 1. • E.L.Post (1897-1954) • Többértékű logika, Lukasievicz-csel egyidőben. • J.M.Keynes (1883-1946) • Ch.S.Peirce-szel együtt a valószínűségi logika megalkotóinak tartják. • Logikai valószínűség: a racionális hit (ésszerű meggyőződés) foka, 0...1 közötti érték. 1. www.fmag.unict.it/PolPhil/ Lukas/Lukas.html 2. www.ssc.upenn.edu/~ues/ 2. 4/ 8 . dr.Dudás László n Propozíciós logika • Egyéb elnevezések: kijelentéskalkulus, ítéletkalkulus, nulladrendű predikátum-kalkulus. • Propozíció: egy kijelentő mondat formában megadott állítás, mely az adott kontextusban egyértelmű igaz, vagy hamis logikai értékkel bír. • A propozíciós logika olyan egyszerű nyelvtani kapcsolatokat alkalmaz a legegyszerűbb "atomi mondatok" között, mint az és, vagy, nem. . • Atomi mondatok : A= " A víz száz fokon forr." B= " A macskák ugatnak." Az ilyen atomi összetevők (objektumok) egyértelműen megítélhetők az igaz, vagy hamis értékek valamelyikével. ( Általános tapasztalat szerint A igaz, B hamis). Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 9 . dr.Dudás László n Propozíciós logika .. • A propozíciós logika tárgya, célja összetett szerkezetek kiértékelésére formális szabályt adni. A kiértékelésben az atomi összetevők (objektumok) igazságértékeit kell csak figyelembe venni, jelentésüktől eltekintünk. • Atomi kijelentések helyett szimbólumok: Esik az eső. ⇒ A • Eltekintünk a természetes nyelvi jelentéstől Nem természetes átalakítás, pl.: . A: Jóska megbetegedett. B: Jóska elment az orvoshoz. Hétköznapi értelemben A és B jelentése eltér B és A összetett kijelentésétől. Csak az igaz, vagy hamis értéke fontos számunkra A-nak és B-nek. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 10 . dr.Dudás László n A propozíciós logika szintaxisa • Jelkészlet • Elválasztójelek: , ( ) [ ] • Logikai operátorok (műveleti jelek): {csökkenő precedenciasorrendben} ¬ negáció 'nem' ∧ konjunkció 'és' ∨ → ≡ diszjunkció implikáció ekvivalencia 'vagy' 'ha ... akkor ...' 'akkor és csak akkor' 'következik' 'azonos' . • Logikai változók (ítéletváltozók): p, q, r, ... • Logikai konstansok (ítélet-, predikátumkonstansok) : T, F (True, False), (igaz, hamis). Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 11 . dr.Dudás László n A propozíciós logika szintaxisa .. • A propozíciós logika (kijelentéskalkulus, ítéletkalkulus) formuláit a jelkészlet elemeiből a szintaxis szabályai szerint építjük fel: • Atomi formula (atom) • Minden ítéletkonstans atom : T, F • Minden ítéletváltozó atom : p, q, r, ... • Formula (jól formált formula): • Minden atomi formula egyben formula • Ha A és B formulák, akkor a . ¬ A, A∧ ∧ B, A∨ ∨ B, A→ → B, A≡ ≡ B kifejezések is formulák. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 12 . dr.Dudás László n A propozíciós logika szemantikája • Egy logikai formulának az igazságértéke ad jelentést, mely igazságértéket a szemantika szabályai szerint kapja meg. • A jelentésadás lépései: 1. Interpretálás 2. Kiértékelés • Interpretálás A formula interpretálása: minden egyes ítéletváltozójához az igaz, vagy a hamis értéket rendeljük minden lehetséges módon. Egy hozzárendelés . egy interpretációt ad. Az interpretációk száma a propozíciós logikában véges: 2 n ahol n a változók száma. pl.: A:=(p∧q) → (r ≡ (¬ s)) két lehetséges interpretációja: I 1 : (p,q,r,s)←(T,T,F,F) I 2 : (p,q,r,s)←(F,T,T,F) Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 13 . dr.Dudás László n A propozíciós logika szemantikája .. • Kiértékelés Az interpretált formula kiértékelését a logikai műveleti jelek szemantikája alapján végezzük: A T T F F B ¬A A∧B A∨B A→ B A≡B T F T T T T F F F T F F T T F T T F F T F F T T . Pl.: Ha süt a nap, nem tanul Péter. süt a nap : p tanul Péter : q A:= p→(¬ q) A lehetséges 4 interpretáció egyike: p= T, q= F, a kiértékelt formula: T→(¬ F); T → T; T, az A állítás igaz. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 14 . dr.Dudás László n Logikai azonosságok a propozíciós logikában • • Összetett kijelentések kiértékelését, illetve egyszerűsítését, vagy kijelentések egyenértékűségének belátását segítik a logikai azonosságok: Igazságtáblával igazolhatók, pl.: A, B, C esetén 2 3 = 8 eset, mindkét oldalon ugyanazt adja. A≡ B = (A→ B) ∧ ( B→ A) A→ B = ¬ A∨ B Ezen két azonosság értelmében elegendő csak a metszet ∧, az unió ∨ és a tagadás ¬ logikai műveletek alkalmazása: A∨False = A . A∧True = A A∨True = True A∧False = False A∨¬A = True A∧¬A = False Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 15 . dr.Dudás László n Logikai azonosságok a propozíciós logikában .. Kettős tagadás: Idempotencia: Kommutativitás: (felcserélhetőség) Asszociativitás: (társíthatóság) Abszorpció: (elnyelés) Disztributivitás: (széttagolhatóság) DeMorgan összefüggés: ¬¬ A A∧ A A∧ B A∨ B (A∧ B)∧ C (A∨ B)∨ C A∧ (A∨ B) A∨ (A∧ B) . A∧ (B∨ C) A∨ (B∧ C) ¬ (A∧ B) ¬ (A∨ B) = = = = = = = = = = = = A A B∧ A B∨ A A∧ (B∧ C) A∨ (B∨ C) A A (A∧ B)∨ (A∧ C) (A∨ B)∧ (A∨ C) ¬ A∨¬ B ¬ A∧¬ B Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 16 . dr.Dudás László n Kielégíthetetlen és érvényes kifejezések A kielégíthetetlen logikai kifejezések és az érvényes kifejezések fontos szerepet játszanak a tételbizonyításban. A tétel azt jelenti, hogy állításokból logikailag következik a konklúzió. • Tautologikus törvény: A ∨ B = A, A ∧ B = B, ha A tautológia, ha A tautológia. A logikai kifejezés tautológia, azaz érvényes kifejezés akkor, ha minden lehetséges helyettesítése igaz. . • Kielégíthetetlenségi törvény: A∨ B = B, ha A kielégíthetetlen, A∧ B =A, ha A kielégíthetetlen. A logikai kifejezés kontradikció, azaz kielégíthetetlen kifejezés akkor, ha minden lehetséges helyettesítésre hamis értéket ad. Természetesen a formulák többsége egyes interpretációkban hamis, más interpretációkban igaz, azaz kielégíthető. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 17 . dr.Dudás László n Tételbizonyítás a propozíciós logikában • Egy propozíciós logikai formula érvényességének igazolására alkalmas módszerek: • Igazságtáblás • Formális levezetés • Quine algoritmusa • Wang algoritmusa • Rezolúció. • A rezolúció szabálya: α ∨ β, ¬β ∨ γ . α ∨ γ Mivel β nem lehet egyszerre igaz és hamis, ezért valamelyik premisszában, előfeltételben a másik tagnak (α, vagy γ ) igaznak kell lennie, tehát az α ∨ γ igaz. • A rezolúció módszere kiemelkedik a többi közül, mivel ez a bizonyítási módszer alkalmazható a predikátum logikában is. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 18 . dr.Dudás László n Tételbizonyítás a propozíciós logikában .. • A tétel igaz állításokból és egy, azokból állítólag következő konklúzióból áll. • A tételbizonyítás feladata formális szabályok gépies alkalmazásán keresztül igazolni, hogy a konklúzió a premisszák következménye. • A rezolúciós módszer lépései: • A bizonyítandó tétel tagadott alakját vesszük alapul azáltal, hogy feltesszük, hogy a konklúzió ellentettje igaz a premisszák igaz értékei mellett. Ha az ily módon kapott összetett formula kielégíthetetlen . voltát sikerül belátni, akkor az eredeti tétel igaz. • Ehhez konjunktív normál forma alakra (KNF) hozzuk az összetett formulát és a rezolúció ismételt alkalmazásával, fokozatos egyszerűsítéseken keresztül jutunk el az ellentmondáshoz. • A rezolúció alkalmazása a propozíciós logikában (ítéletkalkulus) korlátozott, mivel bonyolultabb problémák leírására ez a logika nem ad eszközöket. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 19 . dr.Dudás László n Tételbizonyítás a propozíciós logikában .. • A konjunktív normálforma • Klózok konjunkciója, ÉS kapcsolata • Az eredeti formulával ekvivalens • Egyszerű felépítése miatt gépiesen kezelhető. • • A klóz literálok diszjunkciója (VAGY kapcsolata), vagy egyetlen literál. A literál egy ítéletváltozó (logikai változó), vagy annak negáltja. . Példa: konjunktív normál forma (p ∨ ¬q) ∧ (¬ p ∨ r ) ∧ (¬ r ∨ ¬ s ) ∧ q ∧ s klóz klóz klóz klóz klóz Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 20 . dr.Dudás László n Tételbizonyítás a propozíciós logikában .. • Formulák konjunktív normálformára hozásának lépései: 1. Azonosságok kiküszöbölése: A≡ B = ( A → B ) ∧ ( B → A ) 2. Implikációk kiküszöbölése: A → B = ¬ A ∨ B 3. A negálás hatáskörének redukálása: ¬ (A ∨ B) = ¬ A ∧ ¬ B ¬ (A ∧ B) = ¬ A ∨ ¬ B 4. Klózok konjunkciójának létrehozása: A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C). • A diszjunktív normál formából elhagyva a konjunkció operátorokat, a formula literálokra esik szét, melyek halmazára alkalmazzuk a rezolúció . szabályát ciklusban. Ily módon a rezolúció egy olyan könnyen automatizálható eljárás, melynek segítségével egy klózhalmaz, illetve a neki megfelelő konjunktív normál forma kielégíthetetlenségét belátjuk. • A klózhalmaz egyszer ű sítése rezolválható klózpárokon keresztül történik. • Rezolválható klózpár: egyetlen ellentett literálpárt tartalmaznak, pl: p ∨ A , ¬ p ∨ B ahol A és B közvetlenül tovább már nem rezolválható klózok. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 21 . dr.Dudás László n Tételbizonyítás a propozíciós logikában .. • A rezolúciós folyamat során a rezolválható párok rezolválása eredményeként adódó rezolvens klózt a halmazhoz adjuk. • A klózhalmaz kielégíthetetlenségét az jelzi, hogy végül üres klózt kapunk. • A rezolúció algoritmusa: Procedure Rezolúció 1. KLÓZHALMAZ feltöltése 2. do . 3. Rezolválható klózpár Ci, Cj kiválasztása a KLÓZHALMAZ-ból 4. Rezolválás: Cij ⇐ R(Ci,Cj) 5. KLÓZHALMAZ bővítése Cij rezolvenssel 6. while Cij ≠ NIL end Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. n Tételbizonyítás a propozíciós logikában .. • Példa: KNF: (p ∨ ¬q) ∧ (¬ p ∨ r ) ∧ (¬ r ∨ ¬ s ) ∧ q ∧ s p ∨ ¬q ¬ p ∨ r ¬q ∨ r ¬ r ∨ ¬ s A rezolúció teljességének tétele garantálja, ¬q ∨ ¬ s hogy egy kielégítetlen formula klózhalmazából kiindulva, minden lehetséges módon képezve a klózpárok rezolvensét, véges sok lépésben eljutunk az üres klózhalmazhoz. . q ¬ s s NIL 4/ 22 . dr.Dudás László Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 23 . dr.Dudás László n Predikátum logika További elnevezések: elsőrendű predikátumkalkulus, vagy egyszerűen predikátumkalkulus. • Predikátum: objektumok sajátságainak és az objektumok közötti kapcsolatok, viszonyok, relációk szimbolikus formában való megadására alkalmas állítás, mely egy adott interpretációban egyértelmű igaz, vagy hamis minősítéssel bír. • A predikátum logika jellemzői: • MI feladatok reprezentálására alkalmas (ld.: PROLOG). • Kijelentéseink tartalmát is leírja, mivel az állítások az individuumkonstansok, individuumváltozók és individuumfüggvények . révén egy tartomány (, alaphalmaz, domain) elemeire vonatkozhatnak. • Az ítélet-, vagy logikai függvények, azaz a predikátumok használatá- val indivíduum paraméterektől függő igazságú állítások fogalmazhatók meg. • Új logikai operátorok, a kvantorok segítségével kifejezhetjük a "minden" és a "létezik" fordulatokat is. • Az interpretáció módja eltér a propozíciós logikáétól, és ebből eredően a predikátum logikában egy formulának végtelen sok interpretációja lehetséges az alaphalmaz, és az azon értelmezett függvények és predikátumok tetszőleges választhatósága miatt. 4/ 24 . dr.Dudás László n Predikátum logika .. Bonyolultabb tételek bizonyíthatók, mint a propozíciós logikában: Pl.: Premisszák, ismert tények: (1) Van olyan hallgató, aki minden tárgyat szeret. (2) A szócséplést egyik hallgató sem szereti. ------------------------------------------------------------------------ . Igaz-e a fenti állítások ismeretében a következő állítás? Bizonyítandó állítás: (4) Egyik tárgy sem szócséplés. 4/ 25 . dr.Dudás László n A predikátum logika szintaxisa • Jelkészlet: • Elválasztójelek: , ( ) [ ] • Logikai operátorok (műveleti jelek): ¬ ∧ ∨ → ≡ • Kvantorok: univerzális kvantor ("minden"): ∀ egzisztenciális kvantor ("létezik" vagy "van olyan"): ∃ . (precedencia: ∀ ∃ ¬ ∧ ∨ → ≡ ) • Elemkonstansok (individuumkonstansok): a, b, c,...,vagy nevek (például: János, asztal). . • Elemváltozók (individuum változók): x, y, z... • Függvényszimbólumok (individuumfüggvények): f, g, h,... , vagy például: testvére(Józsi )⇒ Laci • Itéletkonstansok (logikai konstansok): True, False. • Itéletváltozók (logikai változók): p, q, r... • Predikátumszimbólumok (logikai függvények): P, Q, R,... , vagy például: testvérek( x, y ), P(x,y). Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 26 . dr.Dudás László n A predikátum logika szintaxisa .. • A jelkészlet elemeiből a kifejezések 3 osztálya alkotható meg: Term-ek, Atomi formulák (Atomok) és Jólformált formulák (Formulák). • Term (individuum konstans, individuum változó, individuum függvény): • Minden elemkonstans (individuum konstans) term. Pl.: a,b,...,asztal, szék, stb. • Minden elemváltozó (individuum . változó) term. Pl.: x, y. • Ha f egy n-argumentumú függvényszimbólum és t 1 ,...,t n term-ek, akkor f(t 1 ,...,t n ) is term. Pl.: f(a,x), gyereke(Pál,x), színe(haj,időskorban)⇒ősz, színe(haj,fiatalkorban) ⇒ szőke. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 27 . dr.Dudás László n A predikátum logika szintaxisa .. • Atomi formula (kiértékelve True, vagy False): • Minden ítéletkonstans atomi formula. ( True, False ) • Minden ítéletváltozó atomi formula. ( p, q, r,... ) • Ha P egy n-argumentumú predikátumszimbólum (logikai . függvény) és t 1 ,...,t n term-ek, akkor P(t 1 , ...,t n ) atomi formula. Pl.: házaspár(Pál,Irén) ⇒ True. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 28 . dr.Dudás László n A predikátum logika szintaxisa .. • Formula (jólformált formula): • Minden atomi formula egyben formula. (True, p, P(a,b) ) • Ha A és B formulák, akkor a (¬ ¬ A), (A ∧ B), (A∨ ∨ B), (A → B), (A ≡ B) kifejezések is formulák. • Ha az A egy formula és az x egy elem (individuumváltozó), akkor a (∀ ∀ x)A, (∃ ∃ x)A kifejezések is . formulák. Pl.: (∀ x) testvére (x,Pál) Precedenciasorrend: ∀∃¬ ∧ ∨ → ≡, pl.: (((∃x)A) ∨ (B) helyett: (∃x)A ∨ B Példa: Vagy van egy részeg, vagy nem volt már ital. A:= részeg(x)=R(x), C= volt ital.. (∃x)R(x) ∨ ¬C. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 29 . dr.Dudás László n A predikátum logika szintaxisa .. • Kötött változó: Minden előfordulása a formulában kvantor hatása alatt áll. (∀ x) P(x,y) x kötött változó, y nem kötött változó. (∀ x) [P(x,y) ∧ (∃ y) Q(x,y)] mindkét x kötött [] miatt, y első előfordulása nem kötött, második előfordulása kötött. • Mondat: olyan formula, melyben minden változó összes előfordulása kötött. Csak mondatokkal foglalkozunk. . Példa mondatra: (∀ x) [P(x) ∨ (∃ y) Q(x,y)] Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 30 . dr.Dudás László n Példa a formulázásra Feladat: Állítások: (1) Van olyan hallgató, aki minden tárgyat szeret. (2) A szócséplést egyik hallgató sem szereti . ------------------------------------------------------------------ (4) Egyik tárgy sem szócséplés Formalizálás: Alkalmazott predikátumok: H(x): az x egy hallgató . T(y): az y egy tárgy C(y): az y egy szócséplés S(x,y): az x szereti y-t. A formalizált állítások: F1: (∃ ∃ x)[H(x) ∧ (∀ ∀ y)(T(y) → S(x,y))] F2: (∀ ∀ x)[H(x) → (∀ ∀ y)(C(y) → ¬ S(x,y))] F3: (∀ ∀ x)[T(x) → ¬ C(x)] 4/ 31 . dr.Dudás László n A predikátumkalkulus szemantikája • Az elsőrendű predikátumkalkulus formuláinak is hasonlóan adunk jelentést, mint az ítélet-kalkulusban: • először interpretáljuk, majd • kiértékeljük a formulát. (Eredmény: True, vagy False). • Interpretáció: • Individuumtartomány (az értelmezés alaphalmazának) megválasztása: jele D, nem üres. • Hozzárendelések: – Minden individuumkonstans-szimbólumnak . feleltessük meg D egy elemét. (a:= asztal ) – Minden n-argumentumú individuumfüggvényhez (pl.: f(a,b) ) rendeljünk hozzá egy D n ⇒ D leképezést. ( gyermeke(a,b) ⇒ c, gyermeke(Pál,Irén) ⇒ Jutka ). – Minden n-argumentumú predikátumfüggvénynek feleltessünk meg egy D 2 ⇒ {T,F} leképezést, ahol T a logikai igaz, F pedig a logikai hamis értéket jelöli. (Pl.: házaspár(Pál,Irén) ⇒ True ). Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 32 . dr.Dudás László n A predikátumkalkulus szemantikája .. • Kiértékelés: • Ha az A és B formulák igazságértéke ismert, akkor a (¬ ¬ A), (A ∧ B), (A ∨ B), (A → B), (A ≡ B) formulák igazságértékét a logikai műveleti jelek propozíciós logikánál megadott igazságtáblái alapján határozzuk meg. • A (∀ ∀ x)A formula igazságértéke pontosan akkor T az adott interpretációban, ha az A formula igazságértéke minden x ∈ D esetén . True, egyébként (∀ x)A értéke False. • A (∃ ∃ x)A formula igazságértéke pontosan akkor True az adott intrepretációban, ha az A formula igazságértéke legalább egy x ∈ D esetén True; egyébként (∃ x)A értéke False. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 33 . dr.Dudás László n Predikátum formula igazságértéke az interpretáció függvénye • A formula: • Értelmezések: (∀ ∀ x) [ P( f (x,x), b) → P(x, b) ] a., D a természetes számok halmaza. Megfeleltetések: b := 1 f(x,y) := x⋅ y ( f a szorzást jelölő függvény) P := egyenlő ( P legyen az egyenlőség relációja) . Ezekkel a formula: (∀ x) [(x 2 = 1) → (x = 1)] T= igaz, a természetes számok körében. b., D az egész számok halmaza. Megfeleltetések: mint fent. A formula értéke F=hamis, mert x = -1 esetén x 2 = 1 -ből nem következik, hogy x = 1. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 34 . dr.Dudás László n Predikátum-logikai formulák kielégíthetősége • Kielégíthető az a formula, amelyik valamely interpretációban igaz. • Érvényesnek nevezünk egy formulát, ha minden interpretációban igaz. Például a (∀ x)P(x) ∨ (∃ y) ¬ P(y). • Kielégíthetetlen az a formula, amely minden interpretációban hamis értékű. Például a (∀x)P(x) ∧ (∃y) ¬ P(y). • Az érvényes, illetve a kielégíthetetlen formulák a fontosak számunkra, ugyanis a tételbizonyítást egy formula . érvényességének, illetve kielégíthetetlenségének a belátására lehet visszavezetni. • Probléma: az elsőrendű predikátum kalkulus egy formuláját nem tudjuk az összes lehetséges interpretációban kiértékelni, mivel végtelen sok alaphalmazt lehet megadni. • Megoldás: a rezolúciós eljárás, mellyel egy formula érvényessége, vagy kielégíthetetlensége belátható. Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 35 . dr.Dudás László n Logikai azonosságok a predikátum kalkulusban • Két formula ekvivalens, ha minden interpretációban ugyanaz az igazságértékük. • A propozíciós logikában megadott azonosságok itt is érvényesek • További azonosságok: Q jelölheti a ∀, vagy a ∃ jelek bármelyikét. Jelöljön A(x) olyan formulát, amelyben az x változó előfordul, B pedig olyat, amely az x-et nem tartalmazza. (Qx)A(x) ∨ B = (Qx)(A(x) ∨ B) . (Qx)A(x) ∧ B = (Qx)(A(x) ∧ B) ¬ ((∀ x)A(x)) = (∃ x)( ¬ A(x) ) ¬ ((∃ x)A(x)) = (∀ x)( ¬ A(x) ) (∀ x) A(x) ∧ (∀ x) B(x) = (∀ x) (A(x) ∧ B(x)) (∃ x) A(x) ∨ (∃ x) B(x) = (∃ x) (A(x) ∨ B(x)) (Q1x) A(x) ∨ (Q2x) B(x) = (Q1x) (Q2y) (A(x) ∨ B(y)) (*) (Q1x) A(x) ∧ (Q2x) B(x) = (Q1x) (Q2y) (A(x) ∧ B(y)). Forrás: Fekete I.-Gregorics T.-Nagy S.: Bevezetés a mesterséges intelligenciába LSI Oktatóközpont, Budapest, 1990. p290. 4/ 36 . dr.Dudás László n Rezolúció a predikátum logikában Bonyolultabb tételek bizonyíthatók, mint a propozíciós logikában, ugyanakkor a bizonyítás lépései is jóval összetettebbek. A következőkben egy egyszerű példát mutatunk, amely rámutat a predikátum logikán belüli rezolúció egyik erősségére: A bizonyítás folyamán individuumváltozó - individuumkonstans hozzárendeléseket is végez, amely révén arra is választ kapunk, hogy milyen feltételek mellett igaz a tétel. Igazi erejét megtapasztalhatjuk a Prolog programozási nyelvben. Pl.: Feladat: Értik-e a hallgatók a rezolúciót? . Premisszák, ismert tények: (1) A hallgatók értelmesek. (2) Az értelmesek mindent értenek, ami egyszerű. (3) Az értelmeseknek a rezolúció egyszerű. ------------------------------------------------------------------------ Igaz-e a fenti állítások ismeretében a következő állítás? Bizonyítandó állítás: (4) A hallgatók értik a rezolúciót. 4/ 37 . dr.Dudás László n Rezolúció a predikátum logikában .. Formulázás: • Alkalmazott predikátumok: hallgató(x) - az x az egy hallgató értelmes(x) - az x értelmes érti(x,y) - az x érti az y-t egyszerű(y) - az y egyszerű • A premisszák és a negált következmény formalizált alakban: . (1) ¬ hallgató(x) ∨ értelmes(x) (2) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y) (3) ¬ értelmes(x) ∨ egyszerű (Rezolúció) (4) hallgató(x) ∧ ¬ érti(x,Rezolúció) ⇐ tagadása ⇐ ¬ hallgató(x) ∨ érti(x,Rezolúció) 4/ 38 . dr.Dudás László n Rezolúció a predikátum logikában .. A klózhalmaz: ¬ hallgató(x) ∨ értelmes(x) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y) ¬ értelmes(x) ∨ egyszerű (Rezolúció) hallgató(x) ¬ érti(x,Rezolúció) A rezolúciós folyamat lépései: ¬ hallgató(x) ∨ értelmes(x) hallgató(x) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y) értelmes(x) . ¬ érti(x,Rezolúció) érti(x,y) ∨ ¬egyszerű(y) y ⇐ Rezolúció ¬egyszerű(Rezolúció) ¬ értelmes(x) ∨ egyszerű (Rezolúció) ¬ hallgató(x) ∨ értelmes(x) ¬ értelmes(x) ¬ hallgató(x) hallgató(x) NIL 4/ 39 . dr.Dudás László n A Fuzzy logika alapjai A Fuzzy logika Lofti Zadeh nevéhez fűződik. (1965) • A hagyományos kétértékű logika helyett végtelenértékű, folytonos változókat és a hamis és igaz közötti folytonos átmenetet használ a fogalmak, jellemzők igazságértékének megadására. • Hiányos adatok elfogadása, zajtűrő képessége, kollektív döntést utánzó működése a mesterséges neurális hálózatokhoz hasonlóan robusztus, megbízható alkalmazások készítését teszi lehetővé bizonytalan adatok esetére is. • Szimbolikus szinten működik, nyelvi változókat használ, ezáltal közel áll az emberi gondolkodáshoz. • Alkalmazása különösen a szabályozástechnikában igen elterjedt. 4/ 40 . dr.Dudás László n A Fuzzy logika alapjai .. Fuzzy halmazok • Egy elemnek a fuzzy halmazba való tartozásának foka, 0-1 közötti mértéke van, nem merev igen/nem. • Értelmezés: Ha X az x jellemzők, értékek egy csoportja, akkor az X-en értelmezett A fuzzy halmaz a következő rendezett párok halmaza: A = (x, μ A (x)): x ∈ X A μ A (x) neve tagsági függvény, értéke az x tagsági aránya, beletartozásának mértéke az A fuzzy halmazba, ill. az A tagsági függvényhez társított nyelvi érték igazságának foka. A μ A (x) tagsági függvény az X értékhalmazt leképezi az M tagsági térbe ( μ A (x) ∈ [0;1] ). μ A hórihorgas Példa: X testmagasságértékek [cm]. fuzzifikálás 1 A halmaz: a „hórihorgas” nyelvi értéknek megfelel ő x, μ A (x) számpárok halmaza, ábrája: fizikai változó: x= 200 ; fuzzy változó: testmagasság = hórihorgas 0 x 150 200 igazságértéke= 0.9 4/ 41 . dr.Dudás László n A Fuzzy logika alapjai .. A B Fuzzy logikán alapuló következtető rendszer • • Produkciós, szabályalapú működés, de: a szabályok feltételoldalán fuzzy ÉS, ill. fuzzy VAGY logikai műveletekkel összekötött fuzzy változó = nyelvi érték beletartozási relációk vannak, melyek értékét a fuzzy változóhoz tartozó fizikai változó (x) aktuális értéke és a nyelvi értékhez tartozó tagfüggvény együttesen határozzák meg. • A feltételoldali logikai kifejezés eredő érvényességi, igazsági értékét a fuzzy ÉS, ill, VAGY logikai műveletek értelmezésének felhasználásával számítjuk és ez lesz a következmény oldal érvényessége is egyben. A ∧ B • Fuzzy ÉS művelet értelmezése (C= A ∧ B): μ C (x)= min μ A (x), μ B (x) , x ∈ X • Fuzzy VAGY muvelet értelmezése (C= A ∨ B): μ C (x)= max μ A (x), μ B (x) , x ∈ X A ∨ B n A Fuzzy logika alapjai .. Fuzzy logikán alapuló következtető rendszer.. • A következmény oldalon egyetlen fuzzy változó = nyelvi érték reláció áll, melynek érvényessége, igazságértéke megegyezik a feltételoldalra meghatározott értékkel. • Az összes szabály egyszerre működik a fizikai változók, mint bemenő tények felhasználásával és kollektív döntést hoz. A kollektív döntés eredményét a fuzzy nyelvi értékek tagfüggvényeinek felhasználásával, a fuzzy változó terében az érvényességi értékekről a fizikai változóra való áttéréssel, ún. defuzzifikálással nyerjük. • A defuzzifikálás módszerei: • Területközéppont meghatározással (legelterjedtebb eljárás) • Tagsági függvény maximumok súlyozott átlagának meghatározásával • A legnagyobb érvényességű következmény-tagfüggvény maximumával. 4/ 42 . dr.Dudás László Forrás: Erdélyi Ferenc: A technológiai menedzsment informatikai eszközei; információ rendszerek Miskolc, 1997. 4/ 43 . dr.Dudás László n A Fuzzy logika alapjai .. Fuzzyfikálás, defuzzifikálás If Zárthelyieredmény = Jó ÉS Előadáslátogatás = Ritka then Vizsgajegy = Jeles If Zárthelyieredmény = Közepes ÉS Előadáslátogatás = Gyakori then Vizsgajegy = Jó Zárthelyieredmény Közepes Jó Kiváló Előadáslátogatás Ritka Gyakori pontszám Zárthelyieredmény Közepes Jó Kiváló pontszám óra Előadáslátogatás Ritka Gyakori óra 4/ 44 . dr.Dudás László n A Fuzzy logika alapjai .. Fuzzy szabályozórendszer vázlata Fuzzy nyelvi értékek Szabálybázis 2. Fuzzy következtetés 3. Defuzzy- fikálás 1. Fuzzy- fikálás Mért fizikai értékek Fuzzy nyelvi eredmény értékek Szabályozott folyamat Beállítandó fizikai értékek 5/ 1 . dr.Dudás László n Mesterséges intelligencia-orientált programozási nyelvek • A speciális programozási nyelvek kifejlődését egy-egy szakterület sajátos elvárásai, a szakterület feladatait jellemző közös tulajdonságok motiválják. • A mesterséges intelligencia kutatások is kiérleltek több olyan programozási nyelvet, ill. keretrendszert, amelyben a tématerület alkalmazásait könnyebb elkészíteni, hiszen a fejlesztői környezetek már fél megoldást jelentő eszközöket nyújtanak. • A speciális segédeszközöktől az általános felhasználhatóság igényével fellépő programnyelvekig terjed a kínálat. • Az MI nyelvek a szimbólumkezelés eszközei. • Az utóbbi időben a klasszikus MI nyelvek mellett előtérbe kerül a C++ is. Forrás: Yoshiaki Shirai - Jun-ichi Tsujii: Mesterséges intelligencia Alapelvek és alklamazások NOVOTRADE Rt. 1987. 5/ 2 . dr.Dudás László n Klasszikus mesterséges intelligencia nyelvek • Legismertebb és legrégebbi a LISP (John Mc Carthy,1957). • Számtalan LISP dialektus van, a legismertebbek: a Common LISP, az INTERLISP, a MacLISP, valamint a Standard LISP. Mivel a LISP-re nincs szabvány, ezek eltérései az alkalmazói programok hordozhatóságát megnehezítik. • Erős hatást gyakorolt a későbbi nyelvekre. • QA1, QA2, QA3 programnyelvek, 1960-as évek. Általános problémamegoldó rendszerek, illetve tételbizonyítás céljára. Szimbolikus logikát, rezolúciót alkalmaztak. • QA4, 1968. A PLANNER programozási nyelv hatása érezhető rajta. Szimbolikus reprezentáció mellett procedurális reprezentációra is képes volt. 5/ 3 . dr.Dudás László n Klasszikus mesterséges intelligencia nyelvek .. • A PLANNER programozási környezetet C.Hewitt, a MIT hallgatója dolgozta ki 1968-ban. 1. • A PLANNER-nél már megjelent a deklaratív nyelvek fő jellemvonása: csak a problémakört deklaráló, objektumokra és eljárásokra vonatkozó tudást, valamint a megoldandó problémát kellett megadni, a probléma megválaszolásához vezető utat, a szükséges tudás- és eljáráselemeket az út bejárásához maga a rendszer keresi meg és használja fel. • Az ábrázolt kétféle tudásforma a PLANNER-nél fizikailag is elkülönült: a deklaratív tudást a tényadatbázisban, a procedurális tudást a procedure (eljárás)-adatbázisban tárolta. 1. http://www.ai.mit.edu/people/hewitt/hewitt.html 5/ 4 . dr.Dudás László n Klasszikus mesterséges intelligencia nyelvek .. • A PLANNER előnyei: • Mintaillesztés: ha adott az atomok változókat tartalmazó listája, akkor az illeszkedő tények megkeresése, és ezzel a változók értékeinek meghatározása automatikus. • Az eljárásokat a minták hívják. Egy adott célhoz illeszkedő eljárás hívását egyszerűen a cél megadása váltja ki automatikusan, anélkül, hogy az eljárás nevének meghatározása szükséges lenne. • A keresés automatikus. A PLANNER az adatbázisokból alkalmas tényeket és eljárásokat választ ki a cél eléréséhez. • Visszalépés: a kiválasztott tételek nem feltétlenül helyesek. Ha a választás a keresés sikertelenségéhez vezet, a PLANNER visszatér a közvetlenül megelőző döntési ponthoz, és újraválaszt. (Depth first) • Dinamikus tényadatbázis: automatikusan is bővül a kikövetkeztetett tényekkel, tények törölhetők. 5/ 5 . dr.Dudás László n Klasszikus mesterséges intelligencia nyelvek .. • CONNIVER programnyelv, G.J.Sussman, MIT kutató, 1972. • A CONNIVER a PLANNER kiterjesztett változata, használja a tényadatbázist és az eljárás-adatbázist, valamint a minta alapján történő keresést. • Újdonsága abban volt, hogy elhagyta az automatikus keresést , és a problémamegoldás vezérlését a programozóra bízta. Ezáltal a keresés hatásfoka megnőtt. • További beépített függvények. • POP-x programok: európai fejlesztés. • Legújabb verziójuk, a POP-11 négy MI nyelvet integrál egy fejlesztői környezetbe, közte: LISP, PROLOG, POPLOG. A nyelvek közül egy feladaton belül is szabadon választhatunk. • A POPLOG nyelv a POP-11 készítőinek teljesen saját fejlesztése. • Erőteljes grafikai lehetőségek, többféle hardver- platform. • Interpreteres üzemmód, inkrementális fordítás. n A PROLOG • • PROLOG (Programming in Logic, Logika alapú programozás) Alain Colmerauer, Bob Kowalski, 1970. 1. Predikátum konstanson alapuló általános célú programnyelv, amely azonban legelőnyösebben logikai problémák megoldására alkalmazható. 1. • A PROLOG létrehozására kihatott az a tapasztalat, amelyet a korábbi MI programozási nyelvekkel szereztek: minél több a rendszerbe épített lehetőség, a rendszer annál inkább lelassul. • Deklaratív programnyelv: elegendő megadnunk csak a problématerületre vonatkozó tényeket, szabályokat és a megválaszolandó kérdést, ill. minősítendő állítást, és a program generálja a megoldáshoz vezető lépéseket és szolgáltatja a választ. 5/ 6 . dr.Dudás László 1. http://www.york.ac.uk/depts/lang/webstuff/people/sjh/L333intro_to_prolog/creators.html 5/ 7 . dr.Dudás László n Bevezetés a LISP programozási nyelvbe John Mc Carthy, 1957, MIT • • • • • • • • • Mesterséges intelligencia feladatok megoldására előnyös. List Processor - listafeldolgozó, a listák kulcsszerepben. Funkcionális nyelv - a működést függvények kiértékelése jelenti, utasítások nincsenek. Rendkívül homogén felépítés, tömör szintakszis: atom, lista, függvény. Nagy tárigény - oka a rekurzív függvényhívások sokasága. A procedurális nyelvekből ismert ciklus- és elágazásszervezést is függvényekkel végezhetjük. A ciklusszervezés a rekurzió miatt háttérbe szorul. A feladatok deklaratív leírási módját támogatja. Alapvetően interaktív, interpreteres használat, de létezik hozzá fordító is. Hardveres implementációja is van, gyors. 5/ 8 . dr.Dudás László n A LISP programozási nyelv .. • A LISP interpreter, értelmező LISP programunkat, amely nem más, mint egy lista, a listafeldolgozó dolgozza fel. Ez egy parancssoros értelmező, amely akár egy atomot, akár egy lista alakban adott összetettebb kifejezést azonnal feldolgoz és megadja az eredményt: egy atomot, vagy egy listát. • Végtelen ciklusban keringve, a parancs prompt-tal mindig kiértékelendő listára vár. Kiértékelés Beolvasás Kiírás 5/ 9 . dr.Dudás László n A LISP programozási nyelv építőelemei • Atomok - más nyelvek azonosítóinak, konstansainak felelnek meg • Szimbolikus atomok: betűvel kezdődő, tetszőleges hosszúságú betű- szám kombinációval folytatódó nevek, szimbólumok. Mindig van értékük is. Más nyelvek változóit, függvényneveit, felsorolt típusú értékeit helyettesítik. Típusuk nincs. Pl.: VALT LISTAERTEKU SKALAR U11 MEG-VAN • Numerikus atomok: más nyelvek számkonstansainak felelnek meg, de exponenciális alak nincs, ugyanakkor hosszuk tetszőleges. Pl.: 11 -22 +33.44 -555.666 123456789012345678901234567890 • Listák ( ) zárójelek között szóközzel elválasztva felsorolt atomok • Üres lista: ( ), szimbólum alakja a NIL. • A listák elemei listák is lehetnek tetszőleges mélységű beágyazottsággal. Pl.: (ALFA BETA GAMMA) (+12 VALT -24.25 SZO) (HAPCI MORGO TUDOR (DOLGOZO-TORPEK)) ((((1 A) 2) 3) B) • Listák szerepe: a függvények definíciója egy lista, a függvényhívás egy lista, az adatok felsorolása egy lista. n A LISP programozási nyelv építőelemei .. • A listák szerkezete: ( fej faroklista ) A fej az első elem, de mivel bármely elem bármilyen típusú lehet, a fej is lehet akár lista is. Egy homogén, csak elemekből álló lista tagolódása az általában rekurzív feldolgozás során: (ALFA BETA GAMMA DELTA) ALFA (BETA GAMMA DELTA) BETA (GAMMA DELTA) GAMMA (DELTA) DELTA 5/ 10 . dr.Dudás László ( ) 5/ 11 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • A függvénykifejezés a függvény programbeli meghívására szolgál. A függvénykifejezésben megadott függvény lehet beépített, vagy a programban előzetesen a programozó által megadott. • A függvénykifejezés egy lista, melynek első eleme a függvény neve, a többi a függvény aktuális paramétere. Létezik paraméternélküli és tetszőleges számú paraméterrel hívható függvény is. ( függvénynév paraméter1 paraméter2 ... paramétern ) • Pl.: (PRINT EGY-ARGUMENTUMA-LEHET) (TIMES TENYEZO1 TENYEZO2 TENYEZO3 TENYEZO4) • A függvénynév is lehet egy másik függvény eredményeként adott. • A függvény visszaadott értéke lehet egy atom, vagy egy lista. 5/ 12 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények • QUOTE - mivel egy függvényhívás formailag megegyezik egy szimbólummal kezdődő listával és a függvényhívás az alapértelmezett, ha el akarjuk kerülni, hogy egy listát függvénynek nézzen a rendszer, akkor a QUOTE függvénnyel ezt elérhetjük, mert a függvényhívásból listát csinál. Mivel nagyon gyakori ez az igény, helyettesíthetjük az aposztróffal: ‘. Pl.: * (QUOTE (ELEM1 ELEM2)) (ELEM1 ELEM2) * ‘(ELEM1 ELEM2) (ELEM1 ELEM2) • CAR - a lista fejét adja: Pl.: * (CAR ‘(ELEM1 ELEM2 ELEM3)) ELEM1 * (CAR (1 2 3 4 5 6)) 1 * (CAR ‘((ALFA BETA) GAMMA DELTA)) (ALFA BETA) 5/ 13 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • CDR - A lista faroklistáját adja. Pl.: * (CDR ‘(A B C D)) (B C D) • CONS - A lista elejéhez csatol egy újabb elemet. Pl.: * (CONS ‘BOLHA ‘(PIAC ECSERI)) (BOLHA PIAC ECSERI) * (CONS ‘(ELEM1 ELEM2) ‘(ELEM3 ELEM4 ELEM5)) ((ELEM1 ELEM2) ELEM3 ELEM4 ELEM5) ; a fej egy lista • APPEND - Két listát egyesít. Pl.: * (APPEND ‘(TALPRA MAGYAR) ‘(HI A HAZA)) (TALPRA MAGYAR HI A HAZA) • LENGTH - A lista elemeinek számát adja. Pl.: * (LENGTH ‘(A B C)) 3 * (LENGTH ‘(A (B C ))) 2 5/ 14 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • NTH - A lista n. elemét adja. Pl.: * (NTH 3 ‘(A B C D )) C * (NTH 5 ‘(A B C D)) NIL * (NTH 2 ‘(A (B C D))) (B C D) • MEMBER - A megadott elem első előfordulásával kezdődő részlistát adja. Pl.: * (MEMBER ‘JANCSI ‘(PAPRIKA JANCSI MOSOGAT)) (JANCSI MOSOGAT) * (MEMBER ‘KENNEDI ‘(JOHNSON CLINTON BUSH NIXON)) NIL * (MEMBER ‘(TUZROL PATTANT) ‘(CSINOS (TUZROL PATTANT) LEANYZO)) ((TUZROL PATTANT) LEANYZO) * (MEMBER ‘PATTANT ‘(CSINOS (TUZROL PATTANT))) NIL 5/ 15 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • SUBST - Magadott listaelem cseréje megadott elemmel. Pl.: * (SUBST ‘BAJNOKSAG ‘KUPA ‘(LABDA RUGO BAJNOKSAG)) (LABDA RUGO KUPA) * (SUBST ‘AROL ‘BRE ‘(AROL (AROL) AROL)) (BRE (AROL) BRE) * (SUBST ‘E ‘(L1 L2) ‘(A C D E F)) (A C D (L1 L2) F) * (SUBST ‘(L1 L2) ‘E ‘(A C D (L1 L2) F)) (A C D E F) • LIST - A felsorolt elemeket listává egyesíti. Pl.: * (LIST 1 2 3 4) (1 2 3 4) * (LIST ‘ABC ‘DEF ‘GHI) (ABC DEF GHI) * (LIST ‘ABC ‘(DEF GHI)) (ABC (DEF GHI)) 5/ 16 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • SETQQ - Szimbolikus atomhoz értéket rendel. A QUOTE implicite benne van, azaz nem akar kiértékelni. A hozzárendelt értéket kiírja. Pl.: * (SETQQ VALT1 12.4) 12.4 * VALT1 12.4 * (SETQQ LISTA (CAR (12 24)) ; nem értékel ki (CAR (12 24)) • SETQ - Szimbolikus atomhoz értéket rendel, a második argumentumot előbb kiértékeli. Pl.: * (SETQ LISTA (CAR (12 24)) 12 * LISTA 12 • SET - A szimbolikus atomhoz értéket rendel, előtte kiértékeli mindkét paramétert. Pl.: * (SET (CAR ‘(ELEM1 ELEM2)) (NTH 2 (115 335 555)) 335 5/ 17 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • PLUS, vagy + - A numerikus argumentumok összegét adja. Pl.: * (PLUS 1 2 3) 6 * (SETQQ SZAM 21) 21 * (PLUS SZAM 44) 65 • DIFFERENCE, vagy - - Két numerikus paramétere különbségét adja. Pl.: * (DIFFERENCE 55.5 23.4) 32.1 • TIMES, vagy * - A numerikus argumentumok szorzatát adja. Pl.: * (TIMES 3 5 7) 105 • QUOTIENT, vagy / - A két numerikus paramétere hányadosát adja, vagy egészek esetén, ha az nem egész, akkor p/q alakot. Pl.: * (QUOTIENT 6 3 ) 2 5/ 18 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • LISTP - Eldönti, hogy a paramétere lista-e, vagy sem (akkor atom). Pl.: * (LISTP ‘(EGY KETTO HAROM)) T * (LISTP ‘VALT1) NIL * (LISTP (CAR ‘(ALMA KORTE DIO))) NIL • AND - A paraméterek és kapcsolatának eredményével tér vissza. NIL a hamis, T az igaz (true) érték. Pl.: * (AND (LISTP ‘(EGY KETTO HAROM)) NIL) NIL * (AND T T) T • OR - A paraméterek vagy kapcsolatának eredményével tér vissza. Pl.: * (OR (LISTP ‘(EGY KETTO HAROM)) NIL) T * (OR NIL T NIL T) T 5/ 19 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • COND - Feltételek alapján való elágaztatás. Alakja: (COND ( feltétel1 kiértékelendő-1a kiértékelendő-1b ... kiértékelendő-1m ) ( feltétel2 kiértékelendő-2a kiértékelendő-2b ... kiértékelendő-2n ) ... ( feltételk kiértékelendő-ka kiértékelendő-kb ... kiértékelendő-ks ) ) Értéke az első igaz feltétel utolsó kiértékelendőjének értéke lesz. Pl.: * (COND ( (EQUAL 5 6) (PRINT OT-EGYENLO-HATTAL) ) ( (LISTP ‘(A B)) (SETQQ SZAM 12.67)) ) 12.67 5/ 20 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • EQUAL, vagy = - Egyenlőséges reláció. A visszatérő érték T, ha a két paraméter értéke azonos. Pl.: * (EQUAL 15 15) T * (EQUAL 15 (TIMES 3 4)) NIL * (EQUAL ‘(A B C) (LIST ‘A ‘B ‘C)) T • / = - Nemegyenlő reláció. A visszatérő érték T, ha az összes paraméter eltérő. Egyébként NIL. Pl.: * (/= 15 15) NIL * (/= 15 (TIMES 3 4)) T * (/= ‘(A B C) (LIST ‘A ‘B ‘C)) NIL 5/ 21 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • < - A visszatérő érték T, ha a paraméterek értékei monoton növekvő sorozatot alkotnak. Egyébként NIL. Pl.: * (< 12 15) T * (< 12 (TIMES 3 4)) NIL * (< ‘(A B C) (LIST ‘A ‘B ‘D)) T • <= - A visszatérő érték T, ha a paraméterek értékei monoton nem csökkenő sorozatot alkotnak. Egyébként NIL. Pl.: * (<= 12 15) T * (<= 15 (TIMES 3 5)) T * (<= ‘(A B C) (LIST ‘A ‘B ‘C)) T 5/ 22 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • > - A visszatérő érték T, ha a paraméterek értékei monoton csökkenő sorozatot alkotnak. Egyébként NIL. Pl.: * (> 12 11) T * (> 11 (TIMES 3 4)) NIL * (> ‘(A B C) (LIST ‘A ‘B ‘D)) NIL • >= - A visszatérő érték T, ha a paraméterek értékei monoton nem növekvő sorozatot alkotnak. Egyébként NIL. Pl.: * (>= 17 15) T * (>= 15 (TIMES 3 5)) T * (>= ‘(A C D) (LIST ‘A ‘B ‘C)) T 5/ 23 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Beépített függvények .. • WHILE - Ciklusszervező függvény. Első paramétere a feltétel, mindaddig újra és újra kiértékelődnek a további paraméterek, amíg az első paraméter T, azaz igaz. Visszatérési értéke az első paraméter leállási értéke, azaz NIL. • Pl.: Számok összege 12-től 12000-ig: * (SETQQ OSSZEG 0) 0 * (SETQQ CIKLUSVALTOZO 12) 12 * (WHILE (<= CIKLUSVALTOZO 12000) (SETQ OSSZEG (+ OSSZEG CIKLUSVALTOZO)) (SETQ CIKLUSVALTOZO (+ CIKLUSVALTOZO 1)) ) NIL * OSSZEG 71999928 – A WHILE függvényt ritkán használjuk, inkább rekurzív függvényhívást alkalmazunk. 5/ 24 . dr.Dudás László n A LISP programozási nyelv építőelemei .. • Saját függvény definiálása • DEFUN - Függvénydefiniáló függvény. (DEFUN függvénynév ( param1 param2 ... paramn) kiértékelendő1 kiértékelendő2 ... kiértékelendőw ) A függvénydefiniáló függvény hívásának eredményeként a függvénydefiníció eltárolódik. • Pl.: Számok négyzetét adó függvény definiálása: * (DEFUN NEGYZET (SZAM) (TIMES SZAM SZAM) ) NEGYZET 5/ 25 . dr.Dudás László n A LISP programozási példa • Hanoi tornyai feladat megoldása rekurzív függvénnyel A KR kezdőrúdról kell a CR célrúdra átrakni a csökkenő átmérő szerint felsorolt K4,K3,K2,K1 korongokat az SR segédrúd felhasználásával. Mindig csak nagyobb korongra rakhatunk kisebb korongot. Induló helyzet, a három rúdnak megfelelő három listában megadva: (K4 K3 K2 K1) ; KR kezdőrúd () ; CR célrúd () ; SR segédrúd. A rekurzív függvény bemenő paraméterei a KR, CR, SR listák induló tartalommal, kimenő értéke ugyanezen listák tartalma a végállapotnak megfelelően. Az alkalmazott technika: 1. Az átrakni kívánt alsó korong fölötti korongokat képzeletben egyben, valójában ezekre a korongokra a Hanoi algoritmust rekurzívan alkalmazva átrakjuk az SR segédrúdra 2. Az átrakni kívánt, most már rajta lévő korongok nélküli alsó korongot simán áttesszük a CR célrúdra 3. Végül az SR segédrúdról képzeletben egyben, valójában a Hanoi algoritmus rekurzív alkalmazásával a korongokat áttesszük a CR célrúdra. 5/ 26 . dr.Dudás László n A LISP programozási példa • A Hanoi tornyai feladat megoldását elvégző rekurzív függvény * (DEFUN HANOI (KR CR SR) (COND ((= (LENGTH KR) 1) ; a rekurzív hívások visszafordítója, ; ezt az aktuális feladatbeli legalsót már simán ; áttesszük: (LIST () (APPEND CR (LIST (CAR KR))) SR) ) (T ; egynél több korong van, az alsó felettieket rekurzív technikával ;áttesszük CR-re: (SETQ SR (CAR (CDR (HANOI (CDR KR) () () )))) ; 1. lépés: ; a segédrúdon van az eggyel kisebb torony (SETQ CR (APPEND CR (LIST (CAR KR)))) ; 2. lépés: ; a résztorony legalsó korongját áttettük CR célrúdra (SETQ CR (CAR (CDR (HANOI SR CR () ) ))) ; 3. lépés: ; mintha SR lenne a kezdőrúd a résztoronnyal, melyet most ; átraktunk a CR célrúdra (LIST () CR () ) ; a függvény visszaadott értéke ) ) ) HANOIM e s t e r s é g e s n A LISP programozási példa • * (HANOI ‘(K4 K3 K2 K1) () () ) (NIL (K4 K3 K2 K1) NIL) • 5/ 27 . dr.Dudás László A Hanoi tornyai függvény használata Az átrakási folyamat nyomonkövetéséhez PRINT függvényhívások beillesztésére, vagy a nyomkövetéssel történő futtatásra van szükség: * (TRACE HANOI) HANOI * (HANOI ‘(K4 K3 K2 K1) () () ) ; itt nyomon követhetjük a függvényhívásokat és az aktuális paramétereket. Forrás: Futó Iván: Mesterséges intelligencia Aula Kiadó,1999. 5/ 28 . dr.Dudás László n Bevezetés a PROLOG programozási nyelvbe • Jellemzői: Hasonló a PLANNER-hez a következőkben: • Az eljárások és a tények a mintaillesztés során kerülnek elő. Eltér viszont abban, hogy betartja a bemenőállítások sorrendjét. • A keresést automatikus visszalépéssel (back track) hajtja végre, amelyet azonban a programozó a ! (cut, vágás) operátorral módosíthat. Ez a lehetőség ellentmond a logikai programozás ideális koncepciójának: a programozó feladata csak a logikai probléma megadása, a problémaleírás algoritmikus kiértékelését pedig a gépnek kell elvégeznie. Kowalski képlete: algoritmus = logika + vezérlés Jelentése a következő: egy algoritmus mindig két komponenst tartalmaz implicit formában: – a logikai összetevőt, amely megadja a kérdéses problémára vonatkozó tudást, – a vezérlési összetevőt, mely megtestesíti a megoldási stratégiát az adott probléma esetére. 5/ 29 . dr.Dudás László n A PROLOG jellemzői A Prolog további jellemzői: • Bevezetésre került a symbol típus (domain), hogy a predikátumlogika individuumkonstansai, -változói és -függvényei a valóság egy részletét leképezhessék. • Fontos adatszerkezet a lista. A listafeldolgozás a mintaillesztésen és a rekurzión alapul. • A függvények a predikátumfüggvényeken alapulnak, és nincs különbség a bemenő és a kimenő változók között. • A bemeneti állítások (szabályok, clauses) formátuma korlátozott: P fej if Q and R and S. törzs A fej egyetlen predikátum, a törzs pedig atomi formulák (többnyire predikátumok, azaz logikai függvények) negációt nem tartalmazó konjunkciója (csak and lehet). 5/ 30 . dr.Dudás László n A PROLOG jellemzői .. A Prolog további jellemzői .. : • Mivel a törzs atomi formulák konjunkciója, azaz Horn-halmaz, így azt mondhatjuk, hogy a PROLOG a Horn halmazokra a rezolúció elvét alkalmazza. • A felhasználóra hagyja a rezolúciós stratégia megvalósítását: néhány megszorítást tett a bemenőállításokra, és az illesztés a bemenőállítások (clauses, tények és szabályok) megadott sorrendjében hajtódik végre. A rendszer így tömörebb lett és gyorsabb végrehajtást tesz lehetővé. • A predikátum logikára épül, de vannak eltérések: • Csak az elemváltozók kezdődnek nagybetűvel. • Ítéletkonstansok közül a False (fail) ritkán, a True és ítéletváltozók még ritkábban fordulnak elő. • Rendszerpredikátumok léteznek, melyek valamit elvégeznek és eközben igaz értéket vesznek fel. Pl.: read(). write(), circle(), stb. • Infix (közbeírt) alakú relációoperátorok (<,>, <=,>=,<>,=,><) és aritmetikai operátorok (+,-,*,/ ) a predikátumos alak helyett. Pl.: kisebb(X,Y) helyett X 0.2m Alosztály . . Anyag: Anyag: fa Súlya: IF-NEEDED: Térfogat* fajsúly Neve: Szék Szín: barna Lábszám: 4 Funkció: ülőhely Alosztály Alosztály Egy keretrendszer részlete Neve: Asztal Funkció: étkezés Neve: Magasság: default: < 1.4m 1m Magasság: Magasság: > 0.4m Lábszám: 4 Bárszék 1.2m Lábszám: 3 Anyag: alumínium 6/ 18 . dr.Dudás László n Keret alapú tudásszemléltetés .. A szemantikus hálókkal megegyező tulajdonságok: • Hierarchikus egyed - alosztály - osztály szerkezet. • Tulajdonság örökítés, mely kiterjed a procedurális tulajdonságokra is. Konfliktusok feloldása specifikusság, prioritás, vagy alapértelmezés figyelembe vételével. • Hasonló számítógépes reprezentáció: keretek - memóriahelyek; kapcsolatok - mutatók. Gyors működés. • Keretkezelő program a következtetés, problémamegoldás kivitelezésére, de jóval gazdagabb feladatkörrel. • Grafikus ábrázolás használható, de a grafika inkább a keretleíró nyelvek támogatója. (Lásd KappaPC szoftvert.) • Rugalmas tudás bővítés, módosítás, törlés. 6/ 19 . dr.Dudás László n Keret alapú tudásszemléltetés .. A szemantikus hálókon túlmutató tulajdonságok: • Egységbefoglalás: objektum, attribútumok, értékek, deklaratív és procedurális összetevők. Slot - filler, attribútum - érték párok, speciális attribútum a keret neve. • Az attribútumok és attribútum-értékek megadása más keretekre való utalással, többszörös egymásba ágyazással is lehetséges. • Default, alapértelmezett értékek szolgálják a kérdések megválaszolását. • A procedurális ismeretszemléltetés részeként értékeket előállító függvények, az értékváltozásokra működésbe lépő mechanizmusok, eseményvezérelt démon rendszer működik. IF_NEEDED IF_ADDED IF_MODIFIED IF_DELETED démonok működésének eredményeként dinamikus, élő rendszerek alakíthatók ki. 6/ 20 . dr.Dudás László n Keret alapú tudásszemléltetés .. A szemantikus hálókon túlmutató tulajdonságok .. : • Az attribútumok értékkészletére, értéktartományára, alap (default) értékére adhatunk meg előírásokat. • A keret tudásábrázolás sokkal elterjedtebb, mint a szemantikus háló, mivel gyakorlatilag annak összes tulajdonságát magába foglalja. Speciális keretkezelő nyelveket hoztak létre a keretek használatának megkönnyítésére (FRL,KRL,OWL,NETL,KL-ONE, ART, stb). Ezenkívül több hibrid, azaz többféle tudásszemléltetési módszert egyesítő rendszerben is alkalmazásra került (KappaPC, Level5 Object, Nexpert Object/Smart Elements, Aion Development System, CBR Express, stb.). 6/ 21 . dr.Dudás László n Példa eseményt leíró keretre Általános Előadás keret Megnevezés: előadás Terem: Lehetőségek: római számos előadótermek, kb.20db, arab számozású kistermek, kb. 200 db, laborok, kb. 40 db. Kezdési idő: 8:00, 9:00, ... , 18:00. Időtartam: 40 perc - 180 perc. Default: 50 perc. Befejezés időpontja: Ha szükséges: Kezdési idő + Időtartam. Eszközök: Lehetőségek: krétás tábla, filctollas tábla, számítógép, írásvetítő, diavetítő, projektor, video, TV, film, modell, laboreszközök. 6/ 22 . dr.Dudás László n Példa eseményt leíró keretre ME Alkalmazott Informatikai Tanszék MI előadás keret Megnevezés: MI előadás Terem: Lehetőségek: I, II, XXX. Default: I. Kezdési idő: szerda, kb.14:00. Időtartam: 160 perc - 175 perc. Default: 170 perc. Befejezés időpontja (öröklött függvény): http://www.lincoln.ac.nz/about/profile.htm Ha szükséges: Kezdési idő + Időtartam. Eszközök: Lehetőségek: krétás tábla, számítógép, írásvetítő, projektor. 6/ 23 . dr.Dudás László n A forgatókönyvek A Schank-féle forgatókönyv koncepcionális primitíveket és azok kapcsolatait rögzíti. A koncepcionális primitívek magasabb szintű elvonatkoztatásoknak felelnek meg. Példa: Előadás forgatókönyv Feltételezések (díszletek): előadóterem, tábla, kréta, írásvetítő, projektor, transzparensek, filctollak. Szereplők (szerepek): diákok, tanár. www.cf.ac.uk/international/ study/teaching.html Nézőpont: tanár. Eseménysorrend: 1. Belép a terembe 2. Hozzákészül, kivéve, ha nincs diák, mert akkor elmegy 3. Megtartja az előadást 4. Összeszedelődzködik 5. Elmegy. Fő esemény: 3. Megtartja az előadást. 6/ 24 . dr.Dudás László n Szemantikus primitívek és az Epizód-memória • • • • Probléma: két, keretalapú technikával szemléltetett ismerethalmaz vajon ugyanazt az ismeretrészt kódolja-e? Cél: olyan keretalapú rendszer létrehozása, mely az azonos objektumokat, eseményeket, tevékenységeket azonos módon kódolja. Megoldás: szemantikus primitívek, elemi koncepcionális egységek az ismeret atomjainak kódolására. Kidolgozott rendszerek: • Thesaurus ( Roget ) 1040 elemi koncepcionális egység a „kategóriák kapcsolódásának” megadására. • Yorick Wilks rendszere 70 elemből áll: entitások, akciók, típusjelzők, fajták és esetek. Egy mikronyelv ezen elemeknek osztályhierarchiába való szervezésére. Bármilyen összetett fogalom kifejezhető egy megfelelő formula megkonstruálásával. Pl.: folyadék - [FOLYÓ ANYAG] nyílás - [ÁTMENÕ RÉSZ] 6/ 25 . dr.Dudás László n Szemantikus primitívek és az Epizód-memória .. • Koncepcionális Függőség (Conceptional Dependence, CD) Roger Schank, 20 éves munkája eredménye • Természetes nyelvek megértéséhez, történetek felfogásához, újdonságok észleléséhez. • Cél: epizodikus memória, az egymást követő eseményekre vonatkozó tudás modellezése. • Elemi egységek: 11 tevékenység + egy további az ismeretlen esemény jelölésére: ATRANS Egy absztrakt viszony, mint pl. a birtoklás, vagy a tulajdonlás átvitelére ATTEND Az a tevékenység, mely egy érzékszervet egy objektumra irányít EXPEL Egy élőlény testéből a világba irányuló kiválasztás GRASP Egy objektum megfogása egy cselekvő által INGEST Egy objektumnak egy élőlény általi magáhozvétele MBUILD Régi ismeretekből új ismeret származtatása MOVE Egy testrész mozgatása az élőlény által • • • • • • • 6/ 26 . dr.Dudás László n Szemantikus primitívek és az Epizód-memória .. • MTRANS • • • PROPEL PTRANS SPEAK + DO • • Cselekvők közötti, vagy cselekvőn belüli mentális információ átvitel Fizikai erő alkalmazása egy objektumra Egy objektum fizikai helyének megváltoztatása Hangok száj általi generálása Ismeretlen esemény véghezvitele (valamit tenni). A fenti események mindegyike a következő szerkezetű rekorddal adható meg: • Név Az esemény azonosítója • Hely Hol történt az esemény? • Idő Mikor történt az esemény? • Cselekvő Ki (vagy mi) végezte a cselekvést? • Tevékenység Milyen tevékenység ment végbe? • Objektum Mely objektumra irányult a tevékenység, mi volt a tárgya? • (Irány:) • Honnan Honnan indult a tevékenység? • Hová Hol végződött a tevékenység? • Eszköz Hogyan, mivel hajtották végre a tevékenységet? 6/ 27 . dr.Dudás László n Szemantikus primitívek és az Epizód-memória .. • A fenti koncepciókat nem lehet egyszerűbb szimbólumokkal helyettesíteni, ezért primitívek, elemi egységek. • A CD primitívekkel csak eseményeket, tevékenységeket lehet ábrázolni, az eseményleíró keretek attribútumainak és attribútum értékeinek megadásához szükség van a hagyományos, objektumokra, azok jellemzőire vonatkozó keretekre is, mint ahogyan mutatja ezt a következő példa.M e s t e r s é g e s KÖZLEKEDÉS n Példa METRÓ egyed 1. ESEMÉNY rekesz rekesz NEW_YORK NÉV egyed rekesz VÁROS HELY IDÕ-65 rekesz IDÕ egyed rekesz CSELEKVÕ rekesz alosztály DÁTUM rekesz TEVÉKENYSÉG SZÁLLÍTÁS OBJEKTUM rekesz ÓRA rekesz CSOMAG rekesz IRÁNY IRÁNY-9 ÜGYNÖK-9 rekesz egyed HONNAN rekesz HOVÁ ÜGYFÉL-7 egyed 6/ 28 . dr.Dudás László SZEMÉLY MÁJUS 1 17:00 6/ 29 . dr.Dudás László n Esetalapú rendszerek ? • Cél: Régebbi feladatok megoldásakor szerzett tapasztalatok hasznosítása hasonló aktuális feladatok megoldásához. • Egy eset összetevői: • A probléma leírása • A probléma megoldásának leírása • A megoldás jóságának/rosszaságának minősítése. • Az eset leírása történhet bármilyen ismeretreprezentációs módszerrel, leggyakoribb a keretalapú szemléltetés. • A probléma leírásánál olyan formalizmust kell alkalmazni, amely olyan metrikát értelmez, amely révén az esetek problémaleírásai egymással számszerű eredménnyel összehasonlíthatók (Közelség). (10cm - 20cm; piros színű - narancs színű; szép - gyönyörű. Eltérő adattípusokra nem egyformán könnyű metrikát találni.) • Az eseteket esetbázisban tároljuk. 6/ 30 . dr.Dudás László n Az esetalapú következtetés működése ? 1. Visszakeresés: Az esetbázisban megkeressük a megoldandó aktuális problémához legjobban hasonlító, az alkalmazott metrika szerint legközelebbi korábbi problémaleírást. 2. Újrafelhasználás: amennyiben a hasonlóság egy megadott nagy értéket elér, a korábbi eset megoldását használjuk fel az aktuális probléma megoldására. 3. Hozzáigazítás: Amennyiben a legközelebbi eset hasonlósága nem éri el a kívánt szintet, a rendszer interaktív módon hozzáigazítja az eset problémaleírását az aktuális problémához, eközben természetesen az eset megoldás oldalát is módosítva. Az ily módon előállt megoldást használjuk fel az aktuális probléma megoldására. 4. Tanulás: A 3. pontban előállt hozzáigazított esetet az esetbázishoz adja, a megoldás jóságának/rosszaságának minősítésével együtt. 6/ 31 . dr.Dudás László n Az esetalapú következtetés működése .. ? probléma Esetbázis Visszakeresés Újrafelhasználás Hasonlóság megfelelő? i megoldás n Tanulás Hozzáigazítás Felhasználás probléma megoldás megoldás 6/ 32 . dr.Dudás László n Az esetalapú következtetés tulajdonságai ? Előnyök: • A probléma modelljének előzetes kidolgozása nélkül is alkalmazható • Használat közben fejlődik, könnyen bővíthető • Robusztus: hiányos, vagy rosszul definiált fogalmakkal is megadhatók esetek • Nem algoritmizálható problémák esetén is alkalmazható • Képes támogatni a korábbi hibás megoldások elkerülését is. Hátrányok: • Emberi interakciót igényel az esetek többségében • Minősége romolhat az eltérő felhasználók eltérő igényszintje miatt a tanulás során. 6/ 33 . dr.Dudás László n Az esetalapú következtetés tulajdonságai ? Összevetés a szabályalapú rendszerekkel Szabályalapú Szabály: a többi szabálytól független Esetalapú Eset: a többi esettől nem független Szabály visszakeresés: egzakt illesztéssel Eset visszakeresés: közelség vizsgálattal Szabályalkalmazás: szabályok sokaságát láncolva Eset alkalmazás: visszakeresés, hozzáigazítás Előzetes problémamodell kidolgozást igényel Nem igényel problémamodellezést Szűk keresztmetszet: az információkinyerés Csak esetek összegyűjtését igényli Hosszú fejlesztési idő Akár üres esetbázissal is indítható az alkalmazása Nagy szabályszám esetén lelassul Képes nagymennyiségű eset kezelésére Bővítés után validálást, konzisztenciaellenőrzést igényel Bővítése egyszerű Nem tanul Tanul, használat közben fejlődik. 6/ 34 . dr.Dudás László n Az esetalapú szoftvereszközök ? • • • KATE ReCall ReMind Hibrid eszközökben: • • • • CBR Express ART IM ART Enterprise Eclipse 6/ 1 . dr.Dudás László „ Mintaillesztő algoritmusok • Feladat: egy adott P minta összes előfordulásának megtalálása egy adott T szövegben. P és T karakterei egyaránt a véges elemű Σ ábécé jelei. • Input: • T szöveg, pl.: T= ”lelkes labdarúgók” – n = hossz(T) = 17 • P minta, pl.: P= ”labda” – m = hossz(P) = 5 • Output: • s eltolásértékek, melyeknél a P minta a T szövegben megtalálható: T[s+1..s+m] = P[1..m] 0 =< s <= n-m; 123456789 lelkes s = 7 n ... labdarúgók labda 1 2 . . m Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 2 . dr.Dudás László „ Vizsgált algoritmus típusok • • • „ Egyszerű mintaillesztő algoritmus Rabin-Karp mintaillesztő algoritmus Knuth-Morris-Pratt mintaillesztő algoritmus Egyszerű mintaillesztő algoritmus • Minden s eltolást megvizsgál a 0<= s <=n intervallumban. • Egyszerű_mintaillesztő(T, P) n ← hossz(T) m ← hossz(P) for s ← 0 to n-m do j ← 1 while j<=m and T[ s + j ] = P[ j ] do j ← j + 1 if j = m+1 print s Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 3 . dr.Dudás László „ Példák az Egyszerű mintaillesztő algoritmus működésére s = 0 s = 1 12345678 12345678 12345678 fallabda = T aaaaaaaa aaaaaaaa labda = P s = 0 aaaaa 12345 12345 12345678 12345678 12345678 fallabda aaaaaaaa aaaaaaaa labda s = 1 bbbbb s = 1 aaaaa 12345 12345 12345678 12345678 12345678 fallabda aaaaaaaa aaaaaaaa labda s = 2 bbbbb s = 2 aaaaa 12345 12345 12345 s = 3 s = 0 12345 12345 s = 2 bbbbb 12345678 12345678 12345678 fallabda aaaaaaaa aaaaaaaa labda s = 3 bbbbb 12345 12345 Összehasonlítások = 9 Összehasonlítások = 4 s = 3 aaaaa 12345 Összehasonlítások = 20 6/ 4 . dr.Dudás László „ Az Egyszerű mintaillesztő algoritmus elemzése • Legrosszabb eset • For ciklus: (n-m+1) • While ciklus: (m) elem-összehasonlítás • Összes elem-összehasonlítás: (n-m+1)*m • Elem-összehasonlítás arányos futási idő Θ((n-m+1)*m ) • Legjobb eset • For ciklus: (n-m+1) • While ciklus: (1) elem-összehasonlítás • Összes elem-összehasonlítás: (n-m+1)*1 • Elem-összehasonlítás arányos futási idő Θ((n-m+1)) • Átlagos eset • A szöveg és a minta karakterei egyenletes véletlen eloszlásúak • Ο(n-m), elég hatékony Lásd 2. Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 5 . dr.Dudás László „ Rabin-Karp mintaillesztő algoritmus • Alapgondolat: ha a szöveg és a minta is csak számokból állna, valamint a minta számjegykaraktereit egyetlen többjegyű számnak tekinthetnénk, hasonlóan a szöveg mintahossznyi részeit is egy-egy számértékkel reprezentálhatnánk, akkor a mintakeresés n-m+1 lépésben elvégezhető lenne. 1027 12345678 . . n T= 1022301 0272 P= 01027 12345 10223 2230 22301 23010 30102 1027 10272 Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 6 . dr.Dudás László „ Rabin-Karp mintaillesztő algoritmus .. • Jelölések: • Az ábécé Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, |Σ| = 10 • A minta számjegykaraktereit számértékre átszámító függvény: f(P) a Horner séma alkalmazásával O(m) időben kiszámítható, f(P)= P[m] +10*(P[m-1] + 10*(P[m-2] +...+ 10*(P[2] + 10*(P[1]))...)) Pl.: f(”01027”)= 7+10*(2+10*(0+10*(1+10*(0)))) = 1027 • Ha adott, vagy az előző módszerrel számítva rendelkezésre áll a T szöveg s eltolású, mintahosszúságú részének számértéke f s , akkor f s+1 O(1) idő alatt számítható: f s+1 =10*(f s – 10 m-1 * T[ s+1 ]) + T[ s+m+1 ] f s Pl.: T=”10223010272; s=2; f s = 22301; f s+1 = 10*(22301-10 4 *2)+0= 23010 f s+1 A teljes T szöveg értékekre való átalakításának ideje tehát O(m+n-m) Mivel a keresés O(n-m+1) idejű, a teljes algoritmus ideje = O(m + n + n-m+1) = O(2n+1) Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 7 . dr.Dudás László „ Rabin-Karp mintaillesztő algoritmus .. • Az algoritmus Rabin_Karp(T, P) T[s+m+1] f s fp ← f(P) fs ← f(T[1..m]) for s ← 0 to n – m do if fp = fs print s f s+1 T[s+1] if sd • fpm = (P[m] + d*(P[m-1] + d*(P[m-2]+ ... ...+ d*(P[2] + d*P[1])...))) mod q = (d*((d*... ((d*((d*0+P[1]) mod q)+P[2]) mod q)+... ...+ P[m-1]) mod q)+P[m]) mod q • Hasonlóan számítandó fsm a T[1..m] szövegrészletből. • Pl.: P=”1234”; d=10; q=11; 1234 mod 11 = 2 = (10*((10*((10*(1 mod 11)+2) mod 11)+3) mod 11)+4) mod 11 = 2 • Keresés, T[s+1] kiléptetése, T[s+m+1] beléptetése • fsm s+1 =(d*(fsm s – h* T[ s+1 ]) + T[ s+m+1 ]) mod q, ahol a h= d m-1 mod q számítható az előfeldolgozásban. Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 9 . dr.Dudás László „ A módosított Rabin-Karp mintaillesztő algoritmus • Rabin_Karp_Modulo(T, P, d, q) m ←hossz(P) n ← hossz(T) h ← d m-1 mod q // valójában (d mod q) szorzása önmagával ciklusban fpm ← 0 // a minta értékének modulója fsm ← 0 // a szöveg s eltolású része értékének modulója for i ← 1 to m do fpm ← (d*fpm+P[ i ]) mod q fsm ← (d*fsm+T[ i ]) mod q for s ← 0 to n-m do // keresés if fpm=fsm then // csak lehetőség, ellenőrizni kell j ← 1 // szerencsére csak ritkán kell ellenőrizni while j<=m and T[ s + j ] = P[ j ] do j ← j + 1 if j = m+1 print s if s < n-m then fsm ← (d*(fsm – h* T[ s+1 ]) + T[ s+m+1 ]) mod q // léptetés Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 10 . dr.Dudás László „ A módosított Rabin-Karp mintaillesztő algoritmus időkomplexitása • Legrosszabb eset • Csak egyféle karakter a mintában és a szövegben • Futási idő Θ((n-m+1)*m ), minden eltolást végigellenőriz • Általános eset • Általános esetben az érvényes eltolások száma kicsi • Futási idő O(n) + O(m*(v+n/q)), ahol v az érvényes eltolások száma • Ha q >= n, ez az idő O(n) • Megjegyzés • Az algoritmus könnyen kiterjeszthető kétdimenziós mintakeresésre T= P= Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 11 . dr.Dudás László „ Knuth-Morris-Pratt mintaillesztő • • Cél: a szöveg minden egyes karakterét csak egyszer felhasználni összehasonlításban Az Egyszerű mintaillesztő elfelejti a külső ciklus előző lépésében talált részleges illeszkedés során birtokába került információkat: Pl.: T=”kirándulnak a kirándulók a hegyekbe” P=”kiránduló” Mivel csak egy ‘k’ van P-ben, az első eltérést adó pozícióba ugorhatunk az eltolással. T=”blablablablalakban” P=”blablalak” Mekkora a legnagyobb ugrás P eltolásában, mely nem hagy ki esetleges egyezést? Toljuk rá hátulról a P mintát a T text feltárt részére, hogy a legnagyobb egyezést kapjuk: T=”blablablablalakban” P=”blablalak” • Ezek, a mintának önmaga kezdeteire hátulról való rátolhatóságára vonatkozó információk az előkészítési fázisban előállíthatók! Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 12 . dr.Dudás László „ A π prefix függvény • • A π(q) prefix függvény megadja, hogy a P minta q hosszúságú első részére a mintát hátulról nem teljesen rátolva az legfeljebb hány karakterrel hozható fedésbe. π(1) legyen 0. Példa: 12345 6 789 P=”blablalak” blablal ak π(1) = 0 π(6) = 3 π(2) = 0 blablal ak 123 4 56789 π(3) = 0 blablal ak π(4) = 1 blablal ak 1234 5 6789 π(5) = 2 π(7) = 0 π(8) = 0 blablal ak blablal ak π(8) = 0 Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 13 . dr.Dudás László „ A π prefix függvény algoritmusa • A prefix függvény értékei a P minta ismeretében az előkészítő fázisban meghatározhatók • Prefix_függvény_számítás(P) m ← hossz(P) π[1] ← 0 k ← 0 for q ← 2 to m do while k>0 and P[k+1] ≠ P[q] do k ← π[k] if P[k+1] = P[q] then k ← k+1 π[q] ← k return π • A Prefix függvény számítás futási ideje O(m). Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999 6/ 14 . dr.Dudás László „ A Knuth-Morris-Pratt mintaillesztő algoritmusa • A prefix függvény értékeinek ismeretében az algoritmus átugorhatja azon eltolások vizsgálatát, melyek eleve érvénytelenek. • KMP_mintaillesztő m ← hossz(P) n ← hossz(T) π ← Prefix_függvény_számítás(P) q ← 0 for i ← 1 to n do while q > 0 and P[q+1] ≠T[ i ] do q ← π[ q ] if P[q+1] = T[ i ] then q ← q+1 if q = m then print i-m+1 q ← π[ q ] • A KMP mintaillesztő futási ideje O(m+n), igen kedvező. Forrás: 1. Simonas Šaltenis: Advanced Algorithm Design and Analysis (Lecture 3) 2. Cormen-Leiserson-Rivest: Algoritmusok Műszaki Könyvkiadó, 1999Zárthelyi 1 C csoport 2003/2004. II. félév Mesterséges Intelligencia Alapjai ápr. 1. Név:.....................................................Tankör:............ sor:.........oszlop:........... 1. Mit értett Aaron Sloman az intelligencia rugalmasság összetevője alatt ? (3p) 2. Adja meg a reaktív ágens jellemzőit! (4p) 3. Rajzolja meg a fagráfját az "Az veszít, aki az utolsót húzza" játék fájának 4 induló pálcika esetére, ha MIN következik! (4p) 4. 4-5 mondatban ismertesse Joseph Weizenbaum ELIZA programjának lényegét ! (3p) 5. Adja meg a szakértőrendszer definícióját! (4p) ! 6. Mi a célja az adatbányászatnak ? (3p) 7. Adja meg a szabályalapú tudásszemléltetést alkalmazó szakértőrendszerek előreláncoló technikát alkalmazó működésének célját és mutassa be a működés lépéseit öt szabályt és néhány tényt felvéve! (9p) 8. Adja meg a propozíció jelentését ! (3p) 9. Részletezze a predikátum logika szintaxisát! (5p) 10. Bontsa fel klózokra az alábbi logikai kifejezést és végezze el a klózokkal a rezolúciót ! (5p)  p  q  r  s  r  q  p  t  s  t 11. Adjon egy példát egy indivídum függvényre ! (2p) 12. Mire szolgálnak a démonok a keretekben? (2p) 13. Irjon Prolog programot egy számsorozat összegének meghatározására ! (6p) 14. Említse meg a szemantikus háló három hibáját ! (3p) Értékelés: 0-28p: 1; 29-35p:2; 36-42p: 3; 43-49p: 4 50-56p: 5.