TU e ALGORITMIEK keuzemodule Wiskunde B/D
Mark de Berg TU Eindhoven
TU e
Algoritmiek module Wiskunde B/D
Doel: begrip bijbrengen van belangrijke aspecten van de algoritmiek • wat is een algoritme • effici¨entie: – wiskundige analyse van looptijd – snelle computers niet genoeg, ook effici¨ent algoritme nodig • correctheid: belangrijk en niet vanzelfsprekend meer algemeen: • informatica is meer dan computers / programmeren
TU e
Algoritmiek module Wiskunde B/D
Voorkennis / doelgroep: • geen programmeervoorkennis vereist • 5 of 6 VWO leerlingen, profiel NT (of NG?)
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 1: Inleiding • eerste voorbeeld van algoritme • notatie van algoritmen: pseudocode
Voorbeeld: lineair zoeken van getal in een array zoeken naar 8: 23 7 54 16 82 21 8 2 61 33 55 37 74 81 17 66
TU e
Algoritmiek module Wiskunde B/D
zoeken naar 8: A : 23 7 54 16 82 21 8 2 61 33 55 37 74 81 17 66 ← getallen n ← indices 1 LineairZoeken(A, q) Invoer: Een array A[1..n] van getallen, en een getal q. Uitvoer: Een index i zodanig dat A[i] = q, of “niet aanwezig” als zo’n index niet bestaat. 1. i ← 1 2. zolang i ≤ n doe als A[i] = q dan Rapporteer i en stop anders i ← i + 1 3. Rapporteer “niet aanwezig”
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Binair zoeken: zoeken in gesorteerd array zoeken naar 8:
2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• kijk eerst in midden array . . . • . . . en zoek dan verder in linker- of rechterhelft
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Binair zoeken: zoeken in gesorteerd array zoeken naar 8:
2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• kijk eerst in midden array . . . • . . . en zoek dan verder in linker- of rechterhelft
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Binair zoeken: zoeken in gesorteerd array zoeken naar 8:
2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• kijk eerst in midden array . . . • . . . en zoek dan verder in linker- of rechterhelft
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Binair zoeken: zoeken in gesorteerd array zoeken naar 8:
2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• kijk eerst in midden array . . . • . . . en zoek dan verder in linker- of rechterhelft
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Analyse: bepaal max aantal stappen als functie van invoergrootte n 23 7 54 16 82 21 8 2 61 33 55 37 74 81 17 66 • lineair zoeken: maximaal n stappen
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Analyse: bepaal max aantal stappen als functie van invoergrootte n 23 7 54 16 82 21 8 2 61 33 55 37 74 81 17 66 • lineair zoeken: maximaal n stappen 2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• binair zoeken:
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 2: Effici¨entie van algoritmen • binair zoeken • analyse van algoritmen Analyse: bepaal max aantal stappen als functie van invoergrootte n 23 7 54 16 82 21 8 2 61 33 55 37 74 81 17 66 • lineair zoeken: maximaal n stappen 2 7 8 16 17 21 23 33 37 54 55 61 66 74 81 82
• binair zoeken: maximaal 2 log n stappen
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 3: Correctheid van algoritmen • invarianten . . . • en het gebruik om correctheid van algoritmen te beargumenteren
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 3: Correctheid van algoritmen Opgave 3.1.2 EI-taal: taal met “woorden” die bestaan uit de letter E en I. Een van de woorden is EI. Andere woorden kunnen uit EI gemaakt worden door het een of meer keer toepsasen van de volgende regels: • Regel 1: Als het woord eindigt op een I, mag je er een E achter zetten. • Regel 2: Je mag het woord verdubbelen door het achter zichzelf te plaatsen. • Regel 3: Als er ergens een E staat, mag je die wegstrepen. • Regel 4: Als er ergens drie I’s achter elkaar staan, dan mag je deze allemaal wegstrepen. Vragen: (i)
Kan het woord EEII gemaakt worden?
(ii)
Kan het woord III gemaakt worden?
TU e
Algoritmiek module Wiskunde B/D
Invarianten en algoritmen Machtsverheffen(x, n) Invoer: Een getal x, en een geheel getal n ≥ 1. Uitvoer: xn 1. i ← n; y ← x; z ← 1 2. zolang i > 0 doe: als i is even dan y ← y 2 ; i ← i/2 anders z ← z · y; i ← i − 1 3. Rapporteer z
Invariant: z · y i = xn
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 4: Makkelijke en moeilijke problemen • snelle computers zijn niet voldoende • vergelijkbare problemen kunnen toch heel verschillend zijn Goedkoopste samenhangende netwerk (MST) 33
3
2
25
4
23
1 36
Kortste rondrit (TSP)
?
17
5
aantal opspannende bomen: nn−2
aantal rondritten: (n − 1)!
TU e
Algoritmiek module Wiskunde B/D 33
3
2
25
4
23
1 36
17
aantal opspannende bomen: nn−2
5
Opgave 4.1.2 Stel dat we een algoritme hebben dat alle opspannende bomen op n knopen kan genereren. We willen dit algoritme gebruiken om een minimale opspannende boom te vinden. We hebben daartoe een bijzonder snelle computer tot onze beschikking, die 1.000.000.000 opspannende bomen per seconde kan doorrekenen. Het is bekend dat het aantal opspannende bomen op n knopen gelijk is aan nn−2 . Hoeveel tijd heeft het algoritme nodig voor het doorrekenen van alle opspannende bomen voor een verzameling van 10 computers? En voor 20 computers?
TU e
Algoritmiek module Wiskunde B/D
Hoofdstuk 4: Makkelijke en moeilijke problemen • snelle computers zijn niet voldoende • vergelijkbare problemen kunnen toch heel verschillend zijn Goedkoopste samenhangende netwerk (MST) 33
3
2
25
4
23
1 36
Kortste rondrit (TSP)
?
17
5
aantal opspannende bomen: nn−2
aantal rondritten: (n − 1)!
TU e
Algoritmiek module Wiskunde B/D
Ervaringen met de module module getest op Christiaan Huygens College (Eindhoven) in drie 5VWO klassen, als keuzeonderwerp Wiskunde B Met dank aan: Jan Debets, Erik de Rooij, Bertha Scholten
TU e
Algoritmiek module Wiskunde B/D
Aanpak • hele module behandeld, behalve sec 3.2 (tweede deel Invarianten) • leerlingen veel zelfstandig laten werken in de klas • kleine toets na afloop van elk hoofdstuk
TU e
Algoritmiek module Wiskunde B/D
Aanpak • hele module behandeld, behalve sec 3.2 (tweede deel Invarianten) • leerlingen veel zelfstandig laten werken in de klas • kleine toets na afloop van elk hoofdstuk
Resultaten • cijfers gemiddeld iets hoger dan voor reguliere wiskunde toetsen • harde werkers met weing inzicht vallen door de mand • nakijken soms lastig (wanneer is een antwoord goed?)
TU e
Algoritmiek module Wiskunde B/D
Leerlingen-enquete prettige afwisseling met gewone wisk module zelf voldoende afwisselend goede manier van toetsen liever iets met een computer eerste hoofdstuk interessant tweede hoofdstuk interessant derde hoofdstuk interessant vierde hoofdstuk interessant
niet waar 12 3 4 32
beetje waar 24 28 11 13
waar 24 30 45 15
23 17 19 16
23 36 30 28
14 8 12 16
TU e
Algoritmiek module Wiskunde B/D
Module te downloaden via Regionaal Steunpunt Eindhoven Wiskunde D:
www.win.tue.nl/wiskunded −→ Vakken −→ Algoritmiek
Antwoorden op verzoek (mail naar
[email protected])
