Sist endret: 23.09.2016  
 
Øvinger
 
Blackboard
Piazza
 
IDI
NTNU
 
haakowar logget inn
Poengoversikt

Løsningsforslag - Problemer og algoritmer

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 04.09.2017 15:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.

Oppgave 1

[ riktig ]a) En instans av et problem er ... (12.5 %)

en sub-klasse av problemet.
en super-klasse av problement.
løsning på et problem.
en algoritme som løser problemet i polynomisk tid.
input til et problem.
uløselig i polynomisk tid.

Din kommentar: forenklet versjo
LF-forklaring: Definisjon fra kap 1.1 i Cormen.

[ riktig ]b) Hvilket alternativ beskriver best algoritmer og datastrukturer? (12.5 %)

En algoritme brukes til å løse et enkelt problem. Datstrukturer kobler sammen algoritmer for å løse mer komplekse problemer.
En algoritme er et program. En datastruktur består av interminne og harddisk.
En algoritme er en punktvis og detaljert løsningsmetode. En datastruktur uttrykker innholdet og syntaksen i et dataprogram.
En algoritme beskriver utvetydig hvordan et problem kan løses. Algoritmen lager data i (og henter fra) datastrukturer.
En algoritme er en formel, som når gitt en datastruktur som input regner ut et svar (output).

Din kommentar:
LF-forklaring: Det finnes mindre nyanser i definisjonen til en algoritme, men hovedtrekkene er som beskrevet i kap. 1.1. i Cormen. Datastrukturer brukes for å organisere de dataene som algoritmen skal jobbe med (se kap 1.1).

[ riktig ]c) Hva er pseudokode? (12.5 %)

En måte å spesifisere algoritmer på, uavhengig av naturlig språk.
En måte å spesifisere algoritmer på, uavhengig av spesifikke programmeringsspråk.
Et universelt språk for å spesifisere algoritmer, slik at en datamaskin kan kjøre dem.
Et programmeringsspråk, brukt for å programmere algoritmer.

Din kommentar:
LF-forklaring: Pseudokode kan likne på kode skrevet i et programmeringsspråk men er ikke ekte kode. Det er ofte en blanding av naturlig språk og konstruksjoner som man vanligvis finner i programmeringsspråk (if, for, while, etc.).

[ riktig ]d) I dette faget vil vi i hovedsak vurdere algoritmer ut fra ... (12.5 %)

hvor raskt den kan implementeres.
hvordan kjøretiden vokser når n går mot uendelig.
kjøretiden for gjennomsnitts-input.
minnebruk for gjennomsnitts-input.
hvor elegante de er.
hvordan kjøretiden vokser når størrelsen på input går mot uendelig.

Din kommentar:
LF-forklaring:

Oppgave 2

I denne oppgaven skal vi se på en variant av spillet Nim. Reglene er som følger: To spillere skal etter tur plukke vekk fyrstikker fra en haug på bordet. Den som plukker opp den siste fyrstikken har tapt. Hver spiller må plukke opp mins en fyrstikk i hver runde, og kan maksimal plukke opp seks fyrstikker.

[ riktig ]a) Hvis det er 5 fyrstikker igjen, hvor mange må du ta for å vinne? (12.5 %)

1
2
3
4
5
6
Det er ikke sikkert at jeg vinner, uansett hvor mange jeg tar.

Din kommentar:
LF-forklaring: Ta alle bortsett fra en, slik at motstanderen blir tvunget til å ta den siste.

[ riktig ]b) Hvis det er 10 fyrstikker igjen, hvor mange må du ta for å vinne? (12.5 %)

1
2
3
4
5
6
Det er ikke sikkert jeg vinner, uansett hvor mange jeg tar.

Din kommentar:
LF-forklaring: Ved å ta bort to, sørger du for at motstanderen ikke kan ta alle de som er igjen, og at han eller hun ikke kan tvinge deg til å ta den siste.

[ riktig ]c) Hvis det er 250 fyrstikker igjen og det er din tur, hvor mange fyrstikker må du ta for å vinne? (Hint: finn en generell strategi.) (12.5 %)

1
2
3
4
5
6
Det er ikke sikkert jeg vinner, uansett hvor mange jeg tar.

Din kommentar:
LF-forklaring: Hvis du tar fire, så er det 246 igjen. Hvis du siden sørger for å hele tiden ta så mange at de de motstanderen nettopp tok og de tur tar tilsammen blir 7 stykker, så vet du at motstanderen blir sittende igjen med den siste, siden resten får når du deler 246 med 7 er 1.

[ feil ]d) Hvis det er 134 fyrstikker igjen, hvor mange må du ta for å vinne? (12.5 %)

1
2
3
4
5
6
Det er ikke sikkert jeg vinner, uansett hvor mange jeg tar.

Din kommentar:
LF-forklaring: LF: Dersom motstanderen spiller optimalt, etter samme strategi som beskrevet i forrige deloppgave, så er det ingen garanti for å finne da resten etter 134 delt på 7 er 1.