Informatica Deel II: les 3 Electronica – Arrays
Jan Lemeire Informatica deel II februari – mei 2015
Parallel Systems: Introduction
Leibniz’ droom
De “Calculus ratiocinator”
1646 – 1716
Een logisch denkend apparaat
Informatica II: les 3
Jan Lemeire
Pag. 2 / 52
Go digital! Go binary! Van analoog naar digitaal…
Informatica II: les 3
Jan Lemeire
Pag. 3 / 29
Waarmaken van Leibniz’s droom (9) Artificiële intelligentie (8) Communicatie & internet (7) Operating system (6) Computatietheorie & Software
(5) Efficiënt productieproces (4) Hardware architectuur Electronica: (2) ‘relais’-schakeling, (3)geheugen (1) Digitaal & binair (0) Het idee
Informatica deel III: technologie, historiek en economische aspecten
Binaire representatie • Een binair getal (bit) kan voorgesteld worden door 2 voltages die gegeven kunnen worden door een switch: – Waarde 0 = 0 Volt = switch open – Waarde 1 = 5 Volt = switch gesloten
• Een getal van n bits kan 2n waarden aannemen – 2 bits :
4 combinaties
00 01 10 11
– 3 bits :
8 combinaties
000 001 010 011 100 101 110 111
– 8 bits (= 1 byte) 256 combinaties – 16 bits:
65 536 combinaties
– 32 bits:
4 294 967 296 combinaties
Informatica II: les 3
Jan Lemeire
210≈1000 220≈106 230≈109 Pag. 5 / 29
Binair rekenen? 1 input => 1 output Maar 1 niet-triviale functie: NOT
2 inputs => 1 output 0
1
0
?
?
1
?
?
24 = 16 mogelijkheden Genoeg voor een basis: AND, OR, EXOR, NOT
Alle functies zijn samen te stellen uit deze!! Informatica II: les 3
Jan Lemeire
Pag. 6 / 29
2 inputs => 1 output: 16 mogelijkheden 0
1
0
0
0
1
0
0
0
1
0
1
1
1
1
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
1
0
1
0
0
0
1
0
0
1
1
1
1
Informatica II: les 2
or
and
0
1
0
0
0
1
0
1
0
1
0
1
1
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
1
exclusive or (xor)
triviaal 0
0
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
1
1
1
Voorbeeld: sommator Interaktieve applets:
http://parallel.vub.ac.be/education/java/applets.html
HalfAdder: optellen van 2 bits FullAdder: met carry bit (inkomend & uitgaand) Ripple carry adder: sommator bestaande uit een full adder per bit S=A+B
Informatica II: les 1
Jan Lemeire
Pag. 8 / 29
Hoofdstuk 3: De electronische relais
Hoe electrisch maken? 1. Geleider 1.
Weerstand
2.
Spoel
3.
Verbinden van componenten
2. Isolator (dielectric) 1.
Condensator
2.
Scheiden van componenten
Extra component nodig…
Informatica II: les 3
Jan Lemeire
Pag. 10 / 29
Nodig: de relais Electro-mechanisch
Naast de geleider, weerstand, capaciteit en spoel hebben we een component nodig met de werking zoals de electromechanische relais. De relais zorgt ervoor dat een signaal een ander signaal kan beïnvloeden: Het inputsignaal bepaalt of de output ‘aan’ of ‘uit’ is . Met deze component kunnen we electrische schakelingen maken die binair kunnen rekenen. Gebaseerd op de electromechanische relais bouwde de duitser Zuse een volledig-werkende Informatica II: les 3 Pag. 11 / 38 computer die gebruikt werd tijdens de tweede wereldoorlog. Jan Lemeire
Binair rekenen and
A
B
C = A and B
A
or
B
C = A or B
Met deze componenten kan je alles berekenen! Informatica II: les 3
Jan Lemeire
Pag. 12 / 38
Som van bits Half adder Som van 2 bits. De carriage (C) geeft de bit voor de volgende eenheid Rekening houdend met de carriage bit (Cin) van de vorige eenheid
Informatica II: les 3
Jan Lemeire
Full adder
Pag. 13 / 38
Som van getallen Twee getallen (A en B) van 3 bits bij elkaar tellen (S)
Ripple carry adder
Overflow bit
Zie http://parallel.vub.ac.be/education/java/applets.html Informatica II: les 3
Jan Lemeire
Pag. 14 / 38
WOII: de duitsers Electromechanische computer Zuse
Konrad Zuse
Door de mechanische componenten beperkt tot vijftien à Jan Lemeire twintig operaties per seconde
Informatica II: les 3
Pag. 15 / 38
De Vacuümbuis: electronische relais Vrije electronen in vacuüm
grid in out
gloeilamp
diode
versterker
De spanning (in) van het grid van de vacuümbuis bepaalt de geleidbaarheid tussen anode en cathode. Door een grote spanning op out te zetten, zal een klein Informatica II: les 3 inputsignaal versterkt worden. Een signaal met een klein vermogen wordtPag. omgezet 16 / 38 Jan Lemeire in een signaal met een groot vermogen.
Vacuümbuizen
Informatica II: les 3
Jan Lemeire
Pag. 17 / 38
Informatica II: les 3
Jan Lemeire
Pag. 18 / 38
De eerste computer: ENIAC
John Mauchly and John Eckert, 1945
ENIAC’s vacuumtubes Informatica II: les 3
Jan Lemeire
Pag. 19 / 38
Van vacuümbuis naar transistor
grid
halfgeleider
in out
Informatica II: les 5
Jan Lemeire
Pag. 20 / 38
Transistor De spanning -VG bepaalt de geleidbaarheid van de halfgeleider (semiconductor) tussen Source en Drain Te gebruiken als versterker Te gebruiken als relais, voor binaire operaties
halfgeleider
halfgeleider Informatica II: les 9
Jan Lemeire
Pag. 21 / 38
transistors
Informatica II: les 3
Jan Lemeire
Pag. 22 / 38
Analoge electronica Sommeren, integreren, afleiden http://www.falstad.com/circuit/
Informatica II: les 1
Vandaag 1. 2. 3. 4. 5. 6. 7.
Electronische basiscomponent Java: for-lus, strings Array-algoritmen ArrayList & encapsulatie Klasse-oefening OO: interfaces De eerste computer & Alan Turing
Informatica II: les 3
Jan Lemeire
Pag. 24 / 52
Java specificiteiten
Java versus Python 1. 2. 3. 4. 5. 6. 7. 8. 9.
Object-georiënteerde taal. public static void main Puntkomma’s en accolades System.out.println Typeren: sterk en statisch Arrays en ArrayLists Verschil tussen letters en woorden De for-lus Varia
Informatica II: les 3
Jan Lemeire
Pag. 26 / 52
Array array 27 30 63 10 27 30 50 63 3 -9 Array (‘rij’) is een deel van het geheugen waarin een bepaald aantal elementen kunnen worden opgeslagen. Java: enkel elementen van eenzelfde type Grootte moet vastgelegd worden bij het aanmaken (reserveren) Aanmaken via new Informatica II: les 2
Jan Lemeire
Pag. 27 / 52
p. 10-11
Java’s for-lus initialisatie
eindconditie
increment
for(int i=0;i<100;i+=2){ System.out.print(i+", "); } 𝒊 += 𝟐 ≡ 𝒊 = 𝒊 + 𝟐 𝒊++ ≡ Informatica II: les 3
Jan Lemeire
𝒊 += 𝟏
≡ 𝒊= 𝒊+𝟏
Pag. 28 / 52
Niet in cursus
Niet in cursus
Array vs ArrayList Array
ArrayList
Python list
Python tuple
Vaste grootte
Flexibele grootte
Flexibele grootte Vaste grootte
Grootte te specifieren
Initiele grootte facultatief
Niet nodig
Bij initialisatie
int[] array = new int[5];
ArrayList
arrayList = new ArrayList();
list=[]
Creatie en initialisatie samen
array = new int[]{1, 2,3};
Initialisatie niet mogelijk
list=[1, 2, 3] tuple = (1, 2, 3, 4, 5 )
x = array[2];
x = arrayList.get(2);
x=list[2]
x=tuple[2]
array[1] = 5;
arrayList.set(1, 5);
list[1]=5
Veranderen niet mogelijk
Toevoegen niet mogelijk
arrayList.add(7);
list.append(7) Niet mogelijk
array.length Jan Lemeire
arrayList.size()
len(list)
len(tuple) Pag. 30 / 53
p. 10
Verschil letter en string // ==== Verschil tussen letter en string ==== char letter = 'a'; // enkele quotes
String woord = "java"; // dubbele quotes char letter2 = woord.charAt(1); System.out.println("Tweede letter van "+woord+" is "+letter2);
System.out.println("Aantal letters van "+woord+" is "+woord.length()); Informatica II: les 3
Jan Lemeire
Pag. 31 / 52
Oefening
Accolade niet nodig, want maar 1 instructie
Output?
Informatica II: les 2
p. 37-38
Informatica II: les 3
Jan Lemeire
Pag. 34 / 52
Array Algoritmes
p. 39-43
Array algoritmes Zoek minimum in array Bereken totaal van array Bereken gemiddelde Tel het voorkomen van een element Check of de elementen gesorteerd zijn
Informatica II: les 3
Jan Lemeire
Pag. 36 / 52
/** PROGRAMMA */ public static void main(String[] args) { int lengte = 20, maxWaarde = 20; int[] array = randomArray(lengte, maxWaarde); System.out.println("Array : "+Arrays.toString(array)); System.out.println("Minimum : "+minWaarde(array)); System.out.println("Totaal : "+totaal(array)); System.out.println("Gemiddelde : "+gemiddelde(array) +" (ik verwacht hier "+((float)maxWaarde/2)+")"); System.out.println("Aantal 3's : "+aantal(array, 3)+" (ik verwacht hier "+((float)lengte/maxWaarde)+")"); System.out.println("Gesorteerd? Arrays.sort(array); System.out.println("Gesorteerd? }
Informatica II: les 3
Jan Lemeire
"+isGesorteerd(array)); "+isGesorteerd(array));
Pag. 37 / 52
p. 40
Arrays klasse Algemene klasse met nuttige functies, zoals: public static String toString(long[] a) public static void sort(int[] a) public static void sort(int[] a, int fromIndex, int toIndex) Zie online documentatie
Informatica II: les 3
Jan Lemeire
Pag. 38 / 52
public static int[] randomArray(int length, int maxWaarde){ int[] array = new int[length]; Random r = new Random(); for(int i=0;i
Jan Lemeire
Pag. 39 / 52
Totaal berekenen van array
p. 40
int tot = 0; for(int i=0;i<array.length; i++) tot += array[i];
Alternatieve for-lus (a la Python):
int tot = 0; for(int v: array) tot += v;
Jan Lemeire
Pag. 40 / 52
public static float gemiddelde(int[] array){ int tot = totaal(array); return (float) tot / array.length; } public static int aantal(int[] array, int waarde){ int n=0; for(int i=0;i<array.length; i++) if (array[i] == waarde) n++; return n; } public static boolean isGesorteerd(int[] array){ for(int i=1;i<array.length; i++) // ik begin vanaf 1 if (array[i] < array[i-1]) return false; Vraag: wat als ik van 0 begin? return true; }
documenteer de niet-triviale code.
Informatica II: les 3
Jan Lemeire
Pag. 41 / 52
p. 42
Zoeken in array I public static int aantalIteraties = 0; // performantie /** geeft index terug van eerste voorkomen van waarde. Geeft -1 terug als niet gevonden */ public static int zoek(int[] array, int waarde){ aantalIteraties = 0; for(int i=0;i<array.length; i++){ Lineaire zoektijd aantalIteraties++; if (array[i] == waarde) return i; } return -1; } System.out.println("Index van 3: "+zoek(array, 3)+" (aantal zoekiteraties = "+aantalIteraties+", ik verwachtte "+lengte/2+")"); Informatica II: les 3
Jan Lemeire
Pag. 42 / 52
Zoeken in array II
p. 42
public static int zoekAlsGesorteerd(int[] array, int waarde){ // eerst check ik of wel degelijk gesorteerd if (!isGesorteerd(array)) return zoek(array, waarde); aantalIteraties = 0; int min = 0, max = array.length; int midden; do{ aantalIteraties++; Logaritmische zoektijd midden = (max + min) / 2; if (waarde == array[midden]) return midden; // gevonden! if (waarde < array[midden]) max = midden; else // waarde ligt voorbij midden min = midden; } while (min < max); return -1; }
Vraag: wat gebeurt er als het te zoeken getal het eerste element is?
Informatica II: les 3
Jan Lemeire
Pag. 44 / 52
Klasse-oefening
p. 26
Deel III Hoofdstuk 1
ALAN TURING
Jan Lemeire
Pag. 47 / 52
Informatica II: les 3
Jan Lemeire
Pag. 48 / 52
Winston Churchill
Jan Lemeire
Pag. 49 / 52
Bletchley Park
Op zoek naar "cribs"
Jan Lemeire
Pag. 50 / 52
De Enigma code
Jan Lemeire
Pag. 51 / 52
Colossus: the first operational electronic computer
Alan Turing 1912-1954
Jan Lemeire
Pag. 52 / 52
