College "T2":

ANALYSE VAN ALGORITMEN/COMPLEXITEIT (I00010)

************************en

COMPLEXITEITSTHEORIE (SCHAKELCURSUS) (I00125)

Opgaven en stof van de afgelopen weken.

week 36 - 3 sep .........bijeenkomst 1

Stof (bestudeer van tevoren): Hd. 1 (RAM), begin HD. 2 tot 2.3.3
Opgaven: RAM 3

.........

week 36 - 6 sep .........bijeenkomst 2

Stof (bestudeer van tevoren): Hd. 2.
Opgaven: pg. 33/4: 6, 8.

N.b. logaritmen (2.2) en recursies (2.5) worden bekend verondersteld. Uiteraard staat vragen vrij!
Typo: in de definitie van e als een oneindige som (pg. 25, punt 5) moet je niet beginnen met n=1, maar met n=0.

.........

week 37 - 10 sep .........bijeenkomst 3

Stof (bestudeer van tevoren): Hd. 3 (TWEELINGEN) tot 3.4
Opgaven: TWEELINGEN 2a (pg. 50/1)

.........

week 37 - 13 sep .........bijeenkomst 4

Stof (bestudeer van tevoren): Hd. 3: 3.4 tot "dijkstra"
Opgaven: TWEELINGEN 5.

Paar correcties: op pg. 40 r 4 zijn de lijntjes W natuurlijk puntenparen in V (dus niet in E).
Op pg. 41 midden moet de definitie van subgraph iets algemener zijn, nl: (V',E') met V' deel van V, E' deel van E, en de lijntjes uit E' bevatten slechts punten van V'. (De nu in het dictaat staande definitie beschrijft inderdaad wat men i.h.a. noemt de " subgraph op V' "). Vlak daaronder is het dan netter om te zeggen dat de subgraph op een kliek een complete graph is (een kliek zelf is immers een stelletje punten).

.........

week 38 - 17 sep .........bijeenkomst 5

Stof (bestudeer van tevoren): Hd. 3 (TWEELINGEN) 3.5
Opgaven: TWEELINGEN 3. Bewijs daarbij ook, dat iedere samenhangende graph G met n punten en n-1 edges een boom moet zijn.

.........

week 38 - 20 sep .........bijeenkomst 6

Stof (bestudeer van tevoren): Hd. 3: 3.6
Opgaven: TWEELINGEN 7

.........

week 39 - 24 sep .........bijeenkomst 7

Stof (bestudeer van tevoren): Hd 4 (KREEFT): 4.1, 4.2.
Opgaven: pg. 72: KREEFT 3.

.........

week 39 - 27 sep .........bijeenkomst 8

Stof (bestudeer van tevoren): Hd 4 (KREEFT): 4.3, 4.4 tot 4.4.3
Opgaven: KREEFT 8.

Op 4 october is het eerste testje, over de stof en opgaven van bijeenkomst 1 t/m 7. Het testje is in de gewone zaal en duurt 1 uur.

.........

week 40 - 1 oct .........bijeenkomst 9

Stof (bestudeer van tevoren): Hd 4 (KREEFT): 4.4 uit.
Opgaven: pg. 72 e.v: KREEFT 5, 9.

.........

week 40 - 4 oct .........Testje 1

Het testje is in de gewone zaal van 10u45 exact tot 11u45 exact. Het is "open boek" (maar geen electronica).
De stof is die van bijeenkomst 1 t/m 7 incl. de gemaakte opgaven (klik hieronder op "Vorige weken").

.........

week 41 - 8 oct .........bijeenkomst 10

Stof (bestudeer van tevoren): Hd 4: 4.5; Hd 5 (LEEUW): 5.1.
Opgaven: pg. 72 e.v: KREEFT 14, 15a.

.........

week 41 - 11 oct .........bijeenkomst 11

Stof (bestudeer van tevoren): Hd 5: 5.2, 5.3.
Opgaven: pg. 102 e.v: LEEUW 1.

.........

week 42 - 15 oct .........bijeenkomst 12

Stof (bestudeer van tevoren): Hd 5: 5.4.
Opgaven: pg. 102 e.v: LEEUW 5.

.........

week 42 - 18 oct .........bijeenkomst 13

Stof (bestudeer van tevoren): Hd 5: 5.5.1.
Opgaven: pg. 102 e.v: LEEUW 11 (rest).

.........

week 44 - 29 oct .........bijeenkomst 14

Stof (bestudeer van tevoren): Hd 5: 5.5.2, 5.5.3.
Opgaven: pg. 102 e.v: LEEUW 7.

N.b. bij 3SAT wordt vereist dat binnen een clause geen twee literals dezelfde variabele bevatten.

.........

week 44 - 1 nov .........bijeenkomst 15

Stof (bestudeer van tevoren): hd 8 (SCHORPIOEN) t/m 8.2.1.
Opgaven: pg. 154 e.v: SCHORPIOEN 2.

Volgende week op 8 november is er het tweede testje in de gewone zaal van 10u45 exact tot 11u45 exact. Het is "open boek" (maar geen electronica). De stof is die van bijeenkomst 8 t/m 14 incl. de gemaakte opgaven.

.........

week 45 - 5 nov .........bijeenkomst 16

Stof (bestudeer van tevoren): Hd 8: 8.2.2, 8.2.3.
Opgaven: pg. 154 e.v: SCHORPIOEN 6, 14.

.........

week 45 - 8 nov ......... Tweede testje.

Dit is in de gewone zaal van 10u45 exact tot 11u45 exact. Het is "open boek" (maar geen electronica). De stof is die van bijeenkomst 8 t/m 14 incl. de gemaakte opgaven.

.........

week 46 - 12 nov .........bijeenkomst 17

Stof (bestudeer van tevoren): Hd 8: 8.3 (bewijs wordt slechts summier behandeld).
Opgaven: pg. 154 e.v: SCHORPIOEN 10.

.........

week 46 - 15 nov .........bijeenkomst 18

Stof (bestudeer van tevoren): Hd 8 UIT.
Opgaven: pg. 154 e.v: SCHORPIOEN 12.

.........

week 47 - 19 nov .........bijeenkomst 19

Stof (bestudeer van tevoren): Hd 9 (SCHUTTER): 9.4 tot 9.4.3.
Opgaven (lever in!!!!): pg. 170: SCHUTTER 4.

.........

week 47 - 22 nov .........bijeenkomst 20

Stof (bestudeer van tevoren): Hd 7 (WEEGSCHAAL): 7.1, 7.2, 7.3.1, 7.3.2.
Opgaven (lever in!!!!): pg. 138 e.v: WEEGSCHAAL 1, 4a.

.........

week 48 - 26 nov .........bijeenkomst 21

Stof (bestudeer van tevoren): Hd 6 (MAAGD): 6.1, 6.2.
Opgaven (lever in!!!!): pg. 123 e.v: MAAGD 1.

.........

week 48 - 29 nov .........bijeenkomst 22

Stof (bestudeer van tevoren): Hd 6 (MAAGD): 6.3, 6.4.
Opgaven (lever in!!!!): pg. 123 e.v: MAAGD 2, 3.

Volgende week op 6 december is er het derde testje in de gewone zaal van 10u45 exact tot 11u45 exact. Het is "open boek" (maar geen electronica). De stof is die van bijeenkomst 15 t/m 21 incl. de gemaakte opgaven.

.

. week 49 - 3 dec .........bijeenkomst 23

Stof (bestudeer van tevoren): Hd. 6.6.
Opgaven (lever in!!!!): pg. 123 e.v: MAAGD 8 (deel a. alleen voor bitonische rij).

.........

week 49 - 6 dec ......... Derde testje.

Dit is in de gewone zaal van 10u45 exact tot 11u45 exact. Het is "open boek" (maar geen electronica). De stof is die van bijeenkomst 15 t/m 21 incl. de gemaakte opgaven.

.........

week 50 - 10 dec .........bijeenkomst 24

Stof (bestudeer van tevoren): Hd 11 (WATERMAN): 11.1, 11.2.
Opgaven (lever in!!!!): pg. 194: WATERMAN 1, 3.

.........

week 50 - 13 dec .........bijeenkomst 25

Stof (bestudeer van tevoren): Hd 11 (WATERMAN): 11.3, 11.4.1.
Opgaven (lever in!!!!): pg. 195: WATERMAN 5, 8.

(Terug)