Algorithm Analysis: P and NP

Podcast

Play an AI-generated podcast conversation about this lesson

Download our mobile app to listen on the go

Get App

Questions and Answers

Hvað er átt við með ákvörðunarverkefni í samhengi við reiknirit?

Verkefni þar sem útkoman er rauntala.
Verkefni þar sem útkoman er annaðhvort já eða nei. (correct)
Verkefni þar þarf að finna stysta veg milli tveggja punkta.
Verkefni þar sem útkoman er listi af tölum.

Hvernig er tímaflækja reiknirits oftast mæld?

Með því að mæla meðaltíma yfir mörg keyrslutilfelli.
Með því að mæla versta tilfellis tíma. (correct)
Með því að mæla minnsta mögulega minnisnotkun.
Með því að mæla hraðasta tíma sem reikniritið getur keyrt.

Hvað táknar $T(n)$ í samhengi við reiknirit?

Besti tími sem reikniritið getur keyrt.
Meðaltími sem reikniritið keyrir yfir öll möguleg inntök.
Minnsta mögulega minnisnotkun reikniritsins.
Versti tími sem reikniritið getur keyrt miðað við inntaksstærð $n$. (correct)

Hvað er átt við með 'margliðutíma' í flækjugreiningu reiknirita?

Tíminn sem það tekur reiknirit að leysa verkefni vex í margliðufalli með stærð inntaksins. (B) Signup and view all the answers

Hvað þýðir það ef verkefni er í flokknum P ('polynomial time')?

Til er reiknirit sem leysir verkefnið í margliðutíma. (A) Signup and view all the answers

Hver er munurinn á Euler hring og Hamilton hring í grafi?

Euler hringur fer í gegnum allar brúnir nákvæmlega einu sinni, en Hamilton hringur fer í gegnum alla hnúta nákvæmlega einu sinni. (C) Signup and view all the answers

Hvers vegna er 'brute force' aðferðin ekki talin hagkvæm leið til að finna Hamilton hring í stóru grafi?

Vegna þess að fjöldi mögulegra hringa vex mjög hratt með stærð grafsins. (B) Signup and view all the answers

Hver er munurinn á því að ákvarða hvort tiltekið graf inniheldur Euler hring á móti Hamilton hring?

Að finna Euler hring er í flokknum P, en að finna Hamilton hring er í flokknum NP. (A) Signup and view all the answers

Gefin tala $N$, hver er tímaflækjan við að athuga hvort $N$ sé frumtala með því að deila í hana með öllum tölum frá 2 upp í $\sqrt{N}$?

$O(\sqrt{N})$ (C) Signup and view all the answers

Hvað er átt við með 'stærð inntaks' þegar tala $N$ er gefin sem inntak í reiknirit?

Fjöldi bita sem þarf til að tákna $N$ í tvíundakerfi. (C) Signup and view all the answers

Hver er áætluð stærð í bitum fyrir tölu $N$?

$\log_2(N)$ (A) Signup and view all the answers

Ef reiknirit hefur tímaflækju $O(\sqrt{N})$, og stærð inntaks er $n = \log_2(N)$, hver er þá tímaflækjan í tilliti til $n$?

$O(2^{n/2})$ (A) Signup and view all the answers

Hvað þýðir það að verkefni sé í flokknum NP?

Ef svarið er já, þá er til sönnun sem hægt er að staðfesta í margliðutíma. (B) Signup and view all the answers

Ef Hamilton-leið er í NP, hvað þýðir það?

Ef tiltekin leið er Hamilton-leið, þá er hægt að staðfesta það í margliðutíma. (B) Signup and view all the answers

Hvað einkennir co-NP flokkinn?

Ef svarið er nei, þá er til sönnun sem hægt er að staðfesta í margliðutíma. (D) Signup and view all the answers

Ef tala $N$ er ekki frumtala, hvað felur sönnun þess í sér?

Að finna tvær tölur $a$ og $b$, stærri en 2, þannig að $N = a * b$. (B) Signup and view all the answers

Hvað er átt við með því að frumtölur séu í bæði NP og co-NP?

Það er bæði auðvelt að sanna að tala sé frumtala og að tala sé ekki frumtala í margliðutíma. (D) Signup and view all the answers

Hvað felur í sér að öll verkefni í P eru einnig í NP?

Að öll verkefni sem hægt er að leysa í margliðutíma, geta haft sönnun sem hægt er að staðfesta í margliðutíma. (B) Signup and view all the answers

Ef verkefni A er í P, hvað þýðir það fyrir sönnun á tilviki af A?

Það er engin þörf á sönnun, þar sem hægt er að reikna svarið í margliðutíma. (D) Signup and view all the answers

Hvað er CircuitSAT verkefnið?

Að finna inntak fyrir gefna rafrás sem gefur útkomuna 1. (A) Signup and view all the answers

Ef CircuitSAT er í NP, hvað þýðir það?

Ef tiltekin inntaksgildi gefa útkomuna 1, þá er hægt að staðfesta það í margliðutíma. (B) Signup and view all the answers

Hver er munurinn á P og NP vandamálum?

P vandamál er hægt að leysa í margliðutíma, en fyrir NP vandamál er hægt að sannreyna lausn í margliðutíma ef hún er gefin. (C) Signup and view all the answers

Hver er skilgreiningin á NP-fullkomnum (NP-complete) vandamálum?

Vandamál sem er bæði í NP og hægt er að umbreyta öllum öðrum NP vandamálum í það í margliðutíma. (B) Signup and view all the answers

Hvað myndi það þýða ef sýnt væri fram á að P = NP?

Öll vandamál sem hægt er að sannreyna lausn fyrir í margliðutíma, væri einnig hægt að leysa í margliðutíma. (D) Signup and view all the answers

Hver er helsti munurinn á ákvörðunarvandamáli (decision problem) og hagræðingarvandamáli (optimization problem)?

Ákvörðunarvandamál spyrja já/nei spurningar en hagræðingarvandamál leita að bestu lausn. (A) Signup and view all the answers

Hvaða fullyrðing er sönn um samband P, NP og NP-fullkominna vandamála?

Öll P vandamál eru í NP. (C) Signup and view all the answers

Hvað er 'reducible' í samhengi við flækjustig NP vandamála?

Að vandamáli A er hægt að breyta í vandamál B þannig að ef B er leyst, þá er A einnig leyst. (A) Signup and view all the answers

Hver er munurinn á flækjustiginu $O(n)$ og $O(2^n)$?

$O(2^n)$ vex hraðar með inntaksstærð en $O(n)$. (D) Signup and view all the answers

Hver af eftirfarandi fullyrðingum er sönn um samband NP og co-NP?

Ef P = NP, þá er NP = co-NP. (C) Signup and view all the answers

Hvað er átt við með heildsölu reikniriti (heuristic algorithm)?

Reiknirit sem finnur hugsanlega góða lausn, en ekki er víst að hún sé sú besta. (A) Signup and view all the answers

Af hverju er dulkóðun mikilvæg í nútíma tölvunarfræði?

Til að tryggja að gögn séu ólæsileg fyrir óviðkomandi. (B) Signup and view all the answers

Hver er helsta áskorunin við að takast á við NP-fullkomin vandamál í raunveruleikanum?

Þau taka of langan tíma að leysa fyrir stór inntök. (A) Signup and view all the answers

Hvað er átt við með 'approximationsreiknirit' (approximation algorithm)?

Reiknirit sem finnur lausn sem er innan ákveðins vikmarka frá bestu lausn. (D) Signup and view all the answers

Ef þú ert með NP-fullkomið vandamál, hvaða aðferðir gætir þú notað til að takast á við það?

Leita að approximationsreiknirit eða heildsölu reikniriti. (A) Signup and view all the answers

Flashcards

Problem Solving

For every problem, we can often find an algorithm that solves it.

Decision Problem

A problem where the answer is either yes or no.

Worst-Case Time

Measuring an algorithm's efficiency by considering the worst-case scenario time complexity.

P (Polynomial Time)

All problems for which there exists an algorithm with a time complexity of O(n^c) for some constant c > 0.