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

úterý 12:20 S8

cvičení 3.března
- jednoduché predikáty o rodinných vztacích
  bratranec(Kdo,Ci), svagr(Kdo,Ci), prababickazOtcovyStrany(Kdo,Ci), ...
- býti seznamem
- předposlední prvek seznamu
- rozdělení seznamu na dvě poloviny pomocí dvou signálů
- vypuštění prvku ze seznamu - prvního výskytu (amatér/profesionál)
- rozdělení seznamu na seznamy prvků na lichých a sudých místech
- spojování seznamů
- otáčení seznamu v kvadratickém čase pomocí otáčení
- permutace seznamu
- další jednoduché predikáty pro práci seznamy
- Domácí úkol - rozmyslet:
  1. vybraná posloupnost ze seznamu
  2. 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.)
cvičení 10.března
- vybraná posloupnost z dané posloupnosti
- starsiBratr(Kdo, Koho)
- nejstarsiBratr(Kdo, Koho)
- otáčení seznamu v lineárním čase použitím akumulátoru, predikát revers_append
- Matice jako seznam řádkových seznamů a predikáty pro práci s nimi
  obdelnikova(Mat), ctvercova(Matice), hlDiag(+Matice,-HlDiagonala),
  rozmyslet: slupka(Matice,Slupka,Pecka), spirala(Matice Spirala)
- Součtové seznamy, prvni prvek, vypuštění prvního prvku, otočení
  rozmyslet: zřetězení, převod na normální seznam, .....
Podařilo se otevřít další paralelku cvičení v tomtéž čase v S6. Je vítané, pokud tam dobrovolně přejdete, jinak bude cca 7-10 studentů přeřazeno "násilím".
cvičení 17.března
- otáčení matice
- spirála
- převod mezi seznamy a součtovými seznamy, zřetězení součtových seznamů
- flatten(Seznam,PlochySeznam) se zřetězením
  rozmyslet:bez concatenace
- Reprezentace vektorů pomocí vektoru obrazů v(N,Obrazy) pomocí cyklu c(N, SeznamNetriviálníchCyklů)
  převod v2c (návod uděláme pomocnou reprezenaci pomocí seznamu dvojic e(Vzor,Obraz),
  v2d a pak d2c
- Rozmyslet: lze predikát vytvořený predikát v2c použít pro převod opačným směrem?,
  pokud by nebylo efektivní, vytvořit převod c2v
- Domácí úkol číslo 1:
  1. otáčení matice co nejhezčeji
  2. slupka(+Matice,-Slupka,-Pecka)
  3. predikát d2c
  4. mocnění permutací reprezentovaných pomocí cyklů - viz výše
cvičení 24.března
- Pokud jste neposlali domácí úkol, učiňte tak nejpozději pátku 14:00
- krátká písemka
  1. rozdělení seznamu na třetiny - bez aritmetiky
  2. "vybraný" strom z binárního stromu
- listy binárního stromu bez konkatenace
- kanonická reprezentace obecného stromu pomocí binárního stromu
- Domácí úkol číslo 2:
  1. Vyrobte z kanonické reprezentace obecného stromu T seznam, který by vznikl průchodem (obecného) stromu T do šířky
  2. Vyrobte k zadanému binárnímu stromu seznam jeho uzlů v pořadí s rostoucí vzdáleností od listů (pro stejnou vzdálenost odleva do prava)
cvičení 31.března
- flatten(Seznam,PlochySeznam) se zřetězením
- pořadí dané permutace v lexikografickém uspořádání
- nalezení permutace, která je v lexikografickém uspořádání na daném místě
- dvě řešení druhého problému z domácího úkolu
- Domácí úkol číslo 3: Vyrobte proceduru, která zadaný binární strom předělá "otáčením" (výměnou levého a pravého podstromu) na strom, ve kterém v každém uzlu platí, že
  "počet prvků v jeho levém podstromu je alespoń tak velký jako počet v pravém podstromu"
cvičení 7.dubna
- nabídka témat zápočtových úloh
- Nejpozději do 14 dní si každý domluví téma zápočtové úlohy, nejpozději do 3 neděl mi pošle specifikaci jako přílohu mailu s předmětem "NPZAP"
- topologické uspořádání grafu
- několik jednoduchých příkladů na predikáty setof a bagof
- Domácí úkoly: zkuste odladit na počítači
  1. převod reprezenace grafu jako seznamů hran a vrcholů na seznam termů typu
    v(Vrchol, Pocet_predchudcu, Seznam_Naseleniku)
  2. predikát topol(+Graf, -Ok, -Topolgické uspořádání)
    graf je zadaný jako seznam trojic z předchozího úkolu, příznak Ok je true když jde topologicky uspořádat, false když nejde
  3. predikát topol2(+Graf, -OK, - Seznam)
    totéž jen když je OK=false, je seznam nějaký cyklus v grafu G
    pokud predikát topol2 není příliš složitější než by byl predikát topol, není třeba ukol 2) dělat
  4. Definujte operátory pro výrokové spojky: negace, konjunkce, disjunkce a implikace a definujte predikát taut/1,
    který uspěje pokud argumentem je tautologie.
cvičení 14.dubna
Programovací jazyk SCHEME
- Obracení seznamu
- Obracení zseznamu s akumulátorem
- Funkce, která k zadanému seznamu L spočítá seznam, jehož prvky jsou maximální souvislé neklesající úseky zadaného seznamu L
- Definice datové strukturu Mobil - konstruktory a selektory
- Domácí úkol:
  1. Funkce, která počítá, zda je zadaný mobil vyvážený (momentová věta)
  2. Sestavte funkci, která k dvojici (ROST,N), kde ROST je rostoucí seznam a n je číslo (můžete předpokládat, že není delší než délka seznamu ROST
    vrátí dvojici
    (Strom,ZbyteK), kde Strom je dokonale vybalancovaný binární vyhledávací strom vytvořený z prvních N prvků seznamu ROST
Domácí úkol zašlete jako přílohu mailu se subjectem "NPDCV5" nejpozději do soboty 18.dubna 17:00.
Do přílohy uveďte na první řádek jméno,příjmeni a číslo úkolu

Ti, kdož dluží minulý úkol, zašlete ho také

28.dubna si napíšeme "zápočtovou" písemku z Prologu a SCHEME