Nyhetsflöde

Hej

Jag fick en fråga om de extra bilderna från föreläsning 1.

Jag presenterade lite bakgrund i form av bilder om satslogik och predikatlogik

från kursen DD1350 (F2,F3,F4) h17. Samma material presenteras ht18 i DD1351.

Man kan hitta material av denna typ på nätet t.ex. i wikipedia och på andra ställen.

Jag kommer att göra en sammanfattning av vad av detta

ni behöver veta för tenta och vidare studier i kursen, men kanske inte före morgonsagens övning..

Vill ni leta info själva, anv'nd t.ex .sökord som "satslogik" ("propositional logic").,

"predikatlogik", "predicate logic". "Naturlig deduktion" ("Natural deduction").

mvh -Thomas S.

Lektion  nummer 7

Metaprogrammering. Primitiverna var/1, nonvar/1, ground/1.

arg/3 och functor/3 to construct and deconstruct terms.

Hur man samlar upp alla lösningar i en lista: primitiverna findall/3, bagof/3 och setof./3

Reflektiva interpretatorer. "The Vanilla prolog interpreter".

Hur man utvidgar metainterpretatorn för att konstruera ett bevis, för att implementera "depth bounded search" och "iterative deepening".

Expertsystem och Prolog.

Ett diagnossystem för att finna fel i bilar. Utvidgning av "vanilla"-interpretatorn till en "inference engine" för diagnossystemet.

Lite repetition och förtydliganden runt den logiska semantiken för logikprogram.

Metainterpretatorn solve/1 som ett exempel.

Lektion  nummer 6 (räkneövning inställd)

DCG-syntaxen (Definite clause grammar) för att uttrycka kontextberoende grammitor direkt i Prolog.

Hur DCG-regler översätts till Prolog vid inläsningen.

Hur man kan säga att DCG använder differenslistor.

Användning av DCG-regler för att skriva program som modellerar tillståndsövergångar, t.ex. en interpretator för ett programmeringsspråk.

Hur man implementerar apply i Prolog. map_list som exempel på "högre ordningens programmering" à la funktionell programmering.

Att få fram samtliga lösningar i en lista. Primitiverna findall, bagof and setof.

Nästa gång tar vi upp metaprogrammering, samt expertsystem. På räkneövningen går vi igenom gamla tentatal och tar upp era frågor till diskussion.

Avbokat övningstillfälle ID1213 vTorsdag 5 Oktober v 40, 13-15

Jag blev tvungen att ställa in övningstillfälet på torsdag eftermiddag pga

ett möte där jag förväntas vara med.

Lektionen på förmiddagen ges som planerat.

Vill ni diskutera uppgifter i boken eller på webben eller annat i kursen

som ni undrar över så kan ni istället boka enskild handledning med mig.

Jag är ledig 15-17 på torsdag och fredag förmiddag, men jag har uppfattat

att de flesta av er har andra kursen inbokade då. Jag är tillgänglig även

efter fem från och med torsdag, om ni bokar i förväg.

Bästa hälsningar  - Thomas S.

Lektion och räkneövning nummer 5

Vi gick igenom negation med NAF-regeln (negation as failure).

Vi definierade !-primitiven och introducerade "if-then-else"-syntaxen.

Dessutom gick vi igenom sökning i grafer, samt problemformulering med

generate-and-test. permute för att generera alla möjliga permutationer av en lista definierades.

Några exempel togs upp, t.ex. N-queens, missionaries and cannibals,

att hitta en väg genom en graf. Att undvika loopar i grafsökning.

En snabb introduktion till olika sökmetoder för parallellism i Prolog.

Dessutom täckte vi förberedelsen till grammatikdelen, dvs hur man uttrycker

kontextfria respektive kontextberoende grammatikor.

Hur en interpretator för produktionsregler omformas till ett prologprogram som parsar.

Hur diff-listor kan användas för att effektivisera grammatikregler.

Hur man genererar ett syntaxträd som resultat av att parsa en sekvens av symboler.

Alla frågor på materialet är välkomna! Använd e-post eller denna meddelandevägg.

Räkneövning vecka 4

På räkneövningen vecka fyra fokuserade vi på att formulera bra representationer av matriser m*n,

att implementera operatiner på matriser som t.ex. transponat, matrismultiplikation.

Generalisering av matriser till godtyckligt antal dimensioner.

Diskutera för- och nackdelar med representationen ni valt. Finns det alternativ?

Lektion  vecka 4

Repetition av algoritmer på listor och träd.

Hemuppgift, unsort_degree.

Ackumulerade parametrar.

naive reverse.

quicksort.

Effektivare reverse med ackumulerande parametrar.

Differensstrukturer (difflistor)

Differenslistor är en representation av sekvenser.

append med difflistor görs utan rekursion. Endast en unifiering. Mycket effektivt!

append_dl(A-B,B-C,A-C).

Hur man implementerar reverse, quicksort etc., med difflistor som intermediär struktur.

flatten för att "platta ut" listor kan göras effektiv med difflistor. (hemuppgift).

Att implementera köer med difflistor.

FIFO-kön har två operationer, enqueue och dequeue för att sätta in ett element sist

respektive ta bort första elementet i difflistan.

Hur fungerar difflistorna?

Sammanfattning vecka 3, lektion och övning

Repetition av modellteorin för prolog.

Lite repetition om bevisteorin för logikprogrammering, sökträd, bevisträd, bevis. SLD-resolution.

sundhet (allt man kan bevisa är sant) och fullständighet (allt sant kan bevisas) hos SLD-resolution.

Vad händer om SLD-trädet är oändligt? Svar: vi tappar fullständigheten i normalfallet, dvs det kan finnas lösningar som vi inte hittar pga att prologinterpretatorn loopar i en annan gren.

Programmering med träd och listor.

spegelpredikatet mirror(T1,T2) där T2 är en spegelbild av T1 och omvänt.

ATt implementera ett "dictionary" med hjälp av ett partiellt instanterat binärt träd.

append(L1,L2,L), olika användningar, sätta samman listor, ta isär listor, flera lösningar möjliga.

Hitta sista elementet i en lista, last(L,E).

Ta bort duplikat ur en lista.

Sortering av listor med (not so) quicksort.

Exempel med hur man använder listor för att representera mängder.

Invarianter:

- listan är unik, dvs. inget element förekommer mer än en gång,

- listan är sorterad.

Att slå ihop två sorterade listor så att resultatet fortsatt är sorterat, predikatet merge(L1,L2,L).

Skapa predikatet union för mängder representerade av unika och sorterade listor.

Räkneövningen fortsätter att excersera med listor och träd.

Sammanfattning vecka 2 av lektion och övning:

Jag gick igenom hur unifieringsalgoritmen som sköter likhetsteorin fungerar och vad program "betyder" deklarativt ("modellteorin").

Prolog arbetar med bevisregeln Modus Ponens, dvs att använda implikation i ett bevis och unifiering av logiska variabler. Tillsammans kallas denna metod för bevisföring för SLD-resolution.

Unifieringsalgoritmen genererar likheter som behövs för att det man frågar efter skall kunna bevisas.

När man beskriver detta tala man om "substitutioner", en avbildning av variabler till deras värden.

Detta kallas också "bindningsomgivning" och är de "värden" som man får vid en exekvering.

OBS att substitutioner är ett sätt att beskriva vad programmet gör, och inte hanteras explicit i program.

Exempel på program togs upp där unifiering är särskilt viktigt:

- familjerelationer med strukturerad information om individerna.

- Zebraproblemet

Lägg gärna in era frågor om övningsuppgifter i denna tråd, så ser fler som kanske har samma funderingar vpr diskussion. Det går också bra att skicka epost till mig så svarar jag så fort jag hinner.

- Thomas