WINAK

In reeks 2 wordt er gevraagd hoe je een vermenigvuldiging inplementeerd met een DMTT, heeft er iemand dat is helemaal uitgewerkt? En wa is dan de tijd/plaats complexiteit daarvan?

slimmy wrote:In reeks 2 wordt er gevraagd hoe je een vermenigvuldiging inplementeerd met een DMTT, heeft er iemand dat is helemaal uitgewerkt? En wa is dan de tijd/plaats complexiteit daarvan?

Euh ik heb da hier erges ligge, ge moest da ni implementeren he, gewoon uitleggen hoe get zou doen.

Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

Robbe wrote:Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

dat zijn ze ongeveer, enkele zijn wel verouderd.. en hij heeft nog enkele dinges in de les op bord geschreve.

Shinta wrote:

Robbe wrote:Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

dat zijn ze ongeveer, enkele zijn wel verouderd.. en hij heeft nog enkele dinges in de les op bord geschreve.

Iets da hier het vermelden waard is?

reeks 7
voor oef2 heb ik: Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?


reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

Robbe wrote:reeks 7
voor oef2 heb ik:

Code: Select all

begin

    Queue := leeg

    Som := 0

    for j := 1 to n do

        Input[j] vooraan in Queue

        Som += Input[j]

        while Som > 10 do

            Som -= laatste element van Queue

            verwijder laatste element uit Queue

        od

        if Som = 10 then stop fi

    od

end

Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?

reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

dijkstra is dat deel dat we niet moeten kennen
edit: en langs de andere kant moet ge da toch nog kunnen van netwerken vorig jaar dus das toch geen probleem

Norfolk wrote:edit: en langs de andere kant moet ge da toch nog kunnen van netwerken vorig jaar dus das toch geen probleem

ni da'k da ni kan, maar ik moet het wel nog eens opfrissen dan

Robbe wrote:reeks 7
voor oef2 heb ik:

Code: Select all

begin

    Queue := leeg

    Som := 0

    for j := 1 to n do

        Input[j] vooraan in Queue

        Som += Input[j]

        while Som > 10 do

            Som -= laatste element van Queue

            verwijder laatste element uit Queue

        od

        if Som = 10 then stop fi

    od

end

Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?


reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

De body van die while lus wordt hoogstens n -1 keer uitgevoerd. Dit is als er geen substring gevonden wordt. (Wel iets minder dan n -1 keer omdat de laatste 2 getallen ook onder 10 kunnen liggen enzo)
Hiermee bedoel ik ook dat de body van de while lus IN TOTAAL hoogstens n - 1 keer uitgevoerd wordt
De for lus ook n keer. Dus dat wordt 2n keer en dus O(n).


Heeft er iemand een oplossing voor dat algoritme van kortste paden voor een graaf met mogelijk negatieve kosten op zijn kanten?

Norfolk wrote:De body van die while lus wordt hoogstens n -1 keer uitgevoerd. Dit is als er geen substring gevonden wordt. (Wel iets minder dan n -1 keer omdat de laatste 2 getallen ook onder 10 kunnen liggen enzo)
Hiermee bedoel ik ook dat de body van de while lus IN TOTAAL hoogstens n - 1 keer uitgevoerd wordt
De for lus ook n keer. Dus dat wordt 2n keer en dus O(n).


Heeft er iemand een oplossing voor dat algoritme van kortste paden voor een graaf met mogelijk negatieve kosten op zijn kanten?

ja secondje .

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

Shinta wrote:waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

Die while-lus wordt maar hoogstens 2 keer uitgevoerd omdat het laatst ingelezen getal de som hoogstens op 12 brengt, omdat anders een match werd aangeduid in de vorige iteratie van de for.

Robbe wrote:

Shinta wrote:waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

Die while-lus wordt maar hoogstens 2 keer uitgevoerd omdat het laatst ingelezen getal de som hoogstens op 12 brengt, omdat anders een match werd aangeduid in de vorige iteratie van de for.

wtf :s agij 111119 hebt, dan ebde

1
2
3
4
5
14
WHILELUS:
1: 13
2: 12
3: 11
4: 10

=> 19 is match

ik denk da gij een andere opgave hebt, want bij mij is het alfabet maar {1,2,3}

neen wij hebben zelfde maar ja uw algoritme blijft hetzelfde en dan nog kan de while lus meer dan 2 keer doorlopen worden hoor
vb. 333333333322222
3322 zal de substring zijn dus while wordt 8 keer doorlopen