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).

Januari 2017
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 31 oktober 2016

Kan därmed läsas av alla och ändras av lärare.
kommenterade 4 november 2016

När kommer problem-id för Graffärgning och Hamiltonsk cykel?

kommenterade 7 november 2016

^

Dessutom, vad betyder "Inga monologer får förekomma."?

En användare har tagit bort sin kommentar
kommenterade 7 november 2016

Teorifråga 5:

Antalet skådespelare som behövs borde rimligtvis vara relaterat till vilken probleminstans det är frågan om. Tänker jag fel eller är frågan felställd?

kommenterade 7 november 2016

"Inga monologer får förekomma" betyder gissningsvis att en uppsättning inte får innehålla någon scen med endast en skådespelare.

kommenterade 7 november 2016

@Mikael Min tanke också, men har den ingen riktig funktion så borde den istället förekomma som indatakrav (annars tillförd den bara meningslös "komplexitet"). Därav tänkte jag att det kanske var något annat.

Tack för svar ;)

Lärare kommenterade 7 november 2016

Som Mikael beskrev betyder "Inga monologer" att varje scen måste ha minst två roller.

Teorifråga 5 är korrekt ställd.

Jag vet inte när Kattisproblemen kommer upp men förhoppningsvis inom ett dygn. Problemen är klara och behöver bara läggas upp av en Kattisadministratör.

kommenterade 8 november 2016

Tiden rinner iväg och det går inte att testa mot kattis. Känner mig stressad.

Lärare kommenterade 8 november 2016

Robin, inom några dagar ska Kattisuppgifterna vara uppe. Det är fortfarande 10 dagar kvar till bonusdatumet för labben, så ta det lugnt!

kommenterade 8 november 2016

I graffärgningsproblemet påverkar inte eventuella dubbelkanter färgningen på något sätt, eller?

Tack på förhand :)

En användare har tagit bort sin kommentar
kommenterade 10 november 2016

Någon som behöver labbpartner på denna? Skicka mig ett pm så kan vi labba :)

kommenterade 12 november 2016

Att (kontinuerligt) hålla på och smyga in ändringar i labblydelsen så här nära inpå deadline är inte OK. Det är riktigt otrevligt och bestraffar oss som är ute i god tid.

Dessutom gäller enligt kursens labbassistenter inte alls "Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte". Jag var inte ensam om att slösa många timmar av måndagen pga detta. Oseriöst.

En användare har tagit bort sin kommentar
Lärare kommenterade 13 november 2016

Hej Johan! Labbuppgiften har inte ändrats. I tisdags gjordes ett förtydligande av  labblydelsen, nämligen att varje roll i uppsättningen måste förekomma i minst en scen, vilket jag hoppas ingen tycker är konstigt. Igår förmiddags la jag in länkar till dom utlovade Kattisproblemen i labblydelsen. Jag är ledsen att Kattisproblemen las upp bara en vecka före bonusdatumet för labben. Vi ville vara säkra på att den nyskrivna specialdomaren och dom nya testfallen skulle fungera, och det tog några dagar längre än planerat.

Meningen om att man kan få redovisa utan att Kattis godkänt lösningen syftar på fallet då lösningen inte har accepterats av Kattis på grund av att reduktionen gett en så komplicerad probleminstans att Kattis inte hunnit kontrollera den inom rimlig tid. Kattis är ju tvungen att lösa ett NP-fullständigt problem för att kontrollera svaret!

kommenterade 13 november 2016

Hej Viggo! Tack för snabbt svar (målet var dock att belysa missförhållanden snarare än diskussion).

Labbuppgiften har ändrats. Huruvida det senaste kravet är konstigt eller inte påverkar inte det faktum att vi behöver skriva om hela vår tidigare lösning (som var skräddarsydd efter tidigare kravspec, något som ofta behövs i adk:n för att klara tidskravet). Detta kombinerat med den korta tidsfristen och att vi inte alls fick redovisa vår reduktion i fredags har mördat min planering och jag tycker lite självkritik vore på sin plats.

kommenterade 13 november 2016

Så man får alltså redovisa trots att Kattis godkänner vissa testfall för att sedan få time limit exceeded (i vårt fall korrekta lösningar fram till testfall 33/36 då vi får resultatet "time limit exceeded") så länge man kan bevisa att reduktionen är korrekt?

Lärare kommenterade 14 november 2016

David, du beskriver just det fallet då reduktionen skapar en instans som Kattis inte klarar av att lösa inom den uppsatta tidsgränsen. Då är det tillåtet att redovisa och vid redovisningen bevisa att reduktionen är korrekt (inklusive att den är polynomisk!). Men att Kattis får time limit exceeded tyder på att reduktionen är onödigt komplicerad, så det kan ändå vara en bra idé att försöka förenkla den.

Marcus Dicander redigerade 30 november 2016

NP-fullständighetsreduktioner - Rollbesättning Om du redovisar labben senast den 18 november får du en bonuspoäng på tentan. Labbteoriuppgifterna nedan kan redovisas för en bonuspoäng till tentan, och detta görs på övningen den 10 november (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

Ansvarig för castingen på ett filmbolag behöver koppla ihop rätt skådespelare med rätt roller. Samma person kan spela flera roller, men samma roll kan endast innehas av en person. Manus anger vilka roller som är med i samma scener. Inga monologer får förekomma. Varje skådespelare får bara ha en roll i varje scen. Varje roll måste förekomma i minst en scen.

Dessutom är divorna p1 och p2 garanterade att få (minst) en roll var (och de rollerna ska självklart delta i åtminstone en scen var). Detta medför extraarbete eftersom de båda inte tål varandra och rollerna ska besättas så att de aldrig spelar mot varandra. Rollbesättningsproblemet är att avgöra ifall alla roller kan besättas med de skådespelare som finns till hands. Ingående parametrar är alltså: Roller r1, r2,... , rn Skådespelare p1, p2,... ,pk Villkor typ 1 (till varje roll): rt kan besättas av p1, p2, p6 Villkor typ 2 (till varje scen): i su medverkar r1, r3, r5, r6 och r7

IndataformatDe tre första raderna består av talen n, s och k (antal roller, antal scener och antal skådespelare, n≥1, s≥1, k≥2), ett tal per rad. 

De följande n raderna representerar villkoren av typ 1 och börjar med ett tal som anger antalet efterföljande tal på raden, följt av de möjliga skådespelarnas nummer (mellan 1 och k, kursiverade i exemplen nedan). De sista s raderna är villkor av typ 2 och börjar ett tal som anger antalet efterföljande tal på raden, följt av tal som representerar de olika rollerna som är med i respektive scen. Varje roll förekommer högst en gång på varje sådan rad, så antalet roller på en rad ligger mellan 2 och n.

Fråga: Kan rollerna besättas med högst k st skådespelare så att p1 och p2 deltar men inte är med i samma scener som varandra?

Exempel på godkända indata

nej-instans: 55 3 3 1 2 3 2 2 3 2 1 3 1 2 3 1 2 3 2 1 2 2 1 2 3 1 3 4 2 3 5 3 2 3 5        ja-instans: 654 3 1 3 4 2 2 3 2 1 3 1 2 4 1 2 3 4 2 1 4 3 1 2 6 3 2 3 5 3 2 4 6 3 2 3 6 2 1 6 UppgiftI den här laborationen ska du visa att rollbesättningsproblemet är NP-svårt genom att reducera ett känt NP-fullständigt problem, som finns inlagt i Kattis. Din reducerade instans kommer att granskas och lösas av Kattis. Du får välja mellan att reducera problemen Graffärgning (problem-id kth.adk.npreduction1) och Hamiltonsk cykel (problem-id kth.adk.npreduction2). Indataformat för dessa problem beskrivs nedan. Din uppgift är alltså att implementera en reduktion, inte att lösa problemet.

Kattis testar om din reduktion är korrekt, men du måste naturligtvis kunna bevisa att den är det vid redovisningen. Kattis svar är egentligen avsedda att vägleda dig i arbetet med beviset och påpeka om du glömt något viktigt specialfall. Vid redovisningen kommer handledaren också att fråga varför problemet ligger i NP och vad komplexiteten är för din reduktion.

Vid rättningen utnyttjas en lösare för instanser av ett (annat) NP-fullständigt problem inom rimliga storleksgränser. Av tekniska skäl har Kattis en maximal tillåten storlek på instanserna. Du får bara meddelanden om den ifall du skickar in en för stor instans. Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte.

GraffärgningIndata: En oriktad graf och ett antal färger m. Isolerade hörn och dubbelkanter kan förekomma, inte öglor.

Fråga: Kan hörnen i grafen färgas med högst m färger så att inga grannar har samma färg?

Indataformat: Rad ett: tal V (antal hörn, tex:\displaystyle 1 \leq V \leq 300) Rad två: tal E (antal kanter, tex:\displaystyle 0\le E\le 25000) Rad tre: mål m (max antal färger, tex:\displaystyle 1\le m\le 2^{30}) En rad för varje kant (E stycken) med kantens ändpunkter (hörnen numreras från 1 till V)

Hamiltonsk cykelIndata: En riktad graf.

Fråga: Finns det en tur längs kanter i grafen som börjar och slutar på samma ställe och som passerar varje hörn exakt en gång?

Indataformat: Rad ett: tal V (antal hörn, tex:\displaystyle 1\le V\le 200) Rad två: tal E (antal kanter tex:\displaystyle 0\le E\le 5000) En rad för varje kant (E stycken) med kantens starthörn och sluthörn (hörnen numreras från 1 till V)

Teoriuppgifter
* Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
* Visa att rollbesättningsproblemet ligger i NP.
* Förändra nej-instansen i exemplet på indata till en ja-instans. Hur många skådespelare behöver du lägga till i just detta fall?
* Vilken är den minsta möjliga produktion som uppfyller indatakraven för rollbesättningsproblemet och som går att sätta upp? Skriv upp indata för denna produktion!
* Tänk dig en instans där rollerna är indelade i två grupper, ungefär som i matchningsproblemet, där rollerna aldrig förekommer i samma scener som roller ur samma grupp. Hur många skådespelare behövs då?
* Anta att film a innehåller en scen med rollerna 4, 7 och 12 medan film b har tre scener med rollerna 4 och 7, 7 och 12 samt 4 och 12. Om alla övriga villkor är identiska mellan filmerna - kommer svaren då att bli likadana? Varför/varför inte?
Extrauppgift Frivillig extrauppgift som redovisas på ett särskilt redovisningstillfälle den 10 januari 2017 kl 14-17 och då kan ge betyg A eller B på lärandemålet om hantering av problem med hög komplexitet (och då behöver man inte examineras på det lärandemålet på muntan). Uppgiften görs individuellt. För att få redovisa extrauppgiften måste du vara godkänd på momentet TEN1 (dvs teoritentan).

Du ska välja att implementera valfri heuristik som löser konstruktionsproblemet: Vilka skådespelare ska ha vilka roller för att lösa rollbesättningsinstansen med så få skådespelare som möjligt? Indataformatet för rollbesättningsproblemet är detsamma som tidigare. Divorna är 1 och 2.

Utdataformat: Rad ett: antal skådespelare som fått roller En rad för varje skådespelare (som fått roller) med skådespelarens nummer, antalet roller skådespelaren tilldelats samt numren på dessa roller

Problemet ska lösas enligt villkoren som specificerats för rollbesättningsproblemet, dvs divorna måste vara med men får inte mötas, ingen roll får spelas av flera personer, och ingen skådespelare får spela mot sig själv i någon scen. Bättre heuristik (dvs färre skådespelare) ger bättre betyg. Endast lösbara instanser kommer att ges som indata, men för att heuristiken i polynomisk tid säkert ska kunna hitta en lösning så är det tillåtet att använda högst n-1 särskilda superskådisar med nummer k+1, k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll.

Några testfall att testa ditt program med finns på /info/adk16/labb4/testfall/

Skriv en kort rapport (omkring en sida) där du dels beskriver vilka heuristiker din lösning använder och dels reflekterar över hur du arbetat med uppgiften och hur du möjligen kunnat arbeta annorlunda. Skriv namn på rapporten och lämna den till labbassistenten vid redovisningen.

Problemet heter (KOMMER SENARE) ikth.adk.castingheuristic på Kattis. Kattis summerar antalet använda skådespelare i testfallen och returnerar summan. För betyg B krävs ett resultat bättre än 560. För betyg A krävs 460 eller bättre. För betyg A krävs också att algoritmen använder simulated annealling, tabusökning eller annan sofitistikerad lokalsökningsheuristik. Bara den som är godkänd på teoritentan får redovisa extralabben.

I Kattis testfall är antalet roller aldrig större än 600, antalet scener aldrig större än 4000 och antalet skådespelare aldrig större än 400.

En användare har tagit bort sin kommentar
kommenterade 9 december 2016

Om man satsar på B finns det något övrig krav (för extrauppgiften), eller räcker det med Kattispoängen och att man kan förklara hur man tänkt? 

Lärare kommenterade 9 december 2016

Rebecca, det är kraven som står ovan som gäller, till exempel att uppgiften ska göras individuellt, att en rapport på en sida ska lämnas in etc.

kommenterade 31 december 2016

Vad skiljer en sofistikerad lokalsökningsheuristik från en icke-sofistikerad sådan? 

Lärare kommenterade 31 december 2016

Kristian, två exempel på sofistikerade lokalsökningsheuristiker är simulated annealing och tabusökning. Det är också tillåtet att använda andra heuristiker som bygger på lokalsökning men som inte bara gör enkel lokalsökning med fast djup. Du får i så fall själv vid redovisningen och i den korta rapporten tala om i vilken mening som den lösning du valt är sofistikerad.

En användare har tagit bort sin kommentar
 
Lärare Viggo Kann skrev inlägget 2 januari 2017
kommenterade 2 januari 2017

Om man planerar munta 2 moment, räcker det att boka 1 pass?

Lärare kommenterade 2 januari 2017

Ja, man bokar en tid, oavsett hur många betyg man muntar upp. Vid muntan får man en uppgift för varje betyg. 

 
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

En användare har tagit bort sin kommentar
kommenterade 2 januari 2017

Hej, 

Var bokar man sig för att munta? 

Lärare kommenterade 2 januari 2017

Kristian, information om muntabokning finns nu i nyhetsflödet för adk16 och i vänstermenyn på kurswebben.

 
December 2016
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

En användare har tagit bort sin kommentar
kommenterade 28 september 2016

Kan vi anta att n är givet i första uppgiften?

Lärare kommenterade 28 september 2016

Uppgiften säger bara att "Indata är en lista med par av studenter som känner varandra" så ni får själva bestämma hur indata ska representeras. Det är både tillåtet och rekommenderat att välja en representation som gör det lätt att läsa och tolka indata.

kommenterade 28 september 2016

Får man skriva mästarprovet för hand eller måste man använda sig av något i stil med latex ?

kommenterade 28 september 2016

Uppgift 1: Måste vi även skapa en algoritm för hur vi skapar grafen eller räcker det med en förklaring av detta i ord?

Lärare kommenterade 28 september 2016

Kristoffer: Det går utmärkt att skriva lösningarna för hand, men ta då en kopia eller fota av lösningarna innan du lämnar in dom så att du kan kolla på dom före muntliga redovisningen.

Alexander: Algoritmen ska ges i pseudokod. Men lyd Stefans råd att välja en representation av indata som gör det enkelt att tolka indata och skapa grafen.

kommenterade 28 september 2016

Ledsen att vara jobbig men svaret hjälper mig inte. Enligt uppgiftlydelsen ska vi bara presentera en algoritm som löser problemet. Min fråga är: ingår det i problemet att maskinellt tolka indata och konstruera sin graf eller räcker det med utifrån en graf(och valt sätt att representera den) presentera en algoritm som löser 2 provs problemet?

Lärare kommenterade 28 september 2016

Alexander:

1. Algoritmens indata är inte en graf utan en lista av par.
2. Algoritmen ska beskrivas med pseudokod.

Därmed bör frågan vara besvarad.

kommenterade 29 september 2016

Om man i en lösning vill använda någon generisk algoritm i stil med sökning eller sortering, måste denna algoritm då implementeras eller räcker det med att skriva att den görs?

Lärare kommenterade 29 september 2016

Alice: Algoritmer från kurslitteraturen kan användas (anropas) i pseudokoden i dina lösningar. Du måste då noga referera till algoritmen (inklusive sidnummer). Det går också bra att hänvisa till kurslitteraturens tidskomplexitetsanalys och korrekthetsmotivering (med sidnummer) för en anropad algoritm.

kommenterade 29 september 2016

Viggo, ditt svar till Alice gör mig en smula konfunderad.

Visst måste det vara ok att hänvisa till "allmänt kända" algoritmer (och datastrukturer för den delen), såsom görs i tidigare lösningsförslag? Exv "Sort(data)" och sedan förklara att med sorteringsalgoritm X blir det tidskomplexitet Y.

Lärare kommenterade 29 september 2016

Johan, problemet är att "allmänt kända algoritmer" inte är väldefinierat. Om du hänvisar till algoritmer i kurslitteraturen är du på den säkra sidan. Mergesort finns till exempel i kursboken Kleinberg-Tardos på sida 224-225/130-131.

kommenterade 29 september 2016

När jag tittade på tidigare års mästarprov för att få en bra uppfattning om vad som krävdes såg jag att man åtminstone i adk15 behövde skriva sina lösningar på engelska eftersom det fanns ickesvenskspråkiga assistenter som tog emot redovisningar.

Vilka språk är tillåtna för lösningarna till mästarproven den här kursomgången?

Lärare kommenterade 29 september 2016

Martin, det var bara på ommästarprovet förra året där engelska behövdes. 

För årets mästarprov rekommenderar vi att ni skriver på svenska (för att träna på att föra algoritmiska resonemang på svenska - i masterprogrammen får ni träna på att föra dom på engelska).

kommenterade 30 september 2016

Får algoritmer, datastrukturer och tidskomplexitetsanalyser från föreläsningsanteckningarna användas (med hänvisning, givetvis) om de ej förekommer i kurslitteraturen?

Lärare kommenterade 30 september 2016

Alice, detta är inte en så enkel fråga som man kan tro. I vetenskapliga sammanhang ska man inte hänvisa till föreläsningsanteckningar och andra dokument som inte har genomgått granskning och publicering. Även om jag tror att det som står i föreläsningsanteckningarna är korrekt så är det alltså inte god sed att hänvisa till såna dokument. Jag tycker därför att du inte ska göra det. Du kan förstås ändå skriva ner och använda en algoritm från föreläsningsanteckningarna i din lösning (med referens så det inte blir plagiat), men du kan inte hänvisa till föreläsningsanteckningarnas analys av algoritmen utan måste göra analysen av den algoritm du skrivit ner själv.

kommenterade 30 september 2016

Om man refererar till litteraturen - ska man då ta med sig kursboken till den muntliga presentationen för att kunna svara på frågor?

Lärare kommenterade 2 oktober 2016

Haris, det är meningen att man vid den muntliga redovisningen ska kunna svara på frågor om den lösning man lämnat in. Vissa brukar ta med egna anteckningar och figurer för att visa upp när man förklarar hur algoritmerna fungerar, vilket är okej, men vi vill inte att ni drar upp kursboken för att leta efter svar på assistentens frågor om den inlämnade lösningen.

kommenterade 3 oktober 2016

Har jag förstått det rätt om arrayen P[i] i uppgift 2 avser antalet pokestops som ligger exakt efter i kilometer. Bara så det inte är de man passerat också. Känns som en dum fråga, men blev osäker.

kommenterade 3 oktober 2016

Jag har en fråga angående P listan i uppgift 2. I uppgiftslydelsen står det följande "Listan har punkter för 2 km in i vandringen, 4 km in i vandringen, 5 km in i vandringen osv". Om antalet pokestop efter 2km kommer att förekomma på index 0 i P, kommer antalet pokestop vid 3km (som inte är möjligt att nå) finnas representerad på index 1 i P följ av antalet pokestop vid 4km på index 2? Eller kommer antalet pokestop vid 4km kommer direkt efter antalet pokestop efter 2km i P? 

kommenterade 3 oktober 2016

Kan man anta i uppgift 1 att grafen som bildas av vänskapsparen är sammanhängande?

Lärare kommenterade 3 oktober 2016

Mikael och Jakob: P[i] beskriver antalet pokestopp som kan nås i km in i vandringen. Värdet P[3] ska alltså inte användas av algoritmen.

Lärare kommenterade 3 oktober 2016

Arvid, man kan inte anta att grafen som bildas av vänskapsparen har någon speciell egenskap (utöver vad som följer av uppgiftslydelsen). 

kommenterade 5 oktober 2016

I alla problem får man en viss input, t.ex. i form av tuplar '(a1,b1),(a2,b2), etc'. När man ska beräkna komplexiteten, måste man ha med den tid det tar att läsa in tuplarna, eller kan man anta att dessa är redan i minnet i en optimal datastruktur?

T.ex. problem säger att vi får indata som tuplar '(a1,b1),(a2,b2)'. Antingen behöver jag O(n) för att läsa in indata eller så antar jag att det är i minnet som t.ex. en hashmap, etc.

kommenterade 5 oktober 2016

Om det för bästa möjliga tidskomplexitet är vitalt att en viss datastruktur (eller algoritmimplementation) används, ska det då uttryckas i pseudokoden eller i analysen av tidskomplexiteten?

Lärare kommenterade 5 oktober 2016

Artem, hur man beräknar tidskomplexiteten beror på vilken beräkningsmodell man använder. I vissa modeller (som RAM-modellen) kan man indexera till ett specifikt element i indata, i andra (t ex Turingmaskinen) måste man läsa in indata steg för steg. Om det är relevant i din algoritm får du specificera vilken av dessa beräkningsmodell du använder i analysen. 

Alice, om en viss datastruktur behöver användas måste det synas i både pseudokoden och analysen.

kommenterade 5 oktober 2016

I upg 3 står det att "Bokningen av klassrummen görs terminsvis". Kan man då utgå från att det finns ett tidigast startdatum (början av termin) och senast slutdatum (slutet av termin) som man kan boka klassrummen på?

Lärare kommenterade 6 oktober 2016

Kristian, datumen och tiderna representeras i indata av positiva heltal. Kopplingen till verkliga datum och tider är inte relevant för uppgiften. Lägsta möjliga positiva heltal är förstås 1,  men det finns ingen högsta gräns som är given på förhand.

kommenterade 6 oktober 2016

Vilken länk bokar man mästarprovet?

kommenterade 6 oktober 2016

Borde då inte problembeskrivningen ändras? För om en högsta gräns inte existerar, så kan icke-terminsvisa tidsbokningar ske. 

Lärare kommenterade 6 oktober 2016

Mästarprovsbokningarna kommer att göras från denna sida, men länksidan är inte publicerad ännu. Förhoppningsvis får Stefan upp den under dagen. 

Kristian, en högsta gräns behöver inte finnas i uppgift 3, för precisionen i tidsangivelserna är inte given. Med högre precision krävs större heltal för att representera en start- eller sluttid under den aktuella terminen. 
Men det är okej att använda enhetskostnad för att analysera tidskomplexiteten i uppgift 3.

kommenterade 21 oktober 2016

När kommer facit ut till provet någon?

Lärare kommenterade 28 oktober 2016

Nu finns lösningsförslagen till mästarprov 1 upplagda.

kommenterade 22 november 2016

I uppgift 1 står att kantvikterna kan vara godtyckliga heltal. Betyder det att de kan vara icke-positiva eller till och med negativa?

kommenterade 22 november 2016

I uppg 1, står det:

Därför kan indata representeras som en oriktad graf där vägskälen är hörn och kantvikterna, som kan vara godtyckliga heltal, anger väglängder.

Betyder det att indata även kan representeras som riktad graf också?

kommenterade 22 november 2016

Får det finnas dubbel-, trippel-... och så vidare kanter, det vill säga två eller fler vägar från ett vägskäl som leder till samma vägskäl/hörn? Hur representeras dessa i indata i sånt fall? Måste vi bevisa att Hamiltion stig är np-fullständigt, eller räcker det med att hänvisa till beviset i övning 9? 

En användare har tagit bort sin kommentar
kommenterade 22 november 2016

Mästarprov 2:

I lydelsen till uppgift 1 står det "Visa att problemet är NP-svårt genom att reducera problemet Hamiltonsk stig.". Vilket problem menas då? Är det att avgöra om det är möjligt att vinna ett specialpris? 

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
Lärare kommenterade 23 november 2016

Abdallah, kantvikterna i uppgift 1 kan vara godtyckliga positiva heltal.

Joni, banan kan representeras som en oriktad graf och du behöver inte diskutera vad som skulle hända om man istället väljer en riktad graf.

Sonja, uppgift 1 handlar om en graf (och inte en multigraf) så det finns alltså högst en kant mellan två hörn.

Alfrida, "Är det att avgöra om det är möjligt att vinna ett specialpris?". Ja!

kommenterade 24 november 2016

På fråga 3, Konstruktion av Schema

Är en lösningen polynomisk i längden av den längsta lektionen OK?

Lärare kommenterade 25 november 2016

@Johan: Nej, lösningen ska vara polynomisk i indatas storlek. En algoritm som har polynomisk tidskomplexitet i talen i indata (dvs exponentiell i indatas storlek) kallas pseudopolynomisk. En pseudopolynomisk reduktion i uppgift 3 kan möjligen räknas som "mindre fel". Det är något vi lärare och assar kommer att bestämma när vi gör den detaljerade bedömningsmallen inför mästarprovsredovisningarna.

En användare har tagit bort sin kommentar
kommenterade 25 november 2016

Kan man anta att alla vägskäl har en valens större än 2, dvs. \(\forall\delta(v)\ge3\)? För om valensen är 2, så är det inte ett vägskäl?

kommenterade 25 november 2016

Har grafen som ges som indata till Hamiltonstig-problemet kanter med kantvikter?

Lärare kommenterade 25 november 2016

Artem, det går bra att anta att minst tre vägar utgår från varje vägskäl. Men det går också bra att tillåta att vägskäl har en eller två utgående vägar. I verkligheten förekommer det vändplaner i slutet på återvändsgränder (kan tolkas som vägskäl med en väg) och vägar som svänger plötsligt och kraftigt (kan tolkas som vägskäl med två vägar). Något som inte har någon verklighetskoppling är väl vägskäl med noll vägar, så det ska inte förekomma i indata.

Jakob, du kan anta att indata till Hamiltonstigproblemet är en oriktad oviktad graf (se övning 9).

kommenterade 25 november 2016

Får man anta att maratonproblemet innehåller en parameter för storleken på specialpriset?

kommenterade 25 november 2016

På fråga 3, Konstruktion av Schema, "Analysera tidskomplexiteten för din reduktion"

Krävs en tight övre gräns eller är det ok att vara frikostig så länge komplexiteten är polynomisk?

kommenterade 25 november 2016

I uppgift 1, så om man har en graf med en Hamilton-stig, så ska man reducera den till ett maraton-problem där den stigen väger minst lika mycket som hälften av alla kantvikter tillsammans?

Lärare kommenterade 25 november 2016

Artem: Maratonproblemet är att avgöra ifall det är möjligt att vinna ett specialpris eller inte. Storleken på priset är inte relevant i problemet och är därför inte indata.

Erik: Bara frågor om uppgiftsformuleringen får ställas, inte frågor om hur uppgiften kan lösas.

Johan: Ingen jättetight tidskomplexitet behöver visas. Det viktiga är att den visas vara polynomisk. Om tidskomplexitetsanalysen är för vidlyftig kommer du att behöva diskutera den vid den muntliga redovisningen.

kommenterade 25 november 2016

Jag menar om man skall reducera ett Hamilton-stig problem till ett "man kan vinna specialpris"-problem?

Lärare kommenterade 25 november 2016

Erik, i uppgiften står "Visa att det är NP-fullständigt att avgöra om det är möjligt att vinna ett specialpris. Visa att problemet är NP-svårt genom att reducera problemet Hamiltonsk stig (se övning 9 för definition)."

Med problemet i andra meningen avses problemet som nämns i första meningen.

kommenterade 26 november 2016

Kan grafen som ges som indata till Hamiltonstig-problemet ha öglor? 

kommenterade 26 november 2016

Antar att den inte kan det, eftersom den inte är en multigraf!

kommenterade 27 november 2016

Vid analys av algoritmernas tidskomplexitet, är det valfritt att använda antingen modellen för enhetskostad eller bitkostnad eller ska man kunna redogöra för båda?

Lärare kommenterade 28 november 2016

Mailfråga: Är det i uppgift 1 tillåtet att använda en polynomisk Turingreduktion?

Svar: Nej, det måste vara en Karpreduktion.

kommenterade 29 november 2016

Kan man i problem 3 (och då även 2) anta att inga paradoxala krav förekommer (ex "lektion a måste ske efter lektion b" och "lektion b måste ske efter lektion a")?

Lärare kommenterade 29 november 2016

Alice, det kan finnas krav i indata som inte kan uppfyllas. Det är till och med vanligt i schemaläggning i verkligheten.

Om det finns krav som inte kan uppfyllas så finns det ingen lösning, så då ska algoritmen svara att det inte finns någon lösning.

kommenterade 30 november 2016

Uppgift 2. "Skolan vill optimera så att den lektion som slutar sista slutar så tidigt som möjligt" Måste vi ha med det i den polynomiska verifieringen? Alltså att föreslagna schemaläggningen är "Optimalt" i och med att dagarna slutar så tidigt som möjligt med indata?

Lärare kommenterade 30 november 2016

Alexander, jag kan inte svara på frågor om hur man ska lösa problemet. Men observera att det ingår i uppgift 2 att formulera optimeringsproblemet som ett beslutsproblem.

kommenterade 30 november 2016

Ok, samma uppgift. Vad menas med "Beslutsproblemet har dessutom ett mål timelimit som indata"? Är det maximala tiden som algoritmen får utföra beräkningar för att få fram en lösning eller är det maximala tiden in i framtiden som får allokeras till lektionerna?

I och med att det står mål känns det som något man ska pricka in inte komma under. T.ex. om det är maximala tiden in i framtiden så vill vi hamna på precis timelimit och inte under.

Lärare kommenterade 30 november 2016

Alexander, läs om beslutsproblem och optimeringsproblem i avsnitt 8.1 i kursboken eller i föreläsningsanteckningarna för föreläsning 20 och 27.

En användare har tagit bort sin kommentar
kommenterade 1 december 2016

Jag blev fundersam på en definition gällande hamiltonsk stig. Är en graf med endast ett hörn en ja-instans eller en nej-instans till problemet hamiltonsk stig?

Lärare kommenterade 2 december 2016

@Gabriel Det påverkar inte komplexiteten för hamiltonstigproblemet eller svårigheten hos mästarprovsuppgiften, så välj själv ja eller nej. Själv skulle jag nog luta åt att en graf med bara ett hörn har en hamiltonstig.

kommenterade 2 december 2016

Kan inte komma åt bokningslistan ("Sidan är behörighetsskyddad"), är det jag som gör något fel eller är det något annat som knasar? 

Lärare kommenterade 2 december 2016

Darja, nu har du fått behörighet till sidan.

kommenterade 2 december 2016

I uppgift 2 och 3 finns det någon övre gräns på tiden en lektion kan pågå?

Lärare kommenterade 2 december 2016

Rebecca, det finns ingen övre gräns på tiden en lektion kan pågå.

kommenterade 2 december 2016

Taget från bedömningskriterier för mästarprov 2:

"Anger tidskomplexitet i föreskrivna variabler."

Vilka är dem föreskrivna variablerna för uppgift 1?

Lärare kommenterade 3 december 2016

Johannes, det stämmer att det inte finns några variabler som anger storleken i uppgiftslydelsen. Jag har nu ändrat "föreskrivna" till "lämpliga" i kriteriet. I det fall att det finns föreskrivna variabler är det naturligtvis dom som är lämpliga.

En användare har tagit bort sin kommentar
kommenterade 5 december 2016

Är det bara antal anrop man ska ta hänsyn till i 3an eller spelar det också roll hur stor indatan är?

Lärare kommenterade 5 december 2016

Mikael, i uppgift 3 ska man konstruera en polynomisk turingreduktion och analysera tidskomplexiteten för den. Mer kan jag inte säga.

kommenterade 5 december 2016

Taget ur bedömningskriterierna för mästarprov2:

"Beskriver reduktionen övergripande i ord och ev. i bild - måttliga"

Raden under står det:

"Beskriver reduktionen tydligt - Ja "

Ska reduktionen beskrivas måttligt eller tydligt

Lärare kommenterade 5 december 2016

Joni, för uppgift 1 och bedömningsgrunden "Beskriver reduktionen övergripande i ord och ev. i bild" är kraven måtttliga, medan det är krav på bedömningsgrunden "Beskriver reduktionen tydligt".

Det innebär att en tydligt beskriven reduktion krävs i den skriftliga redovisningen, men det behövs ingen övergripande beskrivning som beskriver reduktionen i stora drag i den skriftliga redovisningen. Däremot måste man vid den muntliga redovisningen kunna beskriva reduktionen övergripande någorlunda väl.

kommenterade 19 december 2016

Hej, det står på detaljschemat följande:

Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.

Kommer ommästarprovs uppgifterna upp ikväll eller?

Samt så undrar jag när lösningsförslagen för mästarprov 2 kommer upp?


kommenterade 19 december 2016

Hur går man tillväga för att boka muntliga tentan?

kommenterade 20 december 2016

Testar igen...Hej, det står på detaljschemat följande:

Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.

När kommer ommästarprovs uppgifterna upp?

Samt så undrar jag när lösningsförslagen för mästarprov 2 kommer upp?

Lärare kommenterade 21 december 2016

Både ommästarprovsuppgifterna och lösningsförslagen till mästarprov 2 är nu upplagda.

kommenterade 21 december 2016

Det står följande på ommästarprovs dokumentet:

Du ska lämna in den skriftliga lösningen som en PDF-fil på kurswebben för adk16 senast 6 januari 2017 klockan 24.00.

Sedan står det under länken till ommästarprovsuppgiften:

Lämna in din uppgift i brevlådan utanför CSC-skolans expedition senast 6 januari 2017

Vilket alternativ gäller? Om alternativ två gäller, vart ligger CSC-skolans expedition?

Tack!

Lärare kommenterade 21 december 2016

Tack Joni för att du noterade dom dubbla budskapen om inlämningsplats. Jag har nu lagt upp en inlämningsuppgift med namnet ommästarprov adk16 på kurswebben. Använd den för inlämning av mästarprovet!

Jag vill också passa på att förtydliga att n är en indataparameter i uppgift 1 på ommästarprovet.

kommenterade 23 december 2016

Halloj.

Har hittat lite olika formuleringar på kappsäcksproblemet. Vilken är det som gäller? Är det okej att anta "0-1 kapsack problem"? https://en.wikipedia.org/wiki/Knapsack_problem

kommenterade 23 december 2016

Med reservation för att jag inte företräder kursen tror jag det är ett säkert kort att utgå från definitionen i anteckningarna till föreläsning 21.

kommenterade 23 december 2016

Det framgår ju inte ifall man får välja fler av ett föremål, eller har jag missuppfattat något?

kommenterade 23 december 2016

Jag (gör inte ommästarprovet, men) har förutsatt att varje unikt föremål endast kan förekomma 0 eller 1 gånger i kappsäcken.

Lärare kommenterade 23 december 2016

Victor, det finns bara ett exemplar av varje föremål som man kan stoppa i kappsäcken i kappsäcksproblemet. Varianterna av problemet med flera exemplar som förekommer i Wikipedia kallas inte för bara kappsäcksproblemet, så om man menar en sån variant måste man förtydliga namnet.

kommenterade 23 december 2016

Tack för svar! Ha en riktigt god jul :)

kommenterade 27 december 2016

Hej Viggo, till ommästarprov komplexitet har jag gjort tolkningen att det är ett krav att varje student ska redovisa exakt en gång, varken mer eller mindre. Är det en korrekt tolkning?

Lärare kommenterade 27 december 2016

Sara, jag håller med om din tolkning.

kommenterade 27 december 2016

Ommästarprov 2 Komplexitet:

"Algoritmens uppgift är att tilldela tider så att den sammanlagda prioriteten för de studen-
ter som får redovisa blir så liten som möjligt, samtidigt som den totala kostnaden för passen inte får överstiga M".

Min fråga lyder:

Är det ett krav att konstruera en algoritm enligt ovan för ett E i lösningen? Eller räcker det med en reduktionsomvandling av instanserna?

Lärare kommenterade 27 december 2016

Joni, i uppgift 2E ska man inte konstruera en algoritm som löser problemet utan bara formulera problemet som ett beslutsproblem och visa att det är NP-fullständigt.

kommenterade 28 december 2016

Ommästerprov 2E

Ang indatan, ska man anta att listan med n redovisningspass är en trippel med indata, en för tid, plats och kostnad?

Ang indatan med m listor, ska man även där anta att det är ett talpar med listor, en för student och prioritet? 

Tack på förhand!

kommenterade 28 december 2016

Ommästerprov 2E

Enligt uppgiftslydelse står följande:

...så att den sammanlagda prioriteten för de studenter som FÅR redovisa blir så liten som möjligt.

Om jag uppfattar det rätt, så får inte alla studenter redovisa?

Lärare kommenterade 28 december 2016

Jag har just uppdaterat lydelsen för uppgift 2E på ommästarprovet (den gamla uppgiften var fel) så att man ska maximera (och inte minimera) prioritetssumman. Den nya lydelsen finns i pdf-filen ovan.

kommenterade 28 december 2016

@Abdel-Hakim Rahmani Jag har tolkat frågan som att alla inte får redovisa. Eftersom om två elever bara anger en tid som är likadan så får den eleven med, nu efter ändringen, högst prioritet den tiden. Eftersom den andra eleven ej anget en annan tid så blir den utan redovisningspass. 

kommenterade 28 december 2016

@Victor Kesten Tack så mycket! Jag förstod det efter att Stefan hade uppdaterat lydelsen. 

kommenterade 29 december 2016

Efter uppdateringen av mästarprovet och tidigare studenters frågor blir jag osäker på om Viggos svar på min fråga fortfarande gäller. I uppgiftslydelsen står det "Algoritmens uppgift är att tilldela tider, högst en per student", det tolkar jag som att kravet är att varje student får redovisa 0 eller 1 gång. Vad gäller?

Lärare kommenterade 29 december 2016

Det stämmer Sara. I den uppdaterade uppgiftslydelsen står "högst en per student" vilket betyder 0 eller 1. Det är det som gäller.

 
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 1 september 2016

Kan därmed läsas av alla och ändras av lärare.
En användare har tagit bort sin kommentar
kommenterade 5 september 2016

När jag kompilerar tokenizer.c får jag dessa varningar: Kompilering

När jag sedan använder mig av den kompilerade a.out och lagrar detta till en fil genom kommandot ./a.out < korpus > output så ser jag följande i output filen: Output fil

Hanteringen av ÅÄÖ är alltså inte korrekt.
Någon som känner igen problemet och kanske har en lösning?

Lärare kommenterade 5 september 2016

Alexander, kompilatorvarningen är nog ingen fara. Du kan prova att ge väljaren 
-Wno-invalid-source-encoding
för att slippa varningen om teckenkodningen.

För att se åäö korrekt i terminalfönstret måste du ställa in terminalfönstrets teckenkodning i någon meny till terminalprogrammet. Välj ISO-8859-1 eller ISO-Latin-1.

kommenterade 5 september 2016

Du har helt rätt Viggo, tack för hjälpen!

kommenterade 7 september 2016
  • snabbhet (antal filläsningar och filpositioneringar per sökning)

"filpositionering" och "filpositioneringar" ger 9 resp 7 träffar på google (länkar hit inkluderade). Vad åsyftas egentligen?

Lärare kommenterade 7 september 2016

Med filpositionering avses anrop av seek eller motsvarande funktion, se labbeskrivningen ovan.

kommenterade 10 september 2016

Hej!
Ska användare även kunna söka efter siffror eller tecken, såsom "40" eller "@"?

/ Alfrida

Assistent kommenterade 10 september 2016

Nej, det enda som programmen ska kunna hantera är bokstäver

kommenterade 11 september 2016

Är tanken att vi ska använda Bob Jenkins hashfunktion för latmanshashningen av prefix (aaa, aab, aac osv)?

Vill minnas att det talades om någon hashfunktion som producerar lägre tal, och alltså skulle passa för en mindre array med bara så många index som behövs för alla prefix. Men jag kan minnas fel, eller så var tanken att vi själva skulle skriva en sån hashfunktion?

Lärare kommenterade 11 september 2016

Ernst, det är inte bra att använda Bob Jenkins hashfunktion i detta fall. Använd en så enkel hashfunktion som möjligt som inte gör några krockar. På föreläsning 3 var det en färgfråga om detta. Tipset där var att använda en förberäknad funktion som omvandlar mellanslag till 0, a till 1, b till 2 etc och med hjälp av detta tolkar dom tre bokstäverna i prefixet som ett tal i bas 30.

kommenterade 11 september 2016

Aha ok, ja det bör ju inte vara så svårt. Tack!

En användare har tagit bort sin kommentar
kommenterade 14 september 2016

Är det ett formellt krav att vi ska använda oss av binärsökning för att hitta rätt ord inom en "prefix-grupp"? Det verkar som att linjär sökning går tillräckligt snabbt i det här fallet.

Lärare kommenterade 14 september 2016

Ernst, är du säker på att linjär sökning är tillräckligt snabbt för alla ord? Jag vill att den som gått ADK alltid ska använda binärsökning istället för linjärsökning i tidskritiska algoritmer. Det är så enkelt att programmera binärsökning så det ska mycket till för att inte använda det.

kommenterade 15 september 2016

Rad 48 i tokenizer.c borde ändras till
printf("%s %10ld\n", buf, startpos);
Då paddas siffrorna från tokenized med mellanslag, vilket gör att när den skickas till sort kommer den att sortera siffrorna i numerisk ordning istället för teckenordning. dvs:
a   20
a 100

istället för som det nu blir:
a 100

a 20

Det gör att sammanhangen skrivs ut i den ordningen som de faktiskt förekommer i korpus-filen. Några fel blir lättare att hitta och saker beteer sig allmänt mer som man väntar sig.

Lärare kommenterade 15 september 2016

Mikael, det är en bra idé, men vi kan inte ändra labbfilerna under pågående kurs, så ändringen görs till nästa år. Tack för idén!

kommenterade 16 september 2016

Hej, en fråga inför redovisningen: alla datorer är upptagna i spel- och sporthallen. Är det okej att redovisa på egen laptop? Vår sökning går snabbare på skolans datorer ändå.

Lärare kommenterade 16 september 2016

Vi räknar med att den som redovisat lämnar sin dator, så därför kommer det att bli lediga datorer efterhand. Det är 7-8 labbhandledare som tar emot redovisningar parallellt, så även om kön ser avskräckande lång ut så kommer den att betas av i rask takt.

kommenterade 8 december 2016

Jag har ännu inte fått Labb1 inrapporterad i Rapp (däremot Labb 2, 3 och 4). Normal fördröjning eller bör jag undersöka saken vidare?

Lärare kommenterade 8 december 2016

Johan, om en labb inte har kommit in i Rapp vid det här laget så är det något fel. Var snäll och visa upp ditt påskrivna labbkvitto så för jag in resultatet i Rapp.

 
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 1 september 2016

Kan därmed läsas av alla och ändras av lärare.
kommenterade 4 september 2016

Hej! Om man klarade några av labbarna (inte alla) förra året - är det tillåtet att göra om dem i år för att få bonuspoäng till tentan?

Lärare kommenterade 4 september 2016

Anna-Karin, det går bra att göra om labbteorin och labbarna för att samla nya bonuspoäng.

kommenterade 5 september 2016

Hej, söker en labbpartner:)

kommenterade 28 oktober 2016

När kommer labb 4?

Lärare kommenterade 28 oktober 2016

Labb 4 läggs upp under kommande vecka, förhoppningsvis på måndag 31 oktober. Vi håller på att förbättra Kattisdomaren.

kommenterade 7 december 2016

Frågor angående labbredovisning.

1) Går det att komma in till datorsalarna utan passerkort?

2) Behöver man något speciellt konto för att logga in på datorerna? (Eller räcker det vanliga KTH.SE-kontot som används för webbsidan/Kattis?)

kommenterade 7 december 2016
  1. Nej, men du kan förhoppningsvis beviljas åtkomst om du har ett passerkort och i ett mejl till kortexp@kth.se berättar att du läser kursen. Uppge gärna ditt personnummer och ditt passerkortsnummer för smidigare handläggning.
  2. Man använder uppgifterna för sitt KTH-konto för att logga in på CSC-skolans Ubuntu-datorer.
 
November 2016
Lärare Viggo Kann skrev inlägget 22 november 2016
 
under HT 2016 adk16

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 16 september 2016

Kan därmed läsas av alla och ändras av lärare.
kommenterade 28 september 2016

Vilken algoritm syftar första teoriuppgiften till? "Jämför tidskomplexiteten för algoritmen då grafen implementeras som en grannmatris och då den implementeras med grannlistor."

Lärare kommenterade 28 september 2016

Albin, det syftar på algoritmen för att hitta bästa bipartita matchningen, vilket man kan förstå av meningen "Uttryck tidskomplexiteten i n och m där n är totala antalet hörn och m antalet kanter i den bipartita grafen."

kommenterade 28 september 2016

Vad är relationen mellan c[u,v] och c[v,u]? I indatan får man t.ex. att c[1,2] = 1, men det står ingenting om c[2,1] för kapaciteten går väl bara åt ett håll.

Lärare kommenterade 28 september 2016

Abdallah, det kan finnas kapaciteter (som är olika) i båda riktningarna mellan två hörn, se föreläsningen eller boken för exempel. Om en kapacitet inte omnämns i indata så är den noll.

kommenterade 30 september 2016

Länken till Unixhäftet funkar inte, skulle det gå att fixa?

Tack på förhand!

Lärare kommenterade 30 september 2016

Johan, jag har uppdaterat länken, men det hjälper inte just nu eftersom det är något fel på själva PDF-dokumentet. Jag har felanmält till IT-avdelningen. Tills vidare kan du kolla på den här sidan.

En användare har tagit bort sin kommentar
kommenterade 25 oktober 2016

Hej!

I testfallen i Kattis, i del 2 av denna labb - kan flödesgrafens kapaciteter vara större än 1? För att lösa matchningsproblemet i hela labben använder man ju annars bara ett flöde av max 1.

Lärare kommenterade 25 oktober 2016

Anna-Karin, i flödesgraferna som Kattis testar i del 2 kan kapaciteterna vara större än 1.

kommenterade 27 oktober 2016

I första slingan i Ford-Fulkersons algoritm, om exempelvis c(1,2) = 16, vad är då c(2,1)? Är den -16? 0?

Lärare kommenterade 27 oktober 2016

c[1,2] är kapaciteten från hörn 1 till hörn 2. c[2,1] är kapaciteten från hörn 2 till hörn 1. Dessa är oberoende av varandra.

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 2 november 2016

Hur skall man kunna introducera ett flöde mellan kanterna?

Lärare kommenterade 3 november 2016

Jonathan, flödet går längs kanterna i flödesgrafen. I pseudokoden för Ford-Fulkerson ovan ökas flödet längs en kant på den näst sista raden (i den inre for-slingan).

kommenterade 4 november 2016

Vilken tid öppnas queue för labben?

Vissa har seminarium i Vettig mellan 14 och 15 vilket innebär att det skulle vara trevligt att kunna redovisa inom intervallet 13-14. Märkte att kön är stängd (är förvisso ute i kanske lite väl god tid) så tänkte höra när den öppnar?

En användare har tagit bort sin kommentar
Lärare kommenterade 4 november 2016

Patrick, labbkön öppnas cirka kl 11.30 idag. Men på grund av en krockande programmeringstävling så har vi färre handledare än normalt, så redovisningarna måste spridas ut ganska jämnt över hela labbtiden 13-17. Den som har krockande undervisning 14-15 rekommenderas att redovisa efter kl 15 istället.

Sylwester, matchtest ger felutskrifter om beskrivningen av den bipartita grafen inte uppfyller kraven på indata i uppgiftslydelsen: Hörnen numreras från 1 och uppåt. Om man angett a hörn i X och b hörn i Y så låter vi X = {1, 2,..., a} och Y = {a+1, a+2,..., a+b}. Y är alltså den högra partitionen.

 
September 2016
Lärare Viggo Kann skrev inlägget 28 september 2016
 
Lärare Viggo Kann skrev inlägget 26 september 2016
kommenterade 26 september 2016

Hej! 
Det är synd att ni först nu informerar om att ni ska gå igenom uppgift 1 och 2 på dagens föreläsning. I detaljschemat står det inget om detta, vilket gör att jag som jobbar extra och har läst motsvarande läsning inte har möjlighet att boka av mitt jobb i eftermiddag med så kort varsel.

Jag hoppas att det är ok att jag mailar er eller övningsasse och dubbelkollar att jag uppfattat uppgifterna rätt istället.

Vänliga hälsningar
Alfrida 

Lärare kommenterade 26 september 2016

Hej Alfrida! Mästarproven är skrivna så att formuleringarna ska vara entydiga, och alla lärare och övningsassistenter på kursen har gått igenom formuleringarna. Om det ändå kvarstår någon otydlighet så vill vi att ni i första hand frågar oss i samband med föreläsningar, övningar eller labbar. Mejl är ett ineffektivt medium för sån kommunikation. 

 
Feedback Nyheter