Cvičení z Neprocedurálního programování

čtvrtek 10:40 SU1

1. cvičení 20.února
   • stručný úvod - co je to neprocedurální programování
   • tvar prologovského programu: klausule, fakta, pravidla
   • jednoduchý popis příbuzenských vztahů a dotazy na něj
   • podrobnější a přesnější popis bude na přednášce
   • odpovědí na dotaz bez proměnné je buď yes když vztah platí, nebo no když vztah neplatí
   • obsahuje-li dotaz proměnnou resp. proměnné pak dotaz uspěje pokud se najdou substituce za všechny proměnné takové aby vytvořily platný vztah
   • jednoduché predikáty o rodinných vztazích
     bratr(kdo,Ci), syn(Kdo,Koho), otec(Ot,Koho), sourozenec(Kdo, Koho), babicka(Bab,Vnouce)
   • definice seznamu a syntaktické konvence
     • před | může být výčet prvků seznamu, např. místo [a,[b|[c,d]]] můžeme zapsat jako [a,b|[c,d]]
     • jeli za | prazdny seznam [] , tak ho lze vynechat, např. [a,b,c|[]] je totéž jako [a,b,c]
   • predikát býti seznamem
   • první prvek seznamu, předposlední prvek seznamu
   • spojení seznamů
   • Domácí úkol - rozmyslet
     
     1. předpokládejte "databázi" fakt typu rodic(Rod,Dite), muz(Kdo), zena(Kdo)
        a vytvořte předikáty svagr(Svagr,Koho), pradedeček(Pradded,Koho), potomek(Kdo,Koho) na cvičení byl zadán jen první
     2. nepovinný (pokud by dělalo potíže, netrapte se s tím, tady jsem to přehnal), uděláme to na příštím cvičení
        Předpokládejte, že v databázi jsou fakta typu
        rodina(Otec,Matka,Deti) % Deti je seznam dětí od nejstaršího k nejmladšímu
        muz(Kdo) a zena (Kdo)
        Vytvořte predikáty:
        • nejstarsiBratr(Kdo, Koho)
        • starsiBratr(Kdo, Koho)
        • mladsBratri(MlBratri,Koho) % MlBratri je seznam mladších bratrů Koho (od nejstaršího k nejml.)
        • starsiBratri(StBratri,Koho) % StBratri jsou seznam starsich bratrů Koho (od nejstaršího k nejml.)

        dám návod na jedno z možných řešení:

        • vytvoříme predikát vypust_prvek (Sez, Prv, Zac, Ko), který uspěje pokud je Prv prvkem seznamu Sez,
          a Zac pak bude seznam prvků, které předcházejí c Sez prvku Prv, a Kon pak bude seznam prvků, které následují v seznamu Sez za prvkem Prv
          např. vypust_prvek ([a,b,c,d], b, [a], [c,d]) , vypust_prvek ([a,b,c,d], a, [], [b,c,d])
        • vytvoříme predikát vyhod_zeny(SeznamDeti,Kluci)

2. cvičení 27.února
   • vypuštění prvku ze seznamu - prvního výskytu (amatér/profesionál)
   • vypuštění všech výskytů prvku ze seznamu
   • rozdělení seznamu na seznamy prvků na lichých a sudých místech
   • otáčení seznamu v kvadratickém čase pomocí otáčení - zkusit vymyslet v lineárním čase
   • další jednoduché predikáty pro práci seznamy
   • matice jako seznam seznamů řádkových seznamů
   • obdélníková, čtvercová matice
   • utržení prvního sloupce
   • prázdná matice má více reprezentací - [] a seznam prázdných seznamů
   • hlavní diagonála čtvercové matice
   • řešení nepoviného úkolu z minulého cvičení - různí bratři
   • domácí úkol č.2
     1. otočení matice o 90 stupňů
     2. spirála
     3. slupka a pecka


3. cvičení 5.března
   
   Začněte své prográmky ladit v Prologu, pokud to bude dělat potíže, podíváme se na to příště
   • opakování otáčení seznamu v lineárním čase pomocí akumulátoru
     místo otáčení ot(+Seznam, -otoceny_seznam) vytvářme predikát otA (+Seznam, +Akumulátor, -Otoceny_seznam_zřetězený_s_Akumulátorem) ot(S,OS):- otA(S,[],OS). otA([],A,A). otA([H|T],A,OSA):- otA(T, [H|A], OSA]).
   • obdobně třídění quick sortem bez conkatenace
   • opakování aritmetiky:
     operátor is a aritmetické relační operátory : <, <=, >,>=, =:=, =\=
   • největší společný dělitel dvou čísel a seznamu čísel
   • otáčení matice, i zde můžeme využít akumulátoru
   • spirála sp(+Matice, -Spirála)
   • inverzní vztah, který ze spirály (a rozměru matice) vytvoří matici, ze které spirála byla vyrobena, můžeme dostat "zadarmo".
     vytvoříme matici z anonymních proměnných daných rozměrů - anonym_mat(+Pocet_radek, +PocetSloupcu, -Anonym_mat)
     namotej(-Mat,+PocR, +PocSl, +Spir)
     namotej(Mat,C Spir) :- anonym_mat(PocR, PocSl, Mat), spirala(Mat, Spir).
   • Rozdílové seznamy jsou speciální případ neúplně definovaných datových struktur - obsahují volnou proměnnou
     rozdílová reprezentace seznamu [a,b,c] je [a,b,c|C] - C kde C je volná proměnná, rozdílová reprezentace seznamu [] je C-C kde C je volná proměnná. Tedy vlastně umístíme volnou proměnnou "na konec seznamu "místo []" a když ji dáme ještě někam jinam ( např. za minus můžeme na konec seznamu "přidat cokoli" jen unifikací
     zřetězení rozdílových seznamů v konstantnín čase conc(A-B,B-C,A-C)
   • podívejte se na quicksort bez concatenace - je to vlastně "totéž", jako kdybychom programovali quicksot rozdílových seznamů
   • největší společný dělitel dvou čísel a seznamu čísel
     
   • domácí úkoly
     1. naprogramujte predikáty převádějící seznamy na rozdílové seznamy a zpět (může to být i jen jeden obousměrný)
     2. množinové operace
        množinu reprezentujeme jako rostoucí seznam jejích prvků
        naprogramujte predikáty, které počítají sjednocení, rozdíl a průnik dvou množin
     3. funkci reprezentujeme jako seznam dvojic f(vzor, obraz) uspořanoý podle první složky
        naprogramujte relace obraz(+Funkce,+Mnozina, -Obraz_mnoziny) a vzor(+Funkce,+Mnozina, -obraz(+Funkce,+Mnozina, -Vzor_mnoziny)