Hoppa till huvudinnehållet

ID2213 Logikprogrammering 7,5 hp

Kursomgångar saknas för aktuella eller kommande terminer.
Rubriker med innehåll från kursplan ID2213 (HT 2021–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehå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".

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.

Kurslitteratur och förberedelser

Särskild 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).

Utrustning

Ingen information tillagd

Kurslitteratur

Ingen information tillagd

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

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

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

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

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kursrum i Canvas

Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.

Ges av

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Examensarbete på masternivå  som utnyttjar logikprogrammering.

Kontaktperson

Thomas Sjöland

Övrig information

I denna kurs tillämpas EECS hederskodex, se: http://www.kth.se/eecs/utbildning/hederskodex.

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.