ID2213 Logikprogrammering 7,5 hp
Denna kurs är avvecklad.
Sista planerade examination: VT 2022
Avvecklingsbeslut:
Ingen information tillagdInnehå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
- programsyntax för LP
- likhetsteorin för termer samt unifieringsproceduren
- 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
Kurslitteratur
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
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
Möjlighet till plussning
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
Ges av
Huvudområde
Utbildningsnivå
Påbyggnad
Examensarbete på masternivå som utnyttjar logikprogrammering.
Kontaktperson
Ö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.