Läsanvisningar till programspråksteorin

Kapitel 1: 1.1-1.3, 1.5
Kapitel 2: -
Kapitel 3: 3.1-3.3
Kapitel 4: 4.1-4.12
Kapitel 5: 5.1-5.10
Kapitel 6: 6.1-6.6
Kapitel 7: 7.1
Kapitel 8: 8.1-8.5, 8.7-8.8
Kapitel 9: 9.1-9.3 OBS! Läs detta mycket översiktligt
Kapitel 10:10.1-10.2, 10.3-10.6 (översiktligt),
Kapitel 11:11.1-11.2, 11.10 (översiktligt, handlar om Java)
Kapitel 12:
Kapitel 13:
Kapitel 14:
Kapitel 15:

Läsanvisningar till beräkningsteorin

Kapitel 1
En massa definitioner, termer och begrepp. Inte världens mest spännande läsning, men det mesta ska ni ändå lära er. Ni behöver denna begreppsapparat för att kunna förstå mer spännande saker som kommer senare.

1.1 – 1.4 Förhoppningsvis kan ni redan en del av dessa definitioner. Om inte; läs och begrunda. Det viktigaste (svåraste?) tar jag upp på föreläsningen, men det mesta får ni klara själva. Men se till att fråga om ni kör fast. (Det gäller förstås generellt, inte bara dessa avsnitt.
1.5 Induktionsbevis är viktigast att kunna. (Livsnödvändigt för en datavetare). De övriga två bevisteknikerna räcker det om ni har ett ungefärligt begrepp om.
1.6 Ni ska veta vad som menas med ”closure” (hölje), (det är ett begrepp som återkommer gång på gång), att en relation är sluten under en viss operation etc. Däremot behöver ni inte bekymra er om avsnitten om algoritmer, ”order of growth” et
1.7 Ännu ett avsnitt med en massa begrepp som ska kunnas. Inte så svårt, men inte heller så roligt...
1.8 Ett viktigt avsnitt, ska kunnas.

Kapitel 2

2.1 Viktigt, ska kunnas
2.2 Ni ska kunna definitioner och resultat (t ex sats 2.2.1), men bevisen kan ni hoppa över.
2.3 Ni ska kunna definitioner och resultat. Dessutom kan ett ingående studium av de senare delarna av avsnittet (sid 80-82) göra det betydligt lättare att lösa den första laborationen.
2.4 Känna till ”the pumping lemma” (sats 2.4.1), men inga bevis / detaljer.
2.5 Ingår inte
2.6 Känna till sats 2.6.1 och sats 2.6.2 och resonemanget runtomkring

Kapitel 3

3.1 Viktigt, ska kunnas.
3.2 Ska också kunnas
3.3 Centralt i detta kapitel, ska kunnas
3.4 Ska kunna definitioner och resultat, förstå iden bakom ex 3.4.1. Behöver inte kunna bevisen
3.5 Känna till satserna 3.5.1, 3.5.2 och 3.5.4 (inga bevis)
3.6 Känna till sats 3.6.1
3.7 Läs sid 158-159 och slutsatsen längst ner på sid 161

Kapitel 4

4.1 Viktigt, centrala definitioner
4.2 Ska kunnas
4.3 Ska kunna resultaten, men inga detaljer eller bevis (?)
4.4 Ingår inte
4.5 Kunna definitionerna på ett ungefär + känna till sats 4.5.1
4.6 Kunna definitioner och resultat
4.7 Ingår inte.

Kapitel 5

5.1 Läs och begrunda
5.2 Ingår, ska kunnas
5.3 Det är inte alldeles lätt att förstå detta avsnitt, men läs det flera gånger med någon dag emellan så klarnar det förhoppningsvis till slut. Detta är nämligen ett viktigt avsnitt, centralt i att förstå att det finns oavgörbara problem.
5.4, 5.5 Känna till de viktigaste resultaten (? de som nämns på föreläsningen)
5.6 Ingår inte.
5.7 Känna till sats 5.7.1

Kapitel 6

6.1 Ska kunnas
6.2 Känna till de viktigaste problemen, ungefär fram till TSP, sid 283
6.3 Ingår ej
6.4 Ni ska känna till och förstå innebörden av detta avsnitt (känna till satser och definitioner), men inga bevis eller detaljer.

Kapitel 7

7.1 Ni ska veta vad som menas med "polynomisk reduktion", och vad ett NP-komplett språk / problem är. Sidan 308 är viktig! Övriga detaljer i dwtta avsnitt kan ni hoppa över.
7.2 Ingår inte
7.3 Det kan vara kul (och allmänbildande?!) att ha sett namnen på de olika NP-kompletta problemen i grafen på sid 317. För övrigt kan ni hoppa över detta avsnitt.
7.4 Skumma igenom sid 333-341 mycket översiktligt, bara så ni får lite koll på att det finns metodet för att försöka lösa även NP-kompletta problem. Men fastna för all del inte i några detaljer!