„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés
| 454. sor: | 454. sor: | ||
===Algoritmusok, eljárások és egyebek=== | ===Algoritmusok, eljárások és egyebek=== | ||
* Euklideszi algoritmus: polinomrendű algoritmus két szám (_a_ és _b_) legnagyobb közös osztójának meghatározására. Tegyük fel, hogy <math>a>b</math>, ekkor: | * Euklideszi algoritmus: polinomrendű algoritmus két szám (_a_ és _b_) legnagyobb közös osztójának meghatározására. Tegyük fel, hogy <math>a>b</math>, ekkor: | ||
*# Felírjuk a nagyobb számot, mint a kisebb számmal vett hányados és a kisebb szám sorzata, valamint az osztási maradék összegeként: <math> a = h_1 b + m_1 </math>. | |||
*# Az egészet "balra shifteljük": <math> b = h_2 m_1 + m_2 </math>, majd megint: <math> m_1 = h_3 m_2 + m_m </math>, és így tovább. | |||
*# Egészen addig, amíg az nem lesz, hogy <math> m_n = h_{n+2} m_{n+1} + 0 </math>. Ekkor <math> m_{n+1} </math> a lnko. | |||
==16. Kongruencia fogalma, teljes és redukált maradékrendszer, <math>\varphi</math>-függvény, Euler-Fermat-tétel, kis-Fermat-tétel, lineáris kongruenciák megoldása, Wilson-tétel== | ==16. Kongruencia fogalma, teljes és redukált maradékrendszer, <math>\varphi</math>-függvény, Euler-Fermat-tétel, kis-Fermat-tétel, lineáris kongruenciák megoldása, Wilson-tétel== | ||