{VERSION 2 3 "IBM INTEL NT" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 310 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 312 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 313 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" 18 331 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 335 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 1 12 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 353 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 355 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Hea ding 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 " " 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 } {PSTYLE "Heading 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 5 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 2 2 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "restart:with(linalg) :with(plots):" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, new definition \+ for norm" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for t race" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 27 "V\365redega seotud p\365 him\365isted" }}{PARA 0 "" 0 "" {TEXT 340 17 "V\365re definitsioon" }} {PARA 0 "" 0 "" {TEXT -1 9 "V\365reks L(" }{XPPEDIT 18 0 "b[1]" "&%\"b G6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" } {TEXT -1 4 ",..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 82 " ) nimeteatakse, m-komponendiliste reaalarvuliste lineaarselt s\365ltum atute vektorite" }{MPLTEXT 1 0 1 " " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\" \"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }}{PARA 0 "" 0 "" {TEXT -1 59 "k\365ikv\365imalike t\344isarvulisite lineaarkombinatsioo nide hulka." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 336 62 "Edaspidi vaatame ainult t\344isarvuliste komponentidega v\365r esid. " }{TEXT -1 162 "On lihtne aru saada, et nii oleme vaadanud ka r atsionaalarvuliste komponentidega v\365red. Me v\365ime viia k\365ik v ektorite komponendid \374hisele nimetajale N ja selle n\366." }}{PARA 0 "" 0 "" {TEXT -1 96 "k\365ikide vektorite ette tuua st. veidi formaa lsemalt r\344\344kides korraldame isomorfismi F hulgast L(" }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&% \"bG6#\"\"#" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 38 ") t\344isarvuliste komponentidega L'=N*L(" }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"b G6#\"\"#" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" } {TEXT -1 7 "), kus " }{XPPEDIT 18 0 "F(b[i])" "-%\"FG6#&%\"bG6#%\"iG" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "N*b[i]" "*&%\"NG\"\"\"&%\"bG6#%\"iGF$ " }{TEXT -1 2 ". " }{TEXT 339 69 "Kuna peamiselt huvitavad meid strukt uuri lineaaromadused ja meetrika" }{TEXT -1 419 ", mille F samuti s \344ilitab, siis pole m\365tet ratsionaalseid v\365resid vaadata. Irra tsionaalsete v\365rede korral pole asjad esiteks nii lihtsad ning teis eks ei anna irratsionaalsuste lubamine meile midagi juurde, sest v\365 re on algebralises m\365istes projektiivne moodul \374le Z (Mati Kil p, \"Algebra II\", lk 50-51) ja seega esitatav t\344isarvuliste vekto rite kaudu ning meetrika on v\365imalik vastava normi defineerimisega \+ \374le kanda." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 337 12 "V\365re baasiks" }{TEXT -1 130 " nimetatakse lineaarselt s\365ltumatute vektorite hulka v\365res, mille t\344isarvuliste linea arkombinatsioonidena avaldub iga v\365re vektor." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "V\365re baasiga seotakse \+ " }{TEXT 338 13 "baasimaatriks" }{TEXT -1 162 " B, mille veergudeks on baasi vektorid (m*n maatriks). \334helt baasilt teisele \374leminekum aatriksitel T on j\344rgmine oluline omadus det T=+-1. See tuleneb sel lest, et" }}{PARA 0 "" 0 "" {TEXT -1 2 "T*" }{XPPEDIT 18 0 "T^(-1)" ") %\"TG,$\"\"\"!\"\"" }{TEXT -1 69 "=E. Samuti ilmneb, et sellise omadus ega maatriksid moodustavad r\374hma." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 5 "N\344ide" }}{PARA 0 "" 0 "" {TEXT -1 15 "Vaatame v\365ret \000" }{XPPEDIT 18 0 "Z^2" "*$%\"ZG\"\"# " }{TEXT -1 26 ", mille \374heks baasiks on " }{XPPEDIT 18 0 "b[1]=(1 ,0)" "/&%\"bG6#\"\"\"6$\"\"\"\"\"!" }{TEXT -1 4 " ja " }{XPPEDIT 18 0 "b[2]=(0,1)" "/&%\"bG6#\"\"#6$\"\"!\"\"\"" }{TEXT -1 25 " ning teiseks baasiks on " }{XPPEDIT 18 0 "c[1]=(1,0)" "/&%\"cG6#\"\"\"6$\"\"\"\"\" !" }{TEXT -1 4 " ja " }{XPPEDIT 18 0 "c[2]=(1,1)" "/&%\"cG6#\"\"#6$\" \"\"\"\"\"" }{TEXT -1 11 ", kusjuures" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "b[1]=c[1]" "/&%\"bG6#\"\"\"&%\"cG6#\"\"\"" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "b[2]=c[2]-c[1]" "/&%\"bG6#\"\"#,&&%\"cG6#\"\" #\"\"\"&F)6#\"\"\"!\"\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 33 "Siis \374leminekumaatriks T baasilt " }{XPPEDIT 18 0 "b[1],b[2]" " 6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 10 " baasile " }{XPPEDIT 18 0 " c[1], c[2]" "6$&%\"cG6#\"\"\"&F$6#\"\"#" }{TEXT -1 33 " ning vastavad \+ baasimaatriksid on" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "T:=mat rix(2,2,[1,1,0,1]); B:=matrix(2,2,[1,0,0,1]); C:=evalm(B&*T);C=B*T;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"TG-%'MATRIXG6#7$7$\"\"\"F*7$\"\"! F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG-%'MATRIXG6#7$7$\"\"\"\"\" !7$F+F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG-%'MATRIXG6#7$7$\"\" \"F*7$\"\"!F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%\"CG*&%\"BG\"\"\"% \"TGF'" }}}{PARA 0 "" 0 "" {TEXT -1 38 "N\374\374d baasiteisenduse T p \366\366rdmaatiks on" }{MPLTEXT 1 0 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "T1:=inverse(T);B=C*T1;B=evalm(C&*T1);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T1G-%'MATRIXG6 #7$7$\"\"\"!\"\"7$\"\"!F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%\"BG*&% \"CG\"\"\"%#T1GF'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%\"BG-%'MATRIXG6 #7$7$\"\"\"\"\"!7$F+F*" }}}{PARA 0 "" 0 "" {TEXT -1 193 "Seega on baas iteisendused praktiliselt samasugused nagu vektorruumide korralgi, eri nevuseks on vaid maatriksi elementide t\344isarvulisus ja det T=+-1. G raafiliselt n\344eb teisendus v\344lja j\344rgnevalt" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 13 "" 1 "" {INLPLOT "6+-%'POINTSG6.7$\"\"!F'7$ \"\"\"F'7$\"\"#F'F(7$F'F)7$F)F)7$F)F+7$F'F+7$F+F)7$F+F+-%'COLOURG6&%$R GBGF)F'F'-%'SYMBOLG6#%'CIRCLEG-%'CURVESG6$7'F&F(F-F,F&-F36&F5F'F'F)-%% TEXTG6'7$$\"\"%!\"\"F'%&b1=c1G%+ALIGNRIGHTG%+ALIGNABOVEGF>-FA6'7$$F+! \"#$\"\"&FF%#b2GFHFIF>-F;6$7'F&F(F0F-F&-F36&F5F)F)F'-FA6'7$FOFO%#c2GFH %+ALIGNBELOWGFU-FA6'FLFQFHFIFU-%*AXESSTYLEG6#%&FRAMEG-%(SCALINGG6#%,CO NSTRAINEDG" 2 364 364 364 2 0 1 0 2 9 0 3 1 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20020 0 12010 0 0 0 0 0 0 0 1 1 0 0 0 4 18 0 0 0 0 0 0 }}{PARA 4 "" 0 "" {TEXT -1 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 16 "V\365re determinant" }}{PARA 0 "" 0 "" {INLPLOT "6+-%'POINTSG6.7$\"\"!F'7$\"\"\"F'7$\"\"#F'F(7$F'F)7$F)F)7$F) F+7$F'F+7$F+F)7$F+F+-%'COLOURG6&%$RGBGF)F'F'-%'SYMBOLG6#%'CIRCLEG-%'CU RVESG6$7'F&F(F-F,F&-F36&F5F'F'F)-%%TEXTG6'7$$\"\"%!\"\"F'%&b1=c1G%+ALI GNRIGHTG%+ALIGNABOVEGF>-FA6'7$$F+!\"#$\"\"&FF%#b2GFHFIF>-F;6$7'F&F(F0F -F&-F36&F5F)F)F'-FA6'7$FOFO%#c2GFH%+ALIGNBELOWGFU-FA6'FLFQFHFIFU-%*AXE SSTYLEG6#%&FRAMEG-%(SCALINGG6#%,CONSTRAINEDG" 2 207 205 205 2 0 1 0 2 9 0 3 1 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20020 0 12010 0 0 0 0 0 0 0 1 1 0 0 0 50 21 0 0 0 0 0 0 }}{PARA 13 "" 1 "" {TEXT -1 0 "" }}{PARA 13 "" 1 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "Nagu jooniselt n\344ha v\365ib, katavad m\365lemad baasi vektoritele ehitatud r\366\366pk\374likud \374hesuuruse pinna. See ei \+ ole juhuslik. \334ldistame antud fakti k\365ikidele v\365redele. " } {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 342 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 10 "V\365re L(B ) " }{TEXT 343 14 "determinandiks" }{TEXT -1 29 " loomuliku skalaarkor rutise (" }{TEXT 341 5 ". , ." }{TEXT -1 28 ") suhtes nimetatakse suur ust" }}{PARA 0 "" 0 "" {TEXT -1 7 "det L =" }{XPPEDIT 18 0 "sqrt(det(B ^T*B))" "-%%sqrtG6#-%$detG6#*&)%\"BG%\"TG\"\"\"F*F," }{TEXT -1 57 " st . ruutjuurt v\365re baasi Grami maatriksi determinandist." }}{PARA 257 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 7 "Teoreem" } {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "V\365re determinant e i s\365ltu baasi valikust." }}{PARA 0 "" 0 "" {TEXT -1 29 "Tuleneb sel lest, et det T=+-1" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "Kui v\365re m\365\365de n=m, siis r\344\344gitakse " } {TEXT 344 15 "t\344ism\365\365tmelises" }{TEXT -1 65 "t v\365rest ja s iis on v\365re determinant baasivektoritest moodustatud" }}{PARA 0 "" 0 "" {TEXT -1 92 "r\366\366ptahuka ruumala. \334lej\344\344nud juhtude l tuleneb baasivektorite lineaarsest s\365ltumatusest, et " }{XPPEDIT 18 0 "n0" "2\"\"!%(epsilonG" }{TEXT -1 23 " korral leidub element \+ " }{TEXT 350 1 "y" }{TEXT -1 19 " hulgast X, nii et " }{XPPEDIT 18 0 " abs(abs(x-y))0;" }}{PARA 0 "" 0 "" {TEXT -1 49 "4) iga x korral hulgast G on suuru s inf\{||x-y||: " }{XPPEDIT 18 0 "x<>y" "0%\"xG%\"yG" }{TEXT -1 24 ", \+ x,y on G elemendid\}>0;" }}{PARA 0 "" 0 "" {TEXT -1 34 "5) iga x korra l hulgast G leidub " }{XPPEDIT 18 0 "delta" "I&deltaG6\"" }{TEXT -1 23 ">0 nii, et kui ||x-y||<" }{XPPEDIT 18 0 "delta" "I&deltaG6\"" } {TEXT -1 11 ", siis x=y." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT 347 9 "Teoreem 2" }}{PARA 0 "" 0 "" {TEXT -1 11 "Vektoruu mi " }{XPPEDIT 18 0 "R^m" ")%\"RG%\"mG" }{TEXT -1 45 " alamhulk L on v \365re parajasti siis, kui L on " }{XPPEDIT 18 0 "R^m" ")%\"RG%\"mG" } {TEXT -1 37 " diskreetne alamr\374hm liitmise suhtes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 193 "V\365re diskreetsus o n peamine meetrikaline omadus, mis lubab kasutada teoreemi 1 v\344itei d 3) ja 5), mida kasutatakse nii l\374hima vektori leidumise kui ka te atud algoritmide korrektsuse n\344itamiseks." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 26 "Hermite'i normaalkuju(HNF)" }}{PARA 0 "" 0 "" {TEXT -1 65 "Ilmneb, et v\365re baasil on olemas eriline kuju, mida nimetata kse " }{TEXT 352 25 "Hermite'i normaalkujuks. " }{TEXT -1 42 "Ning ig al v\365rel on olemas t\344pselt \374ks HNF." }}{SECT 1 {PARA 4 "" 0 " " {TEXT -1 23 "T\344ism\365\365tmelise v\365re HNF" }}{PARA 0 "" 0 "" {TEXT 353 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 81 "Me \374tlem e, et v\365re baas B on Hermite'i normaalkujul, kui on t\344idetud 2 t ingimust:" }}{PARA 0 "" 0 "" {TEXT -1 33 "1) B on alumine kolmnurkmaat riks;" }}{PARA 0 "" 0 "" {TEXT -1 20 "2) iga 07&F=7$\"\"&F>7$FB!\"&7$F F,%'b[i,i]G%+ALIGNRIGHT G%+ALIGNBELOWGFF-FK6'7$$\"#6F,$!#9F,FPFQFRFF-FK6'7$$\"#@F,$!#CF,FPFQFR FF-FK6'7$$\"#JF,$!#MF,FPFQFRFF-FK6'7$$\"#TF,$!#WF,FPFQFRFF-F$6-7&F-F+F 37$F(F27&F\\pF37$F*F87$F(F87&F3F1F9F^p7&F_pF^p7$F*F>7$F(F>7&F^pF97$F0F >Fbp7&F9F7F?Fep7&FcpFbp7$F*FD7$F(FD7&FbpFep7$F0FDFhp7&FepF?7$F6FDF[q7& F?F=FEF]q-FG6&FIF*F*F(-F$6-7&F)7$F0F(F/F+7&Fdq7$F6F(7$F6F,F/7&F/FgqF5F 17&Ffq7$F" }{XPPEDIT 18 0 "i[i]" "&%\"iG6#F#" }{TEXT -1 6 " siis " }{XPPEDIT 18 0 "B[i,j]=0" "/&%\"BG6$%\"iG%\"jG\"\"!" } {TEXT -1 38 " st. et maatriks on kolmnurkses kujus;" }}{PARA 0 "" 0 " " {TEXT -1 7 "2) iga " }{XPPEDIT 18 0 "k=1" "1\"\"\"%\"pG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 117 "Neist k\365ige n\365rgem on l \365pmatusnorm ning k\365ige tugevam on 1-norm. K\365ik teised p-normi d j\344\344vad nende kahe normi vahele." }}{PARA 0 "" 0 "" {TEXT -1 358 "Seda illustreerib j\344rgmine joonis \374kikkeradest, kus kollan e on l\365pmatusnormi \374kikkera, punane on 2-normi \374hikkera ning \+ sinine on 1-normi \374hikera. Kui l\365pmatusnorm ja p-normid s\365ltu vad oluliselt baasi valikust, siis 2-norm on invariantne ortonormeerit ud baasi suhtes. Selleks veendumiseks v\365ib m\365elda, mis juhtub ku i kordinaattelgi keerata n\344iteks 30 kraadi." }}{PARA 13 "" 1 "" {INLPLOT "6%-%)POLYGONSG6$7&7$\"\"!\"\"\"7$F)F(7$F(!\"\"7$F,F(-%'COLOU RG6&%$RGBGF(F(F)-F$6$7S7$$F)F(F(7$$\"1#4hRPij!**!#;$\"1kwb#=y_O\"F:7$$ \"18J#))4-Qn*F:$\"1D\\ff*)GLDF:7$$\"1N5')yke[#*F:$\"1Mj&[K5J!QF:7$$\"1 goz=42`')F:$\"1:NXR4U7]F:7$$\"1b](G._U!zF:$\"1`H-qceDhF:7$$\"1]$R'oTd# 3(F:$\"1jB*3qU&fqF:7$$\"1G$>jubk6'F:$\"1:7_\\!>8\"zF:7$$\"1GuIc:x5]F:$ \"1$>p(Qh-a')F:7$$\"1C3nW'R,#QF:$\"1J+16bcT#*F:7$$\"1n9AwiQDDF:$\"1&Q \"[M\"oen*F:7$$\"1C^hAo8X8F:$\"1*fVPO<\"4**F:7$$!1qB/u(p5(f!#>$\"08;t@ )******!#:7$$!1)\\T#fB[i8F:$\"1q%>wGZn!**F:7$$!1crN]@=YEF:$\"1A>=\\D`V '*F:7$$!1zV1J*3Jx$F:$\"1!yAe`m3E*F:7$$!1(\\AOF:B/&F:$\"1V'yI2&oN')F:7$ $!1igNw%*[RgF:$\"1j\")RQ+BqzF:7$$!1XUwYjJ*3(F:$\"1fvOg?x_qF:7$$!1#e_b? /U!zF:$\"14HvXQF:7$$!12RS4Nij'*F:$\"1%p9m#Q%=d#F:7$$!1xpT>+.2**F:$\"1V? 00]Ug8F:7$$!1gKG4>&*****F:$\"1DA\\O%485$!#=7$$!1^Is=!Q%3**F:$!1#4*>c=8 ]8F:7$$!1_NDna1u'*F:$!1NbFGIGKDF:7$$!1`J.8AEj#*F:$!15&=j`Bsw$F:7$$!1v# )4Kh=u')F:$!1ENX')3zv\\F:7$$!1B*z7xng%zF:$!1W(H!pUCrgF:7$$!1D84Pfc5rF: $!1?#o?\"yMJqF:7$$!1Wy6Ike[gF:$!1Jw!yeGL'zF:7$$!1@UD=%)o!*\\F:$!1`Mh6M il')F:7$$!1,1s\"[\"ysPF:$!1/`8S***4E*F:7$$!1yCH\"el'3EF:$!1U>(fp[Pl*F: 7$$!177Cvnc\"H\"F:$!1$RoI*>C;**F:7$$!1zyOHMQdIF\\t$!11O#>E`*****F:7$$ \"1JAj`Ks(G\"F:$!1ZZ3X=u;**F:7$$\"1KRqX8/bDF:$!1$[o%H'z!o'*F:7$$\"1%)y b&Q)zNQF:$!1/2<#>x]B*F:7$$\"17w4w0I.]F:$!1Igb5wMe')F:7$$\"1\\#)[*R]$4h F:$!1a*[=H2o\"zF:7$$\"1/wY'Q+$*4(F:$!1r&)eg?sUqF:7$$\"1f=s$Ry,!zF:$!12 $H2ndo*f QF:7$$\"1mGAp))oa'*F:$!1g]nRQ=0EF:7$$\"1!elf`bp!**F:$!1up91t'4O\"F:7$F 6$\"1PTpSr8/#)!#D-F/6&F1$\"#5F,F(F(-F$6$7&7$F,F)7$F)F)7$F)F,7$F,F,-F/6 &F1F)F)F(" 2 274 232 232 2 0 1 0 2 9 0 4 1 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20030 0 12010 0 0 0 0 0 0 0 1 1 0 0 0 147 95 0 0 0 0 0 0 }}{PARA 0 "" 0 "" {TEXT -1 3 " " }}{PARA 0 "" 0 "" {TEXT -1 35 "Vaatleme siin esmalt l\365pmatusnormi " } {XPPEDIT 18 0 "norm(b)" "-%%normG6#%\"bG" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "max(abs(b[i]))" "-%$maxG6#-%$absG6#&%\"bG6#%\"iG" }{TEXT -1 91 " ning otsime l\374himat vektorit vaadates l\344bi k\365ik vektorid, mi s on mingis keras B(0,r)=\{x | " }{XPPEDIT 18 0 "norm(x)<=r" "1-%%norm G6#%\"xG%\"rG" }{TEXT -1 435 "\}. V\365re diskreetsusest on seal loomu likult l\365plik arv elemente ning me saame leida v\344hima nullist er ineva pikkusega vektori. Seega \374lesande lahendamiseks on meil tarv is teada mingit kandidaatvektori ja selle pikkust. Loomulikult mida l \374hem on kandidaatvektor, seda v\344hem t\366\366d kulub meil keras \+ olevate vektorite l\344bi vaatamiseks. \334ks v\365imalik l\344henemin e on viia v\365re baas HNF-s. Baasivektorite pikkused annavad meile e simese hinnangu " }{XPPEDIT 18 0 "d=min(norm(b[i]))" "/%\"dG-%$minG6#- %%normG6#&%\"bG6#%\"iG" }{TEXT -1 226 " l\374hima vektori pikkusele. T eine eelis on HNF alumine kolmnurkne kuju, mis v\365imaldab suhtelisel t lihtsalt m\344\344rata, kas vektor kuulub kerasse B(0,d) v\365i mitt e. Algoritmi keerukus on eksponentsiaalses s\365ltuvuses v\365re m\365 \365tmest n." }}{PARA 0 "" 0 "" {TEXT -1 532 "Seet\365ttu v\365ib arva ta, et \374lesanne on v\344hemalt NP-t\344ielik(on t\365estatud) 2-nor mi korral ilmneb aga , et kui me teame lahendit st. l\374himat vektori t, siis selle \365igsuse kontrolliks v\365ib halvimal juhul minna eksp onentsiaalne aeg, millest SVP-2 on NP-raske \374lesanne. Seega v\365ik s SVP kuulutada lootusetuks probleemiks, kuid ilmneb, et v\344ga palj udel juhtudel laheneb \374lesanne teoreetilisest hinnangust paremini, \+ mis v\365imaldab lahendada mitmesuguseid probleeme alates kr\374ptogra afilistet r\374nnakutest kuni reaalarvude l\344hendamisprobleemideni. " }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 20 "Erilised v\365re baasid" }} {PARA 0 "" 0 "" {TEXT -1 117 "Eelnevas n\344ites kasutasime v\365re ba asi \374ht erikuju HNF-i ning ilmnes, et see kuju aitab meid l\374hima vektori otsimisel." }}{PARA 0 "" 0 "" {TEXT -1 96 "On olemas veel m \365ned baasi kujud, mis lubavad l\374hima vektori pikkust paremini h innata ja leida." }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 47 "Minimaalse pi kkusega baas(Length Reduced Basis)" }}{PARA 256 "" 0 "" {TEXT -1 238 " Eelnevast teame, et v\365re determinant ei s\365ltu baasi valikust. Te isest k\374ljest on v\365re determinant arvuliselt v\365rdne v\365re b aasivektoritele ehitatud r\366\366ptahuka ruumalaga, seega mida l\344h emal on baasivektorid ristseisule, seda l\374hemad nad on." }}{PARA 0 "" 0 "" {TEXT -1 196 "Vektorruumis sai basivektorid Gram-Schmidti algo ritmi abil ortogonaliseerida, v\365res tekib Gram-Schmidti algoritmi r akendamisel raskusi, kuid \374ldiselt on v\365imalik v\365re vektorid \+ k\374llalt risti ajada." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "Def.(Gram-Schmidti ortogonaliserimis protsess)" }} {PARA 0 "" 0 "" {TEXT -1 20 "Olgu meil v\365re baas " }{XPPEDIT 18 0 " b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6# \"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" } {TEXT -1 33 ", siis Gram-Schmidti algoritmiga " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 2 "*=" }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 2 "*=" }{XPPEDIT 18 0 "b[i]" "&%\"b G6#%\"iG" }{TEXT -1 1 "-" }{XPPEDIT 18 0 "sum(mu[i,j],j=1..i-1)" "-%$s umG6$&%#muG6$%\"iG%\"jG/F);\"\"\",&F(\"\"\"\"\"\"!\"\"" }{TEXT -1 1 " \+ " }{XPPEDIT 18 0 "b[j]" "&%\"bG6#%\"jG" }{TEXT -1 20 "*, i= 2..n" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "mu[i,j]" "&%#muG6$%\"iG%\"jG" } {TEXT -1 2 "=(" }{XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[j]" "&%\"bG6#%\"jG" }{TEXT -1 4 "*)/(" }{XPPEDIT 18 0 "b[j]" "&%\"bG6#%\"jG" }{TEXT -1 2 "*," }{XPPEDIT 18 0 "b[j]" "&%\"b G6#%\"jG" }{TEXT -1 30 "*), i=2..n, j=1..i-1" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "mu[i,i]" "&%#muG6$%\"iGF%" }{TEXT -1 45 "=1, \+ i=1..n," }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "mu[i,j]=0" "/&%#muG6$%\"iG%\"jG\"\"!" }{TEXT -1 37 ", \+ j>i," }}{PARA 0 "" 0 "" {TEXT -1 17 "saadud vektoreid \+ " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 2 "*," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 6 "*,...," }{XPPEDIT 18 0 "b[n] " "&%\"bG6#%\"nG" }{TEXT -1 68 "* nimetatakse v\365re baasi ortogonali seeritud s\374steemiks ja kordajaid " }{XPPEDIT 18 0 "mu[i,j]" "&%#muG 6$%\"iG%\"jG" }{TEXT -1 27 " Gram-Schmidti kordajateks." }}{PARA 0 "" 0 "" {TEXT 256 6 "M\344rkus" }{TEXT -1 50 ": Gram-Schmidi kordajate de finitsioonist on ilmne " }{XPPEDIT 18 0 "b[i]=sum(mu[i,j],j=1..n)" "/& %\"bG6#%\"iG-%$sumG6$&%#muG6$F&%\"jG/F-;\"\"\"%\"nG" }{TEXT -1 1 " " } {XPPEDIT 18 0 "b[j]" "&%\"bG6#%\"jG" }{TEXT -1 10 "*, i=1..n." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "Def" }} {PARA 0 "" 0 "" {TEXT -1 108 "V\365re baasi nimetatakse minimaalse pik kusega baasiks, kui v\365re Gram-Schmidti koradajad rahuldavad v\365r rratust" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "mu[i,j]<=1/2" "1&%#muG6$%\"i G%\"jG*&\"\"\"\"\"\"\"\"#!\"\"" }{TEXT -1 13 ", " } {XPPEDIT 18 0 "i<>j" "0%\"iG%\"jG" }{TEXT -1 3 ". " }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 5 "N\344ide" }}{PARA 0 "" 0 "" {TEXT -1 41 "Kahem\365\365tmelisel juhul kui baasivektorite " } {XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 369 " 2-norm on \374ks, siis selleks et oleks tegu minimaalse baasiga peab baasivektorite vaheline nurk ol ema rohkem 60 kraadi ja v\344hem kui 120 kraadi. \334ldiselt kui esime ne vektor on l\374hem kui teine, siis peab baasivektorite vaheline nur k olema 60 ja 120 kraadi vahel. Mida pikem on teine vektor seda l\344h emal ristseisule peavad vektorid olema. Seda omadust kasutatakse hilje m " }{XPPEDIT 18 0 "L^3 " "*$%\"LG\"\"$" }{TEXT -1 11 "algoritmis " }} {PARA 13 "" 1 "" {INLPLOT "6*-%'CURVESG6'7$7$\"\"!F(7$\"\"\"F(7$F'7$#F *\"\"#$\"+SSDg')!#57$F'7$#!\"\"F.F/-%'COLOURG6&%$RGBGF(F(F(-%*THICKNES SG6#F.-%%TEXTG6(7$$\"\"&F5F(%%b[1]G%+ALIGNRIGHTG%+ALIGNABOVEGF6F:-F>6( 7$$\"#D!\"#$\"#NFK%%b[2]GFDFEF6F:-F>6(7$$!#NFKFL%&b[2]'GFDFEF6F:-%)POL YGONSG6$7%F'F,F3-%&COLORG6&F9F(F*F(-FV6%7%F'F,F)7%F'F37$F5F(-F76&F9F*$ \"\"%F5F]o-%*AXESSTYLEG6#%&FRAMEG-%(SCALINGG6#%,CONSTRAINEDG" 2 315 206 206 2 0 1 0 2 9 0 3 1 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20020 0 12010 0 0 0 0 0 0 0 1 1 0 0 0 14 88 0 0 0 0 0 0 }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 49 "Gram-Schmidti algoritm v\365redele(Length Reduction)" }}{PARA 0 "" 0 "" {TEXT -1 73 "Kohandame Gramm-Schmidti algoritmi v\365redele \+ \374mardades tekkivaid kordajaid" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Length Reduction" }}{PARA 0 "" 0 "" {TEXT -1 12 "Sisend baas " } {XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",. ..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }}{PARA 0 "" 0 "" {TEXT -1 34 "V\344ljund minimaalse pikkusega baas " }{XPPEDIT 18 0 "b[1]" "&%\" bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" } {TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }}{PARA 0 "" 0 "" {TEXT -1 14 "for i=2,..n do" }}{PARA 0 "" 0 "" {TEXT -1 22 " \+ for j=i-1,...1 do" }}{PARA 0 "" 0 "" {TEXT -1 11 " " } {XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "b [i]" "&%\"bG6#%\"iG" }{TEXT -1 1 "-" }{XPPEDIT 18 0 "round(mu[i,j])*b[ j]:" "*&-%&roundG6#&%#muG6$%\"iG%\"jG\"\"\"&%\"bG6#F*F+" }}{PARA 0 "" 0 "" {TEXT -1 7 " od:" }}{PARA 0 "" 0 "" {TEXT -1 3 "od:" }}{PARA 0 "" 0 "" {TEXT -1 7 "return " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 5 ",.. .," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }}}{PARA 0 "" 0 "" {TEXT -1 45 "Algoritmi korrektsus p\365hineb kahel asjaolul:" }}{PARA 0 "" 0 " " {TEXT -1 116 "1) v\365re baasi ortogonaliseeritud s\374steem ei muut u, sest vektoritele liidetakse v\365i lahutatakse juurde vektoreid, mi s" }}{PARA 0 "" 0 "" {TEXT -1 179 " ortogonaliseerimisprotsessis nii kunii kaduma l\344heks. Selles veendumiseks v\365ib baasi esitada orto gonaliseeritud s\374steemi abil ning siis tuleb s\365rmedel arvu tades asi v\344lja." }}{PARA 0 "" 0 "" {TEXT -1 34 "2) Teine tagurpidi ne ts\374kkel viib " }{XPPEDIT 18 0 "abs(mu[i,j])<=1/2" "1-%$absG6#&%# muG6$%\"iG%\"jG*&\"\"\"\"\"\"\"\"#!\"\"" }{TEXT -1 68 " , kusjuures se e parandus ei avalda m\365ju j\344rgnevatele kordajatele " } {XPPEDIT 18 0 "mu[i,j+1]" "&%#muG6$%\"iG,&%\"jG\"\"\"\"\"\"F(" }{TEXT -1 4 ",..." }}{PARA 0 "" 0 "" {TEXT -1 82 " Ja minnes n\374\374d j \344rjest allapoole saamegi k\365ik kordajad vajalikesse piiridesse." }}{PARA 0 "" 0 "" {TEXT -1 196 "Algoritmis on ilmselt pol\374nomiaalne arv samme, v\365ib veenduda et k\365ik arvutatavad suurused on t\365k estatud ning n\365utav t\344psus on ka t\365kestatud, seega on algorit m t\365esti teostatav pl\374nomiaalses ajas. " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 19 "Praktiline algoritm" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "length_reduce:=proc(B::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "local i,j,mu,m,n,B1,B0,M:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "#B0 baasivektorite jada" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "#B1 ortonormaliseeritud s\374steem(jada)" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 60 "#eeldus et maatriksi n esimest veergu lineaa rselt s\365ltumatud" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=rowdim(B) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "#M list [1..n] vektorite erald amiseks baasist" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "M:=[seq(i,i=1..m )]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=rank(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "B0:=[seq(subvector(B,M,i),i=1..n)]:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 20 "B1:=GramSchmidt(B0):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "for i from 2 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " for j from i-1 by -1 to 1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 71 " mu:=round(dotprod(subvector(B,M,i),B1[j])/dotprod(B1[j] ,B1[j])):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " B:=addcol(B,j,i ,-mu): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETU RN(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"AG-%'MATRIXG6#7%7%\"\"\"\"\"#\"\"!7%\"\"%\" \"&\"\"'7%\"\"(\"\")\"\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 142 "V \365iks arvata, et algoritmi rakendamine minimaalse pikkusega baasile \+ j\344tab selle samaks. Aga tegelikult ei ole see nii, nimelt kui ko rdaja " }{XPPEDIT 18 0 "abs(mu[i,j])=1/2" "/-%$absG6#&%#muG6$%\"iG%\" jG*&\"\"\"\"\"\"\"\"#!\"\"" }{TEXT -1 17 " , siis saadakse " } {XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 2 "= " }{XPPEDIT 18 0 " b[i]" "&%\"bG6#%\"iG" }{TEXT -1 2 "-+" }{XPPEDIT 18 0 "b[j]" "&%\"bG6# %\"jG" }{TEXT -1 54 ". Kui on \374hesust tarvis siis v\365ib algoritmi parandada " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "A:=matrix(3,3,[1,2,0 ,4,5,6,7,8,9]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "print(length_red uce(A));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "print(length_reduce(A)) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "print(length_reduce(A));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'MATRIXG6#7%7%\"\"\"\"\"#\"\"! 7%\"\"%\"\"&\"\"'7%\"\"(\"\")\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# -%'MATRIXG6#7%7%\"\"\"F(!\"\"7%\"\"%F(F)7%\"\"(F(!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7%\"\"\"F(\"\"!7%\"\"%F(\"\"$7%\"\"( F(F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7%\"\"\"F(!\"\"7 %\"\"%F(F)7%\"\"(F(!\"%" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 45 "Mini maalse kaaluga baas(Weight Reduced Basis)" }}{PARA 0 "" 0 "" {TEXT -1 102 "P\374\374des leida baasi, mille vektorid oleks veel l\344hedamal \+ ristseisule toome sisse j\344rgneva definitsiooni" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "Def." }}{PARA 0 "" 0 "" {TEXT -1 10 "V\365re baas " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" } {TEXT -1 1 "," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 5 ",... ," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 60 " on minimaalse \+ kaaluga, kui on t\344idetud j\344rgmised tingimused" }}{PARA 0 "" 0 " " {TEXT -1 5 "1) |(" }{XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "b[j]" "&%\"bG6#%\"jG" }{TEXT -1 5 ")| / " } {XPPEDIT 18 0 "abs(abs(b[j]))^2<=1/2" "1*$-%$absG6#-F%6#&%\"bG6#%\"jG \"\"#*&\"\"\"\"\"\"\"\"#!\"\"" }{TEXT -1 9 " , " }{XPPEDIT 18 0 "1<=j" "1\"\"\"%\"jG" }{TEXT -1 1 "<" }{XPPEDIT 18 0 "i<=n" "1%\"iG%\" nG" }}{PARA 0 "" 0 "" {TEXT -1 3 "2) " }{XPPEDIT 18 0 "abs(abs(b[i]))< =abs(abs(b[i+1]))" "1-%$absG6#-F$6#&%\"bG6#%\"iG-F$6#-F$6#&F)6#,&F+\" \"\"\"\"\"F3" }{TEXT -1 24 ", i=1..n-1" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 358 "Esimene tingimus tagab vektorite l\344heduse ristseisule, sest vektorid on baasis j\344rjest atud kasvavas j\344rjekorras. On olemas algoritm, mis teisendab iga ba asi minimaalse kaaluga baasiks, kuid see algoritm pole pol\374nomiaaln e ja seet\365ttu pole seda siin esitatud. Teoreetilised kaalutlused ta gavad selle, et minimaalse kaaluga baasi esimene vektor on l\374him v \365res " }}}{SECT 1 {PARA 4 "" 0 "Gaussi baas" {TEXT -1 33 "Gaussi ba as(SVP lahendus kui m=2)" }}{PARA 0 "" 0 "" {TEXT -1 79 "Vaatleme n \374\374d minimaalse kaaluga baasi, kui ruumi m\365\365de m=2 ja kaugu s on 2-norm" }}{PARA 0 "" 0 "" {TEXT -1 58 "Siis eelmises punktis too dud definitsioon teiseneb kujule" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 7 " Def. 1" }}{PARA 0 "" 0 "" {TEXT -1 46 " M e nimetame v\365re baas a,b Gaussi baasiks kui" }}{PARA 0 "" 0 "" {TEXT -1 7 "1) 0<=" }{XPPEDIT 18 0 "mu[1,2]<=1/2" "1&%#muG6$\"\"\"\" \"#*&\"\"\"\"\"\"\"\"#!\"\"" }}{PARA 0 "" 0 "" {TEXT -1 4 "2) " } {XPPEDIT 18 0 " abs(abs(a))<=abs(abs(b))" "1-%$absG6#-F$6#%\"aG-F$6#-F $6#%\"bG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT 257 7 "M\344rkus:" }{TEXT -1 45 " Teise vektori l\344bi k orrutamisega +-1 tagame " }{XPPEDIT 18 0 "0<=mu[1,2] " "1\"\"!&%#muG6$ \"\"\"\"\"#" }{TEXT -1 110 ", seega on Gaussi baas t\365esti minimaals e kaaluga baasi erijuht. Harilikult antakse definitsioon veidi teisiti ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 6 "Def. \+ 2" }}{PARA 0 "" 0 "" {TEXT -1 46 "Me nimetame v\365re baasi a,b Gaussi baasiks kui " }}{PARA 0 "" 0 "" {TEXT -1 3 "1) " }{XPPEDIT 18 0 "abs( abs(a))<=abs(abs(b))" "1-%$absG6#-F$6#%\"aG-F$6#-F$6#%\"bG" }{TEXT -1 1 ";" }}{PARA 0 "" 0 "" {TEXT -1 3 "2) " }{XPPEDIT 18 0 "abs(abs(b))<= abs(abs(a-b))" "1-%$absG6#-F$6#%\"bG-F$6#-F$6#,&%\"aG\"\"\"F(!\"\"" } {TEXT -1 1 ";" }}{PARA 0 "" 0 "" {TEXT -1 3 "3) " }{XPPEDIT 18 0 " abs (abs(a-b))<=abs(abs(a+b))" "1-%$absG6#-F$6#,&%\"aG\"\"\"%\"bG!\"\"-F$6 #-F$6#,&F)F*F+F*" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 258 7 "M\344rkus:" }{TEXT -1 43 " See on definit sioon 1 esitus kauguse abil." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }} {PARA 0 "" 0 "" {TEXT 259 52 "Lemma 1(Lineaarkombinatsiooni normi alum ine hinnang)" }}{PARA 0 "" 0 "" {TEXT -1 32 "Olgu meil suvaline norm j a olgu " }{XPPEDIT 18 0 "abs(abs(x))<=abs(abs(x+y))" "1-%$absG6#-F$6#% \"xG-F$6#-F$6#,&F(\"\"\"%\"yGF." }{TEXT -1 11 ", siis iga " }{XPPEDIT 18 0 "abs(alpha)>1" "2\"\"\"-%$absG6#%&alphaG" }{TEXT -1 23 " korral k ehtib hinnang " }{XPPEDIT 18 0 "abs(abs(x+y))<=abs(abs(x+alpha*y))" "1 -%$absG6#-F$6#,&%\"xG\"\"\"%\"yGF*-F$6#-F$6#,&F)F**&%&alphaGF*F+F*F*" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 170 "Definitsioon 2 ja lemma 1 kasutades on lihtne veenduda, \+ et a on v\365re l\374him vektor. Seega tuleb meil leida Gaussi baas. \+ Selleks toome sisse h\344sti j\344rjestatud baasi m\365iste" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Def.(Well Odere d Reduced Basis)" }}{PARA 0 "" 0 "" {TEXT -1 76 "Me \374tleme, et v \365re baas a,b on h\344sti j\344rjestatud, kui ||a||<=||a-b||<=||b||. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 7 "M\344 rkus:" }{TEXT -1 53 " Kasutades lemmat 1 on kerge veenduda ||b||<=||a+ b||." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "N \374\374d Gaussi algoritmid" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "Gau ssi algoritm 2-normi jaoks" }}{PARA 0 "" 0 "" {TEXT -1 36 "Sisend baas a,b nii, et ||a||<=||b||" }}{PARA 0 "" 0 "" {TEXT -1 6 "while " } {XPPEDIT 18 0 "abs(mu[1,2])>1/2" "2*&\"\"\"\"\"\"\"\"#!\"\"-%$absG6#&% #muG6$\"\"\"\"\"#" }{TEXT -1 3 " do" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 " a:=b-" }{XPPEDIT 18 0 "round(mu[1,2])*a" "*& -%&roundG6#&%#muG6$\"\"\"\"\"#\"\"\"%\"aGF+" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 12 " b:=a" }}{PARA 0 "" 0 "" {TEXT -1 42 " \+ if ||a||>||b|| then swap(a,b) fi:" }}{PARA 0 "" 0 "" {TEXT -1 6 "od: " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "b:=b*sign(mu[2,1])" ">%\"b G*&F#\"\"\"-%%signG6#&%#muG6$\"\"#\"\"\"F%" }{TEXT -1 11 " //selleks \+ " }{XPPEDIT 18 0 "mu[2,1]>=0" "1\"\"!&%#muG6$\"\"#\"\"\"" }}{PARA 0 " " 0 "" {TEXT -1 10 "return a,b" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 36 "Gaussi algoritm suvalise normi jaoks" }}{PARA 0 " " 0 "" {TEXT -1 36 "Sisend baas a,b nii, et ||a||<=||b||" }}{PARA 0 " " 0 "" {TEXT -1 22 "while ||b||>||a-b|| do" }}{PARA 0 "" 0 "" {TEXT -1 68 " b:=b-mu*a nii, et mu on t\344isarv ja ||b-mu*a|| on mi nimaalne" }}{PARA 0 "" 0 "" {TEXT -1 37 " // t\344psemalt on tar vis vaid ||" }{XPPEDIT 18 0 "b-mu*a" ",&%\"bG\"\"\"*&%#muGF$%\"aGF$!\" \"" }{TEXT -1 9 "||<=||b-(" }{XPPEDIT 18 0 "mu" "I#muG6\"" }{TEXT -1 54 "+-1) a|| aga mida v\344iksem see on seda kiiremini j\365uame" }} {PARA 0 "" 0 "" {TEXT -1 27 " //taadamisega l\365pule" }}{PARA 0 "" 0 "" {TEXT -1 69 " //lihtne viis miinimumi leidmiseks mu=1, 2,4,8... jne kuni ||b-" }{XPPEDIT 18 0 "mu*a" "*&%#muG\"\"\"%\"aGF$" } {TEXT -1 29 "|| norm enam ei lange ja siis" }}{PARA 0 "" 0 "" {TEXT -1 44 " //teostada kahendotsing vahemikus k.." }{XPPEDIT 18 0 "k ^2" "*$%\"kG\"\"#" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 36 " \+ if ||a+b||<||a-b|| then b:=-b" }}{PARA 0 "" 0 "" {TEXT -1 15 " \+ swap(a,b)" }}{PARA 0 "" 0 "" {TEXT -1 2 "od" }}{PARA 0 "" 0 "" {TEXT -1 10 "return a,b" }{MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 102 " M\365lema algoritmi t\366\366 sammude arv s\365ltub a esialgsest pik klusest logaritmiliselt, seega sammude arv on" }}{PARA 0 "" 0 "" {TEXT -1 54 " O(log||a||), mis muudab algoritmid konstruktiivseks. " } }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 19 "Praktiline algoritm" }}{PARA 0 "" 0 "" {TEXT -1 140 "Lihtsuse m\365ttes realiseerime vaid 2-normi alg oritmi. Et eespool on k\365ik sisendid olnud maatrisid, siis on protse duuri sisend m x 2 maatriks." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "gauss_reduction:=proc(B::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "local mu,m,M,a,b,i:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=row dim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "M:=[seq(i,i=1..m)]:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "a:=subvector(B,M,1):" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 20 "b:=subvector(B,M,2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "#paneme vectorid \365igesse j\344rjekorda" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "if dotprod(a,a)>dotprod(b,b) then " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " B:=swapcol(B,1,2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " a:=subvector(B,M,1):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " b:=subvector(B,M,2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "mu:=dotprod( a,b)/dotprod(a,a):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "while abs(mu) >1/2 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " # a:=b-round(mu)*a b :=a:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " B:=swapcol(B,1,2):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " B:=addcol(B,2,1,-round(mu)): " } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " #j\344rjestame vektorid \365iet i " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " a:=subvector(B,M,1):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " b:=subvector(B,M,2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " #paneme vectorid \365igesse j\344rjekord a" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " if dotprod(a,a)>dotprod(b,b ) then " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " B:=swapcol(B,1,2): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " a:=subvector(B,M,1):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " b:=subvector(B,M,2):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " mu:=dotprod(a,b)/dotprod(a,a):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "if mu<0 th en B:=mulcol(B,2,-1): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "RETURN( B)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 5 "N\344ide" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "B:=matrix(2,2,[109,360,360,1189]);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"BG-%'MATRIXG6#7$7$\"$4\"\"$g$7$F+\"%*=\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(gauss_reduction(B));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%&helloG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&helloG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6 #7$7$\"\"\"\"\"!7$F)F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 306 "Muutes maatriksit B \374hte elementi \374he v\365rra saame hoopis teise tule muse. See illustreerib v\365re diskreetsust -- reeglina pole v\365res \+ v\365imalik lahendada \374lesandeid ligikaudselt, v\344ikesed erinevus ed(arvutusvead) progresseruvad ja saadud lahend ei pruugi \374heski m \365ttes olla l\344hedane esialgse \374lesande lahendiga." }{TEXT 261 99 " See ei t\344henda, et pole v\365imalik saada ligikaudseid hinnang uid ja k\374llalt h\344id lahendi kandidaate." }{MPLTEXT 1 0 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "B:=matrix(2,2,[109,360,361,1189]); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(gauss_reduction(B)):" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG-%'MATRIXG6#7$7$\"$4\"\"$g$7$\"$ h$\"%*=\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7$7$\"#;\"\"$ 7$!\"$!#B" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 272 27 "LLL baas(LLL Redu ced Basis)" }}{PARA 0 "" 0 "" {TEXT -1 367 "Eelnevates definitsioonide s on palju kasutatud Gramm-Scmidti kordajaid, sest m\365nes m\365ttes \+ iseloomustavad need baasi l\344hedust ristseisule. Minimaalse kaaluga \+ baas oli k\365ige tugevamate tingimustega, mis tingis baasi ebapraktil isuse. N\365rgendades veidi minimaalse kaaluga baasitingimusi saame LL L-baasi dedinitsiooni. Nii ei ole esimene vektor selles baasis l\374hi m vaid O(" }{XPPEDIT 18 0 "2^n" ")\"\"#%\"nG" }{TEXT -1 136 ") korda p ikem kui v\365re l\374him vektor. Selle puuduse korvab meile pol\374no miaalse algoritmi leidumine, mis viib suvalise baasi LLL-baasiks. " } {TEXT 273 41 "LLL-baasi korral peab norm olema 2-norm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "Def." }}{PARA 0 "" 0 "" {TEXT -1 23 "Olgu meil vektorruumis " }{XPPEDIT 18 0 "R^m" ")%\"RG% \"mG" }{TEXT -1 42 " lineaarselt s\365ltumatu vektorite s\374steem " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ", ...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 15 ". Teisenduse ks " }{XPPEDIT 18 0 "Pi[k]" "&%#PiG6#%\"kG" }{TEXT -1 39 " nimetatakse ortoprojektorit, mis viib " }{XPPEDIT 18 0 "R^m" ")%\"RG%\"mG" } {TEXT -1 22 " vektorid vektoritega " }{XPPEDIT 18 0 "b[1],b[2]" "6$&% \"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[k-1]" "& %\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 29 " risti olevateks vektor iteks." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 5 "" 0 "" {TEXT 262 27 "Ortoprojektori definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 4 "Iga " }{XPPEDIT 18 0 "R^m" ")%\"RG%\"mG" }{TEXT -1 9 " vektori " } {TEXT 263 1 "x" }{TEXT -1 22 " \374heselt kaheks osaks " }{TEXT 264 1 "y" }{TEXT -1 4 " ja " }{TEXT 265 2 "z " }{TEXT -1 8 "nii, et " } {TEXT 266 1 "y" }{TEXT -1 4 " on " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"b G6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[k-1]" "&%\" bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 25 " lineaarkombinatsioon ja \+ " }{TEXT 267 2 "z " }{TEXT -1 21 "on risti vektoritega " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," } {XPPEDIT 18 0 "b[k-1]" "&%\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 16 ". Ortoprojektor " }{XPPEDIT 18 0 "Pi[k]" "&%#PiG6#%\"kG" }{TEXT -1 27 " on defineeritud v\365rdusega " }{XPPEDIT 18 0 "Pi[k]" "&%#PiG6 #%\"kG" }{TEXT -1 1 "(" }{TEXT 268 1 "x" }{TEXT -1 2 ")=" }{TEXT 269 1 "z" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Joonisel on vektori " }{XPPEDIT 18 0 "b[2]" "&%\"bG6# \"\"#" }{TEXT -1 34 " ortoprojektsioon risti vektoriga " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 13 "" 1 "" {INLPLOT "6,-%'CURVESG6%7$7$\"\"!F(7$F(\"\"\"- %'COLOURG6&%$RGBGF*F(F(-%*THICKNESSG6#\"\"#-%%TEXTG6(7$$\"\"&!\"#$F8! \"\"%.z=Pi[1](b[2])G%+ALIGNRIGHTG%+ALIGNABOVEGF+F/-F$6%7$F'7$F2F(-F,6& F.F(F*F(F/-F46(7$$\"#7F;F(%\"yGF=F>FCF/-F$6$7$F'7$F*F(7$F'7$F2F*-F46&7 $F:F(%%b[1]GF=F>-F46&7$F*F:%%b[2]G%*ALIGNLEFTGF>-F$6&7$FBFPF+-F06#F*-% *LINESTYLEG6#\"\"$-%*AXESSTYLEG6#%&FRAMEG-%(SCALINGG6#%,CONSTRAINEDG" 2 355 231 231 2 0 1 0 2 9 0 3 1 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20020 0 12010 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 270 7 "M \344rkus:" }{TEXT -1 67 " Arvestades Gramm-Schmidi kordajate ja v\365r e ortonormaalse s\374steemi " }{XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" } {TEXT -1 2 "*," }{XPPEDIT 18 0 "b[2]" "&%\"bG6#\"\"#" }{TEXT -1 6 "*,. ..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 32 "* definitsioo ni on lihtne saada:" }}{PARA 0 "" 0 "" {TEXT -1 7 " " }{XPPEDIT 18 0 "Pi[k](b[j])=0" "/-&%#PiG6#%\"kG6#&%\"bG6#%\"jG\"\"!" }{TEXT -1 17 ", kui " }{XPPEDIT 18 0 "jj" "6$1-%$absG6#&%#muG6$% \"iG%\"jG*&\"\"\"\"\"\"\"\"#!\"\"0F*F+" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 4 "2) " }{XPPEDIT 18 0 "delta*abs(abs(Pi[k-1](b[k-1]))) ^2<=abs(abs(Pi[k-1](b[k])))^2" "1*&%&deltaG\"\"\"*$-%$absG6#-F(6#-&%#P iG6#,&%\"kGF%\"\"\"!\"\"6#&%\"bG6#,&F1F%\"\"\"F3\"\"#F%*$-F(6#-F(6#-&F .6#,&F1F%\"\"\"F36#&F66#F1\"\"#" }{TEXT -1 18 ", k=2,3,...,n." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 271 7 "M\344rkus :" }{TEXT -1 94 " Ortoprojektori definitsioonist l\344htuvalt saame 2 \+ tingimuse kirjutada \374les ekvivalentsel kujul" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "delta" "I&deltaG6\"" } {TEXT -1 3 " ||" }{XPPEDIT 18 0 "b[k-1]" "&%\"bG6#,&%\"kG\"\"\"\"\"\"! \"\"" }{TEXT -1 9 "*||^2<=||" }{XPPEDIT 18 0 "b[k]" "&%\"bG6#%\"kG" } {TEXT -1 6 "*||^2+" }{XPPEDIT 18 0 "mu[k,k-1]^2" "*$&%#muG6$%\"kG,&F& \"\"\"\"\"\"!\"\"\"\"#" }{TEXT -1 2 "||" }{XPPEDIT 18 0 "b[k-1]" "&%\" bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 5 "*||^2" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 18 "LLL baasi omadus ed" }}{PARA 4 "" 0 "LLL aproksimatsioon" {TEXT 274 9 "Teoreem 1" }} {PARA 0 "" 0 "" {TEXT -1 16 "Kui v\365re L baas " }{XPPEDIT 18 0 "b[1] ,b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 21 " on LLL baas, siis " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "abs(abs(b[1]))<=alpha^((n-1)/2)*lambda[1](L) " "1-%$absG6#-F$6#&%\"bG6#\"\"\"*&)%&alphaG*&,&%\"nG\"\"\"\"\"\"!\"\"F 2\"\"#F4F2-&%'lambdaG6#\"\"\"6#%\"LGF2" }{TEXT -1 2 " ," }}{PARA 0 "" 0 "" {TEXT -1 4 "kus " }{XPPEDIT 18 0 "alpha=1/(delta-1/4)" "/%&alphaG *&\"\"\"\"\"\",&%&deltaGF&*&\"\"\"F&\"\"%!\"\"F,F," }{TEXT -1 7 " ja " }{XPPEDIT 18 0 "lambda[1](L)" "-&%'lambdaG6#\"\"\"6#%\"LG" }{TEXT -1 31 " on v\365re l\374hima vektori pikkus." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "Def." }}{PARA 0 "" 0 "" {TEXT -1 12 "Olgu v\365re L(" }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F $6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" } {TEXT -1 43 "), siis v\365re j\344rjestikusteks miinimumideks " } {XPPEDIT 18 0 "lambda[i](L)" "-&%'lambdaG6#%\"iG6#%\"LG" }{TEXT -1 12 " nimetatakse" }}{PARA 0 "" 0 "" {TEXT -1 3 "1) " }{XPPEDIT 18 0 "lamb da[1](L)" "-&%'lambdaG6#\"\"\"6#%\"LG" }{TEXT -1 53 " v\365re l\374him a lineaarselt s\365ltumatu vektori y pikkust;" }}{PARA 0 "" 0 "" {TEXT -1 3 "2) " }{XPPEDIT 18 0 "lambda[i](L)" "-&%'lambdaG6#%\"iG6#% \"LG" }{TEXT -1 21 " v\365re l\374hima vektori " }{XPPEDIT 18 0 "y[i] " "&%\"yG6#%\"iG" }{TEXT -1 40 " pikkust, mis rahuldab kahte tingimus t:" }}{PARA 0 "" 0 "" {TEXT -1 34 " a) on pikem kui v\365re vektori d " }{XPPEDIT 18 0 "y[1],y[2]" "6$&%\"yG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "y[i-1]" "&%\"yG6#,&%\"iG\"\"\"\"\"\"!\"\"" } {TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 25 " b) vektorite s\374st eem " }{XPPEDIT 18 0 "y[1],y[2]" "6$&%\"yG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "y[i]" "&%\"yG6#%\"iG" }{TEXT -1 26 " on l ineaarselt s\365ltumatu." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT 275 53 "Teoreem 2(j\344rjestikuste miinmumide l\344hendam isteoreem)" }}{PARA 0 "" 0 "" {TEXT -1 16 "Kui v\365re L baas " } {XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",. ..," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 20 " on LLL baa s, siis" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "abs(abs(b[i] ))<=alpha^((n-1)/2)*lambda[i](L)" "1-%$absG6#-F$6#&%\"bG6#%\"iG*&)%&al phaG*&,&%\"nG\"\"\"\"\"\"!\"\"F2\"\"#F4F2-&%'lambdaG6#F+6#%\"LGF2" } {TEXT -1 14 ", i=1,2,...,n." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 12 "L LL algoritm" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Sisend v\365re baas " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 1 " " }} {PARA 0 "" 0 "" {TEXT -1 15 "Parameeter 1/4<" }{XPPEDIT 18 0 "delta" " I&deltaG6\"" }{TEXT -1 2 "<1" }}{PARA 0 "" 0 "" {TEXT -1 17 "k:=2 //in variant " }{XPPEDIT 18 0 "b[k-1]" "&%\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" } {TEXT -1 12 " on LLL baas" }}{PARA 0 "" 0 "" {TEXT -1 6 "while " } {XPPEDIT 18 0 "k<=n" "1%\"kG%\"nG" }{TEXT -1 3 " do" }}{PARA 0 "" 0 " " {TEXT -1 20 " //invariant " }{XPPEDIT 18 0 "b[1],b[2]" "6$&% \"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[k-1]" "& %\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 12 " on LLL baas" }}{PARA 0 "" 0 "" {TEXT -1 22 " lenght_reduce(" }{XPPEDIT 18 0 "b[1],b[ 2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b [k]" "&%\"bG6#%\"kG" }{TEXT -1 1 ")" }}{PARA 0 "" 0 "" {TEXT -1 20 " \+ arvutada \374le " }{XPPEDIT 18 0 "mu[k,j]" "&%#muG6$%\"kG%\"jG" } {TEXT -1 14 " // vektoreid " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\" \"\"&F$6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[k-1]" "&%\"bG6#, &%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 43 " ei muudeta, sest need moodusta vad LLL baas" }}{PARA 0 "" 0 "" {TEXT -1 10 " if " }{XPPEDIT 18 0 "delta*abs(abs(Pi[k-1](b[k-1])))^2>abs(abs(Pi[k-1](b[k])))^2" "2*$-% $absG6#-F%6#-&%#PiG6#,&%\"kG\"\"\"\"\"\"!\"\"6#&%\"bG6#F.\"\"#*&%&delt aGF/*$-F%6#-F%6#-&F+6#,&F.F/\"\"\"F16#&F46#,&F.F/\"\"\"F1\"\"#F/" } {TEXT -1 5 " then" }}{PARA 0 "" 0 "" {TEXT -1 18 " swap(" }{XPPEDIT 18 0 "b[k],b[k-1]" "6$&%\"bG6#%\"kG&F$6#,&F&\"\"\"\"\"\"!\" \"" }{TEXT -1 2 ");" }}{PARA 0 "" 0 "" {TEXT -1 26 " k:=ma x(k-1,2)" }}{PARA 0 "" 0 "" {TEXT -1 11 " else" }}{PARA 0 "" 0 " " {TEXT -1 20 " k:=k+1:" }}{PARA 0 "" 0 "" {TEXT -1 9 " \+ fi:" }}{PARA 0 "" 0 "" {TEXT -1 3 "od:" }}{PARA 0 "" 0 "" {TEXT -1 7 "return " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" } {TEXT -1 5 ",...," }{XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 1 " " }{MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 131 "Algoritmi korre ktsus on ilmne. Ainus raskus on algoritmi keerukushiunnangus. Nimelt t uleb n\344idata \374lemine t\365ke vektorite vahetuste " }{XPPEDIT 18 0 "b[k]" "&%\"bG6#%\"kG" }{TEXT -1 4 " ja " }{XPPEDIT 18 0 "b [k-1]" " &%\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 72 " arvule. Seda tehakse \+ tuues sisse alamv\365rede L(b[1]),L(b[1],b[2]),...,L(" }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 ",...," } {XPPEDIT 18 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 84 " ) determinantide k orrutis D. Ilmneb, et arv D v\344heneb iga vahetuse korral v\344hemalt " }{XPPEDIT 18 0 "delta" "I&deltaG6\"" }{TEXT -1 45 " korda, mis anna b vahetuste arvule \374lemt\365kke " }{XPPEDIT 18 0 "O(log(M)*n^2) " " -%\"OG6#*&-%$logG6#%\"MG\"\"\"*$%\"nG\"\"#F*" }{TEXT -1 12 ", kus M=ma x(" }{XPPEDIT 18 0 "abs(abs(b[i]))^2" "*$-%$absG6#-F$6#&%\"bG6#%\"iG\" \"#" }{TEXT -1 126 "). Veel saab t\365estada, et vajalikku arvutust \344psust saab esmalt hinnata. Need kaks v\344idet annavadki algoritmi pol\374nomiaalsuse. " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 19 "Praktil ine algoritm" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Gramm-Schmidt v \365redele t\344iendatud antud spetsiifilisele olukorrale, kus " } {XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 4 ",. .," }{XPPEDIT 18 0 "b[k-1]" "&%\"bG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 30 " on minimaalse pikkusega baas." }}{PARA 0 "" 0 "" {TEXT -1 79 " Sisendid B baasimaatriks, B1 on ortogonaalse s\374steemi maatriks ja \+ M=[1,2,..m]" }}{PARA 0 "" 0 "" {TEXT -1 8 "V\344ljund " }{XPPEDIT 18 0 "b[1],b[2]" "6$&%\"bG6#\"\"\"&F$6#\"\"#" }{TEXT -1 4 ",..," } {XPPEDIT 18 0 "b[k]" "&%\"bG6#%\"kG" }{TEXT -1 27 " minimaalse pikkuse ga baas." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "length_reduce_last_vect or:=proc(B::matrix,B1::matrix, k::integer,M::list)" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 15 "local j,mu,b,a:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "for j from k-1 by -1 to 1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " a:=subvector(B,M,k): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " b :=subvector(B1,M,j): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " mu:=d otprod(a,b)/dotprod(b,b): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 " i f abs(mu)>1/2 then B:=addcol(B,j,k,-round(mu)): fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN( B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%:length_reduce_last_vectorG:6&'%\"BG%'matrixG'%#B1GF) '%\"kG%(integerG'%\"MG%%listG6&%\"jG%#muG%\"bG%\"aG6\"F7C$?(8$,&9&\"\" \"!\"\"F=F>F=%%trueGC&>8'-%*subvectorG6%9$9'F<>8&-FD6%9%FGF:>8%*&-%(do tprodG6$FBFIF=-FQ6$FIFIF>@$2#F=\"\"#-%$absG6#FN>FF-%'addcolG6&FFF:F<,$ -%&roundGFenF>-%'RETURNG6#FFF7F7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "Gramm-Schmidti kordajate maatriksisse \374he uue rea k lisamine ni ng B1 uue veeru lisamine" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "add_row_to_MU_and_col_to_B1:=proc(B::matrix,B1::matri x,MU::matrix,k,M::list)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "local j, a,b:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "a:=subvector(B,M,k):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "B1:=copyinto(submatrix(B,M,[k]),B1, 1,k):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "for j from 1 to k-1 do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " b:=subvector(B1,M,j): \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 " MU[k,j]:=dotprod(a,b)/dot prod(b,b): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 " if abs(MU[k,j] )>1/2 then print(`failure`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " B1:=addcol(B1,j,k,-MU[k,j]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "MU[k,k]:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "S isend olgu maatriks, mille esimesed n veergu on lineaarselt s\365ltuma tud " }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "LLL_redu ce:=proc(B::matrix,delta)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "local \+ m,n,M,MU,B1,k,i,bk,bk_1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "if delt a>1 or delta<1/4 then ERROR(`Vale parameetri delta v\344\344rtus`): fi :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "#MU sisaldab vajalike Gramm-Sc hmidti kordajaid" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "#B1 sisaldab ar vutatud LLL baasi ortogonaalset vektorite s\374steemi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=rowdim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "#M on vajali vektori eraldamiseks maatriksist" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 19 "M:=[seq(i,i=1..m)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=rank(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "MU:=matrix(n ,n,0):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "MU[1,1]:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "B1:=matrix(m,n,0):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "B1:=copyinto(submatrix(B,M,[1]),B1,1,1):" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 5 "k:=2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "w hile k<=n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " #length reduce t \344iendatud variant " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " lengt h_reduce_last_vector(B,B1,k,M):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " #maatrisite MU ja B1 t\344iendamine " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 " add_row_to_MU_and_col_to_B1(B,B1,MU,k,M):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " #kontrollime LLL teist tingimust" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 28 " bk_1:=subvector(B1,M,k-1):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " bk:=subvector(B1,M,k): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 " if (delta-MU[k,k-1]^2)*dotprod(bk_1,bk_1)>dotprod(b k,bk) then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " B:=swapcol(B,k,k -1):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " if k>2 then k:=k-1:" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 " #n\374\374d tuleb maatriksi B1 esimene veerg \+ \344ra parandada " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " B1:=c opyinto(submatrix(B,M,[1]),B1,1,1):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " else" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 12 " k:=k+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RET URN(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 4 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 14 "SVP rakendused" }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 26 "Harilik seljakoti \374lesanne" }}{PARA 0 "" 0 "" {TEXT 276 7 "Sise nd:" }}{PARA 0 "" 0 "" {TEXT -1 32 " On antud positiivsed t\344isarvud " }{XPPEDIT 18 0 "a[1]" "&%\"aG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "a[2]" "&%\"aG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 35 " ja t\344isarv s, mis on saadud kujul" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "s=sum(a[i]*x[i],i=1..n)" "/%\"sG-%$su mG6$*&&%\"aG6#%\"iG\"\"\"&%\"xG6#F+F,/F+;\"\"\"%\"nG" }{TEXT -1 15 " \+ (*), kus " }{XPPEDIT 18 0 "x[i]" "&%\"xG6#%\"iG" }{TEXT -1 16 " on kas 0 v\365i 1." }}{PARA 0 "" 0 "" {TEXT 277 15 "Oodatav v\344ljund" }{TEXT -1 11 " on vektor " }{TEXT 280 1 "x" }{TEXT -1 2 "=(" } {XPPEDIT 18 0 "x[1]" "&%\"xG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 " x[2]" "&%\"xG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "x[n]" "&%\"x G6#%\"nG" }{TEXT -1 38 ") nii, et oleks rahuldatud v\365rrand (*)" }} {PARA 0 "" 0 "" {TEXT -1 75 "Traditsiooniline lahend \374lesandele on lihtsalt k\365ikide v\365imalike vektori " }{TEXT 281 1 "x" }{TEXT -1 36 " variantide l\344bi vaatamine, mida on " }{XPPEDIT 18 0 "2^n" " )\"\"#%\"nG" }{TEXT -1 20 " erinevat v\365imalust." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "\334ks lihtsamatest ebatr aditsioonilistest meetoditest \374lesande lahendamisel on t\344isarvul ise v\365re L(" }{XPPEDIT 18 0 "a[1]" "&%\"aG6#\"\"\"" }{TEXT -1 1 ", " }{XPPEDIT 18 0 "a[2]" "&%\"aG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 3 ",s)" }}{PARA 0 "" 0 "" {TEXT -1 103 "(t\344histus on ebatraditsiooniline) koostamine. V\365re on de fineeritud kui k\365ikide t\344isarvuliste vektorite " }{TEXT 278 1 "y " }{TEXT -1 2 "=(" }{XPPEDIT 18 0 "y[1]" "&%\"yG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "y[2]" "&%\"yG6#\"\"#" }{TEXT -1 5 ",...," } {XPPEDIT 18 0 "y[n+1]" "&%\"yG6#,&%\"nG\"\"\"\"\"\"F'" }{TEXT -1 26 ") , mis rahuldavad v\365rdust " }{XPPEDIT 18 0 "sum(y[i]*a[i],i=1..n)=y[ n+1]*s" "/-%$sumG6$*&&%\"yG6#%\"iG\"\"\"&%\"aG6#F*F+/F*;\"\"\"%\"nG*&& F(6#,&F2F+\"\"\"F+F+%\"sGF+" }{TEXT -1 29 " (**). On ilmne, et vekto r " }{TEXT 279 2 "x=" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "x[1]" "&%\"xG6# \"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "x[2]" "&%\"xG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "x[n]" "&%\"xG6#%\"nG" }{TEXT -1 3 ",1)" } {TEXT 282 1 " " }{TEXT -1 41 "on v\365res \374ks l\374himaid vektoreid \374ksnormi " }{XPPEDIT 18 0 "abs(abs(y))=sum(abs(y[i]),i=1..n+1)" "/ -%$absG6#-F$6#%\"yG-%$sumG6$-F$6#&F(6#%\"iG/F0;\"\"\",&%\"nG\"\"\"\"\" \"F6" }{TEXT -1 253 " suhtes. Seega intuitiivselt on selge, et kui ots ida l\374him vektor antud v\365res, siis saame suure t\365en\344osuse ga k\344tte seljakoti probleemi lahenduse. Erinevad matemaatikud on se da intuitiivset ideed formaliseerinud ning tulnud v\344ja teoreetilise tulemusega." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 283 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 22 "Kui seljakoti tihedus \+ " }{XPPEDIT 18 0 "d=n/max(seq(log(a[i],i=1..n))" "/%\"dG*&%\"nG\"\"\"- %$maxG6#-%$seqG6#-%$logG6$&%\"aG6#%\"iG/F3;\"\"\"F%!\"\"" }{TEXT -1 39 " on v\344iksem kui 0.6463, siis on v\365re L(" }{XPPEDIT 18 0 "a[1 ]" "&%\"aG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "a[2]" "&%\"aG6#\" \"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 9 ",s) l\374him" }}{PARA 0 "" 0 "" {TEXT -1 55 "vektor suure t\365e n\344osusega seljakoti \374lesande lahendiks." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 284 8 "J\344reldus" }}{PARA 0 " " 0 "" {TEXT -1 135 "Kui meil leidub algoritm, mis suudab efektiivselt lahendada SVP probleemi, siis me suudame efektiivselt lahendada selja koti \374lesannet. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 114 "\334ks v\365imalik efektiivne algoritm SVP lahendamise ks on LLL-algoritm(teatavatel tingimustel annab LLL t\344pse lahendi) " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 33 "\334lesande heuristiline lah endamine" }}{PARA 0 "" 0 "" {TEXT -1 27 "Esimalt tuleb leida v\365re L (" }{XPPEDIT 18 0 "a[1]" "&%\"aG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "a[2]" "&%\"aG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 196 ",s) baas, mida on v\365imalik leida pol \374nomiaalses ajas. Kahjuks ei tea ma muud, algoritmi kui k\365ikide \+ v\365imaluste l\344bi proovimine. J\344rgmised kaks teoreemi lubavad k ontrollida, kas saadu on v\365re baas." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "Seljakoti teoreemid" {TEXT 285 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "Olgu meil nulli st erinev vektor " }{TEXT 286 1 "a" }{TEXT -1 2 "=(" }{XPPEDIT 18 0 "a [1]" "&%\"aG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "a[2]" "&%\"aG6# \"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" } {TEXT -1 25 ") ja naturaalarv s. Olgu " }{XPPEDIT 18 0 "L[a,s]" "&%\"L G6$%\"aG%\"sG" }{TEXT -1 19 " t\344isarvuline v\365re" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "L[a,s]" "&%\"LG6$%\"aG%\"sG" } {TEXT -1 2 "=\{" }{TEXT 287 3 "x| " }{TEXT -1 1 "(" }{TEXT 288 1 "x" } {TEXT -1 1 "," }{TEXT 289 1 "a" }{TEXT -1 14 ")=0(mod s) ja " }{TEXT 290 1 "x" }{TEXT -1 25 " on t\344isarvuline vektor\}," }}{PARA 0 "" 0 "" {TEXT -1 46 "siis v\365re m\365\365de on n ja v\365re determinant \+ det " }{XPPEDIT 18 0 "L[a,b]=s/gcd(a[1],a[2]...a[n],s)" "/&%\"LG6$%\"a G%\"bG*&%\"sG\"\"\"-%$gcdG6%&F&6#\"\"\";&F&6#\"\"#&F&6#%\"nGF)!\"\"" } {TEXT -1 3 " . " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 294 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 20 "Kui v\365re L ala mv\365re " }{XPPEDIT 18 0 "L[1]" "&%\"LG6#\"\"\"" }{TEXT -1 24 " baas i determinant det " }{XPPEDIT 18 0 "L[1]" "&%\"LG6#\"\"\"" }{TEXT -1 72 " on v\365rdne v\365re determinandiga det L, siis langeb alamv\365 re v\365rega \374hte." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 297 7 "N\344ide 1" }}{PARA 0 "" 0 "" {TEXT -1 11 "Kui vektor \+ " }{TEXT 295 1 "a" }{TEXT -1 38 "=(2,7,75,115) ja s=77, siis vektorile " }{TEXT 296 1 "a" }{TEXT -1 15 " vastava v\365re " }{XPPEDIT 18 0 " L[a,s]" "&%\"LG6$%\"aG%\"sG" }{TEXT -1 17 " baasimaatriks on" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "B[a,s]=MATRIX([[1, 0, 0, 0], [0, 1, 0, 0], [0 , 0, 1, 0], [4, 14, 73, 77]]) " "/&%\"BG6$%\"aG%\"sG-%'MATRIXG6#7&7&\" \"\"\"\"!F.F.7&F.\"\"\"F.F.7&F.F.\"\"\"F.7&\"\"%\"#9\"#t\"#x" }}{PARA 0 "" 0 "" {TEXT -1 41 "Lisades siia viimase kontrollrea saame L(" } {XPPEDIT 18 0 "a[1]" "&%\"aG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 " a[2]" "&%\"aG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "a[4]" "&%\"a G6#\"\"%" }{TEXT -1 18 ",s) baasimaatriksi" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "B=MATRIX([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [4, 14, 73, 77],[6,21,110,115]]) " "/%\"BG-%'MATRIXG6#7'7&\"\"\"\"\"!F*F* 7&F*\"\"\"F*F*7&F*F*\"\"\"F*7&\"\"%\"#9\"#t\"#x7&\"\"'\"#@\"$5\"\"$:\" " }}{PARA 0 "" 0 "" {TEXT -1 36 "Rakendame n\374\374d LLL-algoritmi, \+ saame" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "B:=matrix(5,4,[[1, \+ 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [4, 14, 73, 77], [6, 21, 110, 11 5]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "LLL_reduce(B,1); " }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG-%'MATRIXG6#7'7&\"\"\"\"\"!F+F+7 &F+F*F+F+7&F+F+F*F+7&\"\"%\"#9\"#t\"#x7&\"\"'\"#@\"$5\"\"$:\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7'7&!\"\"\"\"#!\"$F(7&\"\" !F(\"\"\"!\"&7&F(!\"#F,F-7&F,F)F)F(7&F(F-\"\"$F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%\"BG" }}}{PARA 0 "" 0 "" {TEXT -1 241 "Nagu n\344ha sa ime k\374ll vektoreid, mille pikkus on v\344iksem kui esialgsed vektor id, kuid siiski mitte \374htegi vektorit, mis sobiks meie seljakoti \374lesande lahendiks. Alternatiivne lahendus on l\344bi kombineerimis e. Me teame, et lahend peab koosnema " }}{PARA 0 "" 0 "" {TEXT -1 163 "nullidest ja \374htedest ja vvimaste vektorite komponendid ei m\365ju ta eelmiste vektorite komponente. Nii saab piirata l\344bivaadatavate vektorite kombinatsioonide arvu:" }}{PARA 0 "" 0 "" {TEXT -1 110 "vek tori (1,0,0,4,6) esimene komponent vastab meie tingimustele seega v \365ib see esineda meie otsitavas vektoris" }}{PARA 0 "" 0 "" {TEXT -1 90 "vektori (1,0,0,4,6)+(0,1,0,14,21)=(1,1,0,18,27) esimesed kaks \+ komponenti sobivad, nagu ka" }}{PARA 0 "" 0 "" {TEXT -1 96 "vektori ( 1,0,0,4,6) esimesed kaks komponenti ja vektori (0,1,0,14,21) esimesed \+ kaks komponenti." }}{PARA 0 "" 0 "" {TEXT -1 75 "Vaatame, millised n \344evad v\344lja esimese kolme vektori sobivad kombinatsiooni" }} {PARA 0 "" 0 "" {TEXT -1 178 "Eelnevatest sobivad (1,0,0,4,6),(0,1,0,1 4,21),(1,1,0,18,27) ja lisatav kolmas vektor (0,0,1,73,110) ja j\344rg mised kombinatsioonid: (1,0,0,1,77,116),(0,1,1,87,131),(1,1,1,91,137) ." }}{PARA 0 "" 0 "" {TEXT -1 118 "Nelja vektori sobivaid kombinatsioo ne on lihtne leida, sobib vaid (1,0,0,1,0,1), kuna neljandat 0 saab le ida vaid \374hel" }}{PARA 0 "" 0 "" {TEXT -1 113 "moel. See vektor 1*2 +0*7+1*75+0*115 ongi \374lesande lahend ning v\365re l\374him vektor. \+ Siit on n\344ha, et LLL-algoritm ei" }}{PARA 0 "" 0 "" {TEXT -1 232 "a nna alati \374lesande lahendust, kuna ei leia piisavalt l\374hikesi ve toreid. Kombineerimismeetod annab loomulikult k\344tte \374lesande vas tuse, kuid kui peadiagonaalil on \374hed, siis on see t\366\366mahult \+ v\365rdne k\365igi vektorite l\344bi proovimisega. " }}{PARA 0 "" 0 " " {TEXT -1 117 "Millest tulenevalt on meetod sobilik vaid siis, kui LL L-algoritm annab k\344tte vastuse. See on aga tagatud juhtudel kui" }} {PARA 0 "" 0 "" {TEXT -1 69 "v\365re determinant ehk otsitav summa on \+ k\374llalt suur v\365rreldes n-ga. " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 9 "\334lesanded" }}{PARA 0 "" 0 "" {TEXT 298 10 "\334lesanne \+ 1" }}{PARA 0 "" 0 "" {TEXT -1 28 "Lahendada seljakoti\374lesanne " } {TEXT 300 1 "a" }{TEXT -1 43 "=(1001,1037,1050,1073) ja s=2051, kui v \365re " }{XPPEDIT 18 0 "L[a,s]" "&%\"LG6$%\"aG%\"sG" }{TEXT -1 17 " b aasimaatriks on" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "B[a,s] := MATRIX([[1 , 0, 0, 0], [1, 1, 0, 0], [0, 0, 1, 0], [1382, 1144, 1813, 2051]])" "> &%\"BG6$%\"aG%\"sG-%'MATRIXG6#7&7&\"\"\"\"\"!F.F.7&\"\"\"\"\"\"F.F.7&F .F.\"\"\"F.7&\"%#Q\"\"%W6\"%8=\"%^?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "B:=?" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 299 10 "\334lesanne 2" }}{PARA 0 "" 0 "" {TEXT -1 31 "Lahendada \+ seljakoti\374lesanne a=(" }{XPPEDIT 18 0 "14444,14274,15531,17551,2005 6,23517,24613,25450)" "6*\"&WW\"\"&uU\"\"&Jb\"\"&^v\"\"&c+#\"&\"&PI#\"&V7#\"&q:\"\"&x4&\"&oB#\"&\")=&" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "B=?" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 301 13 " \334lesanne 3(*)" }}{PARA 0 "" 0 "" {TEXT -1 15 "Lahendada v\365re " } {XPPEDIT 18 0 "L[a,s]" "&%\"LG6$%\"aG%\"sG" }{TEXT -1 79 " baasmaatrik si leidmine pol\374nomiaalses ajas eeldusel, et leidun sellinevektori \+ " }{TEXT 302 1 "a" }{TEXT -1 11 " komponent " }{XPPEDIT 18 0 "a[i]" "& %\"aG6#%\"iG" }{TEXT -1 20 ", mille korral gcd(" }{XPPEDIT 18 0 "a[1] " "&%\"aG6#\"\"\"" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#% \"nG" }{TEXT -1 8 ",s)=gcd(" }{XPPEDIT 18 0 "a[i]" "&%\"aG6#%\"iG" } {TEXT -1 4 ",s)." }}{PARA 0 "" 0 "" {TEXT 303 9 "N\344pun\344ide" }} {PARA 0 "" 0 "" {TEXT -1 27 "1) Kui see komponent oleks " }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 39 ", siis v\365iks viimaseks ve ktoriks v\365tta " }{XPPEDIT 304 0 "b[n]" "&%\"bG6#%\"nG" }{TEXT -1 19 "=(0,0,0...,0,s/gcd(" }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" }{TEXT -1 5 ",s))." }}{PARA 0 "" 0 "" {TEXT -1 113 "2) Teooriast on teada, et leidub alumisel kolmnurkujul maatriks, mille peadiagonaal domineerib \+ absoluutselt(HNF)." }}{PARA 0 "" 0 "" {TEXT -1 19 "3) Teoreemide * ja \+ " }{HYPERLNK 17 "**" 1 "" "Seljakoti teoreemid" }{TEXT -1 43 " j\344rg i on baasimaatriksi determinant s/gcd(" }{XPPEDIT 18 0 "a[1]" "&%\"aG6 #\"\"\"" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "a[n]" "&%\"aG6#%\"nG" } {TEXT -1 4 ",s)." }}{PARA 0 "" 0 "" {TEXT -1 71 "4) Mis kujul on siis \+ t\344nu eelnevatele v\344idetele baasimaatriksi k veerg " }{XPPEDIT 305 0 "b[k]" "&%\"bG6#%\"kG" }{TEXT -1 1 "?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 306 15 "\334lesanne 4(***)" }}{PARA 0 "" 0 "" {TEXT -1 15 "Lahendada v\365re " }{XPPEDIT 18 0 "L[a,s]" "&%\" LG6$%\"aG%\"sG" }{TEXT -1 43 " baasmaatriksi leidmine pol\374nomiaalse s ajas" }}{PARA 0 "" 0 "" {TEXT 307 5 "Ideed" }}{PARA 0 "" 0 "" {TEXT -1 78 "1) Kui me otsime baasimaatrisi vektoreid kolmnurksel kujul, sii s \365ige vektori " }{XPPEDIT 313 0 "b[k]" "&%\"bG6#%\"kG" }{TEXT -1 31 " k-s komponent peab olema v\344him" }}{PARA 0 "" 0 "" {TEXT -1 22 " positiivne v\365imalik. " }}{PARA 0 "" 0 "" {TEXT -1 56 "2) Iga t \344isarvuliste kordajatega vektori(pikkusega k-1) " }{TEXT 308 1 "a" }{TEXT -1 4 " ja " }{TEXT 309 2 "x " }{TEXT -1 16 "skalaarkorrutist" } {TEXT 311 1 " " }{TEXT -1 10 "jagab gcd(" }{XPPEDIT 18 0 "a[1]" "&%\"a G6#\"\"\"" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "a[k-1]" "&%\"aG6#,&%\"kG \"\"\"\"\"\"!\"\"" }{TEXT -1 36 "). Seega kui me otsime vektorit \+ " }{XPPEDIT 310 0 "b[k]" "&%\"bG6#%\"kG" }{TEXT 312 1 "," }{TEXT -1 36 " mille nullist erinevad komponendid " }{XPPEDIT 18 0 "b[i]" "&%\"b G6#%\"iG" }{TEXT -1 29 " algavad kohast k, siis saame" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 " a[k]*b[k]=l*s+sum(a[i]*b[i],i=k+1..n)" "/*&&%\" aG6#%\"kG\"\"\"&%\"bG6#F'F(,&*&%\"lGF(%\"sGF(F(-%$sumG6$*&&F%6#%\"iGF( &F*6#F6F(/F6;,&F'F(\"\"\"F(%\"nGF(" }}{PARA 0 "" 0 "" {TEXT -1 23 "ja \+ seega peab korrutis " }{XPPEDIT 18 0 "a[k]*b[k]" "*&&%\"aG6#%\"kG\"\" \"&%\"bG6#F&F'" }{TEXT -1 16 " jaguma millega?" }}{PARA 0 "" 0 "" {TEXT -1 45 "3) Eukleidese algoritmi j\344reldus iga vektori " }{TEXT 314 1 "a" }{TEXT -1 23 " korral, leidub vektor " }{TEXT 315 2 "x " } {TEXT -1 7 "nii, et" }{TEXT 317 1 " " }{TEXT -1 17 "skalaarkorrutis ( " }{TEXT 316 3 "a,x" }{TEXT -1 6 ")=gcd(" }{XPPEDIT 18 0 "a[1]" "&%\"a G6#\"\"\"" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "a[k-1]" "&%\"aG6#,&%\"kG \"\"\"\"\"\"!\"\"" }{TEXT -1 1 ")" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 32 "V\344ikeste juurte leidmine ringis " }{XPPEDIT 18 0 "Z[N]" "&% \"ZG6#%\"NG" }{TEXT -1 3 "[x]" }}{PARA 0 "" 0 "" {TEXT -1 44 "Erineval t ringidest Z[x] ja Zp[x] on ringis " }{XPPEDIT 18 0 "Z[N]" "&%\"ZG6#% \"NG" }{TEXT -1 68 "[x] pol\374noomide tegurdamine raske kui pole tead a N tegurdus.V\344ikese " }}{PARA 0 "" 0 "" {TEXT -1 107 "astmega pol \374noomi p(x) juurte leidmist on v\365imalik taandada tegurdamisele Z [x], kasutades j\344rgmisi v\344iteid." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 291 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 37 "Olgu meil n-nda astme pol\374noom r(x)=" }{XPPEDIT 18 0 "r[n]" "&%\"rG6#%\"nG" }{TEXT -1 9 "*x^n+...+" }{XPPEDIT 18 0 "r[0]" " &%\"rG6#\"\"!" }{TEXT -1 59 ", siis pol\374noomi Eukleidiliseks normik s nimetatakse suurust" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "abs(abs(r(x))) [2]=sqrt(sum(r[i]^2,i=0..n))" "/&-%$absG6#-F%6#-%\"rG6#%\"xG6#\"\"#-%% sqrtG6#-%$sumG6$*$&F*6#%\"iG\"\"#/F8;\"\"!%\"nG" }{TEXT -1 1 "." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 292 5 "Lemma" } {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 72 "Olgu meil t\344isarvulis te kordajatega pol\374noom r(x) ja naturaalarv X. Kui " }{XPPEDIT 18 0 "abs(abs(r(Xx))) " 0 "" {MPLTEXT 1 0 42 "get_co nstants:=proc(q::polynom,n::integer)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "RETURN(matrix(n,1, [seq(coeff(p,x,i),i=0..n-1)])):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "e nd:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "make_matrix_B:=proc( p::polynom)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "local B,b,i,j,u,v,P, d,q,N,h,n,X:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "X:=4:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 "d:=3:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=2 56:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "h:=25:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=(h+1)*d:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "p:= subs(x=X*x,p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 1 to 7 8 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " v:=floor((i-1)/d):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " u:=i-1-d*v: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " #vajlik pol\374noom q[u,v]" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 37 " q:=expand(256^(h-v)*(X*x)^u*p^v):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " #arvutame uue veeru komponendid" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " b:=get_constants(q,n):" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 25 " B:=copyinto(b,B,1,i):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(B): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%.make_matrix_BG:6#'%\"pG%(polynomG6/%\"BG%\"bG%\"iG% \"jG%\"uG%\"vG%\"PG%\"dG%\"qG%\"NG%\"hG%\"nG%\"XG6\"F8C*>80\"\"%>8+\" \"$>8-\"$c#>8.\"#D>8/*&,&FD\"\"\"FJFJFJF>FJ>9$-%%subsG6$/%\"xG*&F;FJFQ FJFL?(8&FJFJ\"#y%%trueGC'>8)-%&floorG6#*&,&FTFJ!\"\"FJFJF>Fin>8(,(FTFJ FinFJ*&F>FJFYFJFin>8,-%'expandG6#*()FB,&FDFJFYFinFJ)FRF[oFJ)FLFYFJ>8%- %.get_constantsG6$F_oFG>8$-%)copyintoG6&FioF^pFJFT-%'RETURNG6#F^pF8F8 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "find_polynom:=proc(A::m atrix,n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "local B,r,X:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "X:=4:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "B:=LLL_reduce(B,0.99):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "r:=ex pand(sum(B[i,1]*(x/X)^(i-1),i=1..n)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(r):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%-find_polynomG:6$'%\"AG%'matrixG%\"nG6%%\" BG%\"rG%\"XG6\"F/C&>8&\"\"%>8$-%+LLL_reduceG6$F5$\"#**!\"#>8%-%'expand G6#-%$sumG6$*&&F56$%\"iG\"\"\"FH)*&%\"xGFHF2!\"\",&FGFHFLFHFH/FG;FH9%- %'RETURNG6#F=F/F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 194 "N\374\374d \+ pol\374noomi x^3+251*x^2+2*x+8 v\344ikeste juurte leidmiseks mooduli 2 56 j\344rgi tuleb leida protseduuri find_polynom v\344ljundpol\374noo mi juured, mis on v\344iksemad v\365i absoluutv\344\344rtuselt v\365rd sed 4-ga." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 107 "V\365ib m\365elda, miks tuleb nii v\344ikese asja nagu \+ -4,-3,...,4 v\365rrandisse panemise asemel nii palju vaeva n\344ha" }} {PARA 0 "" 0 "" {TEXT -1 88 "Ilmneb, et nii saab leida k\365ik pol\374 noomi juured mis on absoluutv\344\344rtuselt v\344iksemad kui " } {XPPEDIT 18 0 "1/2*N^(1/d)" "*(\"\"\"\"\"\"\"\"#!\"\")%\"NG*&\"\"\"F$% \"dGF&F$" }{TEXT -1 17 ", kui vaid valida" }}{PARA 0 "" 0 "" {TEXT -1 62 "\365ige h ja teha seda pol\374nomiaalses ajas parameetrite log N j a " }{XPPEDIT 18 0 "2^d" ")\"\"#%\"dG" }{TEXT -1 39 " suhtes. Kontroll itavate v\344\344rtuste hulk" }}{PARA 0 "" 0 "" {TEXT -1 222 "O(N^1/d) kasvab kiiremini kui log N. T\344isarvude korral on olemas efektiivse d algoritmid juurte leidmiseks. Ning peale selle on kompleksarvude teo oriat kasutades k\374llaltki lihtne hinnata juure arvu kontrollitavas \+ vahemikus." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 51 "Naturaalarvu esita mine nelja t\344isarvu ruudu summana" }}{SECT 1 {PARA 5 "" 0 "" {TEXT 318 45 " Algarvu esitus kahe t\344isarvu ruutude summana" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 319 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 85 "Kui p=1 mod 4 j\344rgi, siis on t\344isarvu v \365imalik esitada kahe t\344isarvu ruutude summana." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 320 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 64 "Kui p=1 mod 4 j\344rgi, siis leidub korpuses Zp ele ment i nii, et " }{XPPEDIT 18 0 "i^2=-1" "/*$%\"iG\"\"#,$\"\"\"!\"\"" }{TEXT -1 40 " ja t\344isarvulise v\365re L baasimaatriksiga" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "B=MATRIX([[1,0],[i,p]])" "/%\"BG-%'MATRIXG6#7 $7$\"\"\"\"\"!7$%\"iG%\"pG" }{TEXT -1 2 ", " }}{PARA 0 "" 0 "" {TEXT -1 56 "l\374hima vektori Eukleidilise pikkuse ruut on v\365rdne p-ga. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 "T\365e stus" }}{PARA 0 "" 0 "" {TEXT -1 69 "Mikowski teoreem kindlustab, et l \374hima vektori pikkus on v\344iksem kui " }{XPPEDIT 18 0 "sqrt(2)*sq rt(p)" "*&-%%sqrtG6#\"\"#\"\"\"-F$6#%\"pGF'" }{TEXT -1 49 ". Teisalt o n lihtne veenduda, et l\374hima vektori " }{TEXT 323 1 "b" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "(x[1],x[1]*i+x[2]*p)" "6$&%\"xG6#\"\"\",&*&&F$6# \"\"\"\"\"\"%\"iGF,F,*&&F$6#\"\"#F,%\"pGF,F," }{TEXT -1 14 " pikkuse r uut " }{XPPEDIT 18 0 "x[1]^2*(1+i^2)+p(2*x[1]*x[2]+p*x[2]^2)" ",&*&&% \"xG6#\"\"\"\"\"#,&\"\"\"\"\"\"*$%\"iG\"\"#F+F+F+-%\"pG6#,&*(\"\"#F+&F %6#\"\"\"F+&F%6#\"\"#F+F+*&F0F+*$&F%6#\"\"#\"\"#F+F+F+" }{TEXT -1 44 " jagub p-ga, millest l\374hima vektori pikkuse " }}{PARA 0 "" 0 "" {TEXT -1 12 "ruut ongi p." }}{PARA 0 "" 0 "" {TEXT -1 8 "m.o.t.t." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "See anna b meile praktilise algoritmi p lahutamiseks kahe algarvu teguriks, kun a me v\365ime siin l\374hima vektori leidmiseks kasutada " }{HYPERLNK 17 "Gaussi algoritmi" 1 "" "Gaussi baas" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "Suvalise algarvu esi tus nelja t\344isarvu ruutude summana" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 324 5 "Lemma" }}{PARA 0 "" 0 "" {TEXT -1 46 "Iga algarvu korral leiduvad arvud a,b nii, et " }{XPPEDIT 18 0 "a^2+b ^2+1=0 mod p" "/,(*$%\"aG\"\"#\"\"\"*$%\"bG\"\"#F'\"\"\"F'-%$modG6$\" \"!%\"pG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT 327 9 "Teoreem 1" }}{PARA 0 "" 0 "" {TEXT -1 12 "Iga alga rvu " }{XPPEDIT 18 0 "17<=p" "1\"#<%\"pG" }{TEXT -1 24 " korral on j \344rgmise v\365re" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "B:=MATRIX([[1, 0, 0, 0], [a, b, 0, 0], [-b, a, p, 0], [0, 1, 0, p]])" ">%\"BG-%'MATRIXG 6#7&7&\"\"\"\"\"!F*F*7&%\"aG%\"bGF*F*7&,$F-!\"\"F,%\"pGF*7&F*\"\"\"F*F 1" }{TEXT -1 6 ", kus " }{XPPEDIT 18 0 "a^2+b^2+1=0 mod p" "/,(*$%\"aG \"\"#\"\"\"*$%\"bG\"\"#F'\"\"\"F'-%$modG6$\"\"!%\"pG" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 23 "l\374hma vektori ruut p. " }}{PARA 0 " " 0 "" {TEXT -1 87 "Jaguvus t\365estatakse analoogselt eelnevaga. Miko wski hinnang vektori pikkuse ruudule on " }{XPPEDIT 18 0 "4*sqrt(b)*p " "*(\"\"%\"\"\"-%%sqrtG6#%\"bGF$%\"pGF$" }{TEXT -1 96 ", kuid t\344ie ndavaid arvuteoreetilisi nippe kasutades on v\365imalik n\344idata, et vektori pikkus on p." }}{PARA 0 "" 0 "" {TEXT -1 8 "m.o.t.t." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 328 9 "Teoreem 2 " }}{PARA 0 "" 0 "" {TEXT -1 88 "Kui a ja b on esitatavad nelja t\344i sarvu ruuduna summana, siis on seda ka nende korrutis." }}}{SECT 1 {PARA 5 "" 0 "" {TEXT 321 9 "\334lesanded" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 322 10 "\334lesanne 1" }}{PARA 0 "" 0 "" {TEXT -1 105 "J\344rgmised kaks algoritmi lubavad leida -1 ruutjuure k orpuses Zp. Koosta algoritm, mis esitab algarvu kahe" }}{PARA 0 "" 0 " " {TEXT -1 15 "ruudu summana. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "mod_gcd:=proc(f::polynom(integer,x),g::polynom(integer,x),p)" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "local r0,r1,r2:" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "r0:=f mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " r1:=g mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "if r0=0 or r1=0 the n RETURN(0):fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "if degree(r0) " 0 "" {MPLTEXT 1 0 23 "r2:=rem(r0,r1,x) mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " while r2<>0 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " r0:=r1:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " r1:=r2: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " r2:=rem(r0,r1,x) mod p: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "RETURN(r1): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 22 "find_i:=proc(p::prime)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "local i,j,a,b,g1,g2,randp,k:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "if irem(p,4)<>1 then ERROR(`Ei leidu ruutjuurt -1`): \+ fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "randp:=rand(0..p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "a:=0:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "while degree(a)<>1 do a:=randp()*x+randp(): od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "g1:=mod_gcd(x^2+1,a,p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "b:=rem(a^((p-1)/2),x^2+1,x): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "b:=b mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "g2: =mod_gcd(b-1,x^2+1,p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "if degree (g1)=1 then g2:=g1: fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "k:=1:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "while degree(g2)<>1 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " a:=0:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 " while degree(a)<>1 do a:=randp()*x+randp(): od:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 27 " g1:=mod_gcd(x^2+1,a,p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " b:=rem(a^((p-1)/2),x^2+1,x) mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " b:=b mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " g2:=mod_gcd(b-1,x^2+1,p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " if degree(g1)=1 then g2:=g1: fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " if irem(k,100)=0 then print(k): fi:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " k:=k+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "g2:=quo(g2,c oeff(g2,x,1),x) mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "RETURN(p- coeff(g2,x,0) mod p):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "square_prime:=proc(p::prime) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local B:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "if irem(p-1,4)>0 then ERROR(`Korpuses Zp pole ruutjuu rt -1`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "B:=matrix(2,2,[[1,0 ],[find_i(p),p]]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "gauss_reducti on(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "RETURN([B[1,1]^2,B[2,1]^2 ]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "square_prime(13);" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT 326 1 " \334" }{MPLTEXT 1 0 0 "" }{TEXT 325 19 "lesanne 2(*/**/***)" } {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "a) Lahendada algarvu esitus nelja t\344isarvu ruuduna kui " }{XPPEDIT 18 0 "p>=17" "1\"#<% \"pG" }{TEXT -1 51 ", kasutades l\374hima vektori leidmiseks LLL-algor itmi" }}{PARA 0 "" 0 "" {TEXT -1 64 "juhul kui l\374hima vektori ruut \+ ei jagu algarvuga v\344ljastada viga." }}{PARA 0 "" 0 "" {TEXT -1 174 "b) M\365elda v\344lja algoritm, mis lahendab l\374hima vektori proble emi kui antud on alumises kolmnurkujus 4x4 maatriks ja v\365rrelda t \344iustatud algoritmi ning esialgse algoritmi t\366\366d." }}{PARA 0 "" 0 "" {TEXT -1 38 "c) Leida efektiivne algoritm s\374steemi " } {XPPEDIT 18 0 "1+a^2+b^2=0 mod p" "/,(\"\"\"\"\"\"*$%\"aG\"\"#F%*$%\"b G\"\"#F%-%$modG6$\"\"!%\"pG" }{TEXT -1 15 " lahendamiseks." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT 329 14 "\334lesanne 3(* *)" }}{PARA 0 "" 0 "" {TEXT -1 21 "T\365estada teoreem 2. " } {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 50 "Reaalarvude samaaegne diofantiline aproksimatsioon" }}{PARA 0 "" 0 "" {TEXT -1 40 "Algoritm reaalarvude heaks l\344hendamiseks" }}{PARA 0 "" 0 "" {TEXT 330 6 "Sisend" }}{PARA 0 "" 0 "" {TEXT -1 5 "Viga " }{XPPEDIT 18 0 "epsilon>0" "2\"\"!%(epsilonG" }{TEXT -1 23 " ja reaalarvude vekt or " }{XPPEDIT 331 0 "alpha" "I&alphaG6\"" }{TEXT -1 2 "=(" }{XPPEDIT 18 0 "alpha[1]" "&%&alphaG6#\"\"\"" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "alpha[n]" "&%&alphaG6#%\"nG" }{TEXT -1 2 ") " }}{PARA 0 "" 0 "" {TEXT 332 6 "V\344ljud" }}{PARA 0 "" 0 "" {TEXT -1 31 "Nimetaja Q ja \+ lugejate vektor " }{TEXT 333 1 "p" }{TEXT -1 2 "=(" }{XPPEDIT 18 0 "p[ 1]" "&%\"pG6#\"\"\"" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "p[n]" "&%\"pG 6#%\"nG" }{TEXT -1 10 ") nii, et " }{XPPEDIT 18 0 "abs(alpha[i]-p[i]/Q )