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

29. sor:

# <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math>

# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math>

== Egy <math>n \times n</math>-es táblázat mezőin akarunk eljutni a bal felső cellából az utolsó sorba (itt mindegy, hogy a soron belül melyik oszlopba érkezünk). (2022 jun) ==

A szabályok a következők:

* Az első oszlop első mezőjéről kell indulnunk és a végén az utolsó sor tetszőleges mezőjére kell érkeznünk.

* Egy lépésben vagy egy cellát mehetünk lefele (és maradunk ugyanabban az oszlopban) vagy egy cellát megyünk jobbra (és maradunk ugyanabban a sorban) vagy átlósan lépünk egyet lefele jobbra (azaz egy sort lefele és egy oszlopnyit jobbra).

Jelölje <math>T[i, j](1 \leq i, j \leq n</math> esetén) azt, hogy az <math>i</math>-edik sor <math>j</math>-edik oszlopában levő mezőbe hányféleképpen juthatok el a bal felső cellából.

Inicializáljuk a kezdeti értékeket így: mivel az első sor minden cellájába egyféleképpen juthatunk, ezért <math>T[1, j]=1</math> minden <math>1 \leq j \leq n</math> esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért <math>T[i, 1]=1</math> minden <math>1 \leq i \leq n</math> esetén.

Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására?

# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]</math>

# <math>T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}</math>

# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1</math>

# <math>T[i, j]=T[i-1, j-1]+1</math>

Az előző feladat folytatása:

A teljesen kitöltött <math>T</math> táblázat segítségével hogyan kaphatjuk meg azt, hogy hányféleképpen lehet eljutni a bal felső cellából a legalsó sorba?

# <math>\max _{1 < i < n} T[i, n]</math> adja meg ezt.

# <math>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt.

# <math>T[n, n]</math> adja meg ezt.

# <math>\max _{1 \leq j \leq n} T[n, j]</math> adja meg ezt

# <math>\Sigma_{j=1}^{n} T[n, j]</math> adja meg ezt.

== A <math>G</math> egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun) ==

Tekintsük a következő állításokat:

A: <math>G</math> minden minimális feszítőfája tartalmazza a legkisebb súlyú élt.

B: <math>G</math> minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt.

C: <math>G</math> egyik minimális feszítőfája sem tartalmazza a legnagyobb súlyú élt.

Melyik a helyes az alábbi lehetőségek közül?

# Csak az <math>A</math> állítás igaz, a másik kettő nem

# Az <math>A</math>, a <math>B</math> és a <math>C</math> állítás is igaz.

# Csak az <math>A</math> és a <math>B</math> állítás igaz, a <math>C</math> nem.

# Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem.

== Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun) ==

Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?

# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re.

# <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re.

# <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re.

# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.

== Tekintsük azt a <math>K_{20,40}</math> teljes páros gráfot, melynek <math>A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}</math> és <math>B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}</math> a két osztálya. Hány maximális (azaz tovább nem bővíthető) párosítás van ebben a gráfban? (Két párosítás különböző, ha nem pontosan ugyanazokból az <math>\left(a_{i}, b_{j}\right)</math> élekből áll.) (2022 jun) ==

# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20</math> !

# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right)</math>

# <math>40^{20}</math>

# <math>40!</math>

== Az <math>1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16</math> tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun) ==

# 0

# 64

# <math>\left(\begin{array}{c}16 \\ 2\end{array}\right)</math>

# 32

== Az <math>\mathcal{A}</math> algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, <math>n</math>-nek a függvényében <math>O\left(n^{2}\right)</math>. (2022 jun) ==

Melyik nem igaz az alábbiak közül?

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n^{3}</math>.

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n^{3}</math>.

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n</math>.

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n</math>.

== Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): <math>10, 5, x, 7, 8</math>. Az alábbiak közül mi igaz x értékére? (2022 jan) ==

@@ 29. sor: / 29. sor: @@
 # <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math>
 # <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math>
+== Egy <math>n \times n</math>-es táblázat mezőin akarunk eljutni a bal felső cellából az utolsó sorba (itt mindegy, hogy a soron belül melyik oszlopba érkezünk). (2022 jun) ==
+A szabályok a következők:
+* Az első oszlop első mezőjéről kell indulnunk és a végén az utolsó sor tetszőleges mezőjére kell érkeznünk.
+* Egy lépésben vagy egy cellát mehetünk lefele (és maradunk ugyanabban az oszlopban) vagy egy cellát megyünk jobbra (és maradunk  ugyanabban a sorban) vagy átlósan lépünk egyet lefele jobbra (azaz egy sort lefele és egy oszlopnyit jobbra).
+Jelölje <math>T[i, j](1 \leq i, j \leq n</math> esetén) azt, hogy az <math>i</math>-edik sor <math>j</math>-edik oszlopában levő mezőbe hányféleképpen juthatok el a bal felső cellából.
+Inicializáljuk a kezdeti értékeket így: mivel az első sor minden cellájába egyféleképpen juthatunk, ezért <math>T[1, j]=1</math> minden <math>1 \leq j \leq n</math> esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért <math>T[i, 1]=1</math> minden <math>1 \leq i \leq n</math> esetén.
+Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]</math>
+# <math>T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}</math>
+# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1</math>
+# <math>T[i, j]=T[i-1, j-1]+1</math>
+Az előző feladat folytatása:
+A teljesen kitöltött <math>T</math> táblázat segítségével hogyan kaphatjuk meg azt, hogy hányféleképpen lehet eljutni a bal felső cellából a legalsó sorba?
+{{Kvízkérdés|típus=egy|válasz=5}}
+# <math>\max _{1 < i < n} T[i, n]</math> adja meg ezt.
+# <math>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt.
+# <math>T[n, n]</math> adja meg ezt.
+# <math>\max _{1 \leq j \leq n} T[n, j]</math> adja meg ezt
+# <math>\Sigma_{j=1}^{n} T[n, j]</math> adja meg ezt.
+== A <math>G</math> egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun) ==
+Tekintsük a következő állításokat:
+A: <math>G</math> minden minimális feszítőfája tartalmazza a legkisebb súlyú élt.
+B: <math>G</math> minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt.
+C: <math>G</math> egyik minimális feszítőfája sem tartalmazza a legnagyobb súlyú élt.
+Melyik a helyes az alábbi lehetőségek közül?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Csak az <math>A</math> állítás igaz, a másik kettő nem
+# Az <math>A</math>, a <math>B</math> és a <math>C</math> állítás is igaz.
+# Csak az <math>A</math> és a <math>B</math> állítás igaz, a <math>C</math> nem.
+# Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem.
+== Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun) ==
+Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re.
+# <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re.
+# <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re.
+# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.
+== Tekintsük azt a <math>K_{20,40}</math> teljes páros gráfot, melynek <math>A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}</math> és <math>B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}</math> a két osztálya. Hány maximális (azaz tovább nem bővíthető) párosítás van ebben a gráfban? (Két párosítás különböző, ha nem pontosan ugyanazokból az <math>\left(a_{i}, b_{j}\right)</math> élekből áll.) (2022 jun) ==
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20</math> !
+# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right)</math>
+# <math>40^{20}</math>
+# <math>40!</math>
+== Az <math>1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16</math> tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 0
+# 64
+# <math>\left(\begin{array}{c}16 \\ 2\end{array}\right)</math>
+# 32
+== Az <math>\mathcal{A}</math> algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, <math>n</math>-nek a függvényében <math>O\left(n^{2}\right)</math>. (2022 jun) ==
+Melyik nem igaz az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n^{3}</math>.
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n^{3}</math>.
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n</math>.
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n</math>.
 == Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): <math>10, 5, x, 7, 8</math>. Az alábbiak közül mi igaz x értékére? (2022 jan) ==