Informatica. 2 e semester: les 11. Hashing & Internet Slot. Jan Lemeire Informatica 2 e semester februari mei Informatica II: les 11

Informatica 2e semester: les 11

Hashing & Internet Slot

Jan Lemeire Informatica 2e semester februari – mei 2016

Informatica II: les 11

Vandaag 1. Sorteren: laatste deel 2. Internet (deel II) 3. Examen…

Hoofdstuk 9 Hashing

p. 2

Performantie datastructuren Datastructuur

Random access (opvragen ide element)

Find (via naam)

Toevoegen / verwijderen

Array

O(0) ++

O(n) O(log(n)) als gesorteerd

O(n) -

ArrayList

O(0) ++

O(n) O(log(n)) als gesorteerd

O(n) -

Linked list

O(n) -

O(n) --

O(0) ++

Binaire boom

n.v.t.

O(log(n)) +

O(0) ++

Hashtabel

n.v.t.

O(0) ++

O(0) ++ Zolang binnen grootte


Jan Lemeire

Pag. 4 / 54

p. 93

Hashing Probleem: iets terugvinden in een collectie gegevens Is in feite een functie: – Input: object – Output: plaats in geheugen Voor arrays, linked lists of bomen doen we dit met het doorploeteren van de datastructuur Maar waarom niet via een echte functie? – hashfunctie


Jan Lemeire

Pag. 5 / 54

Hashfunctie Index = hashfunctie(object) Bepaalt waar object moet komen in array hashfunctie

java

3

koffie

8

thee

11

hashtabel

java

koffie

thee

O(0) tijd, onafhankelijk van de grootte van de array


Jan Lemeire

Pag. 6 / 54

Enige probleem met hashing: botsingen hashfunctie

java

3

koffie

8

thee

11

jana

3

hashtabel

java jana

koffie

thee

???

goede hashfunctie maakt deze kans klein Vb: “java” & “jana” botsen omdat enkel de eerste 2 letters gebruikt worden (≈ modulo operatie) beter is om alle letters te laten meetellen

Perfecte hashfunctie: kans is gelijk aan de kans op toevallige botsing Informatica II: les 11

Jan Lemeire

Pag. 7 / 54

p. 94

Hashfunctie op woorden eerste letter nemen van elk woord (‘a’ = 0; ‘b’ = 1; ...) eerste 2 letters van elk woord index(woord) = index(eerste letter) * 26 + index(tweede letter) "aa“ geeft 0 “ab” geeft 1 “ba” geeft 26 "zz" 25*26+25=262-1

Neem maximale hashwaarde groter dan arraygrootte en modulo: index = hashwaarde modulo arraygrootte Informatica II: les 11

Jan Lemeire

Pag. 8 / 54

Goede hashfunctie? Botsingen als 2 eerste letters hetzelfde zijn Beter dat alle karakters een invloed op de sleutel hebben Hoe? Stel: hashwaarde heeft 8 bits & arraygrootte n is een macht van 2 enkel de log2n minst-betekenisvolle bits bepalen index

Beter: neem n een priemgetal!


Jan Lemeire

Pag. 9 / 54

Hoofdprobleem: botsingen Ideaal: de array voor p% gevuld => kans op botsing ook p%

Perfect hashing (geen botsingen) mogelijk als verzameling waarden (sleutels) op voorhand gekend is Bvb de gereserveerde woorden van java


Jan Lemeire

Pag. 10 / 54

Hashcode: in Java Object protected Object clone() Creates and returns a copy of this object. boolean protected void

equals(Object obj) Indicates whether some other object is "equal to" this one. finalize() Called by the garbage collector on an object when garbage collection determines that there are no more references to the object.

Class

getClass() Returns the runtime class of this Object.

int

hashCode() Returns a hash code value for the object.

void

notify() Wakes up a single thread that is waiting on this object's monitor.

void

notifyAll() Wakes up all threads that are waiting on this object's monitor.

String

toString() Returns a string representation of the object.

void void

wait() Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object. wait(long timeout) Causes the current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object, or a specified amount of time has elapsed. wait(long timeout, int nanos) Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

Java geeft default hashcode, overschrijf indien nodig

void


Jan Lemeire

Pag. 11 / 54

Oplossing 1: lijst Alle elementen met zelfde index in lijst Bvb linked list hashfunctie

java

3

koffie

8

thee

11

jana

3


Jan Lemeire

hashtabel

java

koffie

thee

jana

Pag. 12 / 54

Oplossing 2: alternatieve index berekenen lineaire hi = (hash(sleutel) +i) MOD n Nadeel: de bezette plaatsen concentreren zich in blokken

kwadratische open adressering hi = (hash(sleutel) +i2) MOD n

Voorbeeld Key

h0 = Hash(Key)

4215 1212 7220 Informatica II: les 11 8219 Jan Lemeire

211 211 213 211

h1 = h0 + 1

h2 = h0 + 2

h3 = h0 + 3 (lineair)

h2 = h0 + 22 (kwadratisc h)

213

214

215

212 212

Pag. 13 / 54

Nadelen hashing 1. Statische karakter van de datastructuur Array kan niet uitgebreid worden, want hashfunctie moet dezelfde blijven

•

2. Elementen staan ongeordend in lijst In volgorde printen kan niet

•

3. Verwijderen van elementen is moeilijk Kan problemen geven bij botsingen • Linked lists: OK • Alternatief adres: als 1e element verwijderd, hoe weten we dat volgende elementen op alternatieve plaats staat… •

Mogelijke oplossing: verwijderde objecten aanduiden met vlag


Jan Lemeire

Pag. 14 / 54

p. 97

Mapimplementaties Map<String, String> map = new TreeMap<String, String>();

Of Map<String, String> map = new HashMap<String, String>();


Jan Lemeire

Pag. 15 / 54

Internet & innovatie

De internetbubbel Technologie-index van USA: Nasdaq


Jaren ‘90: Dot-com (crisis) Internet geeft ongekende nieuwe mogelijkheden Internet zou de wereld totaal veranderen Droom spatte uit elkaar…


Jan Lemeire

Pag. 18 / 54

Na de dotcom-crisis Investeringen vallen stil Maar: Internet wint meer en meer terrein En… Google begint aan het internet te verdienen Komt de droom toch uit?


Jan Lemeire

Pag. 19 / 54

webtechnologie Internet 1.0 Informatie te bekijken via browser

Internet 2.0 Gebruiker interageert en voegt informatie toe

Internet 3.0 Semantiek (betekenis)

Webservices: informatie wordt ter beschikking gesteld, kan automatisch (door computerprogramma) opgehaald worden ipv. via browser Vb: bustijden, google maps, … Informatica II: les 11

Jan Lemeire

Pag. 20 / 54

Door internet: verhoging efficiëntie Sneller en gemakkelijker communiceren Informatie overal aanwezig en toegankelijk Vroeger: bibliotheek met beperkte info

Digitale verwerking Bvb tax-on-web: belastingen online invullen ipv via formulier die dan ingescand moet worden

Webservices: programma’s kunnen info opvragen & gebruiken luchtvaartmaatschappijen …

DatInformatica internettechnologie heel wat mogelijk maakt is duidelijk, maar technologie II: les 11 Pag. 21 / 54 Jan Lemeire is geen garantie op succes…

Technologie is niet alles Wat is de bijdrage van technologie tot het succes? Welke technologie is belangrijk? Onverwachte wendingen… Sms werd onbedoeld een enorm succes, mms dan weer niet

Standaardisatie! Vb: Gsm Eenvormig systeem, van operator veranderen is gemakkelijk USA: alle operatoren hebben een ander systeem Gsm is nu dan ook wereldwijd de standaard (behalve in de USA...)


Jan Lemeire

Pag. 22 / 54

Wat is er nodig voor succes? Ingenieurs/techneuten hebben het dikwijls moeilijk om dit te begrijpen omdat ze vooral bezig zijn met de technologie


Jan Lemeire

Pag. 23 / 54

De lange weg naar de markt

Scientific

Technology

Solution

Product

Iets weten

Iets kunnen

Iets oplossen

Iets waard zijn

Productieproces Fundamenteel onderzoek

Onderzoek & ontwikkeling

Business plan

rol van de ingenieur Informatica II: les 11

Jan Lemeire

Pag. 24 / 54

Wat is er, naast technologie, nodig voor succes?

(1) Vertrouwen Vroeger: securityproblemen Geen vertrouwen

Gebruik VISA, Online banking, Meer en meer online kopen: vertrouwen in kapaza, ebay, … Je betaalt een onbekende en vetrouwt dat hij het opstuurt!

Ons koopgedrag verandert (maar niet eensklaps en massaal) Oud voorbeeld: kernenergie Ingenieur vindt dat de consument maar moest vertrouwen dat alles veilig is. Hij kan niet overweg met ‘irrationele’ Informatica II: les 11 argumenten Pag. 25 / 54 Jan Lemeire

(2) Gebruiksvriendelijk Google maps <> Map24 Google via handige functionaliteiten veel gebruiksvriendelijker Ik ben direct overgeschakeld…

Google verzekerde dat het resultaat steeds snel ter beschikking was (binnen 1 seconde) Voorheen moest je al eens lang wachten

Apps & muziek Wat is een ‘app’ anders dan een softwareprogramma? – Afgebakend programma door systeem beheerd

Itunes store: gemakkelijk muziek kopen Informatica II: les 11

Jan Lemeire

Pag. 26 / 54

(3) Je moet de grootste zijn Of ten minste groot genoeg Hoe bereik je kritische massa? Vb1: website voor gepersonaliseerde concertaankondigen, afhankelijk van je muzieksmaak Bestaat nog geen succesvolle versie Nog geen ‘winner’…

Vb2: smart TV Enkel succesvol met 1 standard Vele initiatieven (Apple, Samsung, Google, Microsoft, …), maar geen duidelijke winnaar. Geen enkele speler gunt de ander de machtspositie!

(4) Het menselijke & sociale aspect Wat zoeken mensen op internet… ‘Contact met andere mensen’

Facebook’s Zuckerberg: studeerde psychologie (naast computer science) Begrijpen van ‘mens’ Apple’s Steve Jobs: nadruk op design, op gebruiker ipv technologie


Jan Lemeire

Pag. 28 / 54

Business model: Winstgevend Google, facebook: via advertenties Hebben informatie over gebruikers => gerichte reclame

Betalende sites (bvb krant): moeilijk We verwachten dat alles gratis is…


Jan Lemeire

Pag. 29 / 54

Facebook Bij beursgang (mei 2012): 100 miljard beurswaarde 38 dollar initiele prijs aandeel Steeg onmiddellijk tot 42 dollar Maar begon toen te dalen… Nu weer aan beterhand

1 miljard bezoekers, 0.5 miljard per dag Geen activa


Jan Lemeire

Pag. 30 / 54

Google (Alphabet)

Belangrijkste IT-bedrijven Key Statistics:

Mei 2015

Omzet

Winst Winstmarge

Beurswaarde (koers)

Koers-winst

Microsoft

94,8

20,0

21%

387 (48,7)

19

Apple

212

48

22%

750 (128)

15,6

Google

67

13,8

20%

373 (500)

27

Facebook

13,5

2,8

20% Mei 2016 Winst Winstmarge

219 (80)

78

Beurswaarde (koers)

Koers-winst

Omzet Microsoft

87

10,5

12%

404 (51,5)

38

Apple

227

50

22%

494 (90)

9,8

Google

78

17

19%

499 (728)

29

4,6

23%

344 (120)

74

(Alphabet)

Informatica II: les 11 Facebook 19,7

Facebook Analyse bij beursgang (2011)

Misschien overgewaardeerd,

maar wel gezond bedrijf Sterktes Informatie over ons Dé tijdsbesteding op het internet Meer & meer gaat via facebook => niemand kan er om heen

Zwaktes Hype? Gaan we op een dag overschakelen? Gaan we de advertenties beu worden (als er gecasht moet worden) Zuckerberg (56% aandelen) houdt de touwtjes in handen Geld van beursgang ging naar oprichters & werknemers – Niet naar bedrijf of investeringen


Jan Lemeire

Pag. 33 / 54

Examen

Doel van het vak Kennis & vaardigheden om informatica te gebruiken als tool Regels kunnen toepassen Redeneren Problemen oplossen Performantie kunnen inschatten


Jan Lemeire

Pag. 35 / 54

Mondeling examen Schriftelijke voorbereiding (maximaal 2 uur) met mondelinge verdeging (15-20 minuten) Enkel eerste 20 minuten van de voorbereiding mogen boek en nota's gebruikt worden (open boek), daarna is enkel pen en papier toegelaten. Niet van toepassing voor vraag uit deel III

Elke vorm van communicatie of technologische hulpmiddelen (zoals computer) zijn uitgesloten. Voorbeeldexamen op website


Jan Lemeire

Pag. 36 / 54

Ophalen 1e semester indien je een 7, 8 of 9 behaalde in het eerste semester en je hebt minstens 12/20 voor je mondeling examen Een extra vraag over de materie van 1e semester waarmee je je punten kan optrekken tot maximaal 10/20 geen specifieke python-vraag, eerder algemene programmatievraag. Je mag je pythonboek gebruiken.


Jan Lemeire

Pag. 37 / 54

Deel I: java & object-oriëntatie Boek dient vooral als hulpmiddel Wel de klassikaal-opgeloste oefeningen (p. 62-65)

Enkel van buiten kennen: de java spelregels Regels kunnen toepassen op oefeningen zoals in de les opgelost

Pijlers van object-oriëntatie (p. 7) Gebruik en nut begrijpen wanneer toegepast op gevallen zoals in de cursus


Jan Lemeire

Pag. 38 / 54

Deel II: datastructuren & algoritmen Begrijpen, niet kunnen reproduceren Varianten wel kunnen genereren

Op voorbeelden kunnen toepassen Voorbeeld van lijst, boom, spelsituatie, …

Wat gebeurt er bij kleine varianten? Waar loopt het fout

Optioneel voor goede programmeurs: 5.2.6 generieke code voor de zoekalgoritmen Je mag dit als vraag kiezen, dan krijg je een andere vraag minder


Jan Lemeire

Pag. 39 / 54

Deel III: technologie, historiek en economische aspecten van de IT-wereld. Aspecten belangrijk voor IT-wereld Essentie kennen, belangrijke onderscheiden van detail Eigen mening wordt gewaardeerd (“redelijk eigenzinnig”) Parate kennis: zodat je verdere info kunt kaderen

Te kennen (gesloten boek): hoofdstukken 1 t.e.m. 8 Niet: namen, geschiedenis, data, wat aangeduid staat met

Extra informatie & eigen inzichten wordt beloond


Jan Lemeire

Pag. 40 / 54

Voorbeelden inzichtsvragen Gegeven dat we weten wat we willen, namelijk een digitale, programmeerbare computer (we hebben gekozen voor een binair, digitaal systeem en voor een systeem dat we kunnen programmeren met bijvoorbeeld Java). Schets de belangrijkste technologieën die zo’n electronische computer mogelijk maken. Focus op de hardware dus. Motiveer het belang van elke technologie. Tijdens de bespreking van de technologie en geschiedenis van de computer hebben we verschillende malen gezien dat de economie een grote rol speelde. Kan je deze belichten? Vergeet niet: productieproces, R&D (research & development), ‘bubbels’, belang van de grootste te zijn, macht en verandering van de macht (wie was/is er aan de macht in de IT-wereld? Wie zal er aan de macht blijven, denk je?), … Informatica II: les 11

Jan Lemeire

Pag. 41 / 54

Vragen tijdens de blok? Mail je vraag

of mail voor een afspraak Of telefonisch

[email protected] of de assistenten 02/629.1679


Jan Lemeire

Pag. 42 / 54

Electronische evaluatie

In te vullen na eerste zittijd

Heeft wel degelijk invloed

Daarnaast: eigen enquete over inhoudelijke en organisatorische aspecten krijgen jullie tijdens het mondeling examen


Jan Lemeire

Pag. 43 / 54

IT-technologie: wat brengt de toekomst? NIET TE KENNEN

Volgend succesproduct van Apple? Na iPod, iPhone & iPad... Ze waren niet de eerste, maar wel de beste

Smartwatch??

Apple TV Waar blijft de universele TV-box

?? Informatica II: les 11

Jan Lemeire

Pag. 45 / 54

Toekomst? Social Media Apps Games


Jan Lemeire

Pag. 46 / 54

Investeren in toekomst Kan Google de wereld redden? Robots (deels een softwareprobleem) Zelfrijdende auto’s (grotendeels een softwareprobleem) Google Glass (virtual reality) – Lijkt klaar om door te breken – Heb je er niet al genoeg van na 1 3D-film?

Maar ... Die brengen voorlopig nog niets op... Aandeelhouders niet kontent Robotafdeling wordt verkocht


Jan Lemeire

Pag. 47 / 54

“You ain’t seen nothing yet” Danny Goderis, hoofd iMinds (Vlaams ICT innovatiecentrum)

Automatische medische monitoring Smart systems Smart cameras

Smart cities Overal sensoren (sensornetwerken)

Van ‘Internet of Things’ naar ‘Everything Connected’


Jan Lemeire

Pag. 48 / 54

Innovatie in industrie Niet een nieuw consumentenproduct Factory of the future Automatiseren

Smart Farming


Jan Lemeire

Pag. 49 / 54

Botsen we op onoverkomelijke technologische hindernissen? Klokfrekwentie kan niet meer beter Ontbreken basiscomponenten voor fotonische computer Batterijen kunnen niet veel beter 100% schone energie Artificiële Intelligentie... robots ‘big data’-uitdaging & data analytics: iets leren uit al die gegevens


Jan Lemeire

Pag. 50 / 54

Film “The Social Network” (2010) David Fincher

Over het ontstaan van facebook

Succes verder! Toegewenst: doorzicht

discipline

planning

doorzettingsvermogen

concentratie/focus

zelf-coaching

Succes met je carriere, met je dromen En misschien tot later Informatica II: les 11

Jan Lemeire

Pag. 52 / 54

Einde

Informatica. 2 e semester: les 11. Hashing & Internet Slot. Jan Lemeire Informatica 2 e semester februari mei Informatica II: les 11

Recommend Documents