Tellen van munten (floats)

[Verwijderd]

Hallo,

Ik lees reeds geruime tijd dit forum en vandaag dus ook m'n eerste post. Ik ben begonnen met het leren van de C-programmeertaal en ben op een probleem gestoten. Ik wil een programma maken dat als input een bedrag krijgt en dan het minimum aantal munten geeft die er nodig zijn om dat bedrag te bereiken.Doordat de floats benaderende waarden zijn kloppen mijn berekeningen niet. Hoe pak ik dit aan?

C:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  
  float waarde_munt[] = {500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01, 0};
  int aantal_munt[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  int i = 0;
  float bedrag;
  
  
  
  printf("Gelieve een bedrag in te vullen: \n");
  scanf("%f", &bedrag);
  
  while (waarde_munt[i] > 0)
  {
        while ( bedrag - waarde_munt[i] >= 0)
        {
              bedrag = bedrag - waarde_munt[i];
              aantal_munt[i] = aantal_munt[i] + 1;
        }
        i++;
  }
  
  for (i=0; i < 15; i++)
  {
      printf("%d van %f\n", aantal_munt[i], waarde_munt[i]);
  }
  
  system("PAUSE");  
  return 0;
}

[ Voor 6% gewijzigd door Verwijderd op 13-04-2006 20:45 ]

[WVL_KsZeN]

simpel, geen floats maar ints gebruiken, evt long_int als dat nodig is..

[whoami]

Door decimals te gebruiken. (ik weet wel niet of dat een standaard type is in C )

WVL_KsZeN schreef op donderdag 13 april 2006 @ 20:47:
simpel, geen floats maar ints gebruiken, evt long_int als dat nodig is..

En hoe stel je dan 10.85 euro voor ?
Dan zou je in centen moeten gaan rekenen.

[ Voor 93% gewijzigd door whoami op 13-04-2006 20:48 ]

[Verwijderd]

Nergens een float gebruiken, en alle munten in centen bijhouden?
Verder hoef je alleen te delen en de rest (modulo) te gebruiken, dat scheelt je een lus en een subtractie. Je hebt dus de operators / en % nodig.

[WVL_KsZeN]

whoami schreef op donderdag 13 april 2006 @ 20:47:
Door decimals te gebruiken.


[...]

En hoe stel je dan 10.85 euro voor ?
Dan zou je in centen moeten gaan rekenen.

alles in centen!

[BasieP]

of doubles..
maar iig geen floats...

[whoami]

BasieP schreef op donderdag 13 april 2006 @ 20:51:
of doubles..
maar iig geen floats...

Een double is ook een float.

[ Voor 73% gewijzigd door whoami op 13-04-2006 20:53 ]

[BCC]

int! Is nog een stuk rapper ook dan floats.

[Zoijar]

Hehe, je denkt ik begin even met een NPC probleem op te lossen (niet dat het niet kan hoor, simpel zoek algoritme, is alleen traag)

[ Voor 35% gewijzigd door Zoijar op 13-04-2006 21:05 ]

[NMe]

BCC schreef op donderdag 13 april 2006 @ 20:55:
int! Is nog een stuk rapper ook dan floats.

En ook pas 3 keer geroepen in dit topic.

[Zoijar]

Met floats is het nog enigszins te doen, met ints is het npc (alleen kom je dan niet precies uit...)

[ Voor 25% gewijzigd door Zoijar op 13-04-2006 21:05 ]

[Verwijderd]

Wat is NPC?

Double is volgens mij ook een type dat een benaderende waarde bevat, alleen meer precies dan float, maar dat doet er hier niet toe.

Ik zou het inderdaad met ints kunnen doen, maar dan moet ik inderdaad in centen rekenen. Maar dan is m'n vraag. Hoe laat ik de gebruiker een decimaal ingeven en toch met ints rekenen?

[ Voor 16% gewijzigd door Verwijderd op 13-04-2006 21:17 ]

[WVL_KsZeN]

Verwijderd schreef op donderdag 13 april 2006 @ 21:15:
vraag?

heel simpel, de waarde vraag je bv in een float.

code:

bedragincenten = int(bedrag*100.0+0.5)

bedragincenten is een int, bedrag is een float (ik doe zelf altijd +0.5 vanwege afronding..). Als je niet +0.5 doet wordt bv 99,9999999 afgerond naar 99 ipv naar 100.

[ Voor 12% gewijzigd door WVL_KsZeN op 13-04-2006 21:36 ]

[Verwijderd]

NPC is een bepaalde complexiteits-klasse van problemen die je via een (computer-) algoritme wilt uitrekenen, voor meer info zie wikipedia. Met deze termen gooien ze graag vaak bij vakken als theoretische informatica

Maaruh, als je het met ints doet en de modulo (%) en deel (/) operators (zoals hierboven voorgesteld), dan is het in principe toch een onzettend simpel probleem dat in constante tijd op te lossen is? Omdat je 15 bekende muntwaardes hebt, hoef je in principe maar 30 operaties uit te voeren als je met ints werkt:

Voor 750 euro bijvoorbeeld:

code:

int b = 75000 ;

int vijfhonderd = b / 50000; // 1
int rest = (b - vijfhonderd * 50000) % 50000;

int honderd = rest / 10000; // 2
rest = (rest - honderd * 10000) % 10000;

int vijftig = rest / 5000; // 1
rest = (rest - honderd * 5000) % 5000;

// en verder voor lagere muntwaardes

Werkt toch ook, of mis ik nu iets?

[WVL_KsZeN]

Verwijderd schreef op donderdag 13 april 2006 @ 21:28:
Werkt toch ook, of mis ik nu iets?

In dit geval werkt het doordat elke grotere munt altijd minstens 2x zoveel waard is als de vorige... Als dat niet het geval is zit je met een knapsack probleem (tenminste, als de voorwaarde is dat je met zo min mogelijk munten moet uitbetalen), en dat is NPC (ok, het is dus NP-hard, weet niet precies wat het verschil is).
http://en.wikipedia.org/wiki/Knapsack_problem

voorbeeld :

stel het bedrag is 78 cent, en je hebt munten van 1ct, 39ct en 40ct.

jouw algoritme zou dan 1x 40ct en 38x 1ct doen.. terwijl 2x39 ct duidelijk makkelijker is

[ Voor 110% gewijzigd door WVL_KsZeN op 13-04-2006 21:38 ]

[Verwijderd]

het is dus NP-hard, weet niet precies wat het verschil is

Ik ook niet meer en dat trauma wou ik ook graag achter me laten

[terabyte]

Verwijderd schreef op donderdag 13 april 2006 @ 21:34:
[...]


Ik ook niet meer en dat trauma wou ik ook graag achter me laten

Stel dat je ooit een bepaalde beslissingsalgoritme voor een bepaald hard-realtime regelsysteem (bijv. besturingssysteem voor vliegtuigen?) moet ontwerpen, dan is het toch best handig om te kunnen weten of het in P danwel NP zit. Je wilt geen NP-moeilijk iets voor een hard-realtime systeem...

[ Voor 14% gewijzigd door terabyte op 13-04-2006 21:41 ]

[Verwijderd]

offtopic:
Trouwens even excuses aan de topicstarter voor onze thread-hijack Een gebruiker een float laten ingeven en dan met ints rekenen kun je doen door het ingegeven bedrag te vermenigvuldigen met 100 en dan te casten naar een int. Hoe dit precies gaat in C weet ik niet, maar in Java is het gewoon int bedragInt = (int)eenFloatWaarde;

stel het bedrag is 78 cent, en je hebt munten van 1ct, 39ct en 40ct. Jouw algoritme zou dan 1x 40ct en 38x 1ct doen.. terwijl 2x39 ct duidelijk makkelijker is

Naja, dat is subjectief Maar ik vraag me af, als je dit nu brute-force (NPC) gaat oplossen, dan kun je eigenlijk toch ook op alletwee de oplossingen uitkomen? De enige manier om tussen deze twee mogelijkheden verschil te maken zou zijn om 'hogere kosten' aan 1x40/1x38 toe te wijzen, niet? Dan heb je het over een tweede restrictie en is da's een heel ander probleem... Volgens mij wordt het met deze tweede restrictie pas equivalent aan het knapsack probleem (waardeoptimalisatie met beperkte ruimte).

Stel dat je ooit een bepaalde beslissingsalgoritme voor een bepaald hard-realtime regelsysteem (bijv. besturingssysteem voor vliegtuigen?) moet ontwerpen, dan is het toch best handig om te kunnen weten of het in P danwel NP zit. Je wilt geen NP-moeilijk iets voor een hard-realtime systeem...

Naja, als ik ooit zo'n multi-miljoenen project binnensleep, dan neem ik m'n professor wel aan om dit voor me uit te zoeken. Ik weet dat het nuttig is, ik zal het wel weer snappen als ik me erin verdiep, maar in het echte wereld heb je dit 99.9999% van de tijd niet nodig (empirisch vastgesteld gedurende 7 jaar commerciele werkervaring )

[ Voor 15% gewijzigd door Verwijderd op 13-04-2006 22:10 . Reden: Excuses en knapsack openbaring :) ]

[terabyte]

Verwijderd schreef op donderdag 13 april 2006 @ 21:59:

offtopic:
Trouwens even excuses aan de topicstarter voor onze thread-hijack

(empirisch vastgesteld gedurende 7 jaar commerciele werkervaring )

offtopic:
De echte wereld in Nederland ja, maar ICT in Nederland stelt qua niveau helemaal niets voor (al willen veel Tweakertjes anders doen geloven). Als academicus werk je dan al snel onder je niveau (al beweren de meeste Tweakertjes dat academici 'niks' kunnen). Bij werk op niveau (dus niet ICT dienstverlening of kantoorautomatisering) heb je zulke kennis (theoretische informatica) weldegelijk nodig, dat kan ik je verzekeren.

[WVL_KsZeN]

Verwijderd schreef op donderdag 13 april 2006 @ 21:59:De enige manier om tussen deze twee mogelijkheden verschil te maken zou zijn om 'hogere kosten' aan 1x40/1x38 toe te wijzen, niet? Dan heb je het over een tweede restrictie en is da's een heel ander probleem... Volgens mij wordt het met deze tweede restrictie pas equivalent aan het knapsack probleem (waardeoptimalisatie met beperkte ruimte).

* WVL_KsZeN :
knapsack probleem (tenminste, als de voorwaarde is dat je met zo min mogelijk munten moet uitbetalen

dat zei ik toch?

[Verwijderd]

Naja, de thread is toch al helemaal stuurloos, dus ik doe ook nog een duit in het zakje (pun intended )

Bij werk op niveau (dus niet ICT dienstverlening of kantoorautomatisering) heb je zulke kennis (theoretische informatica) weldegelijk nodig, dat kan ik je verzekeren.

Even voor de duidelijjkheid vooraf: ik probeer niet de pisvlek uit te hangen, gewoon interesse.

Kun je een realistisch voorbeeld geven van dit werk op niveau dan? Je voorbeeld van die vliegtuigen is een vrij exotische case. Bij beslissingssystemen kan ik me er inderdaad wel iets bij voorstellen, maar die draaien hoogzelden realtime afaik. Voor zover ik heb mogen zien komt de P/NP problematiek alleen echt ter sprake bij academische vraagstukken, dus als je een concreet voorbeeld hebt (natuurlijk het liefst waar je zelf aan gewerkt hebt) dan hoor ik het graag.

dat zei ik toch?

WVL_KsZeN wijzigde dit bericht (110%)

Dat klopt Maar de topicstarter heeft deze restrictie niet, hij wilt gewoon muntjes uitgeven van hoog naar laag en da's dus een veel simpeler probleem... toch?

[ Voor 15% gewijzigd door Verwijderd op 13-04-2006 22:24 ]

[Orphix]

Verwijderd schreef op donderdag 13 april 2006 @ 22:20:
Even voor de duidelijjkheid vooraf: ik probeer niet de pisvlek uit te hangen, gewoon interesse.

Kun je een realistisch voorbeeld geven van dit werk op niveau dan? Je voorbeeld van die vliegtuigen is een vrij exotische case. Bij beslissingssystemen kan ik me er inderdaad wel iets bij voorstellen, maar die draaien hoogzelden realtime afaik. Voor zover ik heb mogen zien komt de P/NP problematiek alleen echt ter sprake bij academische vraagstukken, dus als je een concreet voorbeeld hebt (natuurlijk het liefst waar je zelf aan gewerkt hebt) dan hoor ik het graag.

Als ik even voor mag dringen Bijvoorbeeld bij planningssystemen, iets wat ik laatst heb ontwikkeld. Bij het genereren van een optimale schedule stuit je vaak op NP-harde problemen. Nou is dit op zich geen probleem, er zijn hele goede heuristieken beschikbaar die een probleem wel in constante tijd zijn op te lossen. Zij het iets minder optimaal.

Maar het herkennen van een dergelijk probleem, en het inzien dat het een doodlopende weg is (en dus gaan zoeken naar alternatieven) is wel degelijk belangrijk.

Trouwens, ik ben geen theoretische informaticus en ben absoluut geen kenner op dit gebied. Sterker nog, ik weet enkel dat NP-harde problemen bestaan en wat de implicaties zijn. Maar dit is voor mij voldoende.

/offtopic

[Verwijderd]

Bedankt voor je inzicht, theoretische informatica blijkt inderdaad zowaar nog eens nuttig

offtopic:
*mental note* Neem geen opdrachten voor planningssystemen aan

[Soultaker]

Zoijar schreef op donderdag 13 april 2006 @ 21:04:
Hehe, je denkt ik begin even met een NPC probleem op te lossen (niet dat het niet kan hoor, simpel zoek algoritme, is alleen traag)

Hij is helemaal niet NP-compleet; met geheeltallige bedragen is er een triviaal dynamisch algoritme in O(MB) tijd met M het aantal muntjes en B het totaalbedrag. Dat is nog verder terug te brengen in getallen waarin B heel groot is (meestal zal je dan immers eerst een heleboel keer de 'grootste' munt nemen, en daarna een aantal keer 'kleinere' munten om op het gewenste totaal te komen).

Om geheeltallige bedragen te krijgen moet je een getal zien te vinden waarmee je alle bedragen kunt vermenigvuldigen zodat ze geheel zijn; in de situatie van de TS kun je ze simpelweg in centen rekenen door de getallen met 100 te vermenigvuldigen (werkt slecht met floats natuurlijk).

Het verschil met het knapsack-probleem zit 'm er in dat je muntjes best mag hergebruiken. Dat maakt van een NP-compleet probleem een simpel probleem dat met dynamisch programmeren opgelost kan worden.

[ Voor 25% gewijzigd door Soultaker op 13-04-2006 23:23 ]

[Verwijderd]

Dat zeggen we toch?

[terabyte]

Verwijderd schreef op donderdag 13 april 2006 @ 22:20:
Naja, de thread is toch al helemaal stuurloos, dus ik doe ook nog een duit in het zakje (pun intended )

[...]


Even voor de duidelijjkheid vooraf: ik probeer niet de pisvlek uit te hangen, gewoon interesse.

Als je wilt weten waar Informatica 'op niveau' wordt toegepast, moet je de hele kantoorautomatisering en ICT dienstverlening (waar het op t.net allemaal om lijkt te draaien) even vergeten.

Kun je een realistisch voorbeeld geven van dit werk op niveau dan? Je voorbeeld van die vliegtuigen is een vrij exotische case.
[...]
Bij beslissingssystemen kan ik me er inderdaad wel iets bij voorstellen, maar die draaien hoogzelden realtime afaik. Voor zover ik heb mogen zien komt de P/NP problematiek alleen echt ter sprake bij academische vraagstukken, dus als je een concreet voorbeeld hebt (natuurlijk het liefst waar je zelf aan gewerkt hebt) dan hoor ik het graag.

Wat dacht je van real-time beslissingen mbt instellen van wissels (op stations)? Dat is een bewezen NP moeilijk probleem. Je wilt toch niet dat je trein een half uur blijft wachten voor een rood sein tot de computer klaar is met het oplossen van dit probleem? Overigens is dit probleem nog niet helemaal 'opgelost' (wordt druk aan gewerkt dmv heuristieken en preprocessing).

Ander voorbeeld: sommige Tweakertjes vinden het maar nutteloos, de correctheid van software bewijzen. Ik hoop (nee, ik weet zeker) dat zulke Tweakertjes niet programmeren aan beveiligingssoftware voor diezelfde spoorwegen... Stel je voor dat er een bug zat in de specificatie of implementatie: tientallen doden door een botsing...

Maar omdat ik weet dat de correctheid is bewezen, maak ik me niet zo druk om bugs in het beveiligingssysteem als ik in de trein zit.

[ Voor 5% gewijzigd door terabyte op 13-04-2006 23:29 ]

[Voutloos]

Ook ICT welke niet 100% realtime kritische zaken betreft kan op niveau zijn en bovendien doe je een beetje neerbuigend met 'Tweakertjes'. Het komt over alsof je je echt beter voelt dan de rest hier.

[Grijze Vos]

Soultaker schreef op donderdag 13 april 2006 @ 23:18:
[...]

<snip>

Het verschil met het knapsack-probleem zit 'm er in dat je muntjes best mag hergebruiken. Dat maakt van een NP-compleet probleem een simpel probleem dat met dynamisch programmeren opgelost kan worden.

Precies. Overigens noemen we dit soort algoritmes ook wel Greedy Algorithms.

[terabyte]

Voutloos schreef op donderdag 13 april 2006 @ 23:33:
Ook ICT welke niet 100% realtime kritische zaken betreft kan op niveau zijn en bovendien doe je een beetje neerbuigend met 'Tweakertjes'. Het komt over alsof je je echt beter voelt dan de rest hier.

Je moest eens weten hoe over T.net over informatici wordt gesproken. "Ze kunnen niks" "Ze kunnen niet eens programmeren", daar hoor je dan weer niemand over. Dergelijk volk mag ik best als Tweakertjes aanduiden.

Ik voel me overigens niet beter dan de rest hier, maar ik voel me wel gekrenkt als ik weer eens beschuldigd wordt van het 'niks kunnen' (in andere topics). Vergeef me mijn verbitterdheid.

[ Voor 6% gewijzigd door terabyte op 13-04-2006 23:37 ]

[terabyte]

Ik heb overigens nog een voorbeeld (van collega, niet van mij) waar theoretische informatica een belangrijke rol speelde. In dit geval geen P/NP gebeuren, maar wederom correctheidsbewijzen:

Er moest software worden ontworpen en geimplementeerd voor een marineschip. De software moest correct zijn. Om makkelijk te kunnen bewijzen werd een referentieimplementatie geschreven in Haskell (50 regels). Aangezien Haskell enorm traag is, werd het dmv termherschrijfsystemen omgezet naar C. Toch zat ergens een bug in. Het probleem zat 'm niet in de software (was immers bewezen correct), maar in de hardware!

[ Voor 4% gewijzigd door terabyte op 13-04-2006 23:48 ]

[Soultaker]

Grijze Vos schreef op donderdag 13 april 2006 @ 23:36:
Precies. Overigens noemen we dit soort algoritmes ook wel Greedy Algorithms.

Niet helemaal; een Greedy Algorithm kiest (op basis van een heuristiek) steeds een stap voorwaarts zonder ooit een stap terug te nemen en zonder gebruik van geheugen. Het algoritme in de topic start is bijvoorbeeld greedy: het kiest steeds de grootste munt die het totaalbedrag niet overschrijdt.

Dat algoritme is niet optimaal en ook niet correct; als je bijvoorbeeld een munt van 2 en een munt van 3 hebt en je wil het bedrag 7 maken, dan zal het algoritme eerst twee keer 3 pakken en dan vastgelopen zijn (er is geen manier meer om het resterende bedrag 1 te maken). Een correct algoritme kiest wel voor 3, 2, 2.

Een dynamisch algoritme is simpelweg een efficiëntere herformulatie van een backtracking algoritme, zodat die in polynomiale in plaats van exponentiële tijd uitgevoerd kan worden, meestal ten koste van (een polynomiale hoeveelheid) geheugen.

[terabyte]

Leuk voorbeeldje van de 'time-memory tradeoff'.

[Verwijderd]

Dat algoritme is niet optimaal en ook niet correct; als je bijvoorbeeld een munt van 2 en een munt van 3 hebt en je wil het bedrag 7 maken, dan zal het algoritme eerst twee keer 3 pakken en dan vastgelopen zijn (er is geen manier meer om het resterende bedrag 1 te maken). Een correct algoritme kiest wel voor 3, 2, 2.

Voor jou probleem wel ja, maar onze topicstarter is net C aan het leren. Voor zijn probleeminstantie is dit greedy algoritme een prima oplossing. Net zoals mijn aanpak in constante tijd trouwens

[Grijze Vos]

Soultaker schreef op donderdag 13 april 2006 @ 23:49:
[...]

Niet helemaal; een Greedy Algorithm kiest (op basis van een heuristiek) steeds een stap voorwaarts zonder ooit een stap terug te nemen en zonder gebruik van geheugen. Het algoritme in de topic start is bijvoorbeeld greedy: het kiest steeds de grootste munt die het totaalbedrag niet overschrijdt.

Dat algoritme is niet optimaal en ook niet correct; als je bijvoorbeeld een munt van 2 en een munt van 3 hebt en je wil het bedrag 7 maken, dan zal het algoritme eerst twee keer 3 pakken en dan vastgelopen zijn (er is geen manier meer om het resterende bedrag 1 te maken). Een correct algoritme kiest wel voor 3, 2, 2.

Een dynamisch algoritme is simpelweg een efficiëntere herformulatie van een backtracking algoritme, zodat die in polynomiale in plaats van exponentiële tijd uitgevoerd kan worden, meestal ten koste van (een polynomiale hoeveelheid) geheugen.

Je vergeet dat de munten bewust zo gekozen zijn dat je het probleem wat je beschrijft niet voorkomt. Dus kun je dit probleem wel degelijk zo implementeren.

[Verwijderd]

Verwijderd schreef op donderdag 13 april 2006 @ 22:20:
Naja, de thread is toch al helemaal stuurloos, dus ik doe ook nog een duit in het zakje (pun intended )


[...]


Even voor de duidelijjkheid vooraf: ik probeer niet de pisvlek uit te hangen, gewoon interesse.

Kun je een realistisch voorbeeld geven van dit werk op niveau dan?

[...]

Bij het ontwerp van navigatie-systemen moet je het real-time gedrag ook niet uit het oog verliezen. Je wilt natuurlijk niet dat een bestuurder te horen krijgt: "bij de vorige afslag had u de snelweg moeten verlaten".

Zelfs in het "op ICT gebied niets voorstellende Nederland" wordt er in meerdere bedrijven hieraan gewerkt.

[Soultaker]

Verwijderd schreef op donderdag 13 april 2006 @ 23:59:
Voor jou probleem wel ja, maar onze topicstarter is net C aan het leren.

Dat 'ie C aan het leren is betekent dat 'ie verder niet kan programmeren.

Grijze Vos schreef op vrijdag 14 april 2006 @ 00:11:
Je vergeet dat de munten bewust zo gekozen zijn dat je het probleem wat je beschrijft niet voorkomt. Dus kun je dit probleem wel degelijk zo implementeren.

Accoord, maar dan heeft de hele discussie over complexiteit ook weinig zin.

[ Voor 78% gewijzigd door Soultaker op 14-04-2006 00:14 ]

[Verwijderd]

Soultaker schreef op vrijdag 14 april 2006 @ 00:13:
Dat 'ie C aan het leren is betekent dat 'ie verder niet kan programmeren.

Beetje laagdunkend over C mensen, maar ik begrijp wat je bedoelt. Accoord, 2x

[Voutloos]

offtopic:
Ik neem aan dat Soultaker 'betekent nog niet' bedoelde.

[terabyte]

Soultaker schreef op vrijdag 14 april 2006 @ 00:13:
[...]
dan heeft de hele discussie over complexiteit ook weinig zin.

Da's jammer, want met het oplossen van het P=NP probleem kun je toch wel direct miljonair worden!

[BCC]

terabyte schreef op vrijdag 14 april 2006 @ 00:26:
[...]

Da's jammer, want met het oplossen van het P=NP probleem kun je toch wel direct miljonair worden!

Ik ben er druk mee bezig om erop af te studeren . Grappig is dat je dan ook gelijk alle encryptie direct kan kraken. Maar nou gaat het wel heel offtopic: van C naar Napsack naar NP-Hard problemen, Bruteforce met searchspace shaping naar encriptie en nu zelfs quantumtechnologie

Nog verder offtopic: een double heeft de dubbele priciesie van een float. Hence the "double".

[ Voor 11% gewijzigd door BCC op 14-04-2006 00:51 ]

[Gerco]

BCC schreef op vrijdag 14 april 2006 @ 00:48:
Ik ben er druk mee bezig om erop af te studeren . Grappig is dat je dan ook gelijk alle encryptie direct kan kraken.

Dat kan wel zo zijn, maar als je een NP probleem weet te reduceren tot een P probleem (en dus bewijst dat P=NP), kun je nog steeds niet noodzakelijkerwijs snel alle encryptie kraken

Een P probleem wat O(n^99999999) tijd nodig heeft is nog steeds verdomde moeilijk op te lossen. Nou ja, het is niet moeilijk, maar duurt wel heel erg lang (voor voldoende grote n)

[ Voor 3% gewijzigd door Gerco op 14-04-2006 09:08 ]

[Verwijderd]

De methode om met centen te werken heeft z'n vruchten afgeworpen. Het programma lijkt te werken:

C:

int main(void)
{
  
  int waarde_munt[] = {50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1, 0};
  int aantal_munt[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  int i = 0;
  float bedrag;
  int bedrag_int;
  
  printf("Gelieve een bedrag in te vullen: \n");
  scanf("%f", &bedrag);
  
  bedrag_int = (int) (bedrag * 100.0 + 0.05);
  
  while (waarde_munt[i] > 0)
  {
        while ( bedrag_int - waarde_munt[i] >= 0)
        {
              bedrag_int = bedrag_int - waarde_munt[i];
              aantal_munt[i] = aantal_munt[i] + 1;
        }
        i++;
  }
  
  for (i=0; i < 15; i++)
  {
      printf("%d van %.2f\n", aantal_munt[i], (waarde_munt[i] / 100.0));
  }
  
  system("PAUSE");  
  return 0;
}

Bedankt voor jullie hulp en de geanimeerde discussies

[Stubby]

Oh nog even een mierenneukerig puntje, waar kan ik die munten van 500, 200 euro etc halen?

[Olaf van der Spek]

terabyte schreef op donderdag 13 april 2006 @ 23:27:
Ander voorbeeld: sommige Tweakertjes vinden het maar nutteloos, de correctheid van software bewijzen. Ik hoop (nee, ik weet zeker) dat zulke Tweakertjes niet programmeren aan beveiligingssoftware voor diezelfde spoorwegen... Stel je voor dat er een bug zat in de specificatie of implementatie: tientallen doden door een botsing...

Dat is volgens mij een beetje overdreven. Controleren of een bepaalde oplossing veilig is, is namelijk vrij simpel. Bewijzen dat je algoritme altijd een veilige oplossing genereert is dat natuurlijk niet.

Jouw voorbeeld is meer van toepassing op vliegtuigen enzo, aangezien je daar niet even op de rem kunt gaan staan.

Stubby schreef op vrijdag 14 april 2006 @ 09:51:
Oh nog even een mierenneukerig puntje, waar kan ik die munten van 500, 200 euro etc halen?

Ben jij niet de eerste die het over euro heeft?

Verwijderd schreef op vrijdag 14 april 2006 @ 09:29:
while ( bedrag_int - waarde_munt[i] >= 0)
{
bedrag_int = bedrag_int - waarde_munt[i];
aantal_munt[i] = aantal_munt[i] + 1;
}

Eh, is daar de deling niet voor uitgevonden?

BCC schreef op vrijdag 14 april 2006 @ 00:48:
Nog verder offtopic: een double heeft de dubbele priciesie van een float. Hence the "double".

Dat is volgens mij niet waar. Een double gebruikt in totaal vaak twee keer zoveel bits (64 in plaats van 32). De preciesie is echter meer dan 2x zo hoog aangezien die verdubbeling van bits vooral wordt gebruikt om de preciesie te verbeteren in plaats van het bereik.

[ Voor 45% gewijzigd door Olaf van der Spek op 14-04-2006 10:36 ]

[terabyte]

OlafvdSpek schreef op vrijdag 14 april 2006 @ 10:32:
[...]
Jouw voorbeeld is meer van toepassing op vliegtuigen enzo, aangezien je daar niet even op de rem kunt gaan staan.

Dat is niet waar, want bij treinen ziet een machinist ook pas op het laatste moment hoe de wissels staan ingesteld (en op ingewikkelde emplacementen is het helemaal moeilijk om een 'pad' te zien). Ja, en dan is het (zelfs met slechts 40 km/h) al te laat...
Waar het gaat om leven en dood moet je dus bewijzen dat je algoritme correct werkt, daar is niks overdreven aan.

[Olaf van der Spek]

terabyte schreef op vrijdag 14 april 2006 @ 10:39:
Dat is niet waar, want bij treinen ziet een machinist ook pas op het laatste moment hoe de wissels staan ingesteld (en op ingewikkelde emplacementen is het helemaal moeilijk om een 'pad' te zien). Ja, en dan is het (zelfs met slechts 40 km/h) al te laat...
Waar het gaat om leven en dood moet je dus bewijzen dat je algoritme correct werkt, daar is niks overdreven aan.

Maar het systeem kan wel op tijd controleren of de wissels goed staan, toch?
Het kan niet garanderen dat het de wissels altijd goed zet, maar volgens mij wel dat het aangeeft dat het fout is gegaan als het geen goede oplossing heeft kunnen vinden.

[terabyte]

Ja, maar het is een real-time systeem. Hoeveel oplossingen n moet je genereren en controleren voordat je een veilige oplossing hebt? En kun je bewijzen dat n gelimiteerd is? Voor een middelgroot station kan n oplopen in de tienduizenden, die kun je niet allemaal 'even' controleren op correctheid.

Het probleem is ingewikkelder dan ik in dit topic heb gesteld, dus je moet me gewoon geloven dat het simpelweg bewijzen dat het algoritme correct werkt veruit het makkelijkst is...

[BCC]

Als je nou even op Wikipedia had gekeken :
http://en.wikipedia.org/wiki/Floating_point

Floating-point numbers usually behave very similarly to the real numbers they are used to approximate. However, this can easily lead programmers into over-confidently ignoring the need for numerical analysis. There are many cases where floating-point numbers do not model real numbers well, even in simple cases such as representing the decimal fraction 0.1, which cannot be exactly represented in any binary floating-point format. For this reason, financial software tends not to use a binary floating-point number representation.

[Olaf van der Spek]

terabyte schreef op vrijdag 14 april 2006 @ 10:47:
Ja, maar het is een real-time systeem. Hoeveel oplossingen n moet je genereren en controleren voordat je een veilige oplossing hebt?

Dat weet ik niet. Maar ik beweer ook niet dat je eenvoudig een veilige oplossing kunt genereren.
Ik beweer alleen dat het systeem zelf kan controleren of een bepaalde oplossing veilig is en zo nee, een onveilige situatie kan voorkomen (fail safe).

In de praktijk is het natuurlijk handiger een systeem te hebben dat gegarandeerd op tijd een correcte oplossing genereerd.

En kun je bewijzen dat n gelimiteerd is? Voor een middelgroot station kan n oplopen in de tienduizenden, die kun je niet allemaal 'even' controleren op correctheid.

Het probleem is ingewikkelder dan ik in dit topic heb gesteld, dus je moet me gewoon geloven dat het simpelweg bewijzen dat het algoritme correct werkt veruit het makkelijkst is...

Dat geloof ik best.
Maar wat ik wilde zeggen is dat je ook zonder dat bewijs met zekerheid een onveilige situatie (botsing) kan voorkomen. Er zullen dan wel andere dingen misgaan (vertragingen enzo), maar dat is wat anders.

[BCC]

Het probleem is ingewikkelder dan ik in dit topic heb gesteld, dus je moet me gewoon geloven dat het simpelweg bewijzen dat het algoritme correct werkt veruit het makkelijkst is...

Je doelt hierbij op formele methodes? The way of Z ?

Maar wat ik wilde zeggen is dat je ook zonder dat bewijs met zekerheid een onveilige situatie (botsing) kan voorkomen. Er zullen dan wel andere dingen misgaan (vertragingen enzo), maar dat is wat anders.

Je kan zonder formeel bewijs niet garanderen dat jouw systeem altijd correct werkt. Formele bewijzen zijn gestoeld op logica. Hierdoor kun je voor functies / delen code bewijzen dat ze altijd correct zijn. Erg fijn in bedrijfskritische situaties. Hierbij hoef je niet gelijk te denken aan 'n kernreactor, maar software voor een CV ketel bijvoorbeeld wil je ook zo ontwerpen.

[ Voor 58% gewijzigd door BCC op 14-04-2006 10:58 ]

[terabyte]

OlafvdSpek schreef op vrijdag 14 april 2006 @ 10:52:
[...]Er zullen dan wel andere dingen misgaan (vertragingen enzo), maar dat is wat anders.

En het doel was juist vertraging te vermijden/minimaliseren dmv een optimale wisselinstelling...

[Janoz]

OlafvdSpek schreef op vrijdag 14 april 2006 @ 10:42:
[...]

Maar het systeem kan wel op tijd controleren of de wissels goed staan, toch?
Het kan niet garanderen dat het de wissels altijd goed zet, maar volgens mij wel dat het aangeeft dat het fout is gegaan als het geen goede oplossing heeft kunnen vinden.

Dan moet het systeem wel weten wat goed is. En als hij dat niet op tijd kan berekenen...

Wat dacht je daarnaast van deadlock problemen, veranderende omstandigheden (treinen die niet snel genoeg of juist te snel hun baanvak verlaten).

[terabyte]

Janoz schreef op vrijdag 14 april 2006 @ 11:04:
[...]
Wat dacht je daarnaast van deadlock problemen, veranderende omstandigheden (treinen die niet snel genoeg of juist te snel hun baanvak verlaten).

En dat is idd nog een extra moeilijkheid: de huidige daadwerkelijke situatie moet altijd worden meegenomen in de berekeningen. En de huidige situatie verandert natuurlijk constant.

[admiral866]

vond 't wel grappig, even in php 't volgende alternatief verzonnen

PHP:

<?php

$bedrag = '765.9';
$munten = array(500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01);

foreach($munten as $key => $value){
    if(($aantal_munten = floor("$bedrag"/"$value")) > 0){       
        $bedrag = $bedrag - ($value*$aantal_munten);    
        $resultaat[++$i]['aantal'] = $aantal_munten;
        $resultaat[$i]['waarde'] = $value;          
    }
}

foreach($resultaat as $key => $value)
    echo $value['aantal']." munten van ".$value['waarde']."<br>";


?>

[Olaf van der Spek]

Janoz schreef op vrijdag 14 april 2006 @ 11:04:
Dan moet het systeem wel weten wat goed is. En als hij dat niet op tijd kan berekenen...

Maar controleren of een (kandidaat) oplossing goed is, is vaak een heel stuk simpeler dan het vinden van die oplossing zelf.
Vergelijk het met het vinden van de ontbinding van een getal of de sleutel voor een decryptiealgoritme. Het vinden is erg lastig, het controleren is erg simpel.

Wat dacht je daarnaast van deadlock problemen, veranderende omstandigheden (treinen die niet snel genoeg of juist te snel hun baanvak verlaten).

Dat is inderdaad een probleem, maar in ieder geval voorkom je dan een botsing.

admiral schreef op vrijdag 14 april 2006 @ 11:32:
foreach($munten as $key => $value){

Waar gebruik je $key?

[ Voor 11% gewijzigd door Olaf van der Spek op 14-04-2006 11:41 ]

[admiral866]

OlafvdSpek schreef op vrijdag 14 april 2006 @ 11:39:

Waar gebruik je $key?

hehe, ochja had et eerst ietsie anders. Kan wel weg ja

[Verwijderd]

ok, nog eentje dan

Waar het gaat om leven en dood moet je dus bewijzen dat je algoritme correct werkt, daar is niks overdreven aan.

Dit lijkt natuurlijk een steekhoudend argument, maar het is eigenlijk wel een beetje filosofisch. Je data zal altijd incompleet zijn omdat de echte wereld te groot is om te simuleren, dus volledige correctheid is vaak een ondergeschoven kindje, zelfs bij (bedrijfs)kritische realtime applicaties. Zo lang idioten stoeptegels van bruggen af kunnen gooien en carnavalswagens op spoorlijnen vast komen te staan, kun je met het correctste programma ter wereld geen 100% correcte oplossingen garanderen. IMO valt beperkte correctheid van een programma dus in het niet tegenover alle mogelijke alledaagse eventualiteiten (dit gaat trouwens ook vaak op voor complexiteitsvraagstukken).

Dat kan wel zo zijn, maar als je een NP probleem weet te reduceren tot een P probleem (en dus bewijst dat P=NP), kun je nog steeds niet noodzakelijkerwijs snel alle encryptie kraken

Blij dat je dit zelf al aangeeft, want dit is vaak mijn grootste punt van kritiek op theoretische informatica, practische toepasbaarheid. Als je bijvoorbeeld algoritmes bekijkt die ofwel in lineair of exponentiele tijd draaien, dan gaat TI er bij voorbaat van uit dat het lineaire algoritme sneller is. Dit is natuurlijk helemaal afhankelijk van je data en de worst/bestcase scenario's, maar dit wordt vaak afgedaan als een academische anomalie.

Door deze houding heb je in principe geen mogelijkheid om de echte wereld erbij te betrekken mbv empirische/statistische data en dat is jammer. Je ziet dit bij veel vakgebieden terug (niet alleen bij TI), maar dit is in mijn ogen wel de reden dat dit soort interessante en misschien ook belangrijke vraagstukken (jammergenoeg) voorbehouden blijven aan academische theoretici.

[ Voor 3% gewijzigd door Verwijderd op 14-04-2006 12:09 . Reden: Mooier woord bedacht :) ]

[terabyte]

Verwijderd schreef op vrijdag 14 april 2006 @ 12:03:
ok, nog eentje dan

[...]


Dit lijkt natuurlijk een steekhoudend argument, maar het is eigenlijk wel een beetje filosofisch. Je data zal altijd incompleet zijn omdat de echte wereld te groot is om te simuleren, dus volledige correctheid is vaak een ondergeschoven kindje, zelfs bij (bedrijfs)kritische realtime applicaties. Zo lang idioten stoeptegels van bruggen af kunnen gooien en carnavalswagens op spoorlijnen vast komen te staan, kun je met het correctste programma ter wereld geen 100% correcte oplossingen garanderen. IMO valt beperkte correctheid van een programma dus in het niet tegenover alle mogelijke alledaagse eventualiteiten (dit gaat trouwens ook vaak op voor complexiteitsvraagstukken).

Nou met die redenering kan ik het niet eens zijn. Je zegt nu in feite "ach, we hoeven helemaal geen correcte software te schrijven, ach die bugs in het beveiligingssysteem zijn helemaal niet zo erg zolang iemand zich voor de trein kan gooien"

Of (simpeler voorbeeld) "ah, die afrondingsfouten in dat financieel softwarepakket voor de Belastingsdienst stellen niet zoveel voor want Jan Jansen heeft z'n aangifte ook niet goed ingevuld"

Blij dat je dit zelf al aangeeft, want dit is vaak mijn grootste punt van kritiek op theoretische informatica, practische toepasbaarheid.

Theoretische informatica (waar ik ook even Logica onder schaar) is een van de pijlers van de ICT. Wellicht zie jij geen praktische toepasbaarheid, maar bijvoorbeeld zaken zoals relationele databases (die wel praktisch toepasbaar zijn) zijn gebaseerd op theorien uit de logica en theoretische informatica. De werking van jouw computer (praktisch toepasbaar) is gebaseerd op logica/theoretische informatica. De werking van compilers (praktisch toepasbaar) is gebaseerd op logica/theoretische informatica, etc etc etc.

Vergeet dat allemaal niet. Wellicht beschouw jij een compiler als een 'gegeven', maar denk eens na hoe het komt dat een compiler z'n werk kan doen en wat voor (automaten)theorie daar allemaal voor nodig is...

[Canaria]

Verwijderd schreef op donderdag 13 april 2006 @ 21:15:
Wat is NPC?

Double is volgens mij ook een type dat een benaderende waarde bevat, alleen meer precies dan float, maar dat doet er hier niet toe.

Ik zou het inderdaad met ints kunnen doen, maar dan moet ik inderdaad in centen rekenen. Maar dan is m'n vraag. Hoe laat ik de gebruiker een decimaal ingeven en toch met ints rekenen?

Door het bedrag als string te vangen en met wat string operators hieruit de overbodige tekens te halen.

Wel grappig topic dit, ik heb ooit een kassasysteem geprogrammeerd, in Pascal, nog in het guldentijdperk. Dus eerst het bedrag afronden en dan de optimale verdeling van het wisselgeld laten bepalen. Doordat muntwaarde redelijk binair is, kun je er redelijk vanuit gaan dat als je van hoog naar laag telkens de maximale aantallen eruit haalt met integer deling, het aantal munten minimaal is.

[ Voor 27% gewijzigd door Canaria op 14-04-2006 16:00 ]

[Verwijderd]

Verwijderd schreef op donderdag 13 april 2006 @ 21:15:
Ik zou het inderdaad met ints kunnen doen, maar dan moet ik inderdaad in centen rekenen. Maar dan is m'n vraag. Hoe laat ik de gebruiker een decimaal ingeven en toch met ints rekenen?

printf("%d.%02d",bedrag/100, bedrag%100);

De %02d zorgt dat er altijd twee decimalen staan met een nul vooraan als er maar 1 cijfer is (anders gaat het fout bij een 1-9 cent). De integer delingen zorgen dat alles correct verloopt. (Bedrag moet dus wel een in centen uitgedrukte integer zijn)

(edit: oh, precies andersom dus Waarschijnlijk is dan een afrond truc met floatingpoint makkelijk (vergeet niet goed af te ronden in plaats van te truncaten!), maar het kan inderdaad ook door gewoon zelf de string te parsen omgekeerd aan bovenstaand voorbeeld - dus de string in tweeen opsplitsen op de positie van de punt (of komma) en dan de eerste helft maal 100 plus de tweede helft. Wel even opletten als men geen punt ingeeft (geheel aantal euro's) of als er maar 1 decimaal wordt gegeven)

[ Voor 31% gewijzigd door Verwijderd op 14-04-2006 16:33 ]

[Soultaker]

Je kan het zo omkeren:

C:

int a, b;
if(scanf("%d.%d", &a, &b) == 2)
    printf("Bedrag in centen: %d\n", 100*a + b);

Maar dat werkt alleen goed als de gebruiker precies twee decimalen typt. "1.2" wordt bijvoorbeeld onterecht geïnterpreteerd als 102 cent (in plaats van 120) en net zo voor 1.234. Als je robuust invoer wil uitlezen kun je waarschijnlijk beter de hele regel lezen en dan met de hand uitzoeken of die aan het gewenste formaat voldoet.

Overigens kun je 'm ook wel als float inlezen en dan zelf rekenen met (int)round(100*f) als waarde in centen.

[Verwijderd]

Nou met die redenering kan ik het niet eens zijn. Je zegt nu in feite "ach, we hoeven helemaal geen correcte software te schrijven, ach die bugs in het beveiligingssysteem zijn helemaal niet zo erg zolang iemand zich voor de trein kan gooien"

Da's natuurlijk niet de bedoeling, ik had het meer over bewijsbaar 100% correcte software. Om een trein geen extra gas te laten geven als er een spoorwegovergang niet werkt, daarvoor heb je geen 100% bewijsbaar correcte software voor nodig. Met gezond boerenverstand bij het programmaontwerp kom je ook al een heel eind.

De waarheid ligt denk ik zoals altijd in het midden. Een bewijsbaar correct programma is natuurlijk erg handig, maar in grofweg 90% van de gevallen is een programma zo straightforward dat het voornamelijk overhead is. Zet daar tegenover dat een groot deel van de IT projecten nog altijd niet binnen budget en planning afgerond worden en daar gaat je nobele (misschien zelfs 100% correcte) ideologie.

Daarnaast bestaat er iirc een vrij grote klasse van problemen waarvoor de correctheid van de oplossing / het algoritme niet 100% formeel bewezen kan worden en nog een berg andere problemen zoals het halting problem. Hoe kijk je hier dan tegen aan?

Vergeet dat allemaal niet. Wellicht beschouw jij een compiler als een 'gegeven', maar denk eens na hoe het komt dat een compiler z'n werk kan doen en wat voor (automaten)theorie daar allemaal voor nodig is...

Jaja, dat komt me nog allemaal bekend voor, ik heb zelf nog een aantal automaton simulatie apps mogen schrijven. Maar vergeet dan ook niet dat dezelfde theorie zegt dat je niet elk probleem met een (eindig) computerprogramma kan oplossen (de verzameling problemen is groter dan het aantal mogelijke permutaties van een eindig alfabet, ie het aantal programma's, ook al zijn ze beiden oneindig, maar de één is Aleph0 en de andere Aleph1 oid). Dit zijn dan weer van die dingen dat ik denk "Goh, wat handig"

Ik heb ook nergens beweerd dat deze vakgebieden absoluut nergens praktisch toepasbaar zijn, weer ligt de waarheid in het midden en zijn er zeker concrete voorbeeld van praktische toepasbaarheid, zoals je al aangaf. Maar zeg nou zelf, hoe vaak zul je in je commercieel loopbaan een compiler schrijven? Hoe vaak zul je een processor ontwerpen? Die databases is natuurlijk wel een goed voorbeeld, maar wie heeft er nu tijd om de 623e normaalvorm van een table formeel te construeren, als je met 5 minuten logisch nadenken ook al dicht in de buurt komt?

Een mooi voorbeeld vind ik dat artikel over boomstructuren in databases dat ik al een aantal keer hier op tweakers ben tegengekomen. In plaats van parentid <-> nodeid (prim key) relaties in dezelfde table komt die goeie man met een manier om bomen op te slaan 'zoals het hoort', die wel aan alle normalisatie criteria voldoet, maar waarbij:

• het nagenoeg onmogelijk is om handmatig de structuur aan te passen door de table te editen
• het inserten een soort cascade operatie teweeg brengt, waardoor deze operatie nogal inefficient is
• er kolommen zijn die 'virtuele' info bevatten, die verder geen hout met een boomstructuur van doen heeft, maar wel met deze formeel correct notatie en opslag van bomen

Dit soort excessen bedoelde ik. En als je het echt wilt weten, dan heb ik er nog wel een paar van die voor je. Ergo, de waarheid ligt in het midden

[terabyte]

Ik snap eerlijk gezegd niet wat je probeert te zeggen met dat de waarheid in het midden ligt. Welke waarheid heb je het over? Wat voor boodschap moet ik hebben aan dat (in NL!) weinig gedaan wordt aan compilerbouw of processorontwerp? Omdat 99% het niet kan of wil, betekent dat dat we geen studenten meer mogen opleiden die wel daartoe in staat zijn?

Door zo te redeneren 'bewijs' je alleen maar dat NL nog een lange weg te gaan heef op het gebied van kenniseconomie en innovatie.

Da's natuurlijk niet de bedoeling, ik had het meer over bewijsbaar 100% correcte software. Om een trein geen extra gas te laten geven als er een spoorwegovergang niet werkt, daarvoor heb je geen 100% bewijsbaar correcte software voor nodig. Met gezond boerenverstand bij het programmaontwerp kom je ook al een heel eind.

De discussie begon over een algoritme voor wissel-instelling. Het 'gas' geven is een totaal verkeerd voorbeeld en heeft niks met bewijzen van algoritme-correctheid te maken. Ik heb ik in heel veel posts geprobeerd uit te leggen dat een correctheidsbewijs voor het wissel-instellingsalgoritme wel degelijk van belang is. Maar als je dat blijft betwijfelen: OK, maar ik ga niet al m'n tijd besteden om je te proberen te overtuigen dat in dit geval (en de meeste zaken waar ik aan werk) een correctheidsbewijs wel degelijk van belang is.

[ Voor 51% gewijzigd door terabyte op 14-04-2006 19:35 ]

[Gerco]

Verwijderd schreef op vrijdag 14 april 2006 @ 18:51:
Een mooi voorbeeld vind ik dat artikel over boomstructuren in databases dat ik al een aantal keer hier op tweakers ben tegengekomen. In plaats van parentid <-> nodeid (prim key) relaties in dezelfde table komt die goeie man met een manier om bomen op te slaan 'zoals het hoort', die wel aan alle normalisatie criteria voldoet, maar waarbij:

• het nagenoeg onmogelijk is om handmatig de structuur aan te passen door de table te editen
• het inserten een soort cascade operatie teweeg brengt, waardoor deze operatie nogal inefficient is
• er kolommen zijn die 'virtuele' info bevatten, die verder geen hout met een boomstructuur van doen heeft, maar wel met deze formeel correct notatie en opslag van bomen

Je weet dat het nested sets model bij inserts langzamer is, maar bij selects een paar ordes van grootte sneller dan een parent-child achtige tree? Ik heb meerdere malen een parent-child structuur vervangen/aangevuld met een nested sets structuur omdat de eerste voor geen meter performde.

Natuurlijk heb je daar bij een boom van enkele entries geen last van, maar probeer dat eens bij bomen met meer dan 10k entries en kijk dan nog eens of je structuur zo handig is.

[MSalters]

Verwijderd schreef op vrijdag 14 april 2006 @ 12:03:
Waar het gaat om leven en dood moet je dus bewijzen dat je algoritme correct werkt, daar is niks overdreven aan.]

Dit lijkt natuurlijk een steekhoudend argument, maar het is eigenlijk wel een beetje filosofisch. Je data zal altijd incompleet zijn omdat de echte wereld te groot is om te simuleren, dus volledige correctheid is vaak een ondergeschoven kindje, zelfs bij (bedrijfs)kritische realtime applicaties.

Uit eigen ervaring kan ik vertellen dat er niets overdreven aan is. Sterker nog, je kunt het maar beter bewijzen als je niet veroordeeld wilt worden voor "dood door schuld". Volledige correctheid is in die omgevingen de norm. Je weet misschien niet alles, maar daarom bewijs je alleen de veiligheid van je algoritme (niet kunnen bereiken van onveilige situaties) en niet de efficientie of zo (wan dat gaat over het bereiken van veilige situaties).

[Verwijderd]

Ik snap eerlijk gezegd niet wat je probeert te zeggen met dat de waarheid in het midden ligt. Welke waarheid heb je het over? Wat voor boodschap moet ik hebben aan dat (in NL!) weinig gedaan wordt aan compilerbouw of processorontwerp? Omdat 99% het niet kan of wil, betekent dat dat we geen studenten meer mogen opleiden die wel daartoe in staat zijn?

Met de waarheid in het midden bedoelde ik dat 100% correctheid en andere relatief theoretische zaken zeker nut hebben maar dat het voor veel commerciele projecten het gewoon geen prioriteit is of er zelfs niet eens over wordt nagedacht. Verder heb ik nergens gezegd dat we maar moeten stoppen met deze vakken.

Maar goed, laten we er inderdaad maar over ophouden. IMO doet ieder het op z'n eigen manier en dat zegt verder vrij weinig over hoe goed of slecht we het met z'n allen doen op het gebied van de kenniseconomie en innovatie.

Je weet dat het nested sets model bij inserts langzamer is, maar bij selects een paar ordes van grootte sneller dan een parent-child achtige tree? Ik heb meerdere malen een parent-child structuur vervangen/aangevuld met een nested sets structuur omdat de eerste voor geen meter performde.

Nested sets zijn inderdaad wat ik bedoelde, dank je. Met een paar indices op de table zijn parent-child tabellen ook aardig performant en de rows zijn IMO veel makkelijker te mappen naar gangbare TreeNode objecten in bijvoorbeeld Java of C#. Nested Sets zullen ongetwijfeld efficienter zijn, maar ik werk liever met een table waaruit de hierarchische structuur duidelijk blijkt dan met die left, right kolommen voor nested sets.

Ik probeer hier verder niemand te overtuigen trouwens, ik geef alleen mijn mening

Uit eigen ervaring kan ik vertellen dat er niets overdreven aan is. Sterker nog, je kunt het maar beter bewijzen als je niet veroordeeld wilt worden voor "dood door schuld".

Ben je zelf aangeklaagd dan, of over welke ervaring heb je het? Als ik al jullie verhalen hoor over "leven of dood", "dood door schuld" etc, nou dan laat mij maar fijn domme kantoorautomatiserings- en visualisatie software schrijven.

[ Voor 12% gewijzigd door Verwijderd op 14-04-2006 20:25 ]