SES School, Studie en Onderwijs
Wiskunde in de brugklas, Frans voor het examen of een studie Personeel en Arbeid? Moeilijke formulieren van DUO? Iets weten over studiefinanciering of studentenverenigingen? Dit is het forum voor leerkrachten, scholieren en studenten, van brugklas tot uni
Een algoritme is een rekenmethode. Als je niet weet wat het is, wordt het moeilijk om aan de opgave te voldoen. Ik zal een simpele taal geven, waarin je algoritmen kunt uitdrukken. De taal heet Guarded Command Language (GCL).
Je hebt een aantal verschillende statements en een programma (het recept, algoritme) bestaat uit meerdere atomaire statements. De verschillende statements zijn:
0. assignment (toewijzing)
1. skip (overslaan)
2. abort (afbreken)
3. catenation (koppeling)
4. selection (selectie)
5. repetition (repetitie)
Voordat we uitleggen wat deze statements zijn zal ik even vertellen wat variabelen zijn. Variabelen zijn containers die een waarde bevatten. Stel je declareert een variabele a dan kun je deze a aanroepen in je programma en er wordt dan gerekend met de waarde die a op dat moment bevat.
Assignment:
Stel we hebben een variabele a en we willen dat deze variabele de waarde 0 krijgt, dan schrijven we dit zo:
Willen we dat a de waarde van b krijgt, dan gaat dit zo:
En bijvoorbeeld a krijgt de waarde van a maal b:
Catenation:
Formeel:
P;Q betekent:
Voer eerst P uit dan Q, als P en Q statements zijn.
Stel we willen eerst dat a de waarde van b krijgt en b de waarde van a, dan doen we dit zo:
Waarom is
niet goed?
Selection:
In een algoritme wil je meestal ook een manier hebben om in het ene geval dit te doen en in het andere geval iets anders.
Formeel:
P,Q,R zijn in dit geval predikaten en geen statements. Een predikaat is een uitspraak die afhankelijk van variabelen waar of niet waar is. Als dit wordt uitgevoerd dan wordt op een willekeurige manier 1 van de statements behorende bij de ware predikaten uitgevoerd. Met andere woorden, als P waar is dan kan A uitgevoerd worden, als Q waar is dan B etc. Let op: Er moet altijd een predikaat waar zijn, anders breekt het programma af. Voorbeelden van predikaten zijn:
True (altijd waar)
False (altijd onwaar)
x >= 0
a = b
1 = 2
(a-b)/c = (2*k)+x
Voorbeeld:
Wat doet dit programma?
Repetition:
Stel je wilt iets vaker doen dan 1x keer dan kun je dat middels een repetitie doen.
Formeel:
Zodra dit wordt uitgevoerd wordt gekeken of P,Q of R waar is, als een van de drie waar is, dan wordt 1 van de bij de ware predikaten behorende statements uitgevoerd. Na uitvoering wordt opnieuw gekeken of er een waar is, dit blijft zich herhalen tot ze allemaal onwaar zijn.
Voorbeeld:
Een programma dat a tot de macht b uitrekent:
a wordt nu b maal met zichzelf vermenigvuldigd.
skip:
Dit statement doet helemaal niks, dit wordt gebruikt in een selectie, aangezien een selectie altijd wordt uitgevoerd kan het zijn dat je in een bepaald geval niks wil doen, dan gebruim je het statement skip.
abort:
Bij het uitvoeren van dit statement breekt het programma af.
Ik hoop dat het een beetje duidelijk is. Ik denk niet dat je op deze formele manier een algoritme moet schrijven, maar ik hoop dat dit een beetje aangeeft wat het idee is. Ik zal een voorbeeld geven van een minder formeel algoritme.
Stel je hebt een rij getallen die we f noemen (een soort functie). f.0 geeft het eerste getal, f.1 het tweede en f.(N-1) het laatste dan staan er dus N getallen in de rij. We gaan ervan uit dat N minimaal 1 is. We willen van deze getallen vinden wat het maximum is, hoe kunnen we dat doen. Redelijk eenvoudig, we lopen alle getallen na en als het getal groter is dan het vorige dan slaan we dit getal op, als we aan het einde komen, zal het getal wat opgeslagen het grootste getal zijn uit de rij getallen.
Formeel ziet dit er dan zo uit:
Als jij me kunt uitleggen wat voor soort getallen je zoekt kan ik je misschien nog verder helpen.
Je hebt een aantal verschillende statements en een programma (het recept, algoritme) bestaat uit meerdere atomaire statements. De verschillende statements zijn:
0. assignment (toewijzing)
1. skip (overslaan)
2. abort (afbreken)
3. catenation (koppeling)
4. selection (selectie)
5. repetition (repetitie)
Voordat we uitleggen wat deze statements zijn zal ik even vertellen wat variabelen zijn. Variabelen zijn containers die een waarde bevatten. Stel je declareert een variabele a dan kun je deze a aanroepen in je programma en er wordt dan gerekend met de waarde die a op dat moment bevat.
Assignment:
Stel we hebben een variabele a en we willen dat deze variabele de waarde 0 krijgt, dan schrijven we dit zo:
| 1 | a := 0 |
Willen we dat a de waarde van b krijgt, dan gaat dit zo:
| 1 | a := b |
En bijvoorbeeld a krijgt de waarde van a maal b:
| 1 | a := a*b |
Catenation:
Formeel:
P;Q betekent:
Voer eerst P uit dan Q, als P en Q statements zijn.
Stel we willen eerst dat a de waarde van b krijgt en b de waarde van a, dan doen we dit zo:
| 1 2 3 | c := a; a := b; b := c |
Waarom is
| 1 2 | a := b; b := a |
niet goed?
Selection:
In een algoritme wil je meestal ook een manier hebben om in het ene geval dit te doen en in het andere geval iets anders.
Formeel:
| 1 2 3 4 | if P -> A [] Q -> B [] R -> C fi |
P,Q,R zijn in dit geval predikaten en geen statements. Een predikaat is een uitspraak die afhankelijk van variabelen waar of niet waar is. Als dit wordt uitgevoerd dan wordt op een willekeurige manier 1 van de statements behorende bij de ware predikaten uitgevoerd. Met andere woorden, als P waar is dan kan A uitgevoerd worden, als Q waar is dan B etc. Let op: Er moet altijd een predikaat waar zijn, anders breekt het programma af. Voorbeelden van predikaten zijn:
True (altijd waar)
False (altijd onwaar)
x >= 0
a = b
1 = 2
(a-b)/c = (2*k)+x
Voorbeeld:
| 1 2 3 | if a >= b -> c := a [] b >= a -> c := b fi |
Wat doet dit programma?
Repetition:
Stel je wilt iets vaker doen dan 1x keer dan kun je dat middels een repetitie doen.
Formeel:
| 1 2 3 4 | do P -> A [] Q -> B [] R -> C od |
Zodra dit wordt uitgevoerd wordt gekeken of P,Q of R waar is, als een van de drie waar is, dan wordt 1 van de bij de ware predikaten behorende statements uitgevoerd. Na uitvoering wordt opnieuw gekeken of er een waar is, dit blijft zich herhalen tot ze allemaal onwaar zijn.
Voorbeeld:
Een programma dat a tot de macht b uitrekent:
| 1 2 3 4 | n := 0; do n <> b -> a := a * a; n := n + 1 od |
a wordt nu b maal met zichzelf vermenigvuldigd.
skip:
Dit statement doet helemaal niks, dit wordt gebruikt in een selectie, aangezien een selectie altijd wordt uitgevoerd kan het zijn dat je in een bepaald geval niks wil doen, dan gebruim je het statement skip.
| 1 2 3 | if A -> C [] B -> skip fi |
abort:
Bij het uitvoeren van dit statement breekt het programma af.
| 1 2 3 | if A -> B [] C -> abort fi |
Ik hoop dat het een beetje duidelijk is. Ik denk niet dat je op deze formele manier een algoritme moet schrijven, maar ik hoop dat dit een beetje aangeeft wat het idee is. Ik zal een voorbeeld geven van een minder formeel algoritme.
Stel je hebt een rij getallen die we f noemen (een soort functie). f.0 geeft het eerste getal, f.1 het tweede en f.(N-1) het laatste dan staan er dus N getallen in de rij. We gaan ervan uit dat N minimaal 1 is. We willen van deze getallen vinden wat het maximum is, hoe kunnen we dat doen. Redelijk eenvoudig, we lopen alle getallen na en als het getal groter is dan het vorige dan slaan we dit getal op, als we aan het einde komen, zal het getal wat opgeslagen het grootste getal zijn uit de rij getallen.
| 1 2 3 4 5 | n wordt 1; a wordt f.0 Zolang n <> N doe als f.n > a dan a wordt f.n, als f.n <= a dan doe niets |
Formeel ziet dit er dan zo uit:
| 1 2 3 4 5 6 | n := 1; a := f.0; do n <> N -> if f.n > a -> a := f.n [] f.n <= a -> skip fi od |
Als jij me kunt uitleggen wat voor soort getallen je zoekt kan ik je misschien nog verder helpen.
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Vraag: wat is de looptijd (Big-O notatie) van een algotritme dat voldoet aan de recurrente betrekking:
T(n) = 16T(n/2) + 9
?
T(n) = 16T(n/2) + 9
?
Memento Mori
recursief gedefinieerd dus?quote:Op zaterdag 16 juli 2005 23:02 schreef Lestat het volgende:
Vraag: wat is de looptijd (Big-O notatie) van een algotritme dat voldoet aan de recurrente betrekking:
T(n) = 16T(n/2) + 9
?
Het nationaal product is hetzelfde als een taart waar uiteraard iedereen recht op heeft, als overheden met geld smijten heet het investeren en als bedrijven investeren heet het een sprinkhanenplaag. McCarthy
is T(0) dan niet van belang? Of stond dat niet in de opgave?
Het nationaal product is hetzelfde als een taart waar uiteraard iedereen recht op heeft, als overheden met geld smijten heet het investeren en als bedrijven investeren heet het een sprinkhanenplaag. McCarthy
O(2log(n)). Je halveert n immers bij elke iteratie. Of wil je graag een nog preciezer bewijs hebben? .quote:Op zaterdag 16 juli 2005 23:02 schreef Lestat het volgende:
Vraag: wat is de looptijd (Big-O notatie) van een algotritme dat voldoet aan de recurrente betrekking:
T(n) = 16T(n/2) + 9
?
.
O(2log(n)) toch?
Edit: Dammit!
Edit: Dammit!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
.
Ik zou graag een precier bewijs willen, vanwege:
T(1) = 5
T(2) = 16 * T(2/2) + 9 = 89
T(4) = 16 * T(4/2) + 9 = 16 * 89 + 9 = 1433
T(8) = 16 * T(8/2) + 9 = 16 * 1433 + 9 = 22937
T(16) = 16 * T(16/2) + 9 = 16 * 22937 + 9 = 367001
etc.
Dus deze functie benadert de lijn 5.6n^4
Of doe ik iets gruwelijk fout?
T(1) = 5
T(2) = 16 * T(2/2) + 9 = 89
T(4) = 16 * T(4/2) + 9 = 16 * 89 + 9 = 1433
T(8) = 16 * T(8/2) + 9 = 16 * 1433 + 9 = 22937
T(16) = 16 * T(16/2) + 9 = 16 * 22937 + 9 = 367001
etc.
Dus deze functie benadert de lijn 5.6n^4
Of doe ik iets gruwelijk fout?
Memento Mori
Informeel kan ik het wel duidelijk maken. Stel je wil T(n) berekenen, dan zul je je antwoord staartrecursief moeten herleiden. De stappen waarin je dit doet zijn halveringen en dus krijg je in totaal 2log(n) stappen.
Voorbeeld:
T(1) = 5 (0 stappen, het antwoord is gegeven)
T(2) = 16 * 5 + 9 = 89 (1 stap)
T(16) = 16 * T(8) + 9 = 162 * T(4) + 18 = 163 * T(2) + 27 = 164 * T(1) + 36
De laatste is zoals je ziet 2log(16) = 4 stappen.
Edit: Op deze manier werkt de recursieve functie alleen voor tweede machten van gehele getallen trouwens of de / is eigenlijk een div (integer division).
Voorbeeld:
T(1) = 5 (0 stappen, het antwoord is gegeven)
T(2) = 16 * 5 + 9 = 89 (1 stap)
T(16) = 16 * T(8) + 9 = 162 * T(4) + 18 = 163 * T(2) + 27 = 164 * T(1) + 36
De laatste is zoals je ziet 2log(16) = 4 stappen.
Edit: Op deze manier werkt de recursieve functie alleen voor tweede machten van gehele getallen trouwens of de / is eigenlijk een div (integer division).
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Limburgs dierbaar oord!
Daar is mijn Vaderland,
Limburgs dierbaar oord!
Elke stap vergt nu O(2log(n)) rekentijd vanwege dat kwadraat in de recursie. Er zijn nog steeds 2log(n) stappen die je moet doen, dus de totale rekentijd isquote:Op zondag 17 juli 2005 15:31 schreef Lestat het volgende:
Hmm, wat maak je dan van dezelfde vraag maar dan met T(n) = 8T(n/2) + n^2 ?
O((2log(n))2).
Volgens het boek is het O(n^3), via het Master Theorema. Strikt genomen klopt dat natuurlijk wel.
Memento Mori
Ik heb het volgende sommetje
xx = 1000. Wat is x?
Nu kan ik dit natuurlijk wel iteratief (tussen 4.5 en 4.6) oplossen, maar er moet toch een elgantere manier zijn? Of kan dit alleen mar numeriek?
xx = 1000. Wat is x?
Nu kan ik dit natuurlijk wel iteratief (tussen 4.5 en 4.6) oplossen, maar er moet toch een elgantere manier zijn? Of kan dit alleen mar numeriek?
Volgens mij is zoiets enkel numeriek oplosbaar. Ik heb net zelf wat lopen proberen, maar je komt steeds weer op een dood spoor terecht.
Grafische rekenmachine:quote:Op donderdag 21 juli 2005 18:01 schreef SVDL het volgende:
Ik heb het volgende sommetje
xx = 1000. Wat is x?
Nu kan ik dit natuurlijk wel iteratief (tussen 4.5 en 4.6) oplossen, maar er moet toch een elgantere manier zijn? Of kan dit alleen mar numeriek?
xx = 1000
Formule 1: y = xx
Formule 2: y = 1000
dan met calculate - intersection het snijpunt berekenen.
Bij x = 4,5555357
xx = 1000
Inderdaad, dit is het makkelijkst. Maar volgens mij was de vraagsteller inmiddels ook wel zoverquote:Op dinsdag 26 juli 2005 16:40 schreef NostraBramus het volgende:
[..]
Grafische rekenmachine:
xx = 1000
Formule 1: y = xx
Formule 2: y = 1000
dan met calculate - intersection het snijpunt berekenen.
Bij x = 4,5555357
xx = 1000
Beetje laat, maar toch .quote:Op woensdag 29 juni 2005 17:03 schreef Alter_Ego het volgende:
Welke stoffen worden hier bij elkaar gedaan?
http://www.ebaumsworld.com/marshmallow.html
Waterstofperoxide (weet niet welke concentraties, heel laag iig) en bloed.
Woei!
Ben bang van wel. Je moet dan denken aan bv de Newton Raphson methode. Verder dan x*log(x)=log(1000) kom ik ook niet.quote:Op donderdag 21 juli 2005 18:01 schreef SVDL het volgende:
Ik heb het volgende sommetje
xx = 1000. Wat is x?
Nu kan ik dit natuurlijk wel iteratief (tussen 4.5 en 4.6) oplossen, maar er moet toch een elgantere manier zijn? Of kan dit alleen mar numeriek?
Zit met een wiskundig probleem, een zogenaamd transportprobleem.
een ondernemer heeft in O 50 ton en in C 40 ton graan opgeslagen.
Zijn klant in D kocht 20 ton, in M 36 ton en in N 34 ton.
Kosten van O naar D: 42
Kosten van O naar M: 55
Kosten van O naar N: 60
Kosten van C naar D: 36
Kosten van C naar M: 47
Kosten van C naar N: 51
Nu moeten de tonnen graan tegen zo laag mogelijke kosten naar de klanten.
Noem hierbij de hoeveelheid van O --> D: x
Noem hierbij de hoeveelheid van O --> M: y
Concluderend kan je de hoeveelheid van O --> N 50-x-y noemen.
Van C --> D: 20-x
Van C --> M: 36-y
Van C --> N: 34-(50-x-y) = -16-x-y = 16+x+y
En nu loop ik vast. Heb het al uitgetekend. Heb al 10 dingen geprobeerd, maar ik kom er niet meer uit. Het is vast heel simpel, maar of ik ben te of ik ben gewoon .
Hoop dat een van jullie me kan helpen! Thanks in advance!!!
Grtz Bram
een ondernemer heeft in O 50 ton en in C 40 ton graan opgeslagen.
Zijn klant in D kocht 20 ton, in M 36 ton en in N 34 ton.
Kosten van O naar D: 42
Kosten van O naar M: 55
Kosten van O naar N: 60
Kosten van C naar D: 36
Kosten van C naar M: 47
Kosten van C naar N: 51
Nu moeten de tonnen graan tegen zo laag mogelijke kosten naar de klanten.
Noem hierbij de hoeveelheid van O --> D: x
Noem hierbij de hoeveelheid van O --> M: y
Concluderend kan je de hoeveelheid van O --> N 50-x-y noemen.
Van C --> D: 20-x
Van C --> M: 36-y
Van C --> N: 34-(50-x-y) = -16-x-y = 16+x+y
En nu loop ik vast. Heb het al uitgetekend. Heb al 10 dingen geprobeerd, maar ik kom er niet meer uit. Het is vast heel simpel, maar of ik ben te of ik ben gewoon .
of ik ben gewoon 
.Hoop dat een van jullie me kan helpen! Thanks in advance!!!
Grtz Bram
heb je de doelfunctie al?
Het nationaal product is hetzelfde als een taart waar uiteraard iedereen recht op heeft, als overheden met geld smijten heet het investeren en als bedrijven investeren heet het een sprinkhanenplaag. McCarthy
Verdomme, dat heb ik dit jaar nog gehad...quote:Op donderdag 28 juli 2005 22:36 schreef NostraBramus het volgende:
Hoop dat een van jullie me kan helpen! Thanks in advance!!!
Grtz Bram
Minimal costs.quote:Op donderdag 28 juli 2005 22:44 schreef McCarthy het volgende:
heb je de doelfunctie al?
Alles moest zelf op te stellen zijn uit dit probleem...
