Logik og Sprog, forår 2000

ved Henning Christiansen

Dette kursus udgør sammen med kurset om Databaser det samlede modul 2-kursus på overbygningsuddannelsen i Datalogi på RUC. Kurset kan følges særskilt for studerende på den Tværfaglige IT-uddannelsen, som udbydes på vegne af IT-højskolen, København.

Om kurset

Klik her!

Pensum

Klik her for pensumliste!

Udvalgte, gamle eksamensopgaver

Klik her!

Kursusplan

Kurset er planlagt som følger. Der kan forekomme ændringer undervejs og planen revideres løbende.

Vdr. praktiske øvelser henvises til studienævnets sider og vdr. software, som benyttes i kurset, til din hjælpelærer eller Datalogis driftafdeling; se også Kort vejledning i brug af Prolog på Ruc og links nedenfor til eksempelprogrammer m.v.

dato Titel Læsestof Opgaver

1 Onsdag 2. februar Introduktion og oversigt over kurset.
Historisk perspektiv på udviklingen frem til forståelse af »den moderne computer«. Tanenbaum kap 1 + 2 (selvstændig læsning; kursorisk),
Notat nr. 1. Historiske hovedpunkter Ekstraopgaver 1, 2.
Tanenbaum opg. 1 s. 113

2 Mandag 7. februar Abstrakte maskiner Sprog og abstrakte maskiner, kap. 1–3 Sprog og abstrakte maskiner opg. 1.1 s. 2, 2.1 s. 12, 2.4–2.7 s. 18.

3 Onsdag 9. februar Det digital-logiske niveau Tanenbaum kap. 3 med hovedvægten på stoffet t.o.m. 3.4.2, resten som baggrundslæsning. Tanenbaum opg. 9, 12, 22, evt. 23 (s. 199-201).

4 Mandag 14. februar Ontologi over emnet sprog,
Introduktion til sproget Prolog. Sprog og abstrakte maskiner kap. 4 t.o.m. 4.2 samt kap. 5.
Bratko, kap. 1–2 (minus 2.4 og grafiknotation s. 23–24 og 61). Bratko, 1.1–1.2 (s. 8–9), 1.4, 1.5 s. (s.15), 2.1 (s. 37) 2.3 (s. 43).

5 Onsdag 16. februar Mere Prolog: Lister, operatorer, assert/retract, negation Bratko, kap. 3 pånær 3.2.3–3.2.6, kap. 5, 7.1.1 og 7.4
Notat nr. 2. Et eksempel på kontrol i Prolog Bratko 3.12 (s. 87), 3.18 (s.94)
Sprog og abstrakte maskiner opg. 4.5 s. 18.

6 Mandag 21. februar Sprog og metasprog, Prolog som metasprog,
beskrivelser af imperative sprog Sprog og abstrakte maskiner 4.4–4.5, 6. Sprog og abstrakte maskiner, opg. 6.2, evt. 6.3, 6.4, 6.6, 6.7, 6.8

7 Onsdag 23. februar Systemer af oversættere og fortolkere m.v.
Mikroprogrammering (Overordnet struktur) (eller boolsk algebra+klokke=computer) Sprog og abstrakte maskiner kap 6.
Notat nr. 3. Sammensætning af oversættere og fortolkere vha. T-diagrammer
Tanenbaum, kapitel 4 til og med 4.3 Tanenbaum kap. 4, opg. 3, 6, 7, 8 (side 299);
evt. Ekstraopgaver 5 og 6

8 Mandag 28. februar Mikroprogrammering (detaljer) Tanenbaum, kapitel 4 til og med 4.3 Fortsæt med opgaverne ovenfor.

9 Onsdag 1. marts Beregnelighed og universalitet (Turing-maskiner) Sprog og abstrakte maskiner kap. 10. Sprog og abstrakte maskiner 10.1–10.4, 10.7

10 Mandag 6. marts Syntaksgenkendelse, kobling til fortolkning og oversættelse Sprog og abstrakte maskiner 4.3, 12–14
Side 10–15 af Aho, Sethi, Ullman: Compilers: Principles, Techniques and Tools, Addison-Wesley 1986. (Teknisk hovedvægt på s. 53–59, 177–195 og 203–211 i Sprog og abstrakte maskiner; det øvrige behandles oversigtsligt/kursorisk.)
Ekstraopgaver 3, 4.

Mandag 19. juni
kl. 10-16 Repetition

	dato	Titel	Læsestof	Opgaver
1	Onsdag 2. februar	Introduktion og oversigt over kurset. Historisk perspektiv på udviklingen frem til forståelse af »den moderne computer«.	Tanenbaum kap 1 + 2 (selvstændig læsning; kursorisk), Notat nr. 1. Historiske hovedpunkter	Ekstraopgaver 1, 2. Tanenbaum opg. 1 s. 113
2	Mandag 7. februar	Abstrakte maskiner	Sprog og abstrakte maskiner, kap. 1–3	Sprog og abstrakte maskiner opg. 1.1 s. 2, 2.1 s. 12, 2.4–2.7 s. 18.
3	Onsdag 9. februar	Det digital-logiske niveau	Tanenbaum kap. 3 med hovedvægten på stoffet t.o.m. 3.4.2, resten som baggrundslæsning.	Tanenbaum opg. 9, 12, 22, evt. 23 (s. 199-201).
4	Mandag 14. februar	Ontologi over emnet sprog, Introduktion til sproget Prolog.	Sprog og abstrakte maskiner kap. 4 t.o.m. 4.2 samt kap. 5. Bratko, kap. 1–2 (minus 2.4 og grafiknotation s. 23–24 og 61).	Bratko, 1.1–1.2 (s. 8–9), 1.4, 1.5 s. (s.15), 2.1 (s. 37) 2.3 (s. 43).
5	Onsdag 16. februar	Mere Prolog: Lister, operatorer, assert/retract, negation	Bratko, kap. 3 pånær 3.2.3–3.2.6, kap. 5, 7.1.1 og 7.4 Notat nr. 2. Et eksempel på kontrol i Prolog	Bratko 3.12 (s. 87), 3.18 (s.94) Sprog og abstrakte maskiner opg. 4.5 s. 18.
6	Mandag 21. februar	Sprog og metasprog, Prolog som metasprog, beskrivelser af imperative sprog	Sprog og abstrakte maskiner 4.4–4.5, 6.	Sprog og abstrakte maskiner, opg. 6.2, evt. 6.3, 6.4, 6.6, 6.7, 6.8
7	Onsdag 23. februar	Systemer af oversættere og fortolkere m.v. Mikroprogrammering (Overordnet struktur) (eller boolsk algebra+klokke=computer)	Sprog og abstrakte maskiner kap 6. Notat nr. 3. Sammensætning af oversættere og fortolkere vha. T-diagrammer Tanenbaum, kapitel 4 til og med 4.3	Tanenbaum kap. 4, opg. 3, 6, 7, 8 (side 299); evt. Ekstraopgaver 5 og 6
8	Mandag 28. februar	Mikroprogrammering (detaljer)	Tanenbaum, kapitel 4 til og med 4.3	Fortsæt med opgaverne ovenfor.
9	Onsdag 1. marts	Beregnelighed og universalitet (Turing-maskiner)	Sprog og abstrakte maskiner kap. 10.	Sprog og abstrakte maskiner 10.1–10.4, 10.7
10	Mandag 6. marts	Syntaksgenkendelse, kobling til fortolkning og oversættelse	Sprog og abstrakte maskiner 4.3, 12–14 Side 10–15 af Aho, Sethi, Ullman: Compilers: Principles, Techniques and Tools, Addison-Wesley 1986. (Teknisk hovedvægt på s. 53–59, 177–195 og 203–211 i Sprog og abstrakte maskiner; det øvrige behandles oversigtsligt/kursorisk.)	Ekstraopgaver 3, 4.
	Mandag 19. juni kl. 10-16	Repetition

Litteratur

Ivan Bratko: Prolog, Programming for Artificial Intelligence, Second edition, Addison-Wesley, 1990
Andrew S. Tanenbaum: Structured Computer Organization, Fourth edition, Prentice-Hall, 1999.
Henning Christiansen: Sprog og abstrakte maskiner, 3. reviderede udgave, 2000.
Se rettelsesliste!!
Notater som uddeles løbende eller foreligger som www-sider.

Eksempelprogrammer og anden software

Programmer fra »Sprog og abstrakte maskiner« og enkelte fra Bratkos bog finder du HER.

NB: Til de, som ønsker en større opgave med programmering i Prolog i forbindelse med de sprogorienterede emner, henvises der til en afleveringsopgave fra 1999, som går ud på at lave en typechecker og oversætter for et sprog med rekursive procedurer. Følgende Prologtekster er tilgængelige som udgangspunkt for opgaven: PAXsyntaks.txt, PAXtools.txt.

Simulator for Tanenbaums mikroarkitektur (kapitel 4) i en version, som skulle være nem at installere i et Windows-miljø kan du hente her: mic1.zip. Den er skrevet i Java, og burde kunne køre under de fleste omgivelser; den oprindelige version kan findes via linket ovenfor for Tanenbaums bog.

Vigtige bemærkninger

Det er vigtigt, at du afprøver selv de simpleste opgaver, som stilles i forbindelse med i Prolog, så du opnår en vis fortrolighed med systemet og intuition om udførelse af Prologprogrammer. Det kan meget anbefales også at afprøve de programmer, som er gennemgået ved forelæsningen, og det er en god ide at steppe sig igennem med en tracer. Det giver god indsigt i Prologs udførelsesstrategi.
I kursusoversigten ovenfor er der henvist til de eksakte dele af lærebogsmaterialet, der eksplicit refereres i forelæsningerne, hvorfor det kan se lidt springende ud. Det er vigtigt også at læse litteraturen i sammenhæng, gerne både før og efter forelæsningen. Som det fremgår, svinger sidetallet fra forelæsning til forelæsning, men noget er væsentligt mere koncentreret end andet (og vægtes forskelligt i forelæsningerne).
Opgaverne i Sprog og abstrakte maskiner er en blanding af praktiske opgaver af varierende omfang og diskussionsopgaver, som understreger et aspekt i teksten. Det er en god ide at reflektere over opgaverne under læsningen, også selv om man ikke løser dem her og nu. For at få den fulde forståelse er det væsentligt, at man arbejder praktisk med opgaverne, specielt med de små oversættere, fortolkere og andre sprogbeskrivelser formuleret i Prolog — det er først derigennem man for alvor får internaliseret begreberne.

Nyttige links

Sidst rettet 30. marts 2000