Opgeloste DT opgaven

ex[datum]
examen
nrpo
nieuwe reeks prolog opgaven
oefzXgoY
oefenzitting X, gequoteerde oefening reeks Y
rho
reeks haskell opgaven

Opmerkingen

De meeste oplossingen zijn waarschijnlijk wel correct. Sommigen zijn echter inefficient geschreven en eindigen niet in een redelijke tijd.

Algemene oplossingsmethodes

Zoek een uitdrukking die voldoet aan ...

Prolog

Dit kan zeer eenvoudig opgelost worden in prolog: leg alle voorwaarden op (= generate and test) en prolog zal voor jou backtracken.

Haskell

Gelijkaardig als in prolog, maar de constraints (generate & test) zet je in het rechterdeel van een list comprehension. Je zal met deze methode sowieso een lijst van (alle) oplossingen krijgen. Achteraf kan je het eerste element selecteren met head. Dit is niet inefficiënt, want Haskell evalueert op een luie manier. Je kan een list comprehension ook gemakkelijk opsplitsen over verschillende functies.

Zoek de optimale uitdrukking die voldoet aan ...

Methode 1: zoek & sorteer

Deze methode is equivalent voor haskell en prolog:
  1. Maak een generator g (zie oplossing van het vorige type probleem).
  2. Maak een heuristiek h die de optimaliteit van de oplossing geeft.
  3. Maak een lijst van koppels (H,G) waarbij G een gegenereerde oplossing is en H de heuristische waarde ervan. In prolog gebruik je findall, in haskell gebruik je list comprehension.
  4. Sorteer deze lijst en neem het eerste (of laatste) element. De ingebouwde sort (zowel prolog als haskell) kan overweg met het sorteren van tuples. In prolog worden bovendien de dubbels verwijderd.

Indien er meerdere criteria zijn, kan je de koppels uitbreiden tot (H1, H2, ..., G) waarbij H1 voorrang heeft op H2.

Methode 2: iterative deepening

De vorige methode zal enkel werken wanneer de oplossingsruimte eindig is, wat niet altijd het geval is. Een mogelijke oplossing hiervoor is gebruik maken van iterative deepening. Hierbij maak je weer gebruik van het vorige probleem, waar je nog een extra voorwaarde oplegt: een bovengrens van de heuristiek. Deze mag je niet enkel op het einde controleren, want dan bekom je methode 1 die mogelijks niet zal eindigen in oneindige oplossingsruimtes.

Stel dat de waarde van de heuristiek zo klein mogelijk moet zijn, zoek je eerst voor oplossingen met waarde 0, dan 1, etc. In prolog zal je zo alle oplossingen overlopen, beginnend met de beste. In haskell zal je een lijst krijgen van alle beste oplossingen.

Vergeleken met methode 1 heb je bij het genereren eerst de beste oplossingen gemaakt, zodat de oplossingen op voorhand gesorteerd zijn. Dit wil zeggen dat je niet meer moet sorteren en dus moet je ook niet alle oplossingen kennen.

Het nadeel van deze methode ligt in het 'genereren van oplossingen met een bepaalde heuristische waarde'. Het kan zijn dat de kans om een bepaalde waarde te hebben zeer klein is. De opeenvolgende generaties kunnen veel dubbel werk opleveren.

[ICO]NameLast modifiedSizeDescription

[PARENTDIR]Parent Directory  -  
[TXT]nrpo-cycle.pl2004-06-25 01:58 531  
[TXT]rho1.hs2004-06-25 01:58 3.4K 
[TXT]ex20030616am.hs2004-06-25 01:58 2.9K 
[TXT]ex20030616am.pl2004-06-25 01:58 759  
[TXT]ex20030616pm.hs2004-06-25 01:58 1.5K 
[TXT]ex20030616pm.pl2004-06-25 01:58 2.4K 
[TXT]ex20030618am.hs2004-06-25 01:58 3.6K 
[TXT]ex20030618am.pl2004-06-25 01:58 1.6K 
[TXT]ex20030618pm.hs2004-06-25 01:58 1.8K 
[TXT]ex20030618pm.pl2004-06-25 01:58 1.6K 
[TXT]nrpo-powers.pl2004-06-25 01:58 643  
[TXT]rho5.hs2004-06-25 01:58 1.6K 
[TXT]rho6.hs2004-06-25 01:58 642  
[TXT]rho7.hs2004-06-25 01:58 279  
[TXT]ex20030825am.hs2004-06-25 01:58 2.4K 
[TXT]ex20030825am.pl2004-06-25 01:58 1.9K 
[TXT]haskell.hs2004-06-25 01:58 3.5K 
[TXT]nrpo1.pl2004-06-25 01:58 2.2K 
[TXT]nrpo2.pl2004-06-25 01:58 1.0K 
[TXT]nrpo5.pl2004-06-25 01:58 706  
[TXT]nrpo6.pl2004-06-25 01:58 2.7K 
[TXT]nrpo7.pl2004-06-25 01:58 277  
[TXT]ex20030825pm.hs2004-06-25 01:58 1.6K 
[TXT]ex20030825pm.pl2004-06-25 01:58 1.6K 
[TXT]nrpo-codegen.pl2004-06-25 01:58 1.4K 
[TXT]nrpo-compress.pl2004-06-25 01:58 1.0K 
[TXT]nrpo-spiral.pl2004-06-25 01:58 1.8K 
[TXT]nrpo5bis.pl2004-06-25 01:58 619  
[TXT]oefz3go2.pl2004-06-25 01:58 262  
[TXT]oefz4go1.pl2004-06-25 01:58 432  
[TXT]oefz4go2.pl2004-06-25 01:58 1.0K 
[TXT]oefz4go3.pl2004-06-25 01:58 618  
[TXT]oefz4go4.pl2004-06-25 01:58 617