[Java] Geschikte invariant bij een stuk code ontwerpen *

[Verwijderd]

JAVA:

code:

public int readInt()
    {   boolean r=true; 
        int chr=0, num=0;
        
        chr=read();    //read() leest een character in en geeft de ASCII waarde terug
        num=chr-48;    
        
        while (r==true)
        {   chr=read();
            
            if (Character.isDigit((char)chr)==true)
                num=(num*10)+(chr-48);
            else
            {       
                r=false;
            }
        }
        return num;
    }

Hoe kan ik hier een geschikte invariant bij vinden? Ik weet wel dat je eerst de invariant dient te ontwerpe en dan het stukje code kunt schrijven. Maar als oefening probeer ik bij bovenstaande code een invariant te vinden. Maar ik weet totaal niet waar ik moet beginnen.

[ Voor 4% gewijzigd door Verwijderd op 20-04-2005 21:06 ]

[MrBucket]

Ik meen me te herinneren dat jij voornamelijk jezelf programmeren aan het aanleren was, en geen informatica-opleiding volgt (maw: huiswerkopgaves post).

Wat gebeurt er nu precies in je code. Ik neem aan dat je snapt dat het werkt; ik ga ervan uit dat je het zelf geschreven hebt nl*. Iig, de invariant is een regel die moet gelden na elke iteratie van de while-loop (dat is althans mijn interpretatie van invariant, als er meerdere mogelijkheden zijn hoor ik het graag).
Het geheel werkt als volgt: je leest een karakter in, converteert dat naar een cijfer, en voegt dat toe aan het getal wat je al had. Vervolgens lees je het volgende karakter in; als dat een cijfer is doe je hetzelfde nog een keer, als het geen cijfer is dan is de conversie compleet. Toch?

Blijkbaar is een invariant dat, na elk karakter dat je hebt ingetypt, de variabele 'num' de numerieke waarde bevat van de cijfers die je tot dan toe hebt ingetypt (dat is nl. de 'reden' dat dit stukje code werkt). Dit lijkt mij de belangrijkste invariant; evt. kan je ook zeggen dat 'r' true is zolang men nog met het huidige getal bezig is, maar dit lijkt me triviaal.

* De reden dat ik denk dat dit je eigen code is, is omdat het eerste karakter niet wordt gecontroleerd of het wel een cijfer is of niet. Dus of dit is een preconditie van readInt(), of je bent een isDigit() vergeten

[ Voor 3% gewijzigd door MrBucket op 20-04-2005 23:29 ]

[Robtimus]

Even iemand die aan de TU/e heeft gestudeerd aan het woord

Vraag 1: wat zijn je pre- en postconditie? Daaruit leid je nml vaak je invariant af.

Dan nu de structuur zoals het vaak is:

code:

{PRE}
initialisatie
{P}
while {B} do
    {P}
    block code zonder increment
    {P met increment toegepast}
    increment
    {P}
od
{P&& !B}

Waarbij P && !B samen de postconditie impliceren.

Klein voorbeeld: de gewone sum van een array.

code:

{PRE: array[0..N) is ingevuld}
n, sum = 0, 0;
{P: sum == (sum i: 0 <= 0 < n: array[i])}
while (n != N) do
    {P: sum == (sum i: 0 <= 0 < n: array[i])}
    sum = sum + array[n];
    {P(n = n + 1): sum == (sum i: 0 <= i < n + 1: array[i]) == (sum i: 0<= i < n: array[i]) + array[n])}
    n = n + 1
    {P}
od
{P && n == N => sum = (sum i: 0 <= i < N: array[i])}

Dus eerst je postconditie vaststellen, daarna de invariant.

Edit: en gebruik ipv 48 'a', dat leest makkelijker en is intuitiever.

[ Voor 8% gewijzigd door Robtimus op 21-04-2005 09:44 ]

[staefke]

hmm.. meende dat de preconditie altijd met {P} werd aangeduid en de postconditie met {Q} (hier op de RuG in Groningen 15 jaar geleden althans). Verder was er een guard {B} en een invariant {J} en het idee was dat {J && not B} => {Q}, maar poeh! wat lang geleden
Maar zoals hierboven ook al vermeld is, ga gewoon uitzoeken wat er op een bepaald punt in de while lus nu daadwerkelijk geldt (dat is tenslotte je invariant), en formaliseer dit.

[Verwijderd]

MrBucket schreef op woensdag 20 april 2005 @ 23:28:
Ik meen me te herinneren dat jij voornamelijk jezelf programmeren aan het aanleren was, en geen informatica-opleiding volgt (maw: huiswerkopgaves post).

Ik volg de HP1 module van de AMBI module dmv zelfstudie. Dat is ook de reden waarom ik het niet aan een docent kan vragen. Daarom val ik jullie lastig met dit soort vragen

Wat gebeurt er nu precies in je code. Ik neem aan dat je snapt dat het werkt; ik ga ervan uit dat je het zelf geschreven hebt nl*. Iig, de invariant is een regel die moet gelden na elke iteratie van de while-loop (dat is althans mijn interpretatie van invariant, als er meerdere mogelijkheden zijn hoor ik het graag).
Het geheel werkt als volgt: je leest een karakter in, converteert dat naar een cijfer, en voegt dat toe aan het getal wat je al had. Vervolgens lees je het volgende karakter in; als dat een cijfer is doe je hetzelfde nog een keer, als het geen cijfer is dan is de conversie compleet. Toch?

Hoe de code werkt begrijp ik wel. Maar nu gaat het me om de formele afleidin van de invariant zoals dat op het HP1 examen zou moeten. De theorie moet ik nog eens goed bestuderen (ben nu met discrete wiskunde bezig

Blijkbaar is een invariant dat, na elk karakter dat je hebt ingetypt, de variabele 'num' de numerieke waarde bevat van de cijfers die je tot dan toe hebt ingetypt (dat is nl. de 'reden' dat dit stukje code werkt). Dit lijkt mij de belangrijkste invariant; evt. kan je ook zeggen dat 'r' true is zolang men nog met het huidige getal bezig is, maar dit lijkt me triviaal.

[Verwijderd]

IceManX schreef op donderdag 21 april 2005 @ 09:43:
Even iemand die aan de TU/e heeft gestudeerd aan het woord

Vraag 1: wat zijn je pre- en postconditie? Daaruit leid je nml vaak je invariant af.

Ik heb geen pre- en postconditie. Het gaat er mij om de formele afleidingen te zoeken bij een stukje code dat ik zelf heb geschreven

Klein voorbeeld: de gewone sum van een array.

code:

{PRE: array[0..N) is ingevuld}
n, sum = 0, 0;
{P: sum == (sum i: 0 <= 0 < n: array[i])}
while (n != N) do
    {P: sum == (sum i: 0 <= 0 < n: array[i])}
    sum = sum + array[n];
    {P(n = n + 1): sum == (sum i: 0 <= i < n + 1: array[i]) == (sum i: 0<= i < n: array[i]) + array[n])}
    n = n + 1
    {P}
od
{P && n == N => sum = (sum i: 0 <= i < N: array[i])}

Dus eerst je postconditie vaststellen, daarna de invariant.

Hier heb je het voordeel dat je een grens hebt (N). Bij mijn voorbeeld is dat niet het geval, volgens mij moet je in dat geval een staartinvariant gebruiken.

Edit: en gebruik ipv 48 'a', dat leest makkelijker en is intuitiever.

Bedankt voor de tip!

[tekno]

Voor je huidige programma kun je juist door het ontbreken van zo'n grens eindiging niet bewijzen.
Omdat je niet weet of er ooit nog een niet digit langs zal komen (in theorie).

Stel je weet dat er maximaal een bepaald aantal digits langskomt, of het zelfs zo is dat het aantal digits begrensd moet zijn (ivm overflows). Dan kun je weer totale correctheid aan de hand van pre en postcondities bewijzen.

Van dit programma kun je alleen partiele correctheid bewijzen. Dat wil zeggen je kunt regels opstellen om te bewijzen dat als het programma eindigt het goed werkt (eventuele overflow uitgezonderd), maar je kunt niet bewijzen dat het programma ook daadwerkelijk zal eindigen op basis van je code.

Maar wat me interessant lijkt is wat je wel al aan tussencondities hebt opgesteld, zodat het in ieder geval duidelijk is of je op eindiging na de juiste asserties op de juiste plaats zet.

Hopelijk ben ik niet te laat met deze reactie, omdat het topic al een paar dagen oud is. Maar het lijkt me erg interessant om te kijken wat voor pre en postconditie je opstelt en wat je invariant is.

Zowieso is betrrefende dit onderwerp naar mijn mening het boek: Anne Kaldewaij - Programming: The derivation of algorithms, een zeer nuttig hulpmiddel.

kijk ook eens hier: http://www.liacs.nl/home/devink/pc2001/pc2001.html

[ Voor 4% gewijzigd door tekno op 27-04-2005 16:16 . Reden: link toegevoegd ]

[Verwijderd]

Ik gebruik een ander boek van A. Kaldewaij, het ontwerpen van algoritmen. Het is niet meer verkrijgbaar. Maar AMBI studenten die de HP1 module willen doen kunnen bij Exin kosteloos een kopie krijgen. www.exin.nl (hier is ook de module beschrijving voor HP1 te vinden)

Bovenstaand voorbeeld is misschien niet zo goed om meet te beginnen. Dus heb ik dat voorbeeld laten zitten. Ik heb een ander voorbeeld genomen waarvoor ik geprobeert heb de pre en postconditie te vinden en van daaruit de invarianten af te leiden. Het voorbeeld is een functie die een string (char array) omkeert en weer terug geeft.

Java:

code:

private static char [] InverseString(char [] a)
    {   /*formele specificatie
         *val char a[]
         *var char arrinv[], int k;
         *post: (Ai : 0<=i<a.length : arrinv[i]=a[a.length-i])
         *
                                 *invarianten
         *P0: (Ai : 0<=i<k : arrinv[i]=a[a.length-i])
         *P1: 0<=k<a.length
         *
         *Stopconditie
         *k<=a.length
         *
         *Opdrachten
         *P0:  arrinv[k-1]=a[a.length-k]
         *P1:  k++;
         */
         
         char [] arrinv = new char[a.length];
         int k=1;
         
         while (k<=a.length)
         {  arrinv[k-1]=a[a.length-k];
            k++;
         }
         
         return arrinv;
    }

Misschien zijn de afleidingen niet zoals ze zouden moeten zijn en ook de initialisatie van de variabelen heb ik achterwege gelaten. Maar dit is de eerste keer dat ik op deze manier een programma afleid.

[Robtimus]

Verwijderd schreef op donderdag 28 april 2005 @ 15:20:
Ik gebruik een ander boek van A. Kaldewaij, het ontwerpen van algoritmen. Het is niet meer verkrijgbaar. Maar AMBI studenten die de HP1 module willen doen kunnen bij Exin kosteloos een kopie krijgen. www.exin.nl (hier is ook de module beschrijving voor HP1 te vinden)

Bovenstaand voorbeeld is misschien niet zo goed om meet te beginnen. Dus heb ik dat voorbeeld laten zitten. Ik heb een ander voorbeeld genomen waarvoor ik geprobeert heb de pre en postconditie te vinden en van daaruit de invarianten af te leiden. Het voorbeeld is een functie die een string (char array) omkeert en weer terug geeft.

Java:

code:

private static char [] InverseString(char [] a)
    {   /*formele specificatie
         *val char a[]
         *var char arrinv[], int k;
         *post: (Ai : 0<=i<a.length : arrinv[i]=a[a.length-i])
         *
                                 *invarianten
         *P0: (Ai : 0<=i<k : arrinv[i]=a[a.length-i])
         *P1: 0<=k<a.length
         *
         *Stopconditie
         *k<=a.length
         *
         *Opdrachten
         *P0:  arrinv[k-1]=a[a.length-k]
         *P1:  k++;
         */
         
         char [] arrinv = new char[a.length];
         int k=1;
         
         while (k<=a.length)
         {  arrinv[k-1]=a[a.length-k];
            k++;
         }
         
         return arrinv;
    }

Misschien zijn de afleidingen niet zoals ze zouden moeten zijn en ook de initialisatie van de variabelen heb ik achterwege gelaten. Maar dit is de eerste keer dat ik op deze manier een programma afleid.

Je voorbeeld klopt niet omdat je k op 1 initialiseert. Daarna zou volgens je invariant (die dan al moet gelden) arrinv[0] == a[a.length]. Ten eerste geldt dit niet omdat je geen assignment hebt gedaan, en ten tweede bestaat a[a.length] niet eens.

code:

char [] arrinv = new char[a.length];
int k=0;
// k == 0, dus je domein is leeg: 0 <= i < 0
while (k < a.length)
{
    // P0
    arrinv[k]=a[a.length - k - 1];
    // P0 (k++) == P0 /\ arrinv[k] == a[a.length - k - 1]
    k++;
    // P0
}
return arrinv;

[tekno]

Een duidelijke preconditie ontbreekt.
Zelf zou ik het als volgt hebben geformaliseerd:
Waarbij N dus gelijk is aan a.length.

code:

pre :  {N >= 0}
post : {For all i: 0 <= i < N: arrayinv.i = a.(N-1-i) } 

Hiertoe introduceer ik:

P1 = {For all i: 0 <= i < n; arrayinv.i = A.(N-1-i) }
P2 = {0 <= n <= N}
Q  = {For all i: 0 <= i < N: arrayinv.i = A.(N-1-i) }

|[
var n:         int;
var a:         array[0..N) of int;
var arrayinv:  array[0..N) of int;
|
{N >= 0}
n := 0;
invariant: {P1 /\ P2, bound: N-n}
do n != N -->
  {P1}{P2}{n != N}
  arrayinv.n := a.(N-1-n);
  {P1(n:=n+1)}{P2}{n != N}
  n := n + 1;
  {P1}{P2}
od
{P /\ n = N}
]|
{Q}

Waarbij n != N belangrijk is omdat je anders niet kunt aantonen dat je een element indexeert dat bestaat
en je anders ook de invariant P2 niet kunt aantonen.

Let verder ook goed op bij de postconditie, met name op de N-1-i.

Verder is dit maar snel door mij in elkaar geflansd met een half zatte kop, dus fouten kunnen er zeker nog inzitten

Nu is natuurlijk de tweede zaak om ook alle bewijzen te geven. Bij deze nodig ik je dan ook uit om alle bewijzen te geven die hierbij horen, inclusief eindiging.
Dat zou niet zo'n problemen moeten geven, of mijn afleiding is fout .

Waar je vooral goed op moet letten, en wat iedereen, waaronder ikzelf, vaak fouten mee maakt, zijn de arraygrenzen. Je moet altijd opletten of het element bestaat. Als je array [0..N) is, dan kun je niet element N opvragen, want dat bestaat niet. Dus incorrect.

Dit is overigens niet de enige manier om het te formaliseren, kan nog op vele andere wijzen, maar dit is een beetje de stijl die ik algemeen aanhoud. Al is het weer een tijdje geleden dat ik het actief gebruikt heb.

Hoe je dan dit in je code wilt zetten moet je zelf weten, het is aan te raden eerst het programma in GCL te construeren en dan pas te implementeren, ipv andersom. Dat werkt uiteindelijk toch makkelijker dan een programma proberen te formaliseren achteraf naar mijn mening.

Maar door veel oefenen en eventueel fouten maken leer je vanzelf ;)! Succes

zal zo eens even kijken wat HP1 inhoud.

[Verwijderd]

tekno schreef op vrijdag 29 april 2005 @ 00:04:
Een duidelijke preconditie ontbreekt.
Zelf zou ik het als volgt hebben geformaliseerd:
Waarbij N dus gelijk is aan a.length.

code:

code

Waarbij n != N belangrijk is omdat je anders niet kunt aantonen dat je een element indexeert dat bestaat
en je anders ook de invariant P2 niet kunt aantonen.

Let verder ook goed op bij de postconditie, met name op de N-1-i.

Verder is dit maar snel door mij in elkaar geflansd met een half zatte kop, dus fouten kunnen er zeker nog inzitten

Nu is natuurlijk de tweede zaak om ook alle bewijzen te geven. Bij deze nodig ik je dan ook uit om alle bewijzen te geven die hierbij horen, inclusief eindiging.
Dat zou niet zo'n problemen moeten geven, of mijn afleiding is fout .

Zoals ik al aangaf, moet ik alles nog eens grondig bestuderen waarbij ik veel ga oefenen (ben nu met discrete wiskunde bezig). Nu zou ik niet weten hoe ik bovenstaand stuk code zou moeten bewijzen. Maar ik kan je al aardig volgen

Waar je vooral goed op moet letten, en wat iedereen, waaronder ikzelf, vaak fouten mee maakt, zijn de arraygrenzen. Je moet altijd opletten of het element bestaat. Als je array [0..N) is, dan kun je niet element N opvragen, want dat bestaat niet. Dus incorrect.

Hier raak ik ook altijd mee in de war. Vooral omdat ik ook in VB6 programmeer, daar loopt een array van 0 t/m N en bij Java (of C++) van 0 tot N.

Dit is overigens niet de enige manier om het te formaliseren, kan nog op vele andere wijzen, maar dit is een beetje de stijl die ik algemeen aanhoud. Al is het weer een tijdje geleden dat ik het actief gebruikt heb.

De stijl is idd iets anders als ik in het boek voorgeschoteld krijg

Hoe je dan dit in je code wilt zetten moet je zelf weten, het is aan te raden eerst het programma in GCL te construeren en dan pas te implementeren, ipv andersom. Dat werkt uiteindelijk toch makkelijker dan een programma proberen te formaliseren achteraf naar mijn mening.

Wat is GCL

Op het examen heb ik geen compiler tot mijn beschikking, maar heel vaak kom ik er achter dat het programma niet werkt door het uit te laten voeren. Dan zie ik het vaak gelijk en is het meestal iets simpels. Gelukkig heb ik een Java editor waar je de code niet stap voor stap kunt debugen. Dus als het niet werkt moet ik als nog nadenken Maar eigenlijk vind ik dat een pruts methode en moet ik mezelf aanleren om gelijk goed na te denken. Hoe is dat bij jullie?

[ Voor 10% gewijzigd door Verwijderd op 02-05-2005 21:46 ]

[Robtimus]

Verwijderd schreef op maandag 02 mei 2005 @ 21:45:
Wat is GCL

Guarded Command Language, een abstracte programmeertaal ontworpen door Edsger W. Dijkstra. Door zijn eenvoud heel goed te gebruiken bij theoretisch programmeren.

Vooral de multiple assignments zijn erg erg handig (x, y := 0, 0)

[tekno]

Vooral de multiple assignment met:
x,y := y,x
Scheelt weer een extra variabele

deze url is wellicht ook handig voor je:
[url]http://www.cs.nuim.ie/~jpower/Courses/formalMethods/verification/hoare.pdf[url]

Daar staat heel kort de syntax gegeven, met wat extra zeer nuttige informatie.

Meer hierover zou je kunnen vinden in:
[Dijkstra76] Edsger W. Dijsktra, A discipline of Programming, Prentice-Hall series in Automatic Computation, Englewood Cliffs, N.J., 1976.

Alhoewel de werkwijze daarna nog wel verfijnd is.

Ik denk dat je meer bezig moet zijn met:
1. Wat is het probleem
2. Formaliseer het probleem
3. Hoe kan ik het probleem oplossen (eventueel door afleiden, combinatie bestaande algoritmen)
4. Formaliseer de oplossingsmethode
5. Werk deze methode uit in een programmeertaal
6. Test en kijk of het doet wat je denkt dat het doet

Het vertalen van gcl in programmacode is zeer eenvoudig, en kan zelfs geautomatiseerd worden.
En is in dit geval ook zeker niet moeilijk.

Bij de vakomschrijving van H1 kan ik er nauwelijks achterkomen wat er nu daadwerkelijk getoetst wordt. Ik denk echter dat GCL en het formeel afleiden en bewijzen van algoritmen niet echt onderdeel zal zijn, omdat het naar mijn mening daar een veel te uitgebreid gebied voor is.

Zomaar iets in elkaar tikken, compileren en testen dat kunnen de meeste wel.
De kunst is eigenlijk om eerst te denken, daarna pas te tikken en te compileren en daarna te testen.
Maar ja, veel mensen (ook ik), nemen deze wijze raad meestal niet aan, en beginnen toch zomaar iets te tikken.

[JochemK]

Volgens mij is het boek van Kaldewaij nog wel te verkrijgen hoor.

Auteur: A. Kaldewaij
Titel: "Programming: The Derivation of Algorithms"
Uitgever: Pearson Prentice Hall
ISBN 0-13-204108-1

Ik vind het geen leuk boek, maar dat komt waarschijnlijk omdat ik er tentamens over moet maken

[tekno]

Zo ver ik weet is het niet meer te koop en wordt het gedrukt op aanvraag.
Kosten liggen rond de 80 euro.

[Verwijderd]

Bedankt voor de reacties allemaal!!

Jullie raden het al, ik heb weer een vraag. Ik ben in het boek van A. Kaldewaij (Ontwerpen van Algoritmen) opnieuw begonnen. Dit keer is het mijn bedoeling om alles 100% te begrijpen. Mijn vraag is:

Het berekenen van een (programma) opdracht E mbv van een pre- en een postconditie. De bedoeling is dat je de opdrachten in de postconditie gaat invullen. En dan dmv substitutie en zo verder gaat uitwerken. Als laatste stap, om de opdracht te krijgen, probeer je de expressie in de vorm van de preconditie te schrijven.

Voorbeeld (uit het boek)
{x*y + p*q = N} q=E; x=x-p; {x*y + p*q = N}
//dus opdracht E dient om q bij te werken zodat aan de postconditie voldaan kan worden.

Uitwerking (<= teken substitutie)
(x*y + p*q = N)(x <= x-p)(q <= E)
//binnenste substutitie
((x-p)*y + p*q = N)(q <= E)
//substitutie
(x-p)*y + p*E = N
//vereenvoudigen
x*y - p*y + p*E = N
//vereenvoudigen, richting de preconditie
x*y + p*(E-y) = N
//Tot zover kan ik het goed volgen, nu gaan ze de preconditie verwerken:
//preconditie is x*y + p*q = N
E-y=q
E=q+y

Dus het programma fragment wordt:
{x*y + p*q = N} q=q+y; x=x-p; {x*y + p*q = N}

De laatste stap, van x*y + p*(E-y) = N naar E-y=q, begrijp ik niet helemaal. Kan iemand me precies uitleggen wat er gebeurd?

[Glimi]

Als x*y + p*(E-y)=N en x*y + p*q = N dan is x*y + p*(E-y) = x*y + p*q

Als we vervolgens x*y van rechts naar links halen, valt hij links weg. Vervolgens delen we ook nog door p aan beide kanten. En voila, E-y = q

[Verwijderd]

Glimi schreef op woensdag 18 mei 2005 @ 21:17:
Als x*y + p*(E-y)=N en x*y + p*q = N dan is x*y + p*(E-y) = x*y + p*q

Als we vervolgens x*y van rechts naar links halen, valt hij links weg. Vervolgens delen we ook nog door p aan beide kanten. En voila, E-y = q

Bedankt voor je snelle reactie, ik ga er morgen nog eens naar kijken.
Ben nu een beetje gaar, zit al iets van 10 uur achter een computer.

[Verwijderd]

Glimi schreef op woensdag 18 mei 2005 @ 21:17:
Als x*y + p*(E-y)=N en x*y + p*q = N dan is x*y + p*(E-y) = x*y + p*q

Als we vervolgens x*y van rechts naar links halen, valt hij links weg. Vervolgens delen we ook nog door p aan beide kanten. En voila, E-y = q

Bedankt!
Ik heb wat zitten spelen, met beide expressies en ik zie het nu ook. De eerste opgave heb ik gemaakt, waar ik eerst niet uit kwam. En nu kon ik de opgave vrij makkelijk oplossen, nu de rest van de opgaven nog

[Verwijderd]

Ik heb weer een vraag:

Ik ben bezig met het maken van de opgaven in het boek waar ik mee bezig ben. Maar het probleem is dat er niet voor alle vragen antwoorden worden gegeven met uitwerkingen

Dit is de vraag:
Gegeven zijn een integer array x[0...N] en integers p en q met 0<=p<=q<=N. Schrijf een programma met postconditie:
r=(Ni : p<=i<q && x[i]%2=0 : x[i]!=0)

Ik zal eerst mijn afleiding geven:

Formele specificatie
val int x[0...N], N
var int p, q, r
pre: 0<=p<=q<=N
post: r=(Ni : p<=i<q && x[i]%2=0 : x[i]!=0)

invariant
P0: r=(Ni : p<=i<k && x[i]%2=0 : x[i]!=0)
P1: p<=k<q

stopcriterium
k!=q

initialisatie
k=p
r=0

opdrachten
k=k+1

//invullen
(Ni : p<=i<k+1 : x[i]%2=0 && x[i]!=0)
//afsplitsen
(Ni : p<=i<k : x[i]%2=0 && x[i]!=0) + 0 indien x[k]%2!=0 && x[k]=0
(Ni : p<=i<k : x[i]%2=0 && x[i]!=0) + 1 indien x[k]%2=0 && x[k]!=0
//P0
r + 0 indien x[k]%2!=0 && x[k]=0
r + 1 indien x[k]%2=0 && x[k]!=0

if (x[k]%2=0 && x[k]!=0)
r++;

Programma

code:

int k=p, r=0;
while (k!=q)
{   if (x[k]%2=0 && x[k]!=0)
        r++;
    k++;
}

Mijn vraag is:
Het is een simpel programma het gaat dan ook om de juiste formele afleiding. Kan ik bij het afleiden van de opdracht, zomaar x[i]%2=0 uit het domein halen? Als deze afleiding niet goed is, hoe moet ik dan omgaan met x[i]%2=0 uit het domein?

[Robtimus]

Er gewoon uit halen ja.

Je kunt op 2 manieren met een mod (%) omgaan:
1) zwaar gaan uitschrijven en dan hoogst waarschijnlijk vastlopen.
2) gaan casen. Bij een mod 2 zijn dat maar 2 gevallen, bij mod 100 een stukkie meer, maar dat is toch echt de gemakkelijkste manier.

Overigens, de guard voor het NIET verhogen van r moet een || hebben ipv een &&

[Verwijderd]

IceManX schreef op maandag 25 juli 2005 @ 20:53:
Er gewoon uit halen ja.

Je kunt op 2 manieren met een mod (%) omgaan:
1) zwaar gaan uitschrijven en dan hoogst waarschijnlijk vastlopen.
2) gaan casen. Bij een mod 2 zijn dat maar 2 gevallen, bij mod 100 een stukkie meer, maar dat is toch echt de gemakkelijkste manier.

Overigens, de guard voor het NIET verhogen van r moet een || hebben ipv een &&

Bedankt voor je snelle antwoord
Had ik het toch goed. Zou niet weten hoe ik het anders zou moeten doen.

Wat is guard voor term? Ben het wel eens eerder tegen gekomen maar weet niet precies wat het betekend.
Maar volgens mij is x[k]%2=0 && x[k]!=0 wel goed. In het domein heb je alleen de even getallen zitten en daarvan wil je weten welke getallen ongelijk zijn aan 0.

[Verwijderd]

In het boek wat ik gebruik wordt Pascal als programmeertaal gebruikt. Ik heb echter nog nooit een letter in Pascal geprogrammeerd. Af en toe wordt een Real als variabele type gebruikt, is dit gewoon een floating point type?

[Creepy]

Zie http://www.google.nl/sear...btnG=Google+zoeken&meta=. Ja dus

[Verwijderd]

Creepy schreef op maandag 25 juli 2005 @ 22:09:
Zie http://www.google.nl/sear...btnG=Google+zoeken&meta=. Ja dus

Oke, bedankt, zal de volgende keer voor dit soort simpele dingen zelf effe googlen.

[Robtimus]

Verwijderd schreef op maandag 25 juli 2005 @ 22:00:
Wat is guard voor term? Ben het wel eens eerder tegen gekomen maar weet niet precies wat het betekend.
Maar volgens mij is x[k]%2=0 && x[k]!=0 wel goed. In het domein heb je alleen de even getallen zitten en daarvan wil je weten welke getallen ongelijk zijn aan 0.

Guard is de boolean waarde waarop je controleert in een IF of loop. Dus k!= q en x[k]%2=0 && x[k]!=0 zijn je guards.

Verder is x[k]%2=0 && x[k]!=0 wel goed, maar de negatie ervan is niet x[k]%2!=0 && x[k]=0 maar x[k]%2!=0 || x[k]=0. Je programma klopt dus wel, je hebt alleen een klein foutje in de afleiding staan.

[Verwijderd]

In het stuk waar ik nu mee bezig ben kom ik steeds de volgende soort kwantor tegen:
(Si, j : 0<=i<=j<N : i+j)

Klopt het dat ik dit kan herschrijven naar:
(Sj : 0<=j<N : (Si : 0<=i<=j : i+j))

[Daos]

Verwijderd schreef op dinsdag 13 september 2005 @ 19:46:
In het stuk waar ik nu mee bezig ben kom ik steeds de volgende soort kwantor tegen:
(Si, j : 0<=i<=j<N : i+j)

Klopt het dat ik dit kan herschrijven naar:
(Sj : 0<=j<N : (Si : 0<=i<=j : i+j))

Ik denk het wel.

Waarschijnlijk kan je het ook zo doen:
(Si : 0<=i<N : (Sj : i<=j<N : i+j))

[Verwijderd]

Daos schreef op dinsdag 13 september 2005 @ 23:27:
[...]

Ik denk het wel.

Waarschijnlijk kan je het ook zo doen:
(Si : 0<=i<N : (Sj : i<=j<N : i+j))

Bedankt voor je antwoord

Ik denk het niet, want i moet van 0 t/m j lopen en jij laat i t/m N lopen

[Verwijderd]

Laten we eens een (Java) programma gaan afleiden van:
(Si, j : 0<=i<=j<N : i+j)

formele specificatie
var int N;
var int r;
pre: N>=0
post: r=(Si, j : 0<=i<=j<N : i+j)

Opstellen invarianten
P0: r=(Si, j : 0<=i<=j<k : i+j)
P1: 0<=k<=N

Stopcriterium
k!=N

initialisatie
k=0
r=(Si, j : 0<=i<=j<0 : i+j)=0

opdrachten
//Om aan het stopcriterium te kunnen voldoen, k ophogen;
k=k+1

//invullen
(Si, j : 0<=i<=j<k+1 : i+j)
//afsplitsen
(Si, j : 0<=i<=j<k : i+j)+(Si : 0<=i<=k : k+i)
//P0
r+(Si : 0<=i<=k : k+i)
//introductie Q0
Q0: s=(Si : 0<=i<=k : k+i)
//opdracht P0
r+s

//opdracht s
(Si : 0<=i<=k+1 : k+i)
//afsplitsen
(Si : 0<=i<=k : k+i)+k+k+1
//Q0
s+k+k+1

programma

code:

int k=0; r=0, s=0;
while (k!=N)
{   r=r+s;
    s=s+k+k+1;
    k++;
}

Hebben jullie hier nog opmerkingen over?

[Robtimus]

Verwijderd schreef op donderdag 15 september 2005 @ 15:00:
[...]


Bedankt voor je antwoord

Ik denk het niet, want i moet van 0 t/m j lopen en jij laat i t/m N lopen

In dezelfde argumentatie:
j moet van i t/m N lopen en jij laat j vanaf 0 lopen.

Ze zijn allebei correct AFAIK.

[Verwijderd]

Ik ben weer wat aan het oefenen met het ontwerpen van algoritmen.
Als ik een invariant heb waar meerdere code regels uit afgeleid worden, hoe bepaal ik dan de volgorde van die opdrachtregels?

Een voorbeeldje:
ik lees een getal in van 2 cijfers, die wil ik dmv een char array opslaan in een int variable:
Specificatie:

code:

val char arr[0...2], N
var int r
pre: N>=0
post: r=(Si : 0<=i<N : (10/(10**i))*a[i])
//het doet er niet toe hoe de getallen worden ingelezen

invarianten 
P0: r=(Si : 0<=i<k : (10/(10**i))*a[i])
P1: 0<=k<=N

initialisatie
k=0, r=0

afleiding opdrachten
k=k+1

(Si : 0<=i<k : (10/(10**i))*a[i])
//invullen
(Si : 0<=i<k+1 : (10/(10**i))*a[i])
//splitsen k=i
(Si : 0<=i<k : (10/(10**i))*a[i])+(10/(10**k))*a[k]
//P0
iDay+(10/s)*a[k]
//introductie s
Q0: s=10**k
//invullen
10**(k+1)
s*10

Dus we hebben de volgende opdrachten (Java)

code:

iDay+(10/s)*a[k];
s*=10;
k++;

Het gaat me vooral om de opdrachten 1 en 2 (k++ moet als laatste komen). M'n gevoel zegt dat s*=10; na iDay+(10/s)*a[k]; moet komen. Maar zijn er ook nog regeltjes (en manieren waarop je de volgorde kan afleiden) te geven hiervoor? Bijv. voor een situatie waarin de volgorde wat minder duidelijk is?

[Daos]

Vergeet dat hele gedoe met invarianten. Informatica komt uit de (discrete) wiskunde en stelt niet zo veel voor. Informatici maken het moeilijker dan het is en ze bedenken dingen (zoals fundamentele informatica, UML) waar je niets aan hebt. Mensen die informatica doen weten vaak niets van programmeren en kunnen het dus ook niet.
Het programmeren en alles wat er bij hoort komt uit de elektrotechniek. Ook logica zie je vooral in de elektrotechniek bij het maken van digitale elektronica. Als je echt wil leren programmeren, dan kan je het beste beginnen met simpele digitale elektronica, zoals een adder, mux. Probeer daarna te begrijpen hoe een ALU werkt, hoe een CPU werkt, wat assembly doet en hoe je daar een programma mee maakt en als laatste hoe hogere talen (C, Java) je het makkelijker maken om je algoritme om te zetten tot een werkend programma en je daarmee een hoop werk besparen.

Mijn tips bij programmeren:
Gebruik duidelijke namen voor je variabelen. Dus niet y = 10 * x;, maar snelheid = 10; afstand = snelheid * tijd; (of in het Engels met distance, velocity en time)

Een programma maak je door het algoritme eerst duidelijk (in woorden) op te schrijven. Later kan je met wat logica wat dingen versimpelen, maar vaak is dat niet eens nodig. Wordt het verhaaltje onbegrijpelijk of te lang -> maak/gebruik functies. Een algoritme ontwerp je niet: je schijft gewoon een verhaaltje met dingen die moeten gebeuren (zoiets als het script bij een film). Denk daarbij niet in getalletjes, maar zoveel mogelijk in objecten.

Als je veel keuzes hebt in je verhaaltje dan kan je een flowchart maken met [ ] bij een actie en < > bij een keuze. Wordt dat ding onbegrijpelijk of te groot voor je papiertje -> maak/gebruik functies.

[Verwijderd]

Vergeet dat hele gedoe met invarianten.

Dat zou ik wel willen, maar binnenkort (in februari) wil ik het HP1 (AMBI) examen doen en dat gaat met name over het ontwerpen van algoritmen (met invarianten en bijbhorende afleidingen). Soms vind ik het wel wat ver gaan, een hele pagina met afleidingen en bewijzen voor een simpel while loopje met 3 regels code. (die je normaal gesproken in een paar minuten op je scherm hebt staan)
Maar ik heb wel het idee dat het me wel een bepaald soort inzicht geeft. Ook komen dingen naar voren waar ik hiervoor nog niet zoveel ervaring mee had. Bijvoorbeeld het vereenvoudigen van boolse expressies.
De volgend module van het AMBI diploma (HP2 object georienteerd programmeren) lijkt me veel meer praktischer toepasbaar en daarom ook veel leuker

[RayNbow]

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Informatici maken het moeilijker dan het is en ze bedenken dingen (zoals fundamentele informatica, UML) waar je niets aan hebt. Mensen die informatica doen weten vaak niets van programmeren en kunnen het dus ook niet.

Vertel mij dan eens wat er verkeerd is aan fundamentele informatica?

Over UML, dat is misschien overbodig voor hele kleine projectjes voor jezelf, maar voor hele grote systemen is het misschien wel eens handig om iets op papier te hebben. Als je dat in UML doet, dan doe je het in een taal die je collega's ook begrijpen.

Als je echt wil leren programmeren, dan kan je het beste beginnen met simpele digitale elektronica, zoals een adder, mux.

Deze dingen worden behandeld bij een Informatica-opleiding.

[kenneth]

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Als je echt wil leren programmeren, dan kan je het beste beginnen met simpele digitale elektronica, zoals een adder, mux. Probeer daarna te begrijpen hoe een ALU werkt, hoe een CPU werkt, wat assembly doet en hoe je daar een programma mee maakt en als laatste hoe hogere talen (C, Java) je het makkelijker maken om je algoritme om te zetten tot een werkend programma en je daarmee een hoop werk besparen.

Een bottom-up benadering waar 95% van de dingen die je beschrijft leuk om te weten maar verder nutteloos zijn, noem jij 'een hoop werk besparen' ??

Een programma maak je door het algoritme eerst duidelijk (in woorden) op te schrijven.

Wat denk je dat UML is? Niets meer dan afspraken over notatie.

Je wijst bewezen technieken en hulpmiddelen naar de prullenmand, je wil terug naar het stenen tijdperk om dingen te leren die irrelevant zijn voor het gros van de problemen die een informaticus moet oplossen. NOFI, maar dit getuigt m.i. niet echt van vakkennis.

[Daos]

RayNbow schreef op zaterdag 26 november 2005 @ 17:21:
[...]
Vertel mij dan eens wat er verkeerd is aan fundamentele informatica?

Je wordt doodgegooit met allemaal vreemde termen die je uit je hoofd moet leren. Bij discrete wiskunde kan je je nog iets voorstellen (graaf, boom etc), maar fundamentele informatica vind ik gewoon overbodig.

Over UML, dat is misschien overbodig voor hele kleine projectjes voor jezelf, maar voor hele grote systemen is het misschien wel eens handig om iets op papier te hebben. Als je dat in UML doet, dan doe je het in een taal die je collega's ook begrijpen.

Van UML vind ik alleen in dat opzicht het klassendiagram makkelijk (met alleen publieke velden en methoden)

[...]
Deze dingen worden behandeld bij een Informatica-opleiding.

Dat is meestal maar een vakje in het eerste jaar. Het is zo weinig dat je de link niet kan leggen met het programmeren. Veel informatici weten niet wat registers zijn (meestal denken ze dat dat die 512 kB cache is), weten niet hoe de stack werkt (en waarom je een stack gerelateerde fout krijgt als je recursie niet stopt) en pointers (en call by reference) schijnen ze helemaal niet te begrijpen terwijl dat niet zo veel voorstelt.
In de informatica opleidingen ligt meestal de nadruk op het wiskundige deel omdat ze afgesplitst zijn van de wiskundeopleidingen. Wat bij informatica behandeld wordt is eigenlijk alleen maar een beetje discrete wiskunde en logica. Dit maken ze extra onduidelijk zodat het nog iets lijkt voor te stellen. Informatica zit ergens tussen de Wiskunde en Elektrotechniek opleidingen, maar mist van allebei een hele hoop. Je hebt er dus niet zo veel aan.

[edit]

kenneth schreef op zaterdag 26 november 2005 @ 19:10:
[...]
Een bottom-up benadering waar 95% van de dingen die je beschrijft leuk om te weten maar verder nutteloos zijn, noem jij 'een hoop werk besparen' ??

Het zorgt ervoor dat je weet waarmee je bezig bent.

Wat denk je dat UML is? Niets meer dan afspraken over notatie.

Je wijst bewezen technieken en hulpmiddelen naar de prullenmand, je wil terug naar het stenen tijdperk om dingen te leren die irrelevant zijn voor het gros van de problemen die een informaticus moet oplossen. NOFI, maar dit getuigt m.i. niet echt van vakkennis.

Als je een programma maakt, dan moet je niet gelijk achter de PC gaan zitten en beginnen te typen. Het beste kan je eerst op papier iets uitwerken. Elk probleem is anders en heeft ook een andere plaatje/uitwerking nodig. Bij UML is alles op een hoop gegooit. Je kan alles met UML, maar het is zo log dat je speciale programma's nodig hebt om het te maken. Je zit dan alsnog met je snuffert voor je monitor en je weet al snel niet meer waar je mee bezig bent.

Het is een hetzelfde probleem als bij de huidige generatie middelbare scholieren. Als ze een wiskunde probleem zien pakken ze gelijk hun rekenmachine en gaan wat intoetsen. Bij simpele dingen gaat dit goed, maar als het iets ingewikkelder wordt dan kunnen ze niets meer.

[edit2]
Niet alles vind ik slecht aan informatica. Normaliseren van databases is heel belangrijk.
Model-View-Controller (MVC) werkt ook wel goed.

[ Voor 34% gewijzigd door Daos op 26-11-2005 19:52 ]

[tekno]

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Het programmeren en alles wat er bij hoort komt uit de elektrotechniek. Ook logica zie je vooral in de elektrotechniek bij het maken van digitale elektronica. Als je echt wil leren programmeren, dan kan je het beste beginnen met simpele digitale elektronica, zoals een adder, mux. Probeer daarna te begrijpen hoe een ALU werkt, hoe een CPU werkt, wat assembly doet en hoe je daar een programma mee maakt en als laatste hoe hogere talen (C, Java) je het makkelijker maken om je algoritme om te zetten tot een werkend programma en je daarmee een hoop werk besparen.

Heb je ook een bron of een onderbouwing voor het argument dat programmeren en alles wat erbij hoort uit de elektrotechniek komt? Zou ik wel interessant vinden om te lezen. Ken namelijk de voorgeschiedenis niet zo goed.

Verder heb ik op mijn opleiding informatica toch echt meteen in het begin een vak schakeltechniek naast een vak logica en verzamelingenleer moeten volgen. Dus een adder en mux heb ik wel gezien, maar ik denk niet dat het begrijpen van een mux nou echt van fundamenteel belang is om te programmeren.

Ook alle andere zaken die je noemt zijn aan bod geweest (ALU, CPU, assembly).
Maar waarom zou je eerst iemand leren om in assembly iets te programmeren?
Ik heb zelf ook nog three phase handshaking moeten implementeren in assembly, maar kan nou niet echt zeggen dat ik daar nou voordeel bij heb gehad bij gewone opdrachten.

En ik vraag me zeer af of je er zo veel tijd mee bespaart, ik weet niet of je daar enige vorm van onderbouwing of argumentatie bij kunt geven. Volgens mij zijn abstractie en separation of concerns veel nuttigere methoden om tijd te besparen.

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Een programma maak je door het algoritme eerst duidelijk (in woorden) op te schrijven.

En als je nu geen algoritme hebt? Wat doe je dan?
Daar kan een korte formele afleiding in sommige gevallen zeer veel tijd schelen.

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Een algoritme ontwerp je niet: je schijft gewoon een verhaaltje met dingen die moeten gebeuren (zoiets als het script bij een film). Denk daarbij niet in getalletjes, maar zoveel mogelijk in objecten.

Wat doe je dan als je een verhaaltje schrijft, subproblemen onderscheid, abstractie toepast en met behulp van seperation of concerns het probleem uiteindelijk oplost? Ik dacht dat zo ongeveer wel ontwerpen of afleiden is, alleen dan semi-formeel/informeel in plaats van formeel.

[Confusion]

Daos schreef op zaterdag 26 november 2005 @ 16:06:
Als je echt wil leren programmeren, dan kan je het beste beginnen met simpele digitale elektronica, zoals een adder, mux. Probeer daarna te begrijpen hoe een ALU werkt, hoe een CPU werkt, wat assembly doet en hoe je daar een programma mee maakt en als laatste hoe hogere talen (C, Java) je het makkelijker maken om je algoritme om te zetten tot een werkend programma en je daarmee een hoop werk besparen.

Wat een onzin. Dat soort dingen fundamentele dingen weten helpt op geen enkele manier om te bepalen hoe je de gemiddelde bedrijfsapplicatie moet bouwen. Er zijn anderen mensen die die dingen weten en dingen doen als biossen schrijven, operating systems schrijven, drivers schrijven, C libraries schrijven en meer van zulks. Je kan een held in iedere hogere programmeertaal zijn zonder ooit van je leven C code gezien te hebben.

Als jij een electrotechneut bent, laat ik je dan als natuurkundige verzekeren dat jij helemaal niet begrijpt hoe een transistor werkt en dat je dus kansloos bent om ooit goed te kunnen programmeren.

[RayNbow]

Daos schreef op zaterdag 26 november 2005 @ 19:32:
[...]

Je wordt doodgegooit met allemaal vreemde termen die je uit je hoofd moet leren. Bij discrete wiskunde kan je je nog iets voorstellen (graaf, boom etc), maar fundamentele informatica vind ik gewoon overbodig.

Termen zoals?

Fundamentele informatica is best belangrijk. Je leert dingen als het halting problem, emptiness problem, equivalence problem, etc. Je leert dus dat bepaalde dingen niet mogelijk zijn.

[...]
Van UML vind ik alleen in dat opzicht het klassendiagram makkelijk (met alleen publieke velden en methoden)

Een sequence diagram is ook handig om meer inzicht te krijgen tussen de interactie tussen objecten. Verder geeft bijv. een Use Case diagram inzicht welke gebruikers het systeem gebruiken en wat ze er mee kunnen.

[...]

Dat is meestal maar een vakje in het eerste jaar. Het is zo weinig dat je de link niet kan leggen met het programmeren. Veel informatici weten niet wat registers zijn (meestal denken ze dat dat die 512 kB cache is), weten niet hoe de stack werkt (en waarom je een stack gerelateerde fout krijgt als je recursie niet stopt) en pointers (en call by reference) schijnen ze helemaal niet te begrijpen terwijl dat niet zo veel voorstelt.

In het eerste jaar van de Technische Informatica opleiding van de TU in Delft zit er aan zo'n "vakje" een practicum aan vast, dat twee kwartalen duurt, waarin je een emulator in assembly moet schrijven. 't Lijkt me genoeg om een link te kunnen leggen met programmeren.

In de informatica opleidingen ligt meestal de nadruk op het wiskundige deel omdat ze afgesplitst zijn van de wiskundeopleidingen. Wat bij informatica behandeld wordt is eigenlijk alleen maar een beetje discrete wiskunde en logica. Dit maken ze extra onduidelijk zodat het nog iets lijkt voor te stellen. Informatica zit ergens tussen de Wiskunde en Elektrotechniek opleidingen, maar mist van allebei een hele hoop. Je hebt er dus niet zo veel aan.

Mis je niet bij Wiskunde en Elektrotechniek vakken als Fundamentele Informatica, Software Engineering, Programmeertalen en Semantiek, Computer Systemen, Computer Netwerken, Kennissystemen, Databases, etc, etc? Dus je hebt niet zo veel aan die twee opleidingen?

[Daos]

tekno schreef op zaterdag 26 november 2005 @ 19:48:
En ik vraag me zeer af of je er zo veel tijd mee bespaart, ik weet niet of je daar enige vorm van onderbouwing of argumentatie bij kunt geven. Volgens mij zijn abstractie en separation of concerns veel nuttigere methoden om tijd te besparen.

Dat tijd besparen ging over de hogere talen. Die besparen je veel tijd ten opzichte van assembly.

Een hogere taal gebruiken (bv OO-taal met inheritance) is een vorm van abstractie. "separation of concerns" is gewoon in mooie woorden dat je een functie gaat gebruiken als het te moeilijk wordt of als je een deel vaker nodig hebt.

Beide dingen heb ik genoemd.

Weet je zelf nog wel waarover je praat?

Confusion schreef op zaterdag 26 november 2005 @ 20:07:
[...]

Wat een onzin. Dat soort dingen fundamentele dingen weten helpt op geen enkele manier om te bepalen hoe je de gemiddelde bedrijfsapplicatie moet bouwen. Er zijn anderen mensen die die dingen weten en dingen doen als biossen schrijven, operating systems schrijven, drivers schrijven, C libraries schrijven en meer van zulks. Je kan een held in iedere hogere programmeertaal zijn zonder ooit van je leven C code gezien te hebben.

Ik werk vooral in C. Voor mij is dat programmeren. Ik zie veel informatici die niets van C begrijpen. Is het dan vreemd dat ik vind dat die mensen niet kunnen programmeren?

Als jij een electrotechneut bent, laat ik je dan als natuurkundige verzekeren dat jij helemaal niet begrijpt hoe een transistor werkt en dat je dus kansloos bent om ooit goed te kunnen programmeren.

Dat heb ik al in het eerste jaar gehad (dat vaste stof gebeuren kwam iets later). Ook hebben we in het eerste jaar gehad hoe je van transistor een logische poort maakt.

Maar inderdaad bij digitale elektronica heb je alleen logische poorten nodig. Bij hoge talen zal je niet zoveel van digitale elektronica nodig hebben.

Ik zal niets meer over informatica opleidingen zeggen. Het is een beetje offtopic.

[ Voor 3% gewijzigd door Daos op 27-11-2005 11:06 ]

[Verwijderd]

Daos schreef op zaterdag 26 november 2005 @ 20:52:
[...]
Ik werk vooral in C. Voor mij is dat programmeren. Ik zie veel informatici die niets van C begrijpen. Is het dan vreemd dat ik vind dat die mensen niet kunnen programmeren?

[...]

Dus als je niets van C begrijpt kun je niet programmeren? Vind je niet dat je nu wel HEEL erg kort door de bocht gaat?

Ik ben voornamelijk bezig in Java, en ik geef toe dat ik veel moeite heb om C++ te leren. Maar dat wil nog niet zeggen dat ik, omdat ik geen C ken een slechte programmeur ben. (Niet dat ik zeg dat ik nou zo goed ben, maar volgens mij heeft C daar weinig mee te maken)

[H!GHGuY]

mss mag ik hier even op antwoorden zoals mijn docent me overlaatst antwoord gaf:

de les ging op dat moment over pre/post-condities van functies, en ik vroeg of dit moment in de design-fase niet het geschikte moment was om ook de invariant op te stellen.

hij antwoordde:
een functie verandert altijd gegevens, dus als je weet wat verandert (dmv pre/post-conditie) weet je dat al de rest niet verandert. behoorlijk nutteloos dus om een invariant op te stellen, tenzij expliciet nodig.

[Verwijderd]

Kan iemand nog antwoord geven op mijn vraag (zie een aantal posts terug)

[Daos]

Verwijderd schreef op zaterdag 26 november 2005 @ 13:59:
Ik ben weer wat aan het oefenen met het ontwerpen van algoritmen.
Als ik een invariant heb waar meerdere code regels uit afgeleid worden, hoe bepaal ik dan de volgorde van die opdrachtregels?

Een voorbeeldje:
ik lees een getal in van 2 cijfers, die wil ik dmv een char array opslaan in een int variable:
Specificatie:

code:

val char arr[0...2], N
var int r
pre: N>=0
post: r=(Si : 0<=i<N : (10/(10**i))*a[i])
//het doet er niet toe hoe de getallen worden ingelezen

invarianten 
P0: r=(Si : 0<=i<k : (10/(10**i))*a[i])
P1: 0<=k<=N

initialisatie
k=0, r=0

afleiding opdrachten
k=k+1

(Si : 0<=i<k : (10/(10**i))*a[i])
//invullen
(Si : 0<=i<k+1 : (10/(10**i))*a[i])
//splitsen k=i
(Si : 0<=i<k : (10/(10**i))*a[i])+(10/(10**k))*a[k]
//P0
iDay+(10/s)*a[k]
//introductie s
Q0: s=10**k
//invullen
10**(k+1)
s*10

Dus we hebben de volgende opdrachten (Java)

code:

iDay+(10/s)*a[k];
s*=10;
k++;

Het gaat me vooral om de opdrachten 1 en 2 (k++ moet als laatste komen). M'n gevoel zegt dat s*=10; na iDay+(10/s)*a[k]; moet komen. Maar zijn er ook nog regeltjes (en manieren waarop je de volgorde kan afleiden) te geven hiervoor? Bijv. voor een situatie waarin de volgorde wat minder duidelijk is?

Regeltjes

Wat ik er van begrijp is dat de s in iDay+(10/s)*a[k]; altijd 10**k moet zijn. Doe je het updaten ervoor dan moet je initiele waarde een factor 10 lager zijn vergeleken met updaten erna. Ik zou erna doen want bij ervoor krijg je volgens mij een kommagetal (10**-1 = 0.1) bij je initiele waarde van s.

[kenneth]

HIGHGuY schreef op zondag 27 november 2005 @ 13:15:
hij antwoordde:
een functie verandert altijd gegevens, dus als je weet wat verandert (dmv pre/post-conditie) weet je dat al de rest niet verandert. behoorlijk nutteloos dus om een invariant op te stellen, tenzij expliciet nodig.

Bij een cursus is het altijd nodig, aangezien je het ooit moet leren

Het kan trouwens handig zijn om correctheid van te bewijzen.

[Martin Sturm]

Het kan trouwens handig zijn om correctheid van te bewijzen.

Handig? Als je correctheid wil bewijzen van een loop heb je voor zover ik weet altijd wel een invariant nodig. De docent die HIGHGuY heeft, is dan ook zeker niet iemand die je leert hoe je algoritmen ontwerpt die 100% correct zijn bewezen (en hij is ook geen 'student' van Dijkstra geweest ).

[kenneth]

Dijkstra is God. Nee, echt.

GOTO Heaven // By the shortest path

[zeroxcool]

GOTO, Dijkstra draait zich nog om in z'n graf, tssss... En ja, het Dijkstra-algoritme heerscht .

[ Voor 22% gewijzigd door zeroxcool op 22-12-2005 10:49 ]

[kenneth]

Da's juist de grap man
Dijkstra is geweldig, ik haal hem hier op kantoor zeker nog wel één keer per week aan. Hij was behoorlijk star, maarja, dat is een academicus eigen he.

Testing cannot prove the absence of bugs, only their existence.

[Robtimus]

Ah, Dijkstra. Zijn handschrift is zo bekend dat er een font van gemaakt is.

Wat dan nog erger is is dat een aantal van zijn volgelingen (Wim Feijen, Rob Hoogerwoord en wijlen Netty van Gasteren) alledrie exact hetzelfde handschrift hadden overgenomen.

[H!GHGuY]

Martin Sturm schreef op maandag 28 november 2005 @ 15:17:
[...]

Handig? Als je correctheid wil bewijzen van een loop heb je voor zover ik weet altijd wel een invariant nodig. De docent die HIGHGuY heeft, is dan ook zeker niet iemand die je leert hoe je algoritmen ontwerpt die 100% correct zijn bewezen (en hij is ook geen 'student' van Dijkstra geweest ).

tjah ik zal hem allesbehalve ophemelen, hij's ook niet mijn beste vriend namelijk

maar wij krijgen nu een opgave om een stuk software voor beeldherkenning visueel te controleren en mathematisch te bewijzen. En dit allemaal met enkel pre-/postconditie en tussencondities in de code.
Nergens komt een invariant aan te pas.

Voor zij die meer willen weten over de docent: hij heeft reeds wat boeken geschreven over algoritmes, systeemanalyse etc. Jan Cnops is z'n naam, je kunt zeker wel wat vinden in de boekhandel of op internet.

[kenneth]

Niet gehinderd door enige kennis, maar is een invariant niet een (speciale) tussenconditie?

[tekno]

pre- en postcondities en invarianten zijn allemaal asserties, net zoals de 'normale' asserties.
Een invariant is een assertie die voor en na elke slag van een herhaling geldt.

[prototype]

Niet geheel waar. En invariant kun je onderverdelen in 2 soorten in het OO paradigm, namelijk klasseninvarianten en lusinvarianten. Klasseninvarianten zijn invarianten die over de GEHELE klassen geldig moeten zijn en blijven na constructor invocation. Het nut van invarianten is dat ze correctheid bewijzen.
Zo is een lusinvariant een invariant die de correctheid en werking van een lus aantoont. De invariant moet op de volgende plekken gelden:

Java:

//(1)invariant moet hier geldig zijn
while(guard)
{
    //(2)ook hier moet de invariant geldig zijn
    statement();
    statement();
    //(3)ook hier moet de invariant geldig zijn
}
//(4)ook hier moet de invariant geldig zijn

Dit is de 'textbook' beschrijving ervan. Het is daarbij handig om even stil te staan met wat het nou precies impliceert. Zo kan voor een willekeurige iteratie k, de invariant bij (3) een uitspraak gemaakt worden over alle voorgaande iteraties, namelijk dat ze bij deze allen de guard hebben gerespecteerd. Het is alleen onmogelijk om nu te zeggen of dit bij iteratie k nog steeds het geval is, aangezien de bovenstaande statements eventueel de guard evaluatie niet meer respecteren.
Pre- en postcondities horen bij het Design by Contract (DBC) principe, waarbij dmv asserties de correctheid van methoden wordt aangetoond. Het is een principe die zich berust op het client en server principe, waarin er een 'contract' opgesteld wordt tussen client en server. De client dient hierbij zijn deel van het contract na te komen (de precondities) om ervoor te zorgen dat de server op zijn beurt zijn deel van het contract nakomt (de postconditie). Met een beetje logisch nadenken zul je nu toch een verband moeten zien tussen pre- en postcondities en invarianten, daar ze respectievelijk iets afdwingen, iets verzekeren en een uitspraak doen over iets dat onveranderlijk is en blijft.

[Verwijderd]

Verwijderd schreef op donderdag 28 april 2005 @ 15:20:
Ik gebruik een ander boek van A. Kaldewaij, het ontwerpen van algoritmen. Het is niet meer verkrijgbaar. Maar AMBI studenten die de HP1 module willen doen kunnen bij Exin kosteloos een kopie krijgen.

whosvegas ik ga ook beginnen aan de module HP1. Ik las jou berichtje over dit boek wat gratis te krijgen is bij Exin, maar toen ik exin erover mailde zeiden ze mij dat het niet gratis is maar te koop in hun boekshop. Had jij hem wel gratis gekregen ?

Groeten Alex

[Verwijderd]

Verwijderd schreef op donderdag 22 december 2005 @ 02:39:
[...]


whosvegas ik ga ook beginnen aan de module HP1. Ik las jou berichtje over dit boek wat gratis te krijgen is bij Exin, maar toen ik exin erover mailde zeiden ze mij dat het niet gratis is maar te koop in hun boekshop. Had jij hem wel gratis gekregen ?

Groeten Alex

Deel 3 van de serie is te koop in de Exin winkel, deel 3 wordt in de HP 2 module (objectgeorienteerd programmeren) gebruikt. Deel 2 wordt in HP1 gebruikt en ik ben het nog niet tegen gekomen.
15 februari 2006 ga ik examen doen!
Ik vind het een pittige module, vooral door de wiskunde die er in voor komt.

Hoe zit het met je programmeer en wiskunde voorkennis?
Succes!

[Verwijderd]

Deel 3 van de serie is te koop in de Exin winkel, deel 3 wordt in de HP 2 module (objectgeorienteerd programmeren) gebruikt. Deel 2 wordt in HP1 gebruikt en ik ben het nog niet tegen gekomen.
15 februari 2006 ga ik examen doen!
Ik vind het een pittige module, vooral door de wiskunde die er in voor komt.

Hoe zit het met je programmeer en wiskunde voorkennis?
Succes!

Hoi bedankt voor de uitleg alleen is het me nog niet duidelijk geworden of jij nu wel van Exin een kopie gratis hebt gekregen van Deel 2.
Ik ga ook 15 feb 2006 op examen!
Ik weet nog niet of ik het pittig vind, ben pas net begonnen en ben ook nog literatuur aan het verzamelen. Met het wiskundige deel ben ik dus nog niet begonnen dat. Heb wel gekeken naar wat je moet kennen en een beetje naar de posts hier maar snap er nog niet veel van beginrelaties, eindrelaties (pre-en postcondities) en invarianten maar dat komt wel.
Ik programmeer al jaren web applicaties, maar heb dat en de andere wiskundige begrippen die je voor HP.1 moet leren nog nooit nodig gehad. Zoiezo nooit veel wiskunde nodig gehad dan standaard dingen optellen delen etc percentage uitrekenen modulo enzo.
Maar goed dat wil niet zeggen dat ik nooit meer wiskunde nodig ga hebben. Er wordt altijd gezegd dat een programmeur goed in wiskunde moet zijn. Dus lijkt me niet verkeerd mijn wiskunde kennis te vergroten. JAVA was nieuw voor mij maar de syntax is net als C++, PHP, C# of javaScript wat ik al wel ken en de object orientatie is ook hetzelfde als andere talen.. De syntax is me dus al eigen. Moet alleen nog zorgen dat ik ook alle specifieke JAVA dingen ken. Ook moet ik nog de benamingen binnen het programmeren in het nederlands leren bijv: toekenningsopdracht ik ken die benamingen allemaal alleen in het engels en het liefst had ik dat zo gehouden mja wat moet dat moet. Kwestie van uit je hoofd leren.
Of het een pittige module is weet ik dus nog niet echt. Ik heb er inprincipe wel zin in want het is wel een uitdaging, maar wil natuurlijk wel in 1x slagen gezien de kosten. Met een goede inzet moet het wel goed komen toch ? Gewoon doorgaan tot je het snapt en kent.

[ Voor 3% gewijzigd door Verwijderd op 23-12-2005 18:07 ]

[Verwijderd]

whosvegas heb je interesse om per mail of MSN wat info over de stof die we moeten kennen uit te wisselen ? Ik ben bijvoorbeeld een uittreksel aan het maken aan de hand van de examen eisen daar zul je ook wat aan hebben. En heb ook zo wat vragen, 2 weten meer dan 1.
Mijn email adres is <mijn naam op het forum>@gmail.com (zo krijg ik geen spam)

[Verwijderd]

het me nog niet duidelijk geworden of jij nu wel van Exin een kopie gratis hebt gekregen van Deel 2.

Ik heb wel een kopie van deel 2 gekregen van Exin

Ik ga ook 15 feb 2006 op examen!
Ik weet nog niet of ik het pittig vind, ben pas net begonnen en ben ook nog literatuur aan het verzamelen. Met het wiskundige deel ben ik dus nog niet begonnen dat. Heb wel gekeken naar wat je moet kennen en een beetje naar de posts hier maar snap er nog niet veel van beginrelaties, eindrelaties (pre-en postcondities) en invarianten maar dat komt wel.

Als ik jou was, zou ik echt meer tijd uittrekken. Zoals ik al zei, de stof heeft een sterk wiskundig karakter. Eerst zul je dingen moet begrijpen als: kwantor, herschrijven van logische expressies, domein, distributiviteit enz. Als je nu nog niet weet wat een invariant is lijkt het me niet verstandig om over 2 maanden al examen te gaan doen.

Ik programmeer al jaren web applicaties, maar heb dat en de andere wiskundige begrippen die je voor HP.1 moet leren nog nooit nodig gehad. Zoiezo nooit veel wiskunde nodig gehad dan standaard dingen optellen delen etc percentage uitrekenen modulo enzo.

Ik ook niet daarom heeft het ook meer als een jaar geduurd voordat ik het idee had, dat ik me kon opgeven voor het examen.

Maar goed dat wil niet zeggen dat ik nooit meer wiskunde nodig ga hebben. Er wordt altijd gezegd dat een programmeur goed in wiskunde moet zijn. Dus lijkt me niet verkeerd mijn wiskunde kennis te vergroten.

Deze manier van programmeren wordt in de paktijk niet gebruikt (of in hele uitzonderlijke situaties). M'n baas ziet me al aankomen, met een dik pak aan afleidingen, voor een klein programma van een 100 regels. Eigenlijk vind ik het een beetje geneuzel. Maar deze module heeft wel m'n inzicht vergroot.

maar wil natuurlijk wel in 1x slagen gezien de kosten. Met een goede inzet moet het wel goed komen toch ? Gewoon doorgaan tot je het snapt en kent.

Dan zou ik er wel wat meer tijd voor uittrekken

whosvegas heb je interesse om per mail of MSN wat info over de stof die we moeten kennen uit te wisselen ?

Eerlijk gezegd zie ik dat niet zo zitten. Omdat ik zelf druk ben met m'n voorbereidingen en ik vind dat je er meer tijd voor moet uittrekken. Maar als je vragen hebt kun je die gewoon op Tweakers stellen (heb ik ook veel aan gehad). Als je intresse hebt kan ik je m'n aantekeningen opsturen

[Verwijderd]

Thanks voor de info!
,,meer tijd nja zou kunnen ik heb iig begrepen dat ik het geplande examen gewoon nog kan intrekken. Als ik meer tijd blijk nodig te hebben. Ik ben vandaag begonnen met het wiskunde gedeelte dus ik kan er nog niks van zeggen binnenkort zal ik beter zicht hebben op de tijd die het me gaat kosten. Ben benieuwt!

Jammer dat je niet op MSN wilt overleggen. Ik wou je niet gaan lastig vallen hoor met vragen over de wiskundige begrippen of andere dingen die ik elders zou kunnen vragen. Alleen wat specifieke HP1 dingen overleggen welke niet echt op dit forum thuis horen. Maar goed ik heb er begrip voor, je hebt het druk.
Maar 1 ding zou ik toch nog wel willen vragen.. namelijk wat te doen met die HP1LIB... hoe zorg jij dat je daar 1 en ander van weet ?

[Verwijderd]

Verwijderd schreef op dinsdag 03 januari 2006 @ 20:07:
Thanks voor de info!
,,meer tijd nja zou kunnen ik heb iig begrepen dat ik het geplande examen gewoon nog kan intrekken. Als ik meer tijd blijk nodig te hebben. Ik ben vandaag begonnen met het wiskunde gedeelte dus ik kan er nog niks van zeggen binnenkort zal ik beter zicht hebben op de tijd die het me gaat kosten. Ben benieuwt!

Klopt, tot 1 week van te voren kun je je examen in trekken
In ieder geval succes!

Jammer dat je niet op MSN wilt overleggen. Ik wou je niet gaan lastig vallen hoor met vragen over de wiskundige begrippen of andere dingen die ik elders zou kunnen vragen. Alleen wat specifieke HP1 dingen overleggen welke niet echt op dit forum thuis horen. Maar goed ik heb er begrip voor, je hebt het druk.
Maar 1 ding zou ik toch nog wel willen vragen.. namelijk wat te doen met die HP1LIB... hoe zorg jij dat je daar 1 en ander van weet ?

HP1Lib kun je het beste leren door gewoon een compiler te installeren MS J# kun je gratis downloaden, of je kun de Java compiler van Sun gebruiken. En dan gewoon kijken hoe het allemaal werkt. En ook kun je HP1lib in opgaven in het boek van Kaldewaij gebruiken.
Het is niet dat ik je niet wil helpen, maar voor mezelf heeft het weinig nut, omdat je nog maar net begint.
Mocht je na 15-02 toch nog aan het leren zijn dan wil ik je wel helpen, mail me daarvoor op [e-mail]
Zal ik je mijn aantekeningen nog mailen?

[Verwijderd]

Voor het examen moet je voor een ontwikkeld programma ook de toestand per regel kunnen geven, dit lukt me wel bij een eenvoudig programma, maar zodra het iets moeilijker wordt lukt het niet meer

Voorbeeldje
Schrijf een programma dat machtverheffen uitvoert zonder vermenigvuldigen (de hele afleiding laat ik achterwege):

code:

invarianten
P0: r=k**3
P1: 0<=k<=N
Q0: s=3k**2+3k+1
Q1: t=6k+6

int k=0, r=0, s=1, t=6;
while (k!=N)
{   //r=k**3 && k<N
    r+=s;
    s+=t;
    t+=6;
    //r=(k+1)**3 && k+1<=N
    k++;
    //r=k**3 && k<N
}

Hoe kan ik de toestanden van de 3 regels aangeven?

[Daos]

code:

invarianten
P0: r=k**3
P1: 0<=k<=N
Q0: s=3k**2+3k+1
Q1: t=6k+6

int k=0, r=0, s=1, t=6;
while (k!=N)
{   //r=k**3     && k<N  && s=3k**2+3k+1         && t=6k+6
    r+=s;
    //r=(k+1)**3 && k<N  && s=3k**2+3k+1         && t=6k+6
    s+=t;
    //r=(k+1)**3 && k<N  && s=3(k+1)**2+3(k+1)+1 && t=6k+6
    t+=6;
    //r=(k+1)**3 && k<N  && s=3(k+1)**2+3(k+1)+1 && t=6(k+1)+6
    k++;
    //r=k**3     && k<=N && s=3k**2+3k+1         && t=6k+6
}

Had je dat zelf niet kunnen bedenken?

[ Voor 56% gewijzigd door Daos op 07-01-2006 21:46 ]

[Verwijderd]

Daos schreef op zaterdag 07 januari 2006 @ 21:17:

code:

invarianten
P0: r=k**3
P1: 0<=k<=N
Q0: s=3k**2+3k+1
Q1: t=6k+6

int k=0, r=0, s=1, t=6;
while (k!=N)
{   //r=k**3     && k<N  && s=3k**2+3k+1         && t=6k+6
    r+=s;
    //r=(k+1)**3 && k<N  && s=3k**2+3k+1         && t=6k+6
    s+=t;
    //r=(k+1)**3 && k<N  && s=3(k+1)**2+3(k+1)+1 && t=6k+6
    t+=6;
    //r=(k+1)**3 && k<N  && s=3(k+1)**2+3(k+1)+1 && t=6(k+1)+6
    k++;
    //r=k**3     && k<=N && s=3k**2+3k+1         && t=6k+6
}

Had je dat zelf niet kunnen bedenken?

Misschien heb je gelijk
Maar op dat moment zag ik het even niet

[Daos]

Verwijderd schreef op zondag 08 januari 2006 @ 12:36:
[...]

Misschien heb je gelijk
Maar op dat moment zag ik het even niet

Als het goed is ben je dat tegengekomen bij je afleiding:
Je hebt r(k) = k³. Uit r(k+1) = r(k) + s(k) volgt s(k) = 3k² + 3k + 1.
Je hebt s(k) = 3k² + 3k + 1. Uit s(k+1) = s(k) + t(k) volgt t(k) = 6k + 6.
Je hebt t(k) = 6k + 6. Uit t(k+1) = t(k) + u(k) volgt u(k) = 6. Omdat u(k) gewoon constant is gebruik je gelijk die constante in plaats van u(k). Het wordt dus t(k+1) = t(k) + 6.
.

code:

int k=0, r=0, s=1, t=6;

k begint met 0, dus je initiele waarden zijn r(0), s(0) en t(0) en die stop je in variabelen r, s, en t.

code:

while (k!=N)
{

Bij het begin van de lus heb je r(k), s(k) en t(k) in variabelen r, s, en t. k is kleiner dan N.

code:

  r+=s;

Met bovenstaand statement tel je s(k) bij r(k) en het resultaat stop je in de variabele r. In r zit nu (na het uitvoeren van het statement) dus r(k) + s(k) en dat is hetzelfde als r(k+1). Met de variabelen s, t en k is niets gebeurd.

code:

  s+=t;

Met bovenstaand statement tel je t(k) bij s(k) en het resultaat stop je in de variabele s. In s zit nu dus s(k) + t(k) en dat is hetzelfde als s(k+1). Met de variabelen r, t en k is niets gebeurd.

code:

  t+=6;

Met bovenstaand statement tel je 6 bij t(k) en het resultaat stop je in de variabele t. In t zit nu dus t(k) + 6 en dat is hetzelfde als t(k+1). Met de variabelen r, s en k is niets gebeurd.

code:

  k++;

Met bovenstaand statement tel je 1 bij de huidige/oude k en het resultaat (de nieuwe k) stop je in de variabele k (k_(nieuw) = k_oud + 1 <=> k_oud = k_(nieuw) - 1).
In de variabele r zit r(k_oud+1) en dat is hetzelfde als r(k_(nieuw)). Hetzelfde geldt voor s en t. Er geldt k_oud is kleiner dan N. Er geldt nu dus (k_(nieuw) - 1) is kleiner dan N. Omdat k en N gehele getallen zijn is dat hetzelfde als k_(nieuw) is kleiner dan of gelijk aan N.

code:

}

Je bent nu uit je loop en dus geldt k is gelijk aan N. In variabelen r, s en t zitten nu respectievelijk r(N), s(N) en t(N).

[Verwijderd]

[b]Daos schreef op zondag 08 januari 2006 @ 14:56:

Bedankt voor je uitleg
En ik begrijp het

[Verwijderd]

Nog een vraagje
Ik heb de volgende opgave:

code:

pre: N>=1
post: r=(Ni : 0<=i<N : x[i]=(MAXj : 0<=j<N x[j]))
//het aantal voorkomens van het maximum van x

Bij de opgave staat dat het een lineaire oplossig moet zijn (dus 1 loop). Als je de opgave voor het eerst ziet, denk je: ik moet het aantal voorkomens van het maximum van de hele array tellen. Maar dan ga je nadenken, dat kan helemaal niet! Als ik N (allebei) door k vervang dan wordt alleen het maximum 0<=i<k genomen.
Dus de vraagstelling is fout, of een dubbele loop moet toegestaan zijn.
Zit ik zo een beetje goed met m'n gedachte

[Daos]

Wat je vergeet is dat het maximum niet afhankelijk is van i.

Je kan gewoon 2 lusjes na elkaar gebruiken (1 voor maximum berekenen en 1 voor tellen). Constant aantal lineaire lusjes na elkaar is volgens mij nog steeds lineair.


Je kan ook alles in 1 lusje stoppen. Ik kan dat wiskundig niet zo goed omschrijven, maar het doet dit:
Je hebt max van 0<=i<k en aantal keer r dat max voorgekomen is.
Als x[k] < max dan doe je niets .
Als x[k] = max dan doe je r++.
Als x[k] > max dan doe je max = x[k] en r = 1.

x[k] is in het laatste geval groter dan de rest en wordt dus het nieuwe maximum. Dit maximum is nieuw, dus het aantal keer dat het voorkomt is 1.

[Verwijderd]

Bedankt, daar had ik zelf op moeten komen, dat als je r op 0 zet, bij een nieuw maximum dat het wel kan in een loopje.
Ik heb mijn afleiding nog eens bekeken en daar komt het helemaal niet naar voren dat rop 0 gezet moet worden. Maar goed, ik zal de afleiding over een tijdje nog eens bekijken, misschien zie ik het dan wel.

[Daos]

r moet op 1 als je alles in 1 lus stopt. Misschien kan je wel die afleiding maken als je eerst de afleiding maakt voor de oplossing met twee lussen na elkaar.

De uiteindelijke oplossingen zien er zo uit:
2 lusjes:

Java:

max = x[0];
k = 1;
while (k != N) {
  if (x[k] > max)
    max = x[k];

  k++;
}
// max=(MAXj : 0<=j<N x[j]))

r = 0;
k = 0;
while (k != N) {
  if (x[k] == max)
    r++;

  k++;
}
// r=(Ni : 0<=i<N : x[i]=max)
//  =(Ni : 0<=i<N : x[i]=(MAXj : 0<=j<N x[j]))

alles in een:

Java:

max = x[0];
r = 1;
k = 1;
while (k != N) {
  if (x[k] == max)
    r++;
  else if (x[k] > max) {
    max = x[k];
    r = 1;
  }

  k++;
}
// r=(Ni : 0<=i<N : x[i]=(MAXj : 0<=j<N x[j]))

Veel beginners doen de initiele waarden bij het berekenen van het maximum fout. Ze beginnen met k = 0 en max = 0. Dit gaat fout als er alleen negatieve waarden in x[] zitten (nergens staat dat dit niet zo is).
Je kan beginnen met k = 0 en max = -oneindig, maar handiger is het om te beginnen met k = 1 en max = x[0] (dit mag omdat x is [0,N) en de N>=1 (preconditie)).

[Verwijderd]

Daos schreef op woensdag 11 januari 2006 @ 11:28:
r moet op 1 als je alles in 1 lus stopt. Misschien kan je wel die afleiding maken als je eerst de afleiding maakt voor de oplossing met twee lussen na elkaar.

Zal eens proberen

Veel beginners doen de initiele waarden bij het berekenen van het maximum fout. Ze beginnen met k = 0 en max = 0. Dit gaat fout als er alleen negatieve waarden in x[] zitten (nergens staat dat dit niet zo is).
Je kan beginnen met k = 0 en max = -oneindig, maar handiger is het om te beginnen met k = 1 en max = x[0] (dit mag omdat x is [0,N) en de N>=1 (preconditie)).

Mijn oplossing:

code:

int r=1, s=x[0], k=1;
while (k!=N)
{   if (x[k]>s)
    {   s=x[k];
        r=0;
    }
    if (x[k]==s)
        r++;
    k++;
}

[ Voor 27% gewijzigd door Verwijderd op 12-01-2006 11:33 ]

[Verwijderd]

Over anderhalve week examen

Dus ik ben wat aan het oefenen met 2 dimensionale array's, stel ik heb een eindrelatie:

code:

(Si,j : 0<=i<x.length && 0<=j<x[i].length : x[i][j])

Ik wil dus alle array's bij elkaar optellen. Als je de normale afleiding doet ontstaat er een dubbele loop, nu is mijn vraag: kan het ook in een enkele loop?

[ Voor 7% gewijzigd door Verwijderd op 05-02-2006 12:40 ]

[Robtimus]

Voor sommige problemen waar je standaard een dubbele loop gebruikt kun je ook een enkele loop gebruiken - dit is de zogenaamde saddleback search. Hierbij begin je in 1 van 2 hoekpunten van je matrix (de andere 2 hoekpunten leiden tot een dubbele loop) en per slag schuift je focus of een rij op, of een kolom. Google maar eens.

Voor dit probleem is dit echter niet mogelijk - je moet nml elk element in je matrix nagaan om te zien wat zijn waarde is.

[Verwijderd]

IceManX schreef op zondag 05 februari 2006 @ 17:59:
Voor sommige problemen waar je standaard een dubbele loop gebruikt kun je ook een enkele loop gebruiken - dit is de zogenaamde saddleback search. Hierbij begin je in 1 van 2 hoekpunten van je matrix (de andere 2 hoekpunten leiden tot een dubbele loop) en per slag schuift je focus of een rij op, of een kolom. Google maar eens.

Voor dit probleem is dit echter niet mogelijk - je moet nml elk element in je matrix nagaan om te zien wat zijn waarde is.

Bedankt voor je antwoord. Had ik het toch goed

Het Saddleback (of slope search?) staat in een hoofdstuk dat ik niet hoef te kennen. Aangezien ik vlak voordat examen zit ga ik me er ook niet mee bezig houden. Na het examen (al ik het ga halen) ga ik ik me wel wat meer verdiepen in allerlei algoritmen en datastructuren (zals hashing, backtracking en graafalgoritmen). Volgens mij heb je daar in de praktijk best wel veel aan en zou eigenlijk iedere programmeur dat als basiskennis moeten hebben.

[Robtimus]

Verwijderd schreef op zondag 05 februari 2006 @ 19:17:
Het Saddleback (of slope search?)

Klopt. Ik was al blij zat dat ik de naam goed had na 6 jaar.

[Verwijderd]

IceManX schreef op zondag 05 februari 2006 @ 19:37:
[...]
Klopt. Ik was al blij zat dat ik de naam goed had na 6 jaar.

Morgen HP 1 examen, ben benieuwd