Doel: laat zien dat dingen niet vanzelf gaan. Laat zien dat er verschillende oplossingen mogelijk zijn voor hetzelfde probleem. Dat we die oplossingen kunnen analyseren. En dat we heel precieze waardeoordelen over die oplossingen kunnen geven: de een is echt veel beter dan de ander want ....
(Te tentamineren doel): Inzicht, begrip en zelf kunnen toepassen en bepalen van complexiteits functies O(n) met n een maat voor de grootte van de input. Grafieken kunnen tekenen van O(n), O(log n), O(n log(n)), O(n2), O(2n), en kunnen aangeven welke "beter" is.
In dit deel behandelen we 2 problemen in de klas.
In de klas doen we een veel gebruikte puzzel in sollicitatiegesprekken.
Gegeven 2 personen: Zender en Ontvanger en een getal k.
Zender zegt in willekeurige volgorde 1-voor-1 alle getallen onder de k behalve eentje.
Ontvanger moet erachter komen welk getal Zender niet heeft genoemd.
Vraag: Ontvanger heeft zelf geen geheugen. Hoe kan zij dat toch doen?
Vergelijk lineair zoeken met zoeken met een index (telefoonboek). Met korte lijsten is lineair makkelijker en vaak nog snel genoeg. Met langere lijsten moet je slimmer worden. Laat algorithme zien in Python, en laat zien hoe snel lineair zoeken langzaam wordt.
Huiswerk: leerling speelt met Python en Idle. Werkt de twee zoek algorithmes netjes uit en zet geannoteerde listings op Wiki. Daarnaast introductie opdracht Python in practicum sessie (bijvoorbeeld: programmeer "ik heb een potje met vet"). .
Enige tijd geleden heeft Amsterdam-Amstelland meegewerkt met het project "Current City". Hierbij werden mensen in de massa gevolgd m.b.v. hun gsm. Het project is echter mislukt, door de vertraging van de locaties die de mobiele telefoons aangaven. Die vertraging was te wijden aan het telefoonnetwerk.
You're being watched: there's one CCTV camera for every 32 people in UK.
Doe eens een snelle rekensom: een veiligheidsbeambte kan tegelijk
hooguit 10 TV's bekijken.
Dan moet nog steeds 1 op de 320 mensen in de UK 24 uur per dag voor TV's zitten.
Dat kan natuurlijk niet. Een week heeft 148 uur. Met pauzes en rust
meegerekend kan 1 mens die voltijd werkt hooguit 30 uur per week
naar die TV's kijken. Dus we hebben vijf mensen per week
nodig. Dus dat betekent dat 1 op de 320/5=64 mensen voltijds
naar TV's moeten kijken om al die beelden te analyseren. Dat is
bijna 2 procent van de hele bevolking, iedereen meegeteld.
Andere schattingen gaan uit van 1 camera op de 14 mensen. Dan kijkt
dus 1 op de 28 mensen als baan de hele dag naar
veiligheidscameras. Dat is 1 mens in elke klas!
Korte uitleg XML, met veel voorbeelden. Studenten maken in groepjes van 2 de 'woordenboek-lemma' formaliseer opdracht uit WTT. Input: scan van 1 lemma uit een woordenboek. Output: zelfde informatie in XML, maar dan met alle impliciete informatie expliciet gemaakt.
Main Entry: lan·guage
Pronunciation: 'la[ng]-gwij, -wij
Function: noun
Etymology: Middle English, from Old French, from langue tongue, language, from Latin
lingua - more at TONGUE
Date: 14th century
1 a : the words, their pronunciation, and the methods of combining them used and understood
by a community b (1) : audible, articulate, meaningful sound as produced by the
action of the vocal organs (2) : a systematic means of communicating ideas or feelings by
the use of conventionalized signs, sounds, gestures, or marks having understood meanings
(3) : the suggestion by objects, actions, or conditions of associated ideas or feelings
(4) : the means by which animals communicate (5) : a formal system of signs and symbols
(as FORTRAN or a calculus in logic) including rules for the formation and transformation
of admissible expressions (6) : MACHINE LANGUAGE 1
2 a : form or manner of verbal expression; specifically : STYLE b : the vocabulary and
phraseology belonging to an art or a department of knowledge c : PROFANITY
3 : the study of language especially as a school subject
In de klas: Kan je Torens van Hanoi doen (met 3 stenen)? Kan het ook met n stenen (en 3 stokken)? Idee: hergebruik je eerdere truc/recept op een simpeler geval. Maak dit precies in Python. Draai het in Python. Laat eens zien hoeveel stapjes er nodig zijn voor n stenen. Bereken exact de complexiteit. Huiswerk: Leerling werkt het argument heel precies uit op zijn Wiki.
Dit is naast een schaalbaarheidsprobleem ook vooral een probleem van het zoeken, vinden en combineren van allerlei informatie. Bij het NFI gebeurt dit met een gestructureerde aanpak, in stappen. In verschillende stappen, met verschillende programmas wordt er allerlei soorten impliciete data expliciet gemaakt. Voorbeelden zijn:
Formeer groepjes van 4. Doe de opdracht echt alleen met jouw groepje. Alleen dan leer je er wat van! Bekijk de groepsopdracht. Hardstikke leuk toch? Voor we lekker aan de slag gaan, gaan we eerst heel saai het probleem analyseren en eens kijken hoe moeilijk het is en of het wel haalbaar is.
Om data te verzamelen of expliciet te maken zal je het eerst moeten
herkennen. Veel soorten data zijn best makkelijk te herkennen,
omdat ze steeds een bepaalde vorm hebben. Denk maar aan datums,
of eigennamen.
In deze opdracht schrijven we een patroon waarmee we emailadressen
kunnen oppikken. Zie bijvoorbeeld http://www.regular-expressions.info/email.html. We gebruiken hiervoor reguliere expressies.
(marx@u014417 69) curl http://www.rug.nl/dnpp/contact/contact | grep -o -P '\w+@(\w+\.)+\w+'