Denne sida redigeres av gruppelærer, og innholdet er ikke pensum men kan være til hjelp med å tilegne seg dette (noen ganger for normalt interesserte og noen ganger for spesielt interesserte). Det blir kanskje mest en slags uformell gruppelærerblogg, så sjekk innom nå og da.
7. desember: Om løsningforslag for resten av obligene
Når det gjelder løsningsforslag for andre ting på obligene så har det ikke vært så mye av det, og jeg har ikke tenkt å bruke tid på det siden det står såpass mye i notater etc.
Det dere kan gjøre istedet er å spørre meg dersom det er noe dere ville likt å se en annen løsning enn deres egen på (kode eller tekst), så kan jeg se om jeg kan sende over noe passende (fra min egen levering eller at jeg spør noen andre, avhengig av hva jeg synes om min egen...).
Ellers er det bare å spørre om ting fram til eksamen (møt helst opp på gruppetimen men bare send epost hvis du ikke kan da).
29. november - Løsningsforslag oppgave 2, oblig 3
Jeg fikk lov av Daniel Nebdal å legge ut hans løsning på oppgave 2 .
20. november - Tilbakemelding for oblig 3
Som forrige gang har jeg lagd et notat og noen ressurser som kan lastes ned. Inputfiler for testing tilgjengelig på ~inf3130-området (se nyhetene) så jeg har ikke gjort noe med disse.
- Notat (versjon 2)
- Java-kode med datastrukturer etc. som referert til i notatet (men uten selve algoritmen).
- Eksempeloutput . Med forbehold om feil, disse er med for at en kan få en slags anelse om typisk antall states på en rett-fram implementasjon. Merk at om du får en del større trenger ikke det bety feil, det kan bety at en har en annen rekkefølge med mindre flaks på vilkårlige operasjoner (dvs. hvilken rekkefølge like dyre states blir tatt i, dette påvirkes både av itereringsrekkefølge og prioritetskøimplementasjon).
18. november - Tips til A*-implementasjon
Siden folk spør vil jeg gi et par tips her om implementasjon av A*-søk. Ikke les dette om du vil komme fram til alt selv.
Som nevnt må en prioritetskø inngå, men det er ikke nok. En må også, i det minste, ha informasjon om hvorvidt en tilstand allerede er besøkt, om den ligger på køen, eller om den aldri er besøkt før. Under kommer mitt forslag (men det finnes sikkert andre måter):
- Lag en State-klasse som foruten brettet inneholder posisjonen til 0-en (så en slipper å søke etter denne), foreldrepeker (hvilket State-objekt kom en fra), muligens hvilken retning en kom inn i brettet fra (ikke nødvendig men gjør utskrift lettere), og en eller annen informasjon som sier noe om prioritetskøstatus (mer nederst, dette avhenger av køen).
- Definer hashCode og equals-metodene. Et forslag da er:
class State { ...
byte [] board; ... ...
public int hashCode() {
int result = 0;
for (int i = 0; i < board.length; ++i) {
result = result * 29 + board [i] ;
}
return result;
}
...osv
} - I A*-funksjonen har en så en HashMap<State, State>. Denne fungerer for å "kanonalisere" states. Si at vi står i state x og ønsker å flytte oss ett skritt til høyre. Da lager vi en ny state y utifra x (lag et nytt state-objekt med utgangspunkt i x, men med nullstilt visited/prikø/parent-info).
- Deretter slår en opp i sin HashMap med y som nøkkel for å se om en state med tilsvarende brett er besøkt før, og i såfall erstatter vi referansen vi har til y med denne. Dersom den ikke ligger i HashMap'en legger en den inn.
- I begge tilfeller vil en sitte med et State-objekt som er unik for den staten en er i og det samme "hver gang", så en kan da fritt lagre eller se på parent-informasjon, hvorvidt den er sett allerede eller ligger på køen og så videre.
Til slutt litt om hva som bør ligge i staten angående prioritetskøen. En kan jo se på om det er mulig å klare seg uten noen informasjon og "slutte seg fram til fra kostnader" at den ikke kan ligge i køen (for å være ærlig husker jeg det ikke i øyeblikket). Ellers kan en ha en boolean som sier hvorvidt den ligger på køen (og dersom ikke er den allerede besøkt, siden usette noder ikke eksisterer i minnet). Men mest avansert, dersom en bruker en binomialheap, Fibonacciheap, lenket list eller lignende er det å la nok informasjon ligge i staten til at en kan finne fram til objektet i prioritetskøen på O(1) tid, dette vil kutte litt kjøretid. For eksempel: Dersom en bruker en hjemmelaget binomialheap, kan en lagre indeksen en State ligger lagret med som en variabel i State-objektene (og oppdatere disse underveis). Dersom en da må gjøre en decreaseKey så kan denne gjøres på O(log n) siden en kan hoppe direkte til der objektet ligger.
Fotnote 1: Purister vil nå klage litt på hvordan jeg bruker equals; disse skal få lov til å implementere Board som en separat klasse som brukes som nøkkel i hashmapen, og la State bare holde en referanse til Board. Tilsvarende kan en ha en egen StateInPriQueue-klasse som bare har en referanse til State dersom en er veldig redd for å blande sammen flere ting i en klasse. Men jeg anbefaler det ikke.
17. november: Noe jeg kom over om NP=P osv.
Uten å gå god for innholdet på noen måte (spør Dino :-) ) vil jeg linke til denne (lettlest og populært skrevet bloggpost):
http://scottaaronson.com/blog/?p=266
Den er generelt skeptisk til at kvantedatamaskiner etc. kan løse NP-komplette problemer. Et lite utdrag:
If quantum computers can’t solve NP-complete problems in polynomial time, it raises an extremely interesting question: is there any physical means to solve NP-complete problems in polynomial time?
Well, there have been lots of proposals. One of my favorites involves taking two glass plates with pegs between them, and dipping the resulting contraption into a tub of soapy water. The idea is that the soap bubbles that form between the pegs should trace out the minimum Steiner tree (...)
(...)
Long story short, I went to the hardware store, bought some glass plates, liquid soap, etc., and found that, while Nature does often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs.
15. november: Noen merknader til oblig 3
- Ordet "gjenkjenner" (som i L_2 = { M | M gjenkjenner L_1 }) skal forstås som det vi har definert som "decides". Altså: L_2 består av de Turing-maskiner som er sånn at de svarer Y for input "010" og N for andre input.
5. november: Buildscript er fint (off-topic)
(Dette er ikke veldig relevant for dette kurset. INF3330/INF4330 har mye mer om sånt noe som dette, dvs. "hvordan jobbe effektivt").
Dette er et tips inspirert av at folk glemmer å kopiere over filer til riktig mappe osv. når de leverer. Sett at du kjører følgende mappestruktur:
- kontoen-min/inf3130/oblig2/
-- masse rot og oblig2.pdf
-- oppgave1
--- masse rot og Oppgave1.java
-- oppgave2
--- masse rot og Oppgave2.java
Da kan det ikke undervurderes å lage et bittelite buildscript. Poenget er ikke nødvendigvis å gjøre ting raskere, men å gjøre ting mer etterettelig (etterhvert som en får trening går det på omtrent samme tid som å gjøre det manuelt, samtidig som en kan roe seg ned med å lure på om en kopierer de rette filene osv.).
Eksempel på innhold:
1. slett mappen "target" om den finnes, for å garantere ferskhet
2. lag mappen target, med undermappen som skal pakkes
3. kopier relevante filer
4. gjør pakkinga
På Unix blir det noe sånt som:
OBLIGNAME=oblig2_dagss
[ -d target ]
&& rm -rf target
mkdir -p target/$OBLIGNAME
cp oblig2.pdf */*.java target/$OBLIGNAME
( cd target && tar czf $OBLIGNAME.tar.gz $OBLIGNAME )
På Windows følger det også skriptspråk med (+ Python fungerer fint til sånt og er veldig lett å legge inn på Windows).
1. november: Om gruppetimene framover
Som de fleste har fått med seg skifter kurset nå over til en annen modus:
- Det dreier seg ikke lenger om å lære seg enkeltalgoritmer men om å tilegne seg nye modelleringsverktøy.
- Hittil har hvert tema vært noenlunde selvstendig og vart ca. en uke. Nå blir det en større sammenhengende bolk på fire forelesninger der en er nødt til å få med seg starten for å kunne henge med på slutten - det går (tror jeg?) ikke an å hoppe over noe her.
- Jeg tror flere vil være enige med meg i at vanskelighetsgraden nå stiger et par hakk (men det er jo litt subjektivt).
Derfor vil også gruppetimene endre karakter noe. Hittil har det gått nokså greit å komme på gruppetime og få ting forklart selv om en ikke har vært på forelesning, men fra nå av må jeg forutsette at folk har vært på forelesningene eller lest det som var stoffet. (Dette betyr ikke at en må forstå alt før gruppetimen, men en bør ha det store bildet og vite litt hvilke deler en trenger å tenke mer på).
Dersom du må droppe en forelesning men møter på gruppen vil jeg derfor forutsette at du har lest den relevante biten i kompendiet til Dino før gruppetimen. Det som er pensum er spredd utover i hele kompendiet (annenhver side noen steder, pga fortetning og forenkling), så du må samtidig se på foilene for forelesningen for å se hva som er med og ikke.
1. november: Diagnosekart og testcases for oblig 2
Da har jeg lagd et notat som peker på de vanligste feilene og tipsene jeg har lyst til å gi for oblig 2 . Tilbakemeldingene mine denne gangen vil stort sett referere til avsnitt i dette notatet. Jeg er stort sett ferdig med å rette og tilbakemeldinger vil komme utover dagen og i morra.
Testcasene jeg har brukt kan lastes ned . "1-altins" er datasett der svaret er beregnet med alternativ innsettingsalgoritme. Oppgave 2 blir sjekke via programmet nevnt før og har derfor ikke fact-filer.
26. oktober: Splay-trær og litteratur
Det kan virke som om det beskrives forskjellige innsettings-algoritmer for splay-trær i forskjellige utgaver av Weiss? I alle fall er den som vi skal bruke i oblig 2 den som står i obligteksten og i det som er kopiert opp og på foilene: Splay først noden som ''ville blitt forelder'', og sett så inn ny node direkte i rota. Alternativet, som vi ikke skal bruke, er å sette inn ny node først og så splaye den.
Mens jeg er inne på litteratur: Et tips til tilleggslitteratur for de med litt matematisk bakgrunn er denne klassikeren: Introduction to Algorithms (Cormen/Leiserson/Rivest). Når jeg sier litt matematisk bakgrunn så betyr ikke det at den går så mye dypere ned i det matematiske stoffet, bare at den kanskje benytter litt mer notasjon og ting beskrives bittelitt mer konsist og framfor alt oversiktlig (men dette er en veldig subjektiv vurdering!). Spesielt gjelder dette Fibonacci-heaper, som i kurslitteraturen beskrives noe uoversiktlig bare utifra de endringene en får i forhold til binomial-heaper, mens de i ITA beskrives selvstendig i et eget kapittel.
24. oktober: Debugging for oppgave 2
Dersom en får helt feil flyt underveis så er det kanskje (?) vanskelig å lese av dette direkte fra matrisen. I alle fall syntes jeg det var like greit å dumpe matrisen til dot-format og så visualisere den meg graphviz.
Eksempel: Ta N, f og Nf på et visst steg i prosessen (eller alle steg) og lagre de på seperate filer (uten noe før eller etter, sånn at det bare er selve matrisen som ligger på fila). Last så ned todot.py og kjør:
python todot.py outgraph.dot N.txt f.txt Nf.txt
dotty outgraph.dot
(Evt. bruk andre verktøy enn dotty for å vise .dot-fila). Det skriptet gjør er altså å ta et vilkårlig antall matriser som spesifiserer rettede grafer, og spesifisere de i kantlisteformat med de forskjellige kantvektene i den rekkefølgen de står som label. Kanter som har vekt 0 på alle grafene blir ikke tegnet. Å koble dette sammen med egen koden "is left as an excersise to the reader" (men et tips er å automatisk lage en graf-fil for hver forbedringsvei med inkrementerte navn, enten via system-call eller om en bruker Python bare importere den som modul).
Ellers fungerer ikke tilfeldig genererte testdata så godt på denne algoritmen, sett deg ned og forsøk å lage testdata som framprovoserer ikke-trivielle tilfeller (som grafer der en grådig algoritme ikke fungerer => en virtuell tilbakekant må følges).
22. oktober: Notater om flyt og matching av Bedeho Mender
- Bedeho Mender (som er student på kurset i år) har lagd et par gode notater for Ford-Fulkerson maximum flow og bipartite matching som burde hjelpe på forståelsen av disse. Takk Bedeho!
22. oktober: Diverse obligtips
Merk at obligen er oppdatert, pass på at du har siste versjon (de er like men den siste forklarer bedre på oppgave 3).
Ellers, se notatet mitt
Merknad: Det er litt unøyaktig for oppgave 3, en må huske på at h(p) = 0 om p er en måltilstand også må vises og dette er ikke nevnt.
Å debugge splay-trær kan antagelig være et mareritt uten gode test-cases. Det som nok kan lønne seg er å også skrive kode for å bygge opp et binærtre uten splaying, for så å bytte over til splaying midt i og fortsette med splaying. F.eks. kan en si som så at elementer i input kan starte på : for å bli satt inn uten splay-operasjoner, og så gi inn et parameter som slår av splaying for operasjonen. (Bare lever løsninger som støtter dette i koden, det vil jo ikke påvirke testcase som ikke inneholder :).
Poenget er at da kan en veldig lett bygge opp et testtre som har den formen en ønsker for å framprovosere en zigzig, zigzag osv. Dette bygger jo på at splay-trær ikke inneholder noen ekstra struktur utover vanlige binærtre - alle binærtrær er også splaytrær og omvendt, eneste forskjell er internt underveis i operasjonen.
Følgende eksempel burde framprovosere en zigzag når 5 settes inn:
:4 :8 :6 5
Ta dette tipset med en god klype salt og overse det om du ikke tar poenget umiddelbart: For de litt ambisiøse så er det fullt mulig å kode et splay-tre uten å kode alle symmetritilfellene for seg. En kan istedet gi inn retningen til zig-zag-funksjonene som funksjonspekere (direkte i språk der det er støttet eller kanskje like greit gjennom å implementere et interface) som kan snu get/set-operasjonene på barna til noder. All aksess av barnenoder skjer så gjennom et slikt interface, for evt. å bytte om right og left (dette gir nok ikke en veldig effektiv implementasjon, if-tester er kanskje raskere enn polymorfiske funksjonskall, men det kutter jo kodestørrelsen i to så det blir lettere å håndtere den). I C++ blir en slags hybridløsning mulig med templates: Ikke like kort kode som med polymorfisme, men en slipper unna reimplemntasjon av zigzag etc., og det blir like effektivt som å kode alt fullt ut.