Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil. [16]. Fibonacci arvud. Üldliikme valem ja rakendused. [17]. Lucas` arvud. [18]. Catalani arvud. [19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus. [20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis. [21]. Täistõenäosuse valem. Bayesi reegel. [22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral). [23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud
Vahel võib tulla vale vastus, aga väikese tõenäosusega. Otsimine toimub juhuslikkuse printsiibil. Neid on 2 rühma: Las Vegas: juhuslikult võta 1, kuni tuleb “1”. Quicksort, krüptograafia. Sobib, kui on vähe võimalusi, aga raske leida õiget: alati õige vastus, aga võib minna väga palju aega. Monte Carlo: k korda vali 1 element, kui k korda on läbi, siis ei leidnud. Võib anda vale vastuse (aga alati saab ju korrata), aga aeg (ressursid) on mõistlikud. Algarvulisuse testid, statistilised simulatsioonid. 32 Fermat väike teoreem ja algarvulisuse testid. ap - a jagub p-ga, kui p on algarv. • a erinevat värvi pärlitest saab teha ap kombinatsiooni. (nt 2 värvilistest 8 kombinatsiooni) • lahutame neist a ühevärvilist kombinatsiooni. (ap - a) • saadud kombinatsioonid kuuluvad gruppidesse. saame (ap - a)/p ühesuurust (pxp) gruppi, mis kõik moodustavad p-sammulised tsüklid. (p sammu on vaja teha, et jõuda algsesse asendisse tagasi.)
annaabi.ee 
