Next: About this document ...
Számítástudomány elemei gyakorlat
10. feladatsor (2002. nov. 14.)
- Tegyük fel, hogy van egy
eljárásunk, mely egy
tetszőleges
input gráfra megmondja, hogy van-e
-ben
Hamilton-út. Tervezzünk olyan algoritmust, amely egy adott gráfban
a
eljárást használva polinom sok lépésben talál egy
Hamilton-utat!
(Vizsga, 1999. máj.)
- Mi az alábbi probléma bonyolultsága?
Input:
egyszerű gráf.
Kérdés: Két részre oszthatók-e
csúcsai úgy, hogy
mindkét rész egy-egy teljes részgráf legyen? (Vizsga, 1999. jún.)
- Vezessük vissza polinomiális időben a Hamilton-kör
létezésének problémáját arra, hogy egy adott gráf pontjai
lefedhetők-e 100 (pont)diszjunkt körrel? (ZH, 2001. máj.)
- Mi a bonyolultsága a következő feladatnak?
Input: egy
gráf és egy
pozitív egész szám.
Kérdés: Van-e
-nek olyan
feszítőfája, amelyre
páros fokú pontjainak száma legalább
? (Pótzh, 2001. máj.)
- Keressük meg az alábbi számok legnagyobb közös osztóját az
euklideszi algoritmus segítségével!
- Milyen
egész számokra teljesül, hogy
? (ZH,
2000. máj.)
- Hány olyan
pár van, melyre
és
? Soroljuk fel az összes lehetséges esetet!
- Határozzuk meg az összes olyan
egész számot,
amelyekre teljesül, hogy
pozitív osztóinak száma háromnak egy
hatványa! (Pótzh, 2001. máj.)
- Hány olyan osztója van a
-nak,
ami 0-ra végződik? (Vizsga, 2000. dec.)
- Jelölje
a
-adik Fibonacci-számot, azaz legyen
, és ha
, akkor
. Található-e
olyan
, hogy
és
is osztható hárommal?
(ZH, 1999. máj.)
Next: About this document ...
Veto Balint
2002-11-14