Nyhetsflöde
Logga in till din kurswebb
Du är inte inloggad på KTH så innehållet är inte anpassat efter dina val.
I Nyhetsflödet hittar du uppdateringar på sidor, schema och inlägg från lärare (när de även behöver nå tidigare registrerade studenter).
December 2016
Föreläsningen den 7 dec som skulle ha varit kl 10-12 kommer på grund av schemakrock att vara kl 11.15-12.00.
December 2015
Det är ingen föreläsning den 8 dec kl 8-12. Innehållet (F14) gicks igenom på F13.
Januari 2015
Jag har insett att lösningen till uppgift 2.1 på förra tentan är väl kortfattad. Jag föreslår därför följande omarbetade version:
Använd DFS och låt algoritmen numrera noderna i ordningen de besöks. Vi definierar också en array backcycle[u]. Värdet på denna array är tänkt att vara det lägsta värde som man kan nå från u med en cykel som går "framåt" till en redan besökt nod. Vi initierar backcycle[u] till "oändligt" och gör sedan följande: När vi gör DFS-sökningen och från u når en redan besökt nod v sätter vi backcycle[u] = Min(backcycle[u],v). När vi sedan back-trackar (går bakåt i sökträdet) längs en kant, t.ex. (a,b) där a < b sätter vi backcycle[a] = Min(backcycle[a],backcycle[b]). När vi sedan kört algoritmen kollar vi alla kanter. Antag att vi har en kant (a,b) med a < b. Då är kanten en bro om och endast om backcycle[b] > a. DFS-sökningen går i tid O(|V|+|E|)). (De moifikationer vi gjort i sökningen ändrar inte detta. Eftersom grafen är sammanhängande är O(|V|+|E|)) = O(|E|). Den sista genomgången av kanter tar också tid O(|E|) som också blir totala tidskomplexiteten.
December 2014
Det står i schemat att det är en föreläsning på onsdag den 17 men den är inställd.
Oktober 2014
Hej! Vi söker två frivilliga studenter som kan ställa upp i en kursnämnd. Ni kan kontakta oss på föreläsningen idag (måndag).
