FÖRELÄSNINGSPLAN (preliminär)

FÖRELÄSARE : Lennart Salling

ANMÄRKNING 1: Förutom 15 föreläsningar (se nedanför) och 7 lektioner innehåller kursen även 2 laborationer (se schemat i TimeEdit).

ANMÄRKNING 2: Filer med ändelsen .cdf måste köras i Wolfram CDF Player som är ett fritt program från Wolfram Research.

NR	DATUM	FRÅGOR	MOMENT	KAPITEL
Föreläsning 1	2 sept kl 10-12	Vad handlar kursen om?		1.1-1.4
		Kan alla problem lösas av program?
		Vad har stora och små oändligheter med saken att göra?
Föreläsning 2	4 sep kl 13-15	Vad har språk och beräkningar med varandra att göra?		2.1-2.3
		Reguljära språk, vad är det?
		Vilka automater är specialiserade på reguljära språk?
		Hur många DFA:er finns det?
Föreläsning 3	5 sept kl 10-12	Varför ickedeterminism?		2.3-2.5
		Problemdemonstration 1
Förlläsning 4	11 sept kl 10-12	Hur kan vi vara säkra på att finita automater inte klarar mer komplicerade språk än just de reguljära?		2.6-2.7
		Vilka operationer kan man utsätta reguljära språk för utan att reguljäriteten förloras?
Föreläsning 5	12 sept kl 13-15	Finns det en minsta DFA för varje reguljärt språk?		2.8
		Problemdemonstration 2
Laboration	14 sept kl 10-12	Laboration 1
Föreläsning 6	18 sept kl 13-15	När räcker finita automater inte till?		3.1-3.2
		Hur kan man visa att ett språk inte är reguljärt?
Föreläsning 7	20 sept kl 10-12	Vad behöver man för att hantera programspråk?		3.3-3.4
		Problemdemonstration 3
Laboration	25 sept kl 10-12	Laboration 2
Föreläsning 8	27 sept kl 10-12	Finns det automater även för sammanhangsfria språk?		3.6
		Problemdemonstration 4
Föreläsning 9	1okt kl 10-12	När räcker PDA:er inte till?   Hur visar man att ett språk inte är sammanhangsfritt?		4.1
Föreläsning 10	3 okt kl 10-12	Hur kraftfull kan en grammatik bli?		4.2-4.4, 4.6
		Hur kraftfull kan en automat bli?
		Vad är en interpretator i termer av automater?
Föreläsning 11	4 okt kl 10-12	Hur ser problem ut som inte kan lösas av program?		7.1
		Kan alla TM:er modifieras till avgörande TM.er?
		Problemdemonstration 5
Föreläsning 12	8 okt kl 10-12	Hur kan man visa att ett problem inte kan lösas av program?		7.2
		Några berömda oavgörbara och avgörbara problem
Föreläsning 13	9 okt kl 13-15	Problemdemonstration 6
Föreläsning 14	11 okt kl 13-15	Repetitionsuppgifter
Föreläsning 15	15 okt kl 13-15	Flera repetitionsuppgifter med lösningsförslag

aug 2012