Parallel Systems Introductionparallel.vub.ac.be/education/java/theorie/java HOC 8 - 2015.pdf · moet handig en efficiënt zijn, geschikt voor de taak Informatica II: les 8 High-level

Parallel Systems: Introduction

Informatica

Deel II&III: les 8

Software & binaire bomen

Jan Lemeire

Informatica deel II&III

februari – mei 2015

Jan Lemeire 2Pag. / 67

Leibniz’ droom

Informatica II: les 8

De “Calculus ratiocinator”

Een logisch denkend apparaat

Om met de regels van de logica ondubbelzinnig te kunnen

vaststellen of een statement waar of vals is

Deductief systeem waarin alle regels afgeleid zijn van een

kleine verzameling axiomas

1646 – 1716

Leibniz was één van de eerste die begreep dat als je filosoferen, denken, redeneren, … in formele regels kunt gieten, je dit ook door een apparaat kuntlaten doen

Vandaag

1. Theoretische informatica

2. Software

3. Java GUIs

4. Binaire bomen

(1) Digitaal & binair

(4) Hardware architectuur

(5) Efficiënt productieproces

(6) Computatietheorie & Software

Elektronica: (2) ‘relais’-schakeling,

(3)geheugen

(7) Operating system

(8) Communicatie &

internet

(9) Artificiële

intelligentie

Informatica deel III: technologie, historiek en economische aspecten

Waarmaken van Leibniz’s droom

(0) Het idee


Hoofdstuk 6: Software


George Boole

Logica herleid tot Booleaanse algebra


1815 – 1864

Boole zette een belangrijke stap met het ontwikkelen van een algebra voor het ‘rekenen’ met statements over waar/onwaar.


Gottlob FregeBeschrijft hoe wiskundigen en

logici denken

1879: de universele taal van de logica

1903: brief van Betrand Russel die hem op een onvolledigheid wijst

Extra-ordinaire verzameling = verzameling dat eenelement is van zijn eigen

– Vb: “verzameling van alle dingen die geen spreeuw zijn”

Maar: de verzameling E van alle ordinaireverzamelingen

– En wat is E? Ordinair of extra-ordinair


1848 – 1925


David Hilbert

“Wir mussen wissen; wir werden wissen”

We moeten weten; we zullen weten

Elke logische of mathematische vraag is oplosbaar(en zal opgelost worden)

Nodig: een expliciete procedure om vanuit premises na te gaan of een conclusie volgt of niet (Hilbert’s beslissingsprobleem)


1862 – 1943

Hilbert’s beslissingsprobleem zou leiden tot een doorbraak in de theoretischeinformatica.


Alan Turing

Hilbert’s procedure: algoritme!

Als we een ‘mechanische’ lijst van regels hebben om de oplossing van een mathematisch probleem op te lossen, zoudenwiskundigen geen werk meer hebben…

Bestaat er zo’n algoritme?

Om tegendeel te bewijzen moest hij een ding makendat een/elk algoritme kan uitvoeren


Alan Turing wierp zich op Hilbert’s probleem. Hij bedacht dat er hiervoor eenalgoritme gemaakt moet worden (die nagaat of een statement klopt of niet), en vervolgens een machine die het algoritme kan uitvoeren. De ‘Turing machine’ werd geboren, een theoretisch model van een computer.


De Turing machine


Staat Gelezenbit

Nieuwestaat

Te schrij-ven bit

Bewegen

0 0 0 0 >

0 1 1 1 <

1 0 1 _ >

1 1 HALT

Data: oneindige lange tape voor het lezen of schrijven van 0/1/spatie

Kan 1 vakje naar links of rechts bewogen worden

Staat (toestand): een aantal binaire variabelen

Gedragsregels

Deze machine is alleen maar van theoretisch nut. Ze is bijvoorbeeld niet echtgemakkelijk programmeerbaar.


Voorbeeld

Applet van studenten 2012

http://parallel.vub.ac.be/education/java/studentenprojecten/Turing Machine.html

• “5-state B.B.”: met input ‘_11’ stopt machine, voorandere inputs niet

Java applet:

http://ironphoenix.org/tril/tm/


http://parallel.vub.ac.be/education/java/studentenprojecten/Turing Machine.html

http://ironphoenix.org/tril/tm/


Oplossing van Hilbert’s beslissingsprobleem?

Met de machine nagaan of een logisch statement waar of valsis:

Programma runnen

Als de machine stopt is statement bewezen (waar).

‘Halting problem’ (tegelijkertijd ontdekt door Alonzo Church en Alan Turing)

Gegeven een Turing machine en programma, ga na of ditprogramma zal stoppen.

Hier bestaat geen algoritme voor die dit kan nagaan

Hilbert’s beslissingsprobleem is onoplosbaar

Turing’s resultaten ook belangrijk voor informatica


Het resultaat van Turing was weer een knak in het optimisme van de wetenschap. Je kan niet voor alles bewijzen of het waar of niet waar is. Hieruit onstond mede de moderne relativistische kijk op de wereld. De wetenschap kan niet allesoplossen/verklaren… De VUB blijft echter geloven dat wetenschap veel kan oplossen. Scienta Vincere Tenebras.


De universele computer

Elke computatie kan er op uitgevoerd worden = Turing Machine

Kan alles berekenen wat berekenbaar is

rekenen

ook om logisch te denken…

universeel


Misschien wel het belangrijkste resultaat van Turing is echter het idee van eenuniversele computer. Eén computer (hardware) die alles kan berekenen watmaar te berekenen valt. Dit was revolutionair, omdat velen in die tijd nietkonden geloven dat je met 1 machine totaal verschillende berekeningen kandoen. Alsof je met een wasmachine ook kan autorijden.


Misvattingen omtrent computers


Howard Aiken, bouwde de eerste computer

voor IBM in 1944 en zei in 1956:

“If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regards this as the most amazing coincidence I have ever encountered”

Studie van 1947:

“slechts zes elektronische digitale computers zullen voldoende zijn om al het rekenwerk van de gehele Verenigde Staten te kunnen doen."

http://nl.wikipedia.org/wiki/1947


Basisprincipe

1 universele computer kan elke andere computer simuleren

Zo is je programma ook maar data die zegt wat de computer moet doen. Voor dat programma heb je geenaparte machine nodig, toch?

Nogal logisch, niet?

Dit kan je ook toepassen op programmeertalen: je wilt een taal waarmee je alle mogelijke algoritmes kanprogrammeren, een universele programmeertaal.



Computatietheorie: bewijzen dat eenprogramma correct is?

Heel omslachtig!

Enkel mogelijk voor eenvoudige algoritmes.

Dus: ad-hoc testen noodzakelijk, zorgvuldigprogrammeren, goed structureren van de code, …


Anderzijds zijn er nog vele gaten in de theoretische informatica. Zo zou het toch handig zijn om te bewijzen dat je programma correct is. Dit blijkt heel omslachtig te zijn, zelfs voor simple programma’s. Informatica blijft dan ookgedeeltelijk een ‘praktische’ wetenschap. Maar wij ingenieurs malen daar tochniet om, he? Als het maar nuttig is, die computer.


Hoofdstuk 6: Software


software: weg met de kabeltjes


Programmeertalen


softw

are

Een processor biedt een aantal instructies aan die hij begrijpt en kan uitvoeren. Deze instructies zijn binair en noemt men machinecode. Voor de leesbaarheid biedt assembler mnemonische afkortingen aan voor binaire instructies, variabelen en labels van codelijnen. De assembler maakt de vertaling en zet alle afkortingen om naar binaire machinecode die dan uitgevoerd kan worden.


Machinetaal - assembler

Instructies op machineniveau:STO (store): sla waarde op in geheugenvakje met naam x

EQ/NE (equal): als gelijk aan/is niet gelijk, spring naar xxx (label)

MUL/ADD (multiply/add): vermenigvuldig/voeg toe aan x

JMP (jump): spring naar xxxInformatica II: les 8


Assembler-instructieformaat


OPC OP1 OP2 RES

OPC OP1 OP2 NEXT

Informatieverwerkende instructie

Stuurinstructies (control instructions)

OPeration Code: de aard van de bewerking

OPerand addresses: de adressen van de twee

gegevens waarop operatie zal worden uitgevoerd

RESult address: het adres van het resultaat

NEXT instruction: het adres in het programmageheugen

van de volgende instructie


3e generatietaal

Onafhankelijk van de hardware

≈ beschrijving van het algoritmeGebruik van variabelen ipv geheugenadressen

Geen JUMP, enkel for/while/if/switch – Jumps leidt tot spagetticode, je mag van overal naar overal springen

Functies/methodes mogelijk

Omzetting naar assembler: compilerenCheckt je code op syntaxfouten!


Programmeren in assembler is niet produktief. Het is redelijk omslachtig, je maakt snel fouten en de code is heel onleesbaar. Daarom heeft men programmeertalen ontwikkeld die minder code vergen, meer aansluiten bij algoritmes, meer gestructureerd, leesbaarder en minder foutgevoelig. De Nederlander Edgser Dijkstra was het voornaamste genie achter de 3e

generatietalen.


Edsger Dijkstra (NL)

Welke constructies moet een programmeertaalminimaal bevatten?

While/for

– Goto is onnodig. In oude talen kon je zeggen ‘spring naar lijn 111’, een willekeurige lijn van je programma. Dit leidde echter tot onoverzichtelijke ‘spaghetti’-code. Dijkstra toonde aan dat een while voldoende is

Functies

– In het begin waren er om praktische redenen veelbeperkingen op het gebruik van functies.

Recursie

– Hier was veel tegenkanting tegen, omdat het praktischtamelijk ‘duur’ is (vergt veel van processor)


1930 – 2002


Programma => computer


broncode

Applicatie(executable .exe)

compileren

uitvoeren

Nieuwe compilatie nodig voor

elk systeem (operating

system + hardware)!

Operating System (Windows, Linux, Mac, …)

Hardware(Intel of AMD processor)

Hogere taal

Machinetaal


Java: via virtuele machine


Java code (.java file)

Java applicatie(.class of jar-file)

compileren

uitvoeren

Javacode werkt op elk

operating system!

Je moet wel virtual machine

installeren

Tijdens het uitvoeren wordt

instructies van de class-files

omgezet naar machinetaalOperating System

(Windows, Linux, Mac, …)


Java Virtual Machine

Specifieke tussentaal die iets

hoger is dan assembler


Ideaal voor internet


Jou code staat op

webserver

Via virtuele machine runt

hij op elke lokale machine

(‘client’)

Java applicatie(.class of jar-file)

Operating System (Windows, Linux, Mac, …)


Java Virtual Machine

INTERNET

Doordat Java via een virtuele machine (die wel specifiek is voor elk system) tijdens het uitvoeren wordt omgezet naar machinetaal, kan je programmaoveral uitgevoerd worden.


Python & Mathlab

Geïnterpreteerde talen

Je code wordt tijdens het uitvoeren omgezet naarmachinetaal.

Je moet Python/Mathlab dus geïnstalleerd hebben

Javacode wordt wèl gecompileerd, java-files wordenomgezet naar class-files.

Javacode wordt dus gecontroleerd op fouten


Niet in cursus


4e generatietaal

High-level specification languages: programmerenwat je wilt, niet hoe het moet gebeuren

Vb: GUI aanmaken met een toolTe integreren in Eclipse

– Google Windowbuilder Pro

– Visual Editor

(Nog) niet echt succesvol

Enkel voor specifieke applicaties (zoals GUIs)

Mijn mening: nog geen artificiële intelligentie

=> computer kan nog niet begrijpen wat je wilt


Een GUI aanmaken kan via een tool waarbij je niets moet programmeren. Je bouwt als het ware je applicatie door aan te geven hoe deze er uit moet zien. Dit werkt echter nog niet voor algemene applicaties…


Tool om GUIs te maken


Kan je toevoegen aan Eclipse!


Object-georiënteerde talen

Worden als 3e generatietalen aanzien

Toch is de code-organisatie fundamenteelverschillend

De code is opgesplitst in klasses ipv functies.

Vergt een andere manier van denken

Is dè uitdaging van dit semester, zowel voor jullie alsvoor ons (lesgevers)



Voor ingenieur: welke taal?

moet handig en efficiënt zijn, geschikt voor de taak


High-level (doet veel voor u)

Low-level (kort bij de hardware)

Grote projectenKleine projecten

Java

Python Matlab

C/C++

Zonder al te diep in te gaan over wat nu de beste taal is (een eeuwige steeds-hoog-oplopende discussie onder informatici), een kleine poging tot conclusies. C/C++ zullen velen later nog zien, het is de meest-gebruikte taal die kort bij de hardware staat, daarvoor uitermate geschikt voor het programmeren van systemen (chips, robots, kritische applicaties, …)

Graphical User

Interface (GUI)


GUI

GUI = Graphical User Interface

Gebruiken van de java klasses van Swing

Online documentatie

Toont de kracht van object-georiënteerde talen

Encapsulatie

Overerving (Inheritance)

Abstractie/polymorphisme

Zie



Swing’s klassehiërarchie



Boek p. 38, 39, 43


Boek p. 35

Boek p. 45-46


Tekenvoorbeeld


public class TekenVoorbeeld extends JFrame {

public TekenVoorbeeld(){

setSize( 400, 200 );

setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );

setTitle( "Voorbeeld 0301" );

setContentPane( new Paneel() );

setVisible( true );

}

public static void main( String args[] ) {

JFrame frame = new TekenVoorbeeld();

}

}

Boek p. 69

en volgende

class Paneel extends JPanel {

private int a;

private int b;

private int antwoord;

public Paneel() {

setBackground( Color.WHITE );

a = 174;

b = 26;

antwoord = a + b;

}

public void paintComponent( Graphics g ) {

super.paintComponent( g );

// Zet de waarden van a, b en antwoord op het scherm:

g.drawString( "Overzicht van de berekening:", 40, 20 );

g.drawString( "a = " + a, 40, 40 );

g.drawString( "b = " + b, 40, 80 );

g.drawString( "De som is: " + antwoord, 40, 120 );

g.fillOval(40, 20, 10, 10);

g.drawOval(40, 40, 10, 10);

g.fillRect(40, 80, 10, 10);

g.drawRect(40, 120, 10, 10);

}

}

Binaire bomen


Elke node is een object


class Node<T>{

T data;

Node<T> left, right;

Node(T data){

this.data = data;

this.left = null;

this.right = null;

}

}


Boom object


public class BinaryTree<T> {

Node<T> root;

Comparator<T> comparator;

public BinaryTree(Comparator<T> comparator){

this.comparator = comparator;

root = null;

}

}


Operaties op bomen

7.2 Toevoegen element

7.3 Zoeken element

7.5 Verwijderen element

7.6 Doorlopen van boom (bvb printen)

7.7 ‘Balanceren’ van de boom



2. Zoeken element

Tijd ~ diepte boom

Idealiter: log2nBehalve als ongebalanceerd (zie verder)


public boolean contains(T object){

return find(root, object);

}

private boolean find(Node<T> current, T object){

if (current == null)

return false;

else if (comparator.compare(current.data, object) == 0)

return true;

else if (comparator.compare(object, current.data) < 0)

return find(current.left, object);

else

return find(current.right, object);

}

p. 99


Staartrecursie

Met while:


public boolean containsWithoutRecursion(T object){

Node<T> current = root;

while (current != null){

if (comparator.compare(current.data, object) == 0)

return true; // gevonden!

else if (comparator.compare(object, current.data) < 0)

current = current.left;

else

current = current.right;

}

return false; // niet gevonden

}


Zoektijd binaire boom

Als gebalanceerd

n => n/2 => n/4 => n/8 => … => 1

Of: 1.2x = n

𝑥 = 𝑎𝑎𝑛𝑡𝑎𝑙𝑍𝑜𝑒𝑘𝑠𝑡𝑎𝑝𝑝𝑒𝑛 = log2 𝑛


p. 100


Ongebalanceerde boom


𝑎𝑎𝑛𝑡𝑎𝑙𝑍𝑜𝑒𝑘𝑠𝑡𝑎𝑝𝑝𝑒𝑛 = log4 𝑛 𝑎𝑎𝑛𝑡𝑎𝑙𝑍𝑜𝑒𝑘𝑠𝑡𝑎𝑝𝑝𝑒𝑛 = log1.33 𝑛

Gemiddelde is slechter dan log2 𝑛!


Zoektijd

𝐥𝐨𝐠𝟐 𝒏 𝐥𝐨𝐠𝟒 𝒏 𝐥𝐨𝐠𝟏.𝟑𝟑 𝒏 𝒏/𝟐10 3,3 1,7 8,1 5

100 6,6 3,3 16,1 501000 10,0 5,0 24,2 500

10000 13,3 6,6 32,3 50001000000 19,9 10,0 48,4 5000001000000 19,9 10,0 48,4 500000

10000000 23,3 11,6 56,5 5000000100000000 26,6 13,3 64,6 50000000

1000000000 29,9 14,9 72,7 500000000


/2

*2,433


Verschil in zoektijd

Eigenschap logaritmes :

Verschil in aantal stappen:

Besluit: logaritmisch << lineair

𝑠𝑡𝑎𝑝𝑝𝑒𝑛𝑅𝑎𝑡𝑖𝑜 =log𝑑 𝑛

log2 𝑛=

1

log2 𝑑

𝑠𝑡𝑎𝑝𝑝𝑒𝑛𝑅𝑎𝑡𝑖𝑜 =1

log2 1.33=

1

0.411= 2.43

𝑠𝑡𝑎𝑝𝑝𝑒𝑛𝑅𝑎𝑡𝑖𝑜 =1

log2 4= 1/2

log𝑑 𝑛 =log2 𝑛

log2 𝑑

2 t.o.v. 1.333

2 t.o.v. 4

Verandering van basis



Ongebalanceerde boom 2

Vast aantal (k-1) nodes links, de rest rechts

Rechterboom heeft n/k => n/2k stappen

Totaal n/2k + log(k – 1) ≈ n/2k


lineair

k << n

p. 102


3. Verwijderen van element


4 mogelijkheden:

Element is root

Element is niet in boom

Element heeft 0 of 1 subboom

Element heeft 2 subbomen

p. 102

3

2 6

1 4

5

7

3 mogelijke situaties :a) 2 subbomen:

3, 6b) 0 of 1 subboom:

1, 2, 4, 5, 7c) niet aanwezig:

0, 8, …


4e geval: promoten van node


2 6

1 4

5

7

2 6

1 4

5

7

Meest linkse van rechtersubboom

Meest rechtse van linkersubboom

Jan Lemeire 57Pag. / 67Informatica II: les 8

public boolean remove(T object){

if (comparator.compare(root.data, object)== 0){

root = createSubtree(root);

return true;

} else

return findNodeAndRemove(root, object);

}

private boolean findNodeAndRemove(Node<T> current, T object){

if (current == null)

return false;

if (current.left != null && comparator.compare(current.left.data,

object)== 0){

current.left = createSubtree(current.left);

return true;

} else if (current.right != null

&& comparator.compare(current.right.data, object)== 0){

current.right = createSubtree(current.right);

return true;

} else if (comparator.compare(current.data, object) < 0)

return findNodeAndRemove(current.left, object);

else

return findNodeAndRemove(current.right, object);

}


private Node<T> createSubtree(Node<T> current){

if (current.left == null){

// current.right is the only subtree that we should consider

return current.right;

} else if (current.right == null){

// current.left is the only subtree that we should consider

return current.left;

} else {

// promote rightmost node of left subtree

if (current.left.right == null){

current.left.right = current.right;

return current.left;

} else {

Node<T> rightMostNode=pickRightMostNode(current.left);

// he is new root of subtree

rightMostNode.right = current.right;

rightMostNode.left = current.left;

return rightMostNode;

}

}

}


private Node<T> pickRightMostNode(Node<T> current){

// we expect current.right not to be null

if (current.right.right != null){

return pickRightMostNode(current.right);

} else {

Node<T> rightMostNode = current.right;

current.right = rightMostNode.left;

rightMostNode.left = null;

return rightMostNode;

}

}


4. Doorlopen van boom

public void preOrder(Node<T> node){

if (node != null){

System.out.print(node.data+", ");

preOrder(node.left);

preOrder(node.right);

}

}

public void inOrder(Node<T> node){

if (node != null){

inOrder(node.left);


inOrder(node.right);

}

}

public void postOrder(Node<T> node){

if (node != null){

postOrder(node.left);

postOrder(node.right);


}

} Informatica II: les 8

{a, c, e, f, g, i, k, l, q, r, x, z}

{k, g, a, e, c, f, i, l, x, q, r, z}

{c, f, e, a, i, g, r, q, z, x, l, k}

p. 105

Op boom van p.96


Boom van p.96



Toepassingen

preOrder: backtracking

Is de node de oplossing?

Indien niet, zoek eerst links en daarna rechts

inOrder: in volgorde afgaan van alle elementen



Toepassing postorder


public int aantalKinderen(Node<T> node){if (node == null)

return 0;int n = aantalKinderen(node.left);n += aantalKinderen(node.right);System.out.println("Node "+node.data+" heeft "+n+"

kinderen");return n + 1;

}

p. 106

Documents

Parallel Systems Introductionparallel.vub.ac.be/education/java/theorie/java HOC 8 - 2015.pdf · moet handig en efficiënt zijn, geschikt voor de taak Informatica II: les 8 High-level