„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés

Melyik állítás igaz az alábbiak közül?

{{Kvízkérdés|típus=egy|válasz=1}}

# Az <math>A C</math> élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.

# Az <math>A C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.

Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq N P</math> ?

{{Kvízkérdés|típus=egy|válasz=1}}

# <math>X_{1} \in P</math> és <math>X_{2} \in P</math>

# <math>X_{1} \in \operatorname{coN} P</math> de <math>X_{1} \notin P</math>

Az <math>A[1: n]</math> tömb alapján egy <math>P[1: n]</math> és egy <math>N[1: n]</math> tömböt töltünk ki a következőképpen:

* ha <math>A[1]>0</math> akkor <math>P[1]=A[1]</math> és <math>N[1]=A[1]</math> .

A további értékeket <math>(i>2)</math> így számoljuk:

* ha <math>A[i]>0</math> akkor <math>P[i]=P[i-1]+A[i]</math> és <math>N[i]=\max \{N[i-1]+A[i], A[i]\}</math>

Melyik állítás igaz az alábbiak közül a kiszámolt <math>P[i]</math> és <math>N[i]</math> értékek jelentésére?

# <math>N[i]</math> megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó <math>A[j: i]</math> résztömbből ( <math>1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.

# <math>P[i]</math> megadja a legnagyobb összeget, amit valamelyik <math>A[j: i]</math> résztömbből <math>(1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.

== Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet <math>G</math>-hez úgy, hogy a keletkező gráfban legyen 100 pontú teljes részgráf. (Új csúcsot nem adunk hozzá a gráfhoz, csak éleket húzunk be a már meglevő csúcsok közé.) (2023 jan) ==

Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq N P</math> ?

# A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben.

# A probléma <math>NP</math>-teljes és nincs <math>P</math>-ben.

# A (b), a (c) és a (d) függvény is <math>O\left(n^{2}\right)</math>

{{Kvízkérdés|típus=egy|válasz=3}}

# <math>n</math>

== Egy város úthálózatát a <math>G</math> egyszerú, irányítatlan, összefüggő gráf írja le, a gráf csúcsai a csomópontok, az élek az ezeket összekötőútszakaszokat jelölik. (2021 jan) ==

Az utak sajnos eléggé rossz állapotúak, minden élre adott, hogy azt az útszakaszt mennyiért lehetne felújítani.

A következő ötletek merültek fel a legolcsóbb ilyen felújitás megtalálására:

A: Dijkstra algoritmusával határozzák meg a legrövidebb utakat <math>v</math>-ből az összes többi csúcsba.

== Tegyük fel, hogy <math>\mathrm{P} \neq \mathrm{NP}</math> Tekintsük azt a problémát, amikor adottak az <math>a_{1}, a_{2}, \ldots, a_{n}</math> pozitív egész számok, és azt kell eldönteni, hogy van-e olyan <math>I \subseteq\{1,2, \ldots, n\}</math>, melyre <math>\sum_{i \in I} a_{i}=2020</math> (2020 jan) ==

{{Kvízkérdés|típus=egy|válasz=1}}

# A probléma P-ben és NP-ben is benne van.

# A probléma P-ben van, de nincs NP-ben.

| mélységi  || 4 || 3 || 2 || 5 || 1 || 6

|-

|}

Melyik élről állíthatjuk biztosan, hogy nem lehet a gráfban?