Prirodno-matematički fakultet, 18.03.2020

Materijali



Dok traje privremena obustava nastave studenti mogu koristiti materijal u prilogu. Skeniranu svesku, ukupno 75 strana podjeljenih u dva dijela od 1 do 40 i od 41 do 75. U njoj se nalazi dio predavanja. Studenti mogu samostalno da citaju Algoritme u teoriji brojeva. Napominjem da taj dio nece biti naknadno predavan i nece dolaziti pitanja iz te oblasti.

Ipak sto se tice vjezbi predlazem da procitate Karatcubin i Tomov algoritam za mnozenje velikih brojeva (iz sveske) i pogledate kod u prilogu. To ce vam omoguciti da krenete sa implementacijum Tom_Kukovog algoritma za k=3 (Toom-3). Pogledati Toom–Cook_multiplication Implementacija mora biti u C-programskom jeziku, a moze se koristiti kod u prilogu. Dozvoljeno je da vise studenata brani isti kod ako su radili zajedno. Implementacija ovog algoritma ce biti bodovana sa 25 bodova tj. kao drugi kolokvijum. U slucaju brze normalizacije nastave ovo ce biti odradjeno na vjezbama ili predavanjima... Eventualna pitanja slati na milenko@ucg.ac.me

Kolokvijum je zakazan za 22.4. u 8h sala 106 i na njemu ce biti samo gradivo koje je do sada ispredavano ne ukljucujuci problem poplocavanja. Ako do tog datuma ne dodje do normalizacije nastave provjera znanja ce biti organizovana naknadno i u skladu sa situaciom.

Dopuna (23.3.). Algoritam Toom-3 treba da se brani i to ce biti 13 ili 14 nedelje nastave, ako dodje do normalizacije nastave. U tom smislu za sada ne treba slati nikakav kod vec samo raditi na njegovoj implementaciji. Ako nastava ne bude normalizovana onda cu saopstiti naknadno kako braniti algoritam. Takodje, veliki broj treba pamtiti u nizu recimo A. Duzina i znak se pamte u A[0] zatim cifra najnize tezine u A[1],... Osnova (baza) treba da je stepen 10, ali se preporucuje da to bude 10000. Algoritam treba da radi korektno i ako se baza promjeni npr. na 100. Vrijednost zapamcenog broja se moze sracunati formulom sign(A[0])*(A[1]+A[2]*B+A[3]*B^2+...+A[|A[0]|]*B^{|A[0]|-1}) gdje je B baza. Tako se broj:

- 453 0098 4567 1092 3475 u bazi sa osnovom 10000 pamti kao:

A[0]=-5  , A[1]=3475 , A[2]=1092, A[3]=4567 , A[3]=98, A[5]=453

 

Dokumenti

Broj posjeta : 796