ID2213 Logikprogrammering 7,5 hp

Logic Programming

OBS!

Informationen nedan baseras på en kursplan som ännu inte har börjat gälla.

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

    Datalogi och datateknik
  • Betygsskala

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

Kurstillfällen/kursomgångar

HT19 för programstuderande

HT18 för programstuderande

Lärandemål

Efter godkänd kurs ska studenten kunna

  • förklara de grundläggande begreppen i logikprogrammering
  1. programsyntax för LP  
  2. likhetsteorin för termer samt unifieringsproceduren
  3. sökmekanismerna i Prolog
  • implementera algoritmer över träd och listor som logikprogram
  • förklara och använda de logiska och de vanligaste icke-logiska kontrollstrukturerna i 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
  • genomföra och presentera ett mindre logikprogrammeringsprojekt i grupp eller enskilt inom angivna tidsramar. 

För högre betyg ska studenten dessutom kunna

  • använda DCG-notation för grammatikor i Prolog
  • 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 (t.ex. d-listor)
  • använda metaprogrammeringstekniker i logikspråk.

Kursens huvudsakliga innehåll

Kursen presenterar logik och logikprogrammering för programvaruutveckling. Detta innefattar en översikt av Horn-klausuler och deras tillämpning i kunskapsrepresentation och resonemang samt logikprogrammering i Prolog och dess semantik. Kursen presenterar algoritmer över listor och träd, samt sökalgoritmer i grafer, databasprogrammering, rekursiv programmering, ickedeterministisk programmering. Verktyg för aritmetik i Prolog, strukturinspektion, metalogik, kontrollmekanismer för sökning, negation i Prolog, ofullständiga datastrukturer, parsning m.h.a. DCG. Olika mera effektiva datastrukturer, såsom differensstrukturer introduceras. Vi visar hur tekniker från funktionell programmering passar in i logikprogrammeringens ramverk och kan uttryckas i programspråket Prolog. Slutligen presenterar kursen några AI-tillämpningar, som enkla expertsystem, och ger en kort översikt av aktuella metodologiska trender.

Under denna kurs kommer studenterna att bekanta sig med teorin och de grundläggande designprinciperna inom logikprogrammering, medan de i till exempel examensarbetet, kan praktisera metoderna.

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, moduler, objektorientering och Prolog.

I projektdelen av kursen

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

Behörighet

  • Slutförd kurs ID1018 Programmering I eller DD1393 Mjukvarukonstruktion, eller motsvarande.
  • Slutförd kurs ID1020 eller DD1338 Algoritmer och datastrukturer, eller motsvarande.
  • Slutförd kurs SF1624 eller IX1303 Algebra och geometri, eller motsvarande.
  • Slutförd kurs SF1610 eller IX1500 Diskret Matematik, eller motsvarande.

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

Sterling and Shapiro, The Art of Prolog, 2nd ed. MIT Press 1994, eller annan lämplig text.

Examination

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

Examination sker med skriftlig eller muntlig tentamen samt muntlig projektredovisning, bedömning av medstudenters presentationer, skriftlig projektrapport, samt programkod för projektet. 

Examinator beslutar, i samråd med KTH:s samordnare för funktionsnedsättning (Funka), om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning. Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Ges av

EECS/Datavetenskap

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 HT2019.
Examinationsinformation gäller från och med VT2019.