Övning 4

Mål:

  • Kunna beskriva en graf som grannmatris och grannlista samt rita upp den.
  • Kunna avgöra när en grannmatris respektive grannlista ger effektivast lagring.
  • Känna till vad som karakteriserar ett problemträd (specialfall av graf).
  • Kunna rita upp de första noderna i ett problemträd utgående från en problembeskrivning.
  • Kunna avgöra när breddenförstsökning respektive djupetförstsökning kan användas för att lösa ett problem, och vilken som är lämpligast.
  • Kunna beskriva breddenförstsökning respektive djupetförstsökning för ett givet problem.
  • Kunna implementera breddenförstsökning och djupetförstsökning.
  • Kunna demonstrera hur en heap fungerar internt vid insättning och uttagning, både med trädrepresentation och vektorrepresentation,
  • Känna till tidskomplexiteten för heap-operationer,
  • Avgöra om bästaförstsökning är lämplig givet ett problem,
  • ...samt kunna beskriva algoritmen översiktligt

Ta en titt på Labb 4 och Labb 5

Dessa två labbar är delar av samma uppgift. Glöm inte att göra förberedelseuppgifterna - dom ska också redovisas.

  • Finn kortaste vägen från ett ord till ett annat genom att byta ut en bokstav i taget. Exempel:
    söt -> söm -> döm -> dum -> dur -> sur
  • I labb 4 ska du skriva ett program som avgör om det finns en väg eller inte.
    • Funktionen makechildren ska systematiskt gå igenom alla sätt att byta ut en bokstav
      i startordet (aöt, böt, ..., söö), kolla att det nya ordet finns i
      ordlistan men inte finns i gamla och i så fall skriva ut det nya ordet på
      skärmen och lägga in det i gamla.
    • För fortsatt genomgång av söts barnbarn osv behövs den köklass LinkedQ som du skrev i labb 2, kortkonstlabben. Importera den och skapa kön q. I stället för att skriva ut barnen på skärmen ska nu makechildren() lägga in dom i kön.
  • I labb 5 ska du sedan skriva ut vägen.
    • I stället för att bara lagra själva orden i kön så inför vi ParentNode-objekt som innehåller både ett ord och en pekare. Om pekarna sätts rätt kan vi följa dom för att skriva ut vägen.

Grannmatriser och grannlistor (inför Labb 4)


Graf lagrad på olika sätt

A B C D E F
A 8 5 6
B 2
C 3
D 1
E 4
F

Rita upp den graf som grannmatrisen ovan representerar. Skriv också upp motsvarande grannlistor. Vilken representation är mest sparsam?

Download lösning


Problemträd: breddenförst och djupetförst (inför Labb 4 & 5)


Strykord

Ordet orkan är ett strykord eftersom man kan stryka sista bokstaven om och om igen och bara få riktiga ord. orkan - orka - ork - or - o Uppgiften är att finna det längsta strykordet i svenska språket. Ordlistan finns på fil. Rita problemträdet och jämför olika tänkbara algoritmer.

lösning

lösning (kod från övning) Links to an external site.


Sjuor till hundra

Det gäller att skriva talet 100 med enbart sjuor och dom fyra räknesätten, till exempel så här.

7 +7 /7 *7 *7 = 98 

Det var ett gott försök som inte nådde ända fram. För att man ska få använda / måste divisionen gå jämnt ut.

a) Rita problemträdet och diskutera bästa algoritm för att avgöra OM problemet är lösbart.

b) (Kommer på nästa övning) Om man dessutom vill veta hur lösningen ser ut krävs en mer komplicerad datastruktur. Beskriv den och skissa ett program.

lösning

a) lösning (kod från övning) Links to an external site.

b) lösning med utskrift (kod från övning) Links to an external site.

 

Heap (inför KS3)

Heap på vektorform och trädform

På vektorform ser heapen ut så här:

10 40 30 42 41 48 50 49
  1.  Är detta en min-heap eller en max-heap? 
  2.  Rita upp heapen på trädform.
  3.  Rita steg för steg hur det ser ut när man plockar ut två element.
  4.  Vad är tidskomplexiteten för att plocka ut ett element?
  5.  Stoppa in de nya värdena 80 och 17.
  6.  Vad är tidskomplexiteten för att stoppa in n element?
  7.  Visa hur heapen nu ser ut på vektorform.
  8.  Vilka skillnader finns mellan en heap och ett binärt sökträd?

                              


Fler problemträdsuppgifter


  1. Labyrint

    Tilda går ensam omkring i en labyrint, hennes kompisar har redan hittat ut. Det finns gångar och korsningar. En del gångar är blindgångar. Vid varje korsning kan man gå åt höger eller vänster alternativt gå tillbaka dit man kom ifrån. Tilda bestämmer sig för att hålla till höger i varje korsning tills hon hittar utgången. Vad kallas en sådan sökalgoritm? Väl hemma bestämmer sig Tilda för att skriva ett program som hittar vägen genom en labyrint. Vad behöver man för datastrukturer för att implementera en sådan algoritm?

    animation av labyrint Links to an external site.


  2. Taltävling

    Under sommaren har det gått en tävling i radio där det gäller att så snabbt som möjligt hitta ett tal som uppfyller två villkor. Första villkoret, som gäller hela tävlingen, är att siffrorna i talet måste vara strikt stigande (23578 är OK men inte 235578 eller 23587). Andra villkoret är nytt för varje dag och kan t ex vara att talet ska vara ett primtal, jämnt delbart med 599 eller en tvåpotens. Beskriv utförligt en breddenförst- eller djupetförstsökning (effektivare metod ger fler poäng) som hittar det minsta talet som uppfyller villkoren. Vilka klasser och metoder behövs?


  3. Patiens

    I patiensen "Rutan" använder man bara ess, kungar, damer och knektar, alltså sexton kort. Det gäller att lägga ut korten i en 4x4-matris så att två kort av samma färg eller valör aldrig finns i samma rad, kolumn eller någon av de båda diagonalerna. Man vill att ett program ska skriva ut alla lösningar till patiensen på nedanstående sätt.

          hj E   sp D   kl Kn  ru K
          kl K   ru Kn  hj D   sp E
          ru D   kl E   sp K   hj Kn
          sp Kn  hj K   ru E   kl D
    

    Du behöver inte skriva programkod, men du ska förklara algoritmen utförligt och beskriva datastrukturer, metoder och klasser.


  4. Sudoku

    Sudoku är ett spel som består av ett rutnät på 9x9 rutor, uppdelat i nio 3x3-rutor. Rutnätet har n siffror ifyllda från början och det gäller att fylla varje rad, varje kolumn och varje 3x3-ruta med siffrorna 1-9. En siffra får aldrig förekomma mer än en gång per rad, kolumn och 3x3-ruta. Beskriv en algoritm som hittar en lösning till ett givet Sudoku-problem, och tala om hur algoritmen skulle kunna implementeras.


  5. Pokémontränaren

    Du är så uppskattad i ditt arbete som pokémontränare att du kan välja och vraka bland erbjudandena. Givet ett antal förslag (anbudsgivare, startdag, slutdag, arvode) vill du planera nästa månad så att den blir så lönsam som möjligt. Rita först upp problemträdet (roten och några noder i de första två nivåerna räcker). Föreslå en algoritm som finner det schema som ger störst inkomster. Motivera ditt val av algoritm och beskriv hur du skulle implementera algoritmen.


  6. Aliententan 2015-03-20, uppgift 5 (betyg E)

    När rymdvarelserna reser använder de sig av maskhål (Einstein-Rosen-brygga aka wormhole) vilka förbinder två platser i rymden. De har en förteckning (graf) över vilka platser som är förbundna med varandra (det kan finnas fler än ett maskhål vid en plats). För att räkna ut en rymdfärdplan med så få maskhålsanvändningar som möjligt använder de följande algoritm tillsammans med maskhålsförteckningen samt en kö.

    • 1) Lägg startmaskhålet tillsammans med en tom föräldrareferens i en kö
    • 2) Plocka ut nästa maskhål och föräldrareferens ur kön och
    • 3) Om detta är destinationsmaskhålet:
      • a) Skicka föräldrareferens och maskhålet till en rekursiv färdutskriftsmetod som skriver ut reshoppsvägen:
      • b) Avsluta
    • 4) Annars:
      • a) Slå upp vilka andra maskhål som är förbundna med detta maskhål och lägg respektive nytt maskhål tillsammans med en föräldrareferens till detta maskhål i kön
    • 5) Upprepa från punkt 2.

    Rymdvarelserna berättar att algoritmen fungerar ibland men ibland är det som att de bara hoppar runt mellan samma platser utan att komma fram.

    • Vad är det som är problemet med deras algoritm?
    • Förbättra algoritmen så att problemet löses!
    • Vad kallas algoritmen?

  7. SL-tentan 2014-03-18, uppgift 2 (betyg E)

    Paris pendel- och tunnelbana är ett virrvarr av olika stationer som står i förbindelse med varandra. Beskriv översiktligt en effektiv algoritm som räknar ut en resväg från en station till en annan med så få stationsstopp som möjligt. Att byta linje på en station räknas som ett stopp. 


  8. Arkitektur bygger slott (C-uppgift från Tildatenta 2018-06-07)

    Ett magiskt sagoslott har många rum som är förbundna med varandra. En del rum angränsar till väldigt många rum och andra rum gränsar bara till ett enda. Ibland så ändras planlösningen magiskt. Det som händer då är att antingen så försvinner en förbindelse mellan två rum eller så tillkommer en ny förbindelse mellan två rum.

    • addVertex(node) Lägger till hörnet node till grafen.
    • addEdge(node1, node2) Drar en kant mellan hörnen node1 och node2.
    • v = getVertex(key) Hittar det hörn som har nyckeln key
    • vlist = getVertices() Returnerar en lista med alla hörn.

    En tildastudent får uppdraget att lagra hur rummen är förbundna med varandra i en graf. Man ska kunna

    • se om två rum är förbundna med varandra,
    • se vilka rum som är förbundna med ett givet rum,
    • uppdatera grafen när magi inträffar (rumsförbindelse försvinner/tillkommer).

    a) Rita och beskriv kortfattat hur grafen kan representeras som en grannlista.

    b) Rita och beskriv kortfattat hur grafen kan representeras som en grannmatris.

    c) Jämför grannlista och grannmatris med avseende på prestanda och minnesåtgång för de tre punkterna ovan.

    lösningsskiss (se uppg 8 C)


Uppgifter för eget arbete

  1. Billigaste hörlurarna

    Dina hörlurar har gått sönder (igen!) och du måste köpa nya. Som vanligt letar du efter de allra billigaste.
    1. Lägg in de olika priserna i en min-heap. Rita heapen på trädform i varje steg.
    2. Plocka nu ut den billigaste, och visa hur heapen förändras.
  2. Oturstentan 23 oktober 2015, uppgift 4 (betyg E)

    Att använda rätt datastruktur till algoritmen handlar mer om kunskap än tur. Skriv upp tre olika korrekta meningar givet alternativen nedan: Vid [breddenförstsökning/bästaförstsökning/djupetförstsökning] är det lämpligt att använda en [prioritetskö/kö/stack].
  3. Prioritetskö betyg C (Tildatenta 6 april 2016)

    En prioritetskö (heap) brukar implementeras med en vektor som representerar ett träd. Barnen och föräldrar kommer man åt via matematiska funktioner (2*N, 2*N+1, N/2). Antag att man istället implementerar prioritetskön med ett pekarbaserat binärt träd.

    class Nod: 
    def __init__(self, d, p, l = None, r = None):
    self.data = d
    self.parent = p #föräldern
    self.left = l #vänsterbarnet
    self.right = r #högerbarnet ...

    class Heap:
    def __init__(self):
    self.first = None # pekar ut första (mest prioriterade) elementet
    self.last = None # pekar ut sista elementet ...

    Antag en heap om 1000 element. Jämför implementationerna med avseende på

    Prestanda

    Minnesåtgång

    Alla operationer (tilldelning, multiplikation etc) kan antas kosta ett (1 i någon enhet) och alla enstaka minnesplatser kan antas vara lika stora.

  4. TJUGONDAG KNUT KASTAS JULEN UT (Tildtenta 16 januari 2001)

    För att kontrollera sanningen i detta talesätt har man i en fil samlat tre miljoner datum för svenska julgranars utkastning. Man vill veta mediandatum, alltså det datum då hälften av granarna slängts ut, ut, ut och hälften ännu står gröna och granna i stugan.

    Rangordna följande sex föreslagna metoder efter deras effektivitet. Binärsökning, hashning, insättningssortering, distributionsräkning, djupet-först-sökning, trappsortering (heap sort).

    lösning

  5. SKATTEREGISTRET

    Riksskatteverkets databas med nio miljoner svenskar finns sorterad på efternamn. Man vill sortera om den på personnummer. Hur många jämförelser krävs med quicksort? Hur många med den bästa metoden?

    lösning