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.