Logikai programozás gyakorlat

• A  kabinetes rendszereken a /pub/LogikaiProgramozas könyvtár alatt különböző, a kurzushoz kapcsolódó anyagok találhatók. Többek között:
  
• előadásjegyzet pdf (prolog04.pdf) illetve Word (prolog04.doc) formátumban,
• Maluszinsky angol nyelvű logikai programozás könyve, illetve
  
• letölthető prolog rendszerek.
• A gyakorlathoz kapcsolódó követelmények és határidők.
• A kötelező programokkal kapcsolatos tudnivalók és néhány témaötlet, valamint az eddigi választásokat tartalmazó lista.
  
• A gyakorlást segítendő:
  
• az órához kapcsolódó feladatok egy-egy megoldása
  
• a félév végi beugróhoz hasonló jellegű feladatok.
• Prologgal kapcsolatos hasznos tudnivalók.
• On-line help a SICStus prologhoz (angolul), azon belül
  
• egy kis rész a be- és kimenő paraméterekről,
  
• a beépített predikátumokról,
• a könyvtári modulokról.
  

• Ismerkedés a prologgal: a csalad példa, mely szemléltet néhány alapvető módszert:  a rekurziót, illetve a több szabállyal történő definiálást.
  Feladat: további rokoni kapcsolatok definiálása prologban.
• A prolog - a termek legáltalánosabb egyesítésén (lásd pl. előadás jegyzet) alapuló - kiértékelési mechanizmusa egy példán szemléltetve. Ezen mechanizmus ismerete sokszor nagy segítéget jelent a hibák elerülésében egy-egy program írásakor. Például könnyedén megválaszolható, miért kerül végtelen ciklusba a prolog, ha a csalad példában az os/2 predikátumhoz tartozó szabályok helyett az
  
      os(X,Y):- os(Z,Y), szulo(X,Z).

      os(X,Y):- szulo(X,Y).
  szabályokat felvéve feltesszük a következő kérdést:
      os(a,C).
1. feladat: készíts egy végtelen ciklust a természetes számok kilistázására! <mo>
  2. feladat: készíts egy végtelen ciklust az egész számok kilistázására! (0, 1, -1, 2, -2, 3, -3, 4, -4, ... sorrendben) <mo>
•  A prolog aritmetikai eszközei (műveletek, egyenlőségjelek, stb.), a kiiratás egy elemi formája, ciklusok szimulálása, illetve a tagadás néhány formája: szamok1, szamok2, szamok3 példák.
  3. Feladat: adot N, M és K inputok esetén listázd ki az összes N és M közötti K-val osztható egész számot! <mo>
  4. Feladat: írj egy függvényt pozitív egészek gyökének kiszámítására/közelítésére! <mo>
  Feladat: módosítsd a prímszámokat definiáló klózokat úgy, hogy csak 1 és (nagyjából) n gyöke közti számokkal való oszthatóságot ellenőrizzen!
• Listák kezelése, és néhány alkalmazása: rutin példák, tökéletes számok (órai feladat),  sorozat generálás.
  5. Írj egy programot listák különbségének legenerálására: az előállított listábában pontosan azon elemek szerepeljenek, melyek csak az első listában fordulnak elő, és pontosan annyiszor. <mo>
  6. Feladat: definiálj egy predikátumot, mely listák használata nélkül ellenőrzi, hogy az inputja tökéletes szám-e! <mo>
  7. Adott K és N input esetén állítsd elő az összes, az 1, 2, . . . , K számokból képzett, legalább/legfeljebb N hosszú monoton növő/csökkenő sorozatot! <mo>
• A vágás: egyszerű példák, illetve egy speciális LP feladat lehetséges megoldásainak legenárálása. Egy kis leírás a vágásról a SICStus honlapján, és egy ábra annak szemléltetésére, hogyan módosítja a kiértékelési mechanizmust, miként szűkíti a keresési teret a vágók használata.
  Órai feladat: (koordinátatengelyekkel párhuzamos átlójú) rombusz által lefedett rácspontok kilistázása.
  8. Generáld le egy középpontjával és sugarával megadott kör által lefedett rácspontokat. <mo>
  9. Generáld le K db, középpontjával és sugarával megadott körlap metszetében levő rácspontok halmazát. (Vigyázat! Ezen metszet állhat csupa nem-szomszédos elemből is, mint például a (0,0) és az (1,1) középpontú 1 sugarú körök esetén!) <mo>
• Fák, gráfok megvalósítása.  +
  10. Feladat: irányítatlan gráf komplementerének kiiratása . <mo>
  
• Megoldásgyűjtők használata, és egy-két alkalmazása gráfokon.
  11. Feladat: irányított gráf csúcsainak kifok (esetleg fokszám) szerinti szétválogatása. <mo>
• Stringek kezelése néhány példán  keresztül.  +
  12/a. Feladat: adott egy K egész és szavak egy L listája; gyűjtsd össze azokat a kizárólag L-beli szavakból összerakott (whitespace nélküli!) palindromákat, melyek hossza legfeljebb K! <mo>
  
• File-kezelés demonstrálása egy szortírozási problémán, és egy hozzá való adat file.
  12/b. Feladat: ugyanaz, mint 11/a, de a palindromákat file-ba kell írni, és az input szavakat is file-ból kell beolvasni. <mo>
• Dinamikus predikátumok alkalmazása: maximális hosszúságú prefix keresése (és egy példa az input file-ra). Ugyanez polinomiális időben.
  13. Feladat: file-ban felsorolt szavakból olyan szólista-párok legenerálása, melyek összeolvasva ugyanazt adják, de a páros két listájában nincs azonos pozíción szóhatár. Ilyen például ([hatalma,sok],[hatalmas,ok]), ha  az input file tartalmazza a szo(ok). szo(sok). szo(hatalma). szo(hatalmas) definíciókat.
• Beugró példák.
  Feladat: oldd meg az első példát a következő felépítésben:
  
  1. részlisták legenerálása
  2. tesztelés:
  1. a lemérhető távolságok összegyűjtése egy Tav nevű listába
  2. Tav listában egyező elemek keresése
  3. kiiratás
  Feladat: oldd meg a második példát a kovetkező felépítésben:
1. azon listák legenerálása, melyek N darab 'l' (azaz "lefelé") és N darab 'j' (azaz "jobbra") szimbólumból állnak
2. tesztelés: az adott lista által kódolt út megfelel-e a feltételnek
3. kiiratás
• DCG nyelvtanok használhatók attribútumos illetve attribútum nélküli, környezetfüggetlen illetve (bizonyos megkötésekkel) környezetfüggő nyelvtanok leírására/definiálására. Egy alkalmazás nyelvtani elemzésekhez, illetve egy rövid, angol nyelvű leírás a SICStus honlapján.

• Maximális párosítás keresése páros gráfban a magyar módszer segítségével - illetve ugyanez a repeatet használva -, mely az inputot a graf.pl file-ból veszi.

• Ninety-Nine Prolog Problems