ID2213 Logikprogrammering 7,5 hp

Logic Programming

Detta är en kurs om teori och metoder för logikprogrammering. Det mest kända logikbaserade språket Prolog introduceras och används i kursen. En översiktlig introduktion ges till olika tillämpningsområden samt till villkorsprogrammering och andra utvidgningar.

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT18 för programstuderande

Lärandemål

I kursen utvecklar studenten kunskaper om och färdigheter i att konstruera och förstå innebörden av logikprogram. Logikprogrammering är programmering med en speciell klass av logiska uttryck. I system som exekverar logikprogram ställer användaren frågor till en databas av påståenden (programmet) och systemet svarar på dessa frågor.

Kursen bidrar till civilingenjörens repertoar av programmeringssystem. Framförallt kan detta vara av stort värde för att konstruera prototyper av program men även hela tillämpningar kan konstrueras.

Kursen ingår som valbar i flera kompetensinriktningar för civilingenjörsprogram, framförallt teoretisk datalogi på D-programmet. Kursen är användbar i sammanhang med kurser i kompilatorkonstruktion eller för verifiering av formella system (både hårdvara och programvara).

Efter godkänd kurs skall studenten kunna:

  • förklara de grundläggande begreppen i logikprogrammering (programsyntax för LP inklusive DCG-notation för grammatikor, likhetsteorin för termer, unifieringsproceduren)
  • implementera algoritmer över träd och listor som logikprogram
  • förklara och använda de logiska och de vanligaste icke-logiska kontrollstrukturerna i Prolog
  • diskutera de starka och svaga sidorna hos logikprogrammering och Prolog
  • skissartat kunna redogöra för huruvida och varför en viss uppgift är lämpad (eller inte lämpad) att implementeras med användning av logikprogrammeringstekniker
  • kunna implementera mindre programprototyper som logikprogram
  • genomföra ett mindre logikprogrammeringsprojekt i grupp eller enskilt inom angivna tidsramar
  • muntligt och i skrift kunna redogöra för innebörden (den operationella och den deklarativa semantiken) av logikprogram.

Det är också önskvärt att studenten kan:

  • förklara den operationella och deklarativa semantiken för logikprogram
  • konstruera adekvata representationer av abstrakta datatyper som t.ex. mängder, glesa matriser, hashtabeller i logikprogram
  • använda och förklara differensstrukturer (d-listor)
  • använda metaprogrammeringstekniker i logikspråk
  • kunna bedöma förslag till förbätringar av språkdesignen inklusive dess operationella semantik.

Kursens huvudsakliga innehåll

Detta är en kurs om teori och metoder för logikprogrammering. Det mest kända logikbaserade språket Prolog introduceras och används i kursen. En översiktlig introduktion ges till olika tillämpningsområden samt till villkorsprogrammering och andra utvidgningar.

Horn-klausuler och dess tillämpning i kunskapsrepresentation och resonemang. Ren Prolog och dess informella semantik. Teori för ren Prolog. Verklig Prolog: verktyg för aritmetik, strukturinspektion, metalogik, kontrollmekanismer för sökning, negation. Programmeringsteknik i Prolog: databasprogrammering, rekursiv programmering, icke-deterministisk programmering, ofullständiga datastrukturer, parsning m.h.a. DCG.

Tillämpningsexempel: pussel och spel, parsning, kompilering, formelmanipulering, expertsystem. Introduktion till modifikationer och utvidgningar av Prolog: parallell Prolog, ekvations- och restriktionslösning, rikare former av klausuler.

I projektkursen:

  • väljer studenten ut ett problemorienterat projekt som lämpar sig för att illustrera användning av logikprogrammeringstekniker
  • formulerar studenten projektet med hjälp av logikprogrammeringen terminologi (implementation av ett program eller analys av ett program/system)
  • genomför studenten projektet i grupp eller enskilt inom tidsramen
  • redovisar studenten sintt arbete med en kort rapport och en muntlig presentation i "miniworkshop".

Behörighet

  • ID1018 Programmering I 7,5 hp eller motsvarande kurs. 
  • ID1020 Algoritmer och datastrukturer 7,5 hp eller motsvarande kurs. 
  • SF1624 eller IX3103 Algebra och geometri 7,5 hp eller motsvarande kurs. 
  • SF1610 eller IX1500 Diskret matematik 7,5 hp eller motsvarande kurs. 

Rekommenderade förkunskaper

Programmering i högnivåspråk. Någon erfarenhet av rekursion som programmeringsteknik.

Kunskaper och färdigheter i grundläggande logik (logikens språk, härledningar, modeller).

Litteratur

The Art of Prolog, Leon Sterling och Ehud Shapiro

Upplaga: 2:a upplagan Förlag: MIT Press År: 1990

ISBN: 0-262-19338-8

Kurskompendium och OH-bilder(Sjöland m.fl.)

Examination

  • PRO1 - Projekt, 3,0, betygsskala: P, F
  • TEN1 - Tentamen, 4,5, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

Godkänd skriftlig tentamen (TEN1; 4,5 hp) samt 1 godkänd projektuppgift (LAB1; 3 hp).

För godkänt betyg på tentamen för kursdelen (4,5hp) skall studenten kunna:

  • förklara de grundläggande begreppen i logikprogrammering (programsyntax för LP inklusive DCG-notation för grammatikor, likhetsteorin för termer, unifieringsproceduren)
  • implementera algoritmer över träd och listor som logikprogram
  • förklara och använda de logiska och de vanligaste icke-logiska kontrollstrukturerna i Prolog.

För högre betyg förväntas studenten också kunna:

  • förklara den operationella och deklarativa semantiken för logikprogram
  • konstruera adekvata representationer av abstrakta datatyper som t.ex. mängder, glesa matriser, hashtabeller i logikprogram
  • använda och förklara differensstrukturer (d-listor)
  • använda metaprogrammeringstekniker i logikspråk
  • diskutera de starka och svaga sidorna hos logikprogrammering och Prolog (det finns inte några tydliga "sanningar" i detta, det är förmågan att resonera tydligt som värdesätts).

I projektkursen förväntas studenten:

  • välja ut ett problemorienterat projekt som lämpar sig för att illustrera användning av logikprogrammeringstekniker
  • kunna formulera projektet med hjälp av logikprogrammeringen terminologi (implementation av ett program eller analys av ett program/system)
  • genomföra projektet i grupp eller enskilt inom tidsramen
  • redovisa med en kort rapport och en muntlig presentation i "miniworkshop".

Projektkursen (3,0 hp) betygsätts med Pass/Fail. Om man lämnar in en projektrapport i tid, kan man få bonuspoäng på tentamen.

Man kan få högst 10 bonuspoäng i tillägg till de som givits för tentamen. Notera att bonuspoäng gäller enbart för det innevarande akademiska året.

Uppgifterna på tentamen är värda 50 poäng.

Betygsstegen för hela kursen bestäms av antalet poäng på tentamen plus eventuella bonuspoäng som har fått på projektkursen
the assignments. Minst 25 poäng krävs totalt för godkänd kurs. Kursen betygsätts med stegen A-F.

Betygsstegen för det totala antalet poäng n är som följer:

n >= 45: A
45 > n >= 40: B
40 > n >= 35: C
35 > n >= 30: D
30 > n >= 25: E
25 > n >= 20: Fx
20 > n : F

Om betyget Fx har givits, kan komplettering av kursen ske inom tre månader efter den skriftliga tentamen. I det fallet kommer den kursansvarige att på begäran efbjuda en hemuppgift som studenten skall lösa inom en vecka. Observera att komplettering enbart medges om studenten INTE fått bonuspoäng. Om studenten med bonuspoäng får en totalsumma poäng inom intervallet 25 >= n >=20 och utan bonuspoäng 20>n, räknas bonuspoängen inte utan betyget F ges.

Ges av

ICT/Programvaruteknik och Datorsystem

Kontaktperson

Thomas Sjöland

Examinator

Alf Thomas Sjöland <sjoland@kth.se>

Övrig information

Kursen utvärderas och utvecklas i enlighet med KTH:s policy för Kursanalys.

Kursen ingår som valbar i flera inriktningar och program åk3 och uppåt. Kursen är användbar i sammanhang med kurser i kompilatorkonstruktion eller för verifiering av formella system (både hårdvara och programvara).
Dessutom ger kurser en utökad förståelse för vad programmering kan anses vara.

Kursens kunkapsinnehåll överlappar med grundkurs ID1213. Denna kurs på avancerad nivå innehåller ett större projekt.

Påbyggnad

Examensarbete på masternivå  som utnyttjar logikprogrammering.

Versionsinformation

Kursplan gäller från och med HT2010.
Examinationsinformation gäller från och med HT2007.