PRM046 Co bylo na přednáškách a cvičeních

Domluvili jsme se, že nebudeme striktně rozlišovat mezi cvičením a přednáškou, ale fomu budeme pružně přizpůsobovat potřebám probírané látky i jednotlivých studentů.
Nebudu zde uvádět výčet všech příkladů, které jsme dělali, jen témata, která jsme probali.

1. 1.října
2. 8.října
3. 15.října
4. 22.října
výuka 29.října nebude, nahradíme prodloužením výuky v jiných termínech
5. 5.listopadu
6. 12.listopadu
7. 19.listopadu
8. 26.listopadu
9. 3.prosince
10. 10.prosince
11. 17.prosince
12. 7.ledna
13. 14.ledna

1. 1.října
   • Náplň kursu, podmínky pro zápočet, zkouška.
   • Neprocedurální funkcionální, logické programování.
   • Příklad jednoduchého programu v Prologu a dotazů na něj.
   • Fakt, pravidlo, proměnná, anonymní proměnná.
   • Definice seznamu a notace pro jejich zápis.
   • Jednoduché predikáty pro práci se senamy, např.
     prvek, první, poslední, předposlední prvek seznamu
     vypuštění a vládání prvku ze a do seznamu,
     permutace seznamu, zřetězení seznamů,
     otáčení seznamu v kvadratickém čase, atd.
2. 8.října
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
   • opakování jednoduchých predikátů pro práci se seznamy, další predikáty
   • rozpůlení seznamu bez aritmetiky, dvě řešení
   • predikát reverze_append - otáčení seznamu pomocí akumulátoru
   • Rozmyslet: Vytvořit predikáty nejstarší bratr, starší bratr, sestry
3. 15.října
   • Unifikace
   • Algoritmus interpretu Prologu (unifikace + backtracking).
   • Procedurální a deklarativní význam prologiovskéhio programu
   • Deklarativně správná procedura v čisém (pure) Prologu je parciálně správná v operačním smyslu
   • Dvě varianty dekarativně správných procedur pro vyjádření vztahu predek(Kdo, Koho), z nichž jeden odpoví vždy a druhý nikdy
   • Rozmyslet: chování čtyř (deklarativně ekvivalentních) variant procedury predek
   • Reprezentace matice jako seznamu řádkovych seznamů,
     hlDiag(Matoce,HlDiag), bytiobdelnikovou(Mat), bytictvercova(Matice), bytiPrazdnouMatici(Matice),otočení matice o 90 stupňů
   • Rozmyslet: několik predikátů pracujících s maticemi:
     slupka(Matice,Slupka,Pecka), spirala(Matice,Spirala)
     řešení mi pošlete do středy mailem se subjectem DCv1
   • Binární stromy - jedna možná reprezentace
   • jednoduché predikáty pro práci se seznamy
     prvek/2, inorder průchod, výpis listů (i varianty bez konkatenace pomocí akumulátoru)
4. 22.října
   • Opakování:
     procedurální (unifikace a backtracking) a deklarativní (formule) význam programu, jak se může chovat deklarativně správný program
   • predikát spirála, otáčení matice pomocí akumulátoru
   • proměnná v Prologu je jen označení místa pro substituci
   • rozdílové seznamy ja příklad neúplně definovaných datových struktur
     konkatenace rozdílových seznamů v konstantním čase
     převod mezi seznamy a rozfílovými seznamy uděláme později
   • Aritmetika, is, aritmetické operátory
     jednoduché predikáty
   • vkládání do binárního vyhledávacího stromu
   • vypouštěni z binárního vyhledávacího stromu
   • vypouštění čísel mimo zadaný interval z binárního vyhledávacího stromu
   • následující permutace v lexikografickém uspořádání
   • Zopakujte si vše, co jsme dosud dělali,
     dohodli jsme se, že přístě (za 14 dní) si mimo jiné napíšeme krátkou písemku
   • Příklady na rozmyšlenou
     pokud to zvládnete, pošlete mailem do 3.11. se subjectem DCv2
     1. naprogramujte proceduru vkládání do binárního vyhledávacího stromu, kterou by šlo použít i pro vypouštění
     2. reprezentace permutace jako vektoru obrazů a jako seznam netriviálních cyklů, udělejte převodní predikáty
     3. predikát slupka(Matice, Slupka, Pecka)
5. 5.listopadu
   • podrobný návod k domácímu úkolu z minula
   • podrobný rozbor úlohy najít k-tou mocninu permutace zadané pomocí netriviálních cyklů
   • Průchody grafu do hloubky a do šířky - algoritmus pomocí seznamů OPEN a CLOSE
     procedury pro průchody stromem
   • Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-listejná, pak odleva do prava)
   • Predikáty consult/1, reconsult/1, halt/0,
   • Krabičkový model výpočtu odpovědi na dotaz. Princip ladění v Prologu, predikáty trace/0, notrace/0, spy/1, nospy/1.
   • ukázka páce s kompilátorem SWI prologu a ladění v něm
   • Na příště:
     Je třeba "srovnat krok", jinak by Vám látka mohla "zcela utéct"
     1. Pohrajte si s kompilátorem
     2. přečtěte si se skriptíček kapitoly 1-10
     3. Zopakujte si vše, co jsme dosud dělali,
        dohodli jsme se, že přístě si mimo jiné napíšeme krátkou písemku
     4. pošlete pokud možno do středy (nejdéle do čtvrtka v poledne) mailem se subjectem DCv3
        příklady, které byly na minule plus mocninu permutace zadanou jsko seznam netriviálních cyklů
     5. Lehčí příklady k tréningu programování:
        Množina (čísel) je reprezentována jako rostoucí seznam jejich prvků.
        Funkce je reprezentována jako seznam dvojic f(Vzor,Obraz) seřazený vzestupně podle vzoru.
        Sestavte procedury pro:
        1. základní množninové operace: sjednocení, průnik, rozdíl
        2. k dané množně M a funkci F najde obraz F(M) a vzor f^-1(M)
        3. test zda je funkce F prostá
        4. k dané funkci F najde funkci k ní inverzní
        5. skládání dvou funkcí