Informatica. Deel II&III: les 4. geheugen set, stacks & queues - interfaces. Jan Lemeire Informatica deel II&III februari mei 2015

Informatica Deel II&III: les 4 geheugen – set, stacks & queues - interfaces Jan Lemeire Informatica deel II&III februari – mei 2015

Parallel Systems: Introduction

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

Hoofdstuk 3: Geheugen

Ponskaarten Beschrijven de programma’s

Informatica II: les 4

Jan Lemeire

Pag. 4 / 66

Moderne ponskaart?


Jan Lemeire

Pag. 5 / 66

Magnetische banden zoals muziek- en videocassettes


Jan Lemeire

Pag. 6 / 66

Harde schijf Non-volatile, rotating magnetic storage


Jan Lemeire

Pag. 7 / 66

Flashgeheugen Non-volatile semiconductor storage 100× – 1000× faster than disk Smaller, lower power, more robust But more $/GB (between disk and DRAM)


Jan Lemeire

Pag. 8 / 66

Hoe werkt Flash geheugen? 1. Geleider 1. 2. 3.

Weerstand Spoel Verbinden van componenten

2. Isolator 1.

condensator

3. Halfgeleider 1. 2.

Versterker: transistor Flashgeheugen halfgeleider


Jan Lemeire

Pag. 9 / 64

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. 10 / 66

transistorwerking


Jan Lemeire

Pag. 11 / 66

Hoe werkt Flashgeheugen? Electrische lading wordt bewaard in een ingekapselde geleider (de floating gate). 50.000 electronen zijn voldoende, duurt meer dan 10 jaar opdat deze ‘gelekt’ zijn door de isolator De floating gate bepaalt geleidbaarheid van halfgeleider Control gate Floating gate

halfgeleider


Jan Lemeire

Flashgeheugen bestaat uit een matrix van cellen Pag. 12 / 66

Op- of ontladen flash bit Op- of ontladen van floating gate gebeurt door isolator via tunneling (kwantum-mechanisch effect) Geactiveerd via hoge spanning op control gate

opladen

ontladen Floating gate


Jan Lemeire

Pag. 13 / 66

Permanent versus volatiel geheugen Permanent: “eeuwigdurend” Optisch: Ponskaarten en CDs Magnetisch: banden, diskettes en harde schijven Flash-geheugen Optisch & magnetisch enkel sequentieel leesbaar: je moet eerst ‘doorspoelen’ naar de juiste positie

Vluchtig of volatiel: electriciteit nodig om gegevens aktief te behouden Wordt gebruikt als werkgeheugen Random Access Memory (RAM): elke byte kan onmiddellijk gelezen worden, is direct toegankelijk Informatica II: les 4

Jan Lemeire

Pag. 14 / 66

Lading bewaren: capaciteit

Het geheugen dat de snelste transfer van bits van en naar de processor toelaat is dat type van geheugen waarbij elektrische schakelingen gebruikt worden, waarbij 1 of 0 wordt voorgesteld als de aanof afwezigheid van spanning over een geleider. Maar lading zal langzaam wegvloeien en lekken… Informatica II: les 4

Jan Lemeire

Pag. 15 / 66

Volatiel geheugen: refreshen!

Waarde van geheugen hou je bij op een capaciteit, maar die lading vloeit weg regelmatig weer opladen! Dynamic Random Access Memory (DRAM): elke cel slaat 1 bit op en bestaat uit een capaciteit voor de bitwaarde te bewaren, en een transistor voor refreshen

Static Random Access Memory (SRAM): een alternatief bestaande uit enkel transistors. SRAM is sneller, maar neemt Informatica II: les 4 meer plaats in en is duurder. Pag. 16 / 66 Jan Lemeire

Werk- versus perifeer geheugen Werk- of primair geheugen: rechtsstreeks bruikbaar in je programma’s Elk programma krijgt een deel van het geheugen toegewezen om in te ‘werken’ Heeft electriciteit nodig, bestaat enkel als computer opstaat, is dus vluchtig of volatiel, dus niet voor het opslaan van permanente gegevens

Perifeer of secundair geheugen: om gegevens permanent op te slaan Gebeurt via files Vanuit programma lees en schrijf je files Goedkoop, maar wel traag Informatica II: les 4

Jan Lemeire

Pag. 17 / 66

Werkgeheugen: RAM DRAM-geheugenchips in te pluggen zijn in de DDR-slots van het moederbord

Het cache geheugen (SRAM) is typisch in de CPU chip zelf ingebouwd en gebruikt hoge snelheidsconnecties zodanig dat de data erin opgeslagen extreem snel kan aangesproken worden. Het DRAM geheugen daarentegen is op afzonderlijke chips ondergebracht en communiceert met de CPU tegen een lagere snelheid. De data aanwezig in het DRAM-geheugen kan dus minder snel aangesproken worden dan de data in het cache geheugen, maar het DRAM-geheugen is veel goedkoper. Men zal daarom kostprijs tegenover performatie afwegen en een klein gedeelte (meestal uitgedrukt in kilobyte) cache geheugen voorzien voor de opslag van essentiële gegevens, terwijl men voor de overige gegevens RAM geheugen zal voorzien (meestal uitgedrukt in megabyte of gigabyte). Er is naast het RAM geheugen ook nog een beperkt gedeelte ROM (afkorting voor Read-only Memory) aanwezig. Read-Only-Memory (ROM) is geheugen waarvan de inhoud permanent is, het kan enkel gelezen worden en niet overschreven. Bovendien verdwijnt de inhoud van dit geheugen niet wanneer de stroom komt weg te vallen. Typisch wordt het ROM geheugen gebruikt om permanente programma's in te stockeren Informatica II: les 9 Pag. 18 / 66 zoals die bv. nodig zijn wanneer de computer wordt aangezet. Jandeze Lemeire

Processorchip

Dual core CPU chip met aanduiding in blauw van registers. Registers: zeer snel, klein geheugen voor het bijhouden van tussentijdse waarden van berekeningen.

Het cache geheugen bevindt zich in het donkere linkergedeelte. Informatica II: les 4

Jan Lemeire

Pag. 19 / 66

kort bij Registers processor Cachegeheugen (SRAM)

Werkgeheugen (DRAM)

Snelheid en kost

Capaciteit en energie

Geheugenhiërarchie

Harde schijf of flash drive

‘ver’ van processor Jan Lemeire

Pag. 20 / 66

Snelheid versus kost


Jan Lemeire

Pag. 21 / 66

Vandaag 1. 2. 3. 4. 5. 6.

Geheugen Klasse-oefening Verzamelingen Stacks & queues Recursive Halving Abstractie: interfaces

Klasse-oefening

p. 27

Verzameling Set

De Set

p. 46

Definitie van documentatie: “A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.”

Een wiskundige verzameling dus... In Java gedefinieerd als interface


Jan Lemeire

Pag. 26 / 55

Method Summary boolean add(E e) Adds the specified element to this set if it is not already present. boolean addAll(Collection c) Adds all of the elements in the specified collection to this set if they're not already present (optional operation). void clear() Removes all of the elements from this set. boolean contains(Object o) Returns true if this set contains the specified element. boolean containsAll(Collection c) Returns true if this set contains all of the elements of the specified collection.

boolean equals(Object o) Compares the specified object with this set for equality. boolean isEmpty() Returns true if this set contains no elements. boolean remove(Object o) Removes the specified element from this set if it is present (optional operation). boolean removeAll(Collection c) Removes from this set all of its elements that are contained in the specified collection. boolean retainAll(Collection c) Retains only the elements in this set that are contained in the specified collection. int size() Informatica II: les 4 Returns the number of elements in this set (its cardinality). Pag. 27 / 55 Jan Lemeire

Bewerkingen bewerking

methode

Unie

aUb

AddAll()

Doorsnede

a∩b

RetainAll()

Verschil

a\b

RemoveAll()

Symmetrische verschil

(a \ b) U (b \ a)

Combinatie van bovenstaande


Jan Lemeire

Pag. 28 / 55

Pijlers van object-georiënteerde programmeertalen

p. 3

I. Encapsulatie 2.4 Conclusies ArrayList versus array p. 45 3.2 Stapel-datastructuur p. 50 6.2 Java’s LinkedList p. 88 7.8.2 AVL-boom p. 110 II. Overerving (inheritance) 1.2 Studentvoorbeeld p. 14 1.4 Vriendenvoorbeeld p. 17 4.3 FunctieMetAfgeleide-interface p. 60 - 61 7.8.4 AVLTree subklasse p. 113 III. Polymorfisme en abstractie 4.2 Functie-interface p. 55 9.6 Mapimplementaties p. 116 Addendum bij hoofdstuk 5 (zie website) Abstract zoekalgoritme Vergelijking van zoekalgoritmes

Jan Lemeire

Pag. 29 / 55

Set Object: implementatie Implementaties voldoen aan het “Setkontrakt” Gebruik: TreeSet en HashSet Komen we op terug in hoofdstuk 8


Jan Lemeire

Pag. 30 / 55

public static void main(String[] args) { System.out.print("Geef range: "); Scanner scanner = new Scanner(System.in); int N = scanner.nextInt();

p. 48

Set getallen = new HashSet(); for(int i=2;i
// de zeef van Erathostenes for(int i=2;i
Jan Lemeire

Pag. 31 / 55

Interfaces

Abstracte methodes en interfaces

Abstractie, polymorphisme (pijler 3)


Jan Lemeire

Pag. 33 / 55

Interfaces

p. 4

Alle methodes zijn abstract: enkel header, geen implementatie Klasse die interface implementeert moet alle methodes implementeren

Filosofie: een interface definieert hoe je met een object communiceert. Je hoeft de implementatie niet te kennen Informatica II: les 4

Jan Lemeire

Pag. 34 / 55

Stapel Stack

De stapel of ‘stack’

p. 48

Pop

Push

Push

Push

Twee operaties: dingen opleggen en afnemen YELLOW

YELLOW

BLUE

BLUE

BLUE

Pop

Pop

Push

BLUE

Pop

ORANGE YELLOW

GREEN YELLOW

YELLOW

BLUE

BLUE

BLUE

Fig.1.5. Last-in, first-out stack

last-in, first-out (lifo) structuur Informatica II: les 4

Jan Lemeire

Pag. 36 / 55

‘interface’ van stack Wat willen we er mee doen? Pop Push isEmpty isFull

Headers van de methods (interface): void push(int element) int pop() boolean isEmpty() boolean isFull()


Jan Lemeire

Pag. 37 / 55

import java.nio.BufferOverflowException; import java.nio.BufferUnderflowException;

p. 49-50

public class Stack { int[] data; int pointer=0; // wijst naar het eerste vrije element public Stack(int capacity){ data = new int[capacity]; } public void push(int element){ if (pointer == data.length) // check of vol throw new BufferOverflowException(); data[pointer] = element; pointer++; } public int pop(){ if (pointer == 0) // check of leeg throw new BufferUnderflowException(); pointer--; return data[pointer]; } public boolean isEmpty(){ Informaticareturn II: les 4 pointer == 0; Jan Lemeire }

Pag. 38 / 55

Vraagjes Je zou ook een pointer kunnen bijhouden naar het bovenste element van de stack, waarbij je met -1 aanduid dat hij leeg is. Wat verandert er aan de code?

Voeg een size() methode toe die aangeeft hoeveel elementen er op de stack zijn. Nu werkt ie enkel met integers. Hoe generiek maken, t.t.z. bruikbaar voor elk type? zie volgende datastructuur Informatica II: les 4

Jan Lemeire

Pag. 39 / 55

Waarom niet gewoon een array gebruiken? 1. Code van stack komt overal in je programma terecht

2. Moeilijk om fouten met stack op te sporen 3. Je geeft niet aan wat je met de array wilt doen 4. Een collega-programmeur kan de array of pointer aanpassen Consistentie om zeep helpen

Voorbeeld van het Encapsulatieprincipe Informatica II: les 4

Jan Lemeire

Pag. 40 / 55

Je programma wordt dan: ... int[] data = new int[capacity]; Stack stack = new Stack(3); int pointer=0; ... if (pointer == data.length) throw new BufferOverflowException(); data[pointer] = element; stack.push(element); pointer++; ... if (pointer == 0) throw new BufferUnderflowException(); pointer--; element = stack.pop(); element = data[pointer]; ... Informatica II: les 4

Jan Lemeire

Pag. 41 / 55

Wachtrij Queue

Wachtrij of Fifo-queue

p. 51

Fifo = First-in, first out Informatica II: les 4

Jan Lemeire

Pag. 43 / 55

Internetknopen

Zie deel III hoofdstuk 8

Switch: knooppunt Router: bepaalt ook route van pakketje

Als queue vol: packetdrop  Verlies van gegevens  Moeten opnieuw verstuurd worden Informatica II: les 4

Jan Lemeire

Pag. 44 / 55

Fifo-queue Basisoperaties: add() get()


Jan Lemeire

Pag. 45 / 55

Implementatie met array

p. 53

2 pointers nodig eerste

eerste

eerste

data

data

data

30 50 63

10 27 30 50 63

laatste

laatste

laatste

eerste data

eerste data

20

30 50 63 -9 78

laatste

20 -2 30 50 63 -9 78

laatste

en ... boolean voor te weten of vol/leeg Informatica II: les 4

Jan Lemeire

Pag. 46 / 55

p. 51-52 public class FIFOQueue{ T[] data; int eerste=0; // pointer naar eerste element (als niet leeg) int laatste=0; // pointer naar de plaats voor het volgend element boolean full = false; // als queue vol is public FIFOQueue(int capacity){ data = (T[]) new Object[capacity]; } public void add(T waarde){ if (full) throw new BufferOverflowException(); data[laatste] = waarde; laatste++; if (laatste == data.length) laatste = 0; if (laatste == eerste) full = true; } public T get(){ if (isEmpty()) throw new BufferUnderflowException(); T waarde = data[eerste]; data[eerste] = null; public boolean isEmpty(){ eerste++; return !full && laatste == eerste; if (eerste == data.length) } eerste = 0; public boolean isFull(){ if (full) return full; Informatica II: les 4 full = false; } Pag. 47 / 55 Jan Lemeire return waarde;

Oefening Iets met een functie

Testje… wat is de output?

Absolute waarde


Testje… wat is de output?

Voorbeeld van een statische method van de Math-klasse


Abstractie: Functie

p. 55


Jan Lemeire

Pag. 52 / 64

p. 56-7

Functie als object


Jan Lemeire

Pag. 53 / 64

Functie: iets abstracts Nulpunt zoeken via een Functie object De methode werkt immers voor alle functies Definiëren wat een functie is: Methode: double f(double x)

Hiërarchie van functies


Jan Lemeire

Pag. 54 / 64

p. 4

Interfaces

Je definieert ze als interface ipv klasse


Jan Lemeire

Pag. 55 / 64

public interface Functie { /** geeft functiewaarde in opgegeven punt */ double f(double x); } class Functie1 implements Functie{ public double f(double x) { return 2 *(x - 3); } } class Functie2 implements Functie{ public double f(double x) { return x * x + 12 *(x - 3); } } class Functie3 implements Functie{ public double f(double x) { return - x * x * x / 8 + x * x + 20 *(x - 3); } } Informatica II: les 3

Jan Lemeire

p. 56

Pag. 56 / 64

Klasses


Jan Lemeire

Pag. 57 / 64

Gebruik Constructor: hier zonder parameters Default constructor: moet je niet definiëren Als je een andere constructor definieert, vervalt deze. Met de andere constructor geef je aan dat je parameters moet meegeven. Functie functie = new Functie2(); double nulpunt = vindNulpunt(a, b, functie);


Jan Lemeire

Pag. 58 / 64

Extra klasses


Jan Lemeire

Pag. 59 / 64

class LineaireFunctie implements Functie{ double m, q; public LineaireFunctie(double m, double q){ this.m = m; this.q = q; } public double f(double x) { return m * x + q; } } class KwadratischeFunctie implements Functie{ double a, b, c; public KwadratischeFunctie(double a, double b, double c){ this.a = a; this.b = b; this.c = c; } public double f(double x) { return a * x * x + b * x + c; } } Functie functie = new KwadratischeFunctie(1, 12, -36); double nulpunt = vindNulpunt(a, b, functie); Informatica II: les 3


Functie met specifieke parameters class LineaireFunctie implements Functie{ double m, q; public LineaireFunctie(double m, double q){ this.m = m; this.q = q; } public double f(double x) { return m * x + q; } } class Functie1 extends LineaireFunctie{ Functie1(){ super(2, -6); } } Informatica II: les 4

Jan Lemeire

Pag. 62 / 64

class KwadratischeFunctie implements Functie{ double a, b, c; public KwadratischeFunctie(double a, double b, double c){ this.a = a; this.b = b; this.c = c; } public double f(double x) { return a * x * x + b * x + c; } } class Functie2 extends KwadratischeFunctie{ Functie2(){ super(1, 12, -36); } }


Jan Lemeire

Pag. 63 / 64

Informatica. Deel II&III: les 4. geheugen set, stacks & queues - interfaces. Jan Lemeire Informatica deel II&III februari mei 2015

Recommend Documents