{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 "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE " " 0 21 "" 0 1 0 0 0 1 0 0 0 0 2 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 0 1 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 "" 0 1 0 0 0 0 0 1 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 2 0 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 "" 1 14 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 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 2 2 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 "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 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 "" -1 364 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 383 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 384 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 385 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 389 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 391 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 392 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 393 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 394 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 395 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 396 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 397 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 398 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 399 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 400 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 401 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 402 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 403 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 404 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 405 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 406 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 407 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 408 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 409 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 410 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 411 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 412 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 413 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 414 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 415 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 416 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 417 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 418 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 419 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 420 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 421 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 422 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 423 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 424 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 425 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 426 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 427 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 428 "" 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 "Heading 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 O utput" 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 "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 "" 0 256 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 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 1 13 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 }} {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 256 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 257 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 289 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 258 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 259 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 1 {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 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 16 "V\365re de terminant" }}{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&%$RGBGF )F'F'-%'SYMBOLG6#%'CIRCLEG-%'CURVESG6$7'F&F(F-F,F&-F36&F5F'F'F)-%%TEXT G6'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%+AL IGNBELOWGFU-FA6'FLFQFHFIFU-%*AXESSTYLEG6#%&FRAMEG-%(SCALINGG6#%,CONSTR AINEDG" 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 324 279 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 baasivektoritele ehitatud r\366\366pk\374 likud \374hesuuruse pinna. See ei ole juhuslik. \334ldistame antud fak ti k\365ikidele v\365redele. " }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 261 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 10 "V\365re L(B) " }{TEXT 262 14 "determinandiks" } {TEXT -1 29 " loomuliku skalaarkorrutise (" }{TEXT 260 5 ". , ." } {TEXT -1 28 ") suhtes nimetatakse suurust" }}{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 256 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 7 "Teoreem" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "V\365re determinant ei s\365ltu baasi valikust." }}{PARA 0 "" 0 "" {TEXT -1 29 "Tuleneb sellest, 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 266 15 "t\344ism\365\365tmelises " }{TEXT -1 65 "t v\365rest ja siis on v\365re determinant baasivektor itest moodustatud" }}{PARA 0 "" 0 "" {TEXT -1 92 "r\366\366ptahuka ruu mala. \334lej\344\344nud juhtudel tuleneb baasivektorite lineaarsest s \365ltumatusest, et " }{XPPEDIT 18 0 "n0" "2\"\"!%(epsilonG " }{TEXT -1 23 " korral leidub element " }{TEXT 294 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 suurus 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 korral 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 264 9 "Teoreem \+ 2" }}{PARA 0 "" 0 "" {TEXT -1 11 "Vektoruumi " }{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 ala mr\374hm liitmise suhtes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 193 "V\365re diskreetsus on peamine meetrikaline omadu s, mis lubab kasutada teoreemi 1 v\344iteid 3) ja 5), mida kasutatakse nii l\374hima vektori leidumise kui ka teatud algoritmide korrektsuse n\344itamiseks." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 26 "Hermite'i no rmaalkuju(HNF)" }}{PARA 0 "" 0 "" {TEXT -1 65 "Ilmneb, et v\365re baas il on olemas eriline kuju, mida nimetatakse " }{TEXT 265 24 "Hermite' i normaalkujuks." }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 23 "T\344ism\365 \365tmelise v\365re HNF" }}{PARA 0 "" 0 "" {TEXT 267 12 "Definitsioon " }}{PARA 0 "" 0 "" {TEXT -1 81 "Me \374tleme, et v\365re baas B on He rmite'i normaalkujul, kui on t\344idetud 2 tingimust:" }}{PARA 0 "" 0 "" {TEXT -1 33 "1) B on alumine kolmnurkmaatriks;" }}{PARA 0 "" 0 "" {TEXT -1 20 "2) iga 07&F=7$\"\"&F>7$FB!\"&7$FF,%'b[i,i]G%+ALIGNRIGHTG%+ALIGNBELOWGFF-FK6'7$$ \"#6F,$!#9F,FPFQFRFF-FK6'7$$\"#@F,$!#CF,FPFQFRFF-FK6'7$$\"#JF,$!#MF,FP FQFRFF-FK6'7$$\"#TF,$!#WF,FPFQFRFF-F$6-7&F-F+F37$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/FgqF5F17&Ffq7$F0" }{TEXT -1 3 " do" }} {PARA 0 "" 0 "" {TEXT -1 14 " c:=floor(" }{XPPEDIT 18 0 "b1[row]/b 2[row]" "*&&%#b1G6#%$rowG\"\"\"&%#b2G6#F&!\"\"" }{TEXT -1 2 ");" }} {PARA 0 "" 0 "" {TEXT -1 5 " " }{TEXT 271 12 "b1:=b1-c*b2 " } {TEXT -1 22 "//siin kohas on selge " }{XPPEDIT 18 0 "b1[row]>=0" "1\" \"!&%#b1G6#%$rowG" }{TEXT -1 1 ";" }}{PARA 0 "" 0 "" {TEXT -1 5 " \+ " }{TEXT 273 7 "b1:=:b2" }}{PARA 0 "" 0 "" {TEXT -1 5 " od;" }}{PARA 0 "" 0 "" {TEXT -1 8 " return " }{TEXT 274 5 "b1,b2" }{MPLTEXT 1 0 0 " " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Et t egu on Eukleidese algoritmiga, on tulemuseks veerud " }{TEXT 297 3 "b1 '" }{TEXT -1 4 " ja " }{TEXT 296 3 "b2'" }{TEXT -1 7 ", kus " } {XPPEDIT 18 0 "b1[row]" "&%#b1G6#%$rowG" }{TEXT -1 5 "=GCD(" } {XPPEDIT 18 0 "b1[row]" "&%#b1G6#%$rowG" }{TEXT -1 1 "," }{XPPEDIT 18 0 "b2[row]" "&%#b2G6#%$rowG" }{TEXT -1 5 ") ja " }{XPPEDIT 18 0 "b2[ro w]=0" "/&%#b2G6#%$rowG\"\"!" }}{PARA 0 "" 0 "" {TEXT -1 29 "Algoritmi \+ keerukushinnang on " }{XPPEDIT 18 0 "O(n*m)" "-%\"OG6#*&%\"nG\"\"\"%\" mGF'" }{TEXT -1 33 " vektoroperatsiooni, kus m,n on " }{XPPEDIT 18 0 "b1[row]" "&%#b1G6#%$rowG" }{TEXT -1 6 " ja " }{XPPEDIT 18 0 "b2[row ]" "&%#b2G6#%$rowG" }{TEXT -1 18 " pikkused bittides" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 6 "Idee 3" }}{PARA 0 "" 0 "" {TEXT -1 94 "Idee 2 annab v\365imaluse reas olevate elementide null imiseks, seega HNF 1 tingimus pole probleem" }}{PARA 0 "" 0 "" {TEXT -1 68 "Teise tingimuse saame t\344ita, siis kui jagame eelnevaid rea e lemente " }{XPPEDIT 18 0 "b1[i+1]" "&%#b1G6#,&%\"iG\"\"\"\"\"\"F'" } {TEXT -1 1 "," }{XPPEDIT 18 0 "b2[i+1]" "&%#b2G6#,&%\"iG\"\"\"\"\"\"F' " }{TEXT -1 3 ",.." }{XPPEDIT 18 0 "bi[i+1]" "&%#biG6#,&%\"iG\"\"\"\" \"\"F'" }{TEXT -1 16 " l\344bi elemendiga" }}{PARA 0 "" 0 "" {MPLTEXT 0 21 9 "bi+1[i+1]" }{TEXT -1 25 " ja j\344tame alles j\344\344gi. " } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 276 12 " HNF Algoritm" }}{PARA 0 "" 0 "" {TEXT -1 7 " row=1;" }}{PARA 0 "" 0 " " {TEXT -1 7 " col=1;" }}{PARA 0 "" 0 "" {TEXT -1 17 " while(col<=n) d o" }}{PARA 0 "" 0 "" {TEXT -1 92 " for i=col,..,n do if bi[row]<0 t hen bi:=-bi od; //k\365ik elemendid reas row on positiivsed" }}{PARA 0 "" 0 "" {TEXT -1 107 " for i=col+1,..,n do [bcol,bi]:=ColumnGCD(b col,bi,row) od;// k\365ik elemendid reas row on nullid kui i>col" }} {PARA 0 "" 0 "" {TEXT -1 30 " //kuna rank B=n, siis peab " } {XPPEDIT 18 0 "bcol[row]<>0" "0&%%bcolG6#%$rowG\"\"!" }{TEXT -1 68 " \+ " } {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 " for i=1,..,col-1 d o" }{MPLTEXT 1 0 1 " " }}{PARA 0 "" 0 "" {TEXT -1 35 " c=floor( bi[row]/bcol[row]);" }}{PARA 0 "" 0 "" {TEXT -1 239 " bi:=bi-c* bcol; // Et sellel hetkel on maatriks kuni veeruni col alumisel kolmnu rksel kujul, siis see op. ei muuda //eel mistel ridadel olevat ja selle elemendi bi[row] jaoks on HNF 2. tingim us t\344idetud." }}{PARA 0 "" 0 "" {TEXT -1 6 " od;" }}{PARA 0 "" 0 "" {TEXT -1 18 " row++;col++; " }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 6 "od; " }{MPLTEXT 1 0 0 "" }}}{PARA 5 "" 0 "" {TEXT 277 16 "Keerukushinnang." }}{PARA 5 "" 0 "" {TEXT 298 301 "Esimene ts \374kkel n\365uab n(n-1)/2 vektori l\344bi korrutamist, teine ts\374kk el n\365uab n(n-1)/2 ColumGCD tegemist ja viimane ts\374kkel n\365uab \+ n(n-1)/2 jagamist ja vektoriga korrutamist ning liitmist. Seega, kui m eil oleks vektori komponentide v\344\344rtused t\365kestatud, siis ole ks selgelt tegu pol\374nomiaalse \374lesandega." }}}{SECT 1 {PARA 4 " " 0 "" {TEXT -1 19 "Praktiline algoritm" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "ColumnGCD:=proc(B::matrix,col,k,row,n)" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "local abix,i,c;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "#veegude vahetamine" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "if B [row,k]=0 then B:=swapcol(B,k,col) fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "while B[row,k]<>0 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " # Maple k\344sk iquo ei sobi, sest negatiivsete arvude " }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 22 " #annab vale tulemuse" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " c:=floor(B[row,col]/B[row,k]);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 39 " #liidame veerule col -c korda veeru k" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " B:=addcol(B,k,col,-c);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " B:=swapcol(B,k,col): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "#RETURN(B) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "HNF1:=proc(B::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "local row,k,i,c,n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "if coldim(B)<>rowdim(B) then ERROR(`Pole ruutmaatriks`): fi:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "if det(B)=0 then ERROR(`Pole t\344i sm\365\365tmeline v\365re`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for row from 1 to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from row to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 " #korrutame vajaduse kor ral veeru -1 l\344bi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " if B [row,k]<0 then B:=mulcol(B,k,-1): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 " for k from row+1 \+ to n do ColumnGCD(B,row,k,row,n): od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " for k from 1 to row-1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " c:=floor(B[row,k]/B[row,row]): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " B:=addcol(B,row,k,-c):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 46 "N\344ide maatriksi elementide kiirest kas vamisest" }}{PARA 0 "" 0 "" {TEXT -1 510 "Eelpool n\344idatud algoritm t\366\366tab pol\374nomiaalses ajas vaid siis, kui maatriksi elementi de absoluutv\344\344rtused on kogu algoritmi k\344igus t\365kestatud. \+ Siin on n\344ide maatriksistest, mille korral alustame \374sna lihtsa te elementidega maatriksiga ja l\365petame sammuti \374sna lihtsate el ementidega maatriksiga, aga algoritmi k\344igus paisuvad elemendid \+ \374sna suureks. Need maatrisid on saadud t\344iesti juhuslikult korda jaid valides mitte spetsiaalselt elemente konstrueerides, seega on ele mentide paisumine \374sna t\365sine probleem. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 377 "A1:=matrix([[-4, -2, 3, -4, 3, 0, 5, -4, 3, -3] , [-4, -1, -4, 2, 1, -2, 2, -5, 0, -5], [2, 1, -1, 4, -2, -5, -3, 2, 2 , -5], [2, 5, 4, -2, -1, 4, 0, 2, 2, 0], [-1, 5, -3, 3, -3, 2, 1, 3, 0 , 0], [4, -2, -3, -5, 3, 2, 5, 0, 4, -4], [3, -1, 3, 2, 0, 2, 3, -1, - 1, 5], [0, 3, -5, -4, -1, -5, -4, 5, -1, 4], [3, 2, 4, 5, -4, 0, -5, 2 , -2, 5], [-1, 4, -5, 4, -5, -2, -5, -2, -1, 1]]);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 389 "A2:=matrix([[5, -5, -2, -1, 4, 1, -5, -4, -1, -4], [5, -5, 0, -5, 2, 2, -1, 0, 1, -2], [3, 1, -5, -5, 2, 0, 2, -2, -3, 5 ], [-1, 5, 4, -1, 5, 5, -5, -4, -1, -5], [-4, -4, 2, 5, 0, -5, -5, 5, \+ -2, 5], [-1, -5, -1, -1, -4, -3, 4, -5, -4, -2], [-3, 4, 0, -1, -3, -4 , 5, -2, 4, -1], [-1, 4, 2, -5, -4, 2, 4, 1, -5, 5], [3, 1, 3, -2, 2, \+ -5, 0, -5, -2, -5], [-2, 2, 4, -1, 2, -2, -4, -2, 2, -3]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 382 "A3:=matrix([[4, 0, -1, 1, -2, 2, 4, 4, 4 , 4], [1, 4, -5, -5, -3, -5, -2, -1, -5, -4], [0, -2, 0, 2, -4, -3, 0, -1, 0, 3], [-2, -4, 5, 0, 3, -5, -3, -5, 1, -1], [-3, -2, 3, 5, -3, 2 , 2, 0, 0, 5], [-2, 2, -3, 5, 3, -3, 0, -2, -4, 1], [-4, -4, 4, -4, 3, -5, 2, -4, 3, 5], [5, -4, -4, -2, 3, -2, -2, 2, 1, -1], [5, 2, -1, -3 , -4, -2, 5, 5, -1, 5], [1, -3, 4, -3, -4, 2, -1, 1, 1, -5]]);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 381 "A4:=matrix([[3, -4, -4, 1, -1, 2, \+ 3, -1, 5, 5], [3, -3, 3, 5, -5, 4, 2, 1, 4, 3], [4, 4, 3, -3, -5, 2, - 4, 1, 0, 0], [-5, -1, -3, -2, 3, 3, -4, 0, 3, -2], [-1, -2, 5, 3, -4, \+ -5, -5, -2, -3, 2], [2, -3, -5, -4, 5, -2, -4, -3, 5, 4], [5, -2, -3, \+ -3, -3, 3, 3, 2, 5, -3], [-5, 2, -5, -2, 3, 0, -1, -1, -4, -5], [2, 1, 4, -2, 4, -3, 2, -3, -3, 2], [0, 0, -1, 3, 3, -5, -5, 5, 3, -3]]);" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 377 "B1:=matrix([[-4, -2, 3, -4, 3, 0, 5, -4, 3, -3], [-4, -1, -4, 2, 1, -2, 2, -5, 0, -5], [2, 1, -1, 4, -2 , -5, -3, 2, 2, -5], [2, 5, 4, -2, -1, 4, 0, 2, 2, 0], [-1, 5, -3, 3, \+ -3, 2, 1, 3, 0, 0], [4, -2, -3, -5, 3, 2, 5, 0, 4, -4], [3, -1, 3, 2, \+ 0, 2, 3, -1, -1, 5], [0, 3, -5, -4, -1, -5, -4, 5, -1, 4], [3, 2, 4, 5 , -4, 0, -5, 2, -2, 5], [-1, 4, -5, 4, -5, -2, -5, -2, -1, 1]]):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 389 "B2:=matrix([[5, -5, -2, -1, 4, 1, \+ -5, -4, -1, -4], [5, -5, 0, -5, 2, 2, -1, 0, 1, -2], [3, 1, -5, -5, 2, 0, 2, -2, -3, 5], [-1, 5, 4, -1, 5, 5, -5, -4, -1, -5], [-4, -4, 2, 5 , 0, -5, -5, 5, -2, 5], [-1, -5, -1, -1, -4, -3, 4, -5, -4, -2], [-3, \+ 4, 0, -1, -3, -4, 5, -2, 4, -1], [-1, 4, 2, -5, -4, 2, 4, 1, -5, 5], [ 3, 1, 3, -2, 2, -5, 0, -5, -2, -5], [-2, 2, 4, -1, 2, -2, -4, -2, 2, - 3]]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 382 "B3:=matrix([[4, 0, -1, 1, -2, 2, 4, 4, 4, 4], [1, 4, -5, -5, -3, -5, -2, -1, -5, -4], [0, -2, 0 , 2, -4, -3, 0, -1, 0, 3], [-2, -4, 5, 0, 3, -5, -3, -5, 1, -1], [-3, \+ -2, 3, 5, -3, 2, 2, 0, 0, 5], [-2, 2, -3, 5, 3, -3, 0, -2, -4, 1], [-4 , -4, 4, -4, 3, -5, 2, -4, 3, 5], [5, -4, -4, -2, 3, -2, -2, 2, 1, -1] , [5, 2, -1, -3, -4, -2, 5, 5, -1, 5], [1, -3, 4, -3, -4, 2, -1, 1, 1, -5]]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 381 "B4:=matrix([[3, -4, -4, 1, -1, 2, 3, -1, 5, 5], [3, -3, 3, 5, -5, 4, 2, 1, 4, 3], [4, 4, 3, - 3, -5, 2, -4, 1, 0, 0], [-5, -1, -3, -2, 3, 3, -4, 0, 3, -2], [-1, -2, 5, 3, -4, -5, -5, -2, -3, 2], [2, -3, -5, -4, 5, -2, -4, -3, 5, 4], [ 5, -2, -3, -3, -3, 3, 3, 2, 5, -3], [-5, 2, -5, -2, 3, 0, -1, -1, -4, \+ -5], [2, 1, 4, -2, 4, -3, 2, -3, -3, 2], [0, 0, -1, 3, 3, -5, -5, 5, 3 , -3]]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'MATRIXG6#7,7,!\"%!\"#\"\"$F*F,\"\"!\"\"&F*F,! \"$7,F*!\"\"F*\"\"#\"\"\"F+F2!\"&F-F47,F2F3F1\"\"%F+F4F/F2F2F47,F2F.F6 F+F1F6F-F2F2F-7,F1F.F/F,F/F2F3F,F-F-7,F6F+F/F4F,F2F.F-F6F*7,F,F1F,F2F- F2F,F1F1F.7,F-F,F4F*F1F4F*F.F1F67,F,F2F6F.F*F-F4F2F+F.7,F1F6F4F6F4F+F4 F+F1F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A2G-%'MATRIXG6#7,7,\"\"&! \"&!\"#!\"\"\"\"%\"\"\"F+!\"%F-F07,F*F+\"\"!F+\"\"#F3F-F2F/F,7,\"\"$F/ F+F+F3F2F3F,!\"$F*7,F-F*F.F-F*F*F+F0F-F+7,F0F0F3F*F2F+F+F*F,F*7,F-F+F- F-F0F6F.F+F0F,7,F6F.F2F-F6F0F*F,F.F-7,F-F.F3F+F0F3F.F/F+F*7,F5F/F5F,F3 F+F2F+F,F+7,F,F3F.F-F3F,F0F,F3F6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #A3G-%'MATRIXG6#7,7,\"\"%\"\"!!\"\"\"\"\"!\"#\"\"#F*F*F*F*7,F-F*!\"&F1 !\"$F1F.F,F1!\"%7,F+F.F+F/F3F2F+F,F+\"\"$7,F.F3\"\"&F+F5F1F2F1F-F,7,F2 F.F5F7F2F/F/F+F+F77,F.F/F2F7F5F2F+F.F3F-7,F3F3F*F3F5F1F/F3F5F77,F7F3F3 F.F5F.F.F/F-F,7,F7F/F,F2F3F.F7F7F,F77,F-F2F*F2F3F/F,F-F-F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A4G-%'MATRIXG6#7,7,\"\"$!\"%F+\"\"\"!\"\" \"\"#F*F-\"\"&F/7,F*!\"$F*F/!\"&\"\"%F.F,F3F*7,F3F3F*F1F2F.F+F,\"\"!F5 7,F2F-F1!\"#F*F*F+F5F*F77,F-F7F/F*F+F2F2F7F1F.7,F.F1F2F+F/F7F+F1F/F37, F/F7F1F1F1F*F*F.F/F17,F2F.F2F7F*F5F-F-F+F27,F.F,F3F7F3F1F.F1F1F.7,F5F5 F-F*F*F2F2F/F*F1" }}}{PARA 0 "" 0 "" {TEXT -1 112 "Need maatriksid on \+ \374sna v\344ikeste komponentidega. Kasutades n\374\374d HNF1 algori tmi, mis v\344ljastab ka vahetulemused" }}{PARA 0 "" 0 "" {TEXT -1 37 "on n\344ha maatriksielementide paisumine" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "illustrative_HNF1:=proc(B::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "local row,k,i,c,n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "if coldim(B)<>rowdim(B) then ERROR(`Pole ruutmaatriks`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "if det(B)=0 then ERROR(`Pole t \344ism\365\365tmeline v\365re`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for row from 1 to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from row to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 " #korrutame vajadus e korral veeru -1 l\344bi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " \+ if B[row,k]<0 then B:=mulcol(B,k,-1): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 " for k \+ from row+1 to n do ColumnGCD(B,row,k,row,n): od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " print(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " \+ for k from 1 to row-1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " \+ c:=floor(B[row,k]/B[row,row]): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " B:=addcol(B,row,k,-c):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " o d: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " print(B):" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "#prin t(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 89 "#illustrative_HNF1(B1);illustrative_HNF1(B2);i llustrative_HNF1(B3);illustrative_HNF1(B4);" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 51 "T\344ism\365\365tmelise v\365re HNF saamine pol\374nom iaalses ajas" }}{PARA 0 "" 0 "" {TEXT -1 117 "Et t\344ism\365\365tmeli se v\365re HNF leidmise algoritm oleks ajas pol\374nomiaalne, on tarvi s kuidagi piirata maatriksi elementide" }}{PARA 0 "" 0 "" {TEXT -1 46 "suurust. Seda v\365imaldab meile j\344rgmine teoreem" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 278 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 64 "Iga t\344ism\365\365tmeline L v\365re sisaldab endas alamv\365rena v\365ret det L " }{XPPEDIT 18 0 "Z^n" ")%\"ZG%\"nG" } {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 44 "T\365estus tuleb v\344lj a LVS Crameri lahenditest." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 279 6 "Idee 4" }}{PARA 0 "" 0 "" {TEXT -1 431 "HNF algor itm t\366\366tab \365ieti ka juhul, kui me lisame baasile veel m\365ne d veerud. Ainult siis saame algoritmi v\344ljundisse nende lisatud vee rgude asemele nullveerud. Lisades n\374\374d veerud (det L,0,...),(0,d et L,..),...,(..,0,det L), oleme, saanud teoreetilise p\365hjenduse, m iks v\365ib igal sammul teha teisendusi mod det L, sest tagumist maatr iksi osa v\365ib kasutada modulaarseks taandamiseks. Peadiagonaalile p eab kirjutama s\374t(detL,B[i,i])." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 48 "Seega on v\365imalik leida HNF pol\374no miaalses ajas." }}}{SECT 1 {PARA 257 "" 0 "" {TEXT 288 23 "T\344iendat ud HNF algoritm" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "mod_Colum nGCD:=proc(B::matrix,col,k,row,modulus,n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "local abix,i,c;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "if B[row,k]=0 then B:=swapcol(B,k,col): fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "while B[row,k]<>0 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " c:=floor(B[row,col]/B[row,k]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " for i from 1 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " \+ B[i,col]:=irem(B[i,col]-c*B[i,k], modulus);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " B:=swapc ol(B,k,col)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "od: " }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 10 "#print(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "mod_HNF1:=proc(B ::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "local row,k,i,c,detB,n ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "#t\344ism\365\365tmelise v\365 re determinant on v\365rdne baasimaatriksi determinandi" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 19 "#absoluutv\344\344rtusega" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 60 "if coldim(B)<>rowdim(B) then ERROR(`Pole ruutmaatri ks`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "detB:=abs(det(B)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "if detB=0 then ERROR(`Pole t\344ism\365\365tmeli ne v\365re`): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "#maatriksi ele mentide normaliseerimine mod detB" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 1 to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " for k from 1 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " B[i,k]: =irem(B[i,k],detB):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for row from 1 to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " \+ for k from row to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 " \+ if B[row,k]<0 then B:=mulcol(B,k,-1): fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 " for k \+ from row+1 to n do mod_ColumnGCD(B,row,k,row,detB,n): od:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 62 " #element peadiagonaalil tuleb asendada gc d(B[row,row],detB)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " B[row,row] :=gcd(B[row,row],detB):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " for k from 1 to row-1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " c:=flo or(B[row,k]/B[row,row]): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " \+ for i from 1 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " B[i ,k]:=irem(B[i,k]-c*B[i,row],detB): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od: " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 10 " print(B)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(B);" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "V \365rdle n\374\374d hariliku HNF algoritmiga" }{MPLTEXT 1 0 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "#mod_HNF1(A1);mod_HNF1(A2);mod_HNF1 (A3);mod_HNF1(A4);" }}}{PARA 4 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 22 "Alam\365\365tmelise v\365re HNF" }}{PARA 0 "" 0 "" {TEXT 299 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 35 "Alam \365\365tmeliseks v\365reks vektoruumis " }{XPPEDIT 18 0 "R^m" ")%\"RG %\"mG" }{TEXT -1 95 " loetakse v\365ret, mille baasis on v\344hem vekt oreid kui m st. kui B on m x n baasimaatriks, siis " }{XPPEDIT 18 0 " n" }{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 "ki" "2%\"iG%\"jG" }{TEXT -1 7 ", 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 "kcol " }}{PARA 0 "" 0 "" {TEXT -1 29 " if B[row,col]=0 then row++" }} {PARA 0 "" 0 "" {TEXT -1 7 " else" }}{PARA 0 "" 0 "" {TEXT -1 26 " \+ for i=1,..col-1 do" }{MPLTEXT 1 0 1 " " }}{PARA 0 "" 0 "" {TEXT -1 38 " c=floor(bi[row]/bcol[row]);" }}{PARA 0 "" 0 "" {TEXT -1 290 " bi:=bi-c*bcol; // Et sellel hetkel on maatrik s kuni veeruni col alumisel kolmnurksel kujul, siis see operatsioon ei \+ //muuda eelmistel ridadel olevat ja selle elemendi bi[row] on HNF \+ teine tingimus t\344idetud." }}{PARA 0 "" 0 "" {TEXT -1 23 " ro w++;col++; " }}{PARA 0 "" 0 "" {TEXT -1 13 " od; " } {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 6 "od; " }{MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 98 "Ka selle algoritmi keerukus v\365 ib tulla seoses vektori komponentide kasvamisega mittepol\374nomiaalne ." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 19 "Praktiline algoritm" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "HNF2:=proc(B::matrix)" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "local row,col,k,i,c,m,n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=rowdim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "r ow:=1:col:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "while row<=m and c ol<=n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from col to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " if B[row,k]<0 then B :=mulcol(B,k,-1): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 " for k from col+1 to n do ColumnG CD(B,col,k,row,m): od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " if B[r ow,col]=0 then row:=row+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " els e " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " for k from 1 to row-1 d o" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " c:=floor(B[row,k]/B[ro w,col]): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " B:=addcol(B,ro w,k,-c):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " od: " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 28 " row:=row+1:col:=col+1: " }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 7 " fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "pr int(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "A:=matrix(3,2,[5,4,3,2,1,0 ]):HNF2(A,3,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7$\" \"\"\"\"!7$F(!\"#7$F(!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIX G6#7%7$\"\"\"\"\"!7$F(\"\"#7$F(\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#-%'MATRIXG6#7%7$\"\"\"\"\"!7$F(\"\"#7$F(\"\"%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Kontrollime v\365re determinandi s\344ilimist " } {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 " A:=matrix(3,2, [5,4,3,2,1,0]);det(transpose(A)&*A);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "A:=matrix([[1, 0],[1,2], [1,4]]):det(transpose(A)&*A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'MATRIXG6#7%7$\"\"&\"\"%7$\"\"$\"\"# 7$\"\"\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#C" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 50 "Alam\365\365tmelise v\365re HNF saamine p ol\374nomiaalses ajas" }}{PARA 0 "" 0 "" {TEXT -1 137 "Idee seisneb al am\365\365tmelise v\365re HNF leidmise taandamises t\344ism\365\365tme lise v\365re HNF leidmisele Olgu maatriksi B astak k, siis leiduvad re ad " }{XPPEDIT 18 0 "r[1]" "&%\"rG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "r[2]" "&%\"rG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "r[k]" "&%\"rG6#%\"kG" }{TEXT -1 207 ", mis on lineaarselt s\365ltumatud. Nee d read saab v\344lja eraldada n\344iteks Gramm-Schmidti ortogonaliseer imisprotsessi abil st. kui Gramm-Schmidti algoritm teisendab rea null iks, siis ei kuulu rea indeks hulka \{" }{XPPEDIT 18 0 "r[1]" "&%\"rG6 #\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "r[2]" "&%\"rG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "r[k]" "&%\"rG6#%\"kG" }{TEXT -1 2 "\}." } {TEXT 286 45 "Oluline on veel see, et kui rida pole hulgas " }{TEXT -1 1 "\{" }{XPPEDIT 18 0 "r[1]" "&%\"rG6#\"\"\"" }{TEXT -1 1 "," } {XPPEDIT 18 0 "r[2]" "&%\"rG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "r[k]" "&%\"rG6#%\"kG" }{TEXT -1 1 "\}" }{TEXT 300 56 ", siis avaldu b ta eelnevate lineaarkombinatsioonina.(*) " }{TEXT -1 28 "N\374\374d \+ defineerime projektori " }{XPPEDIT 18 0 "Pi" "I#PiG6\"" }{TEXT -1 3 " \+ : " }{XPPEDIT 18 0 "R^m" ")%\"RG%\"mG" }{TEXT -1 4 " -> " }{XPPEDIT 18 0 "R^n" ")%\"RG%\"nG" }{TEXT -1 79 " nii, et igale vektorile x seab projektor vastavusse vektori x komponentidest \{" }{XPPEDIT 18 0 "r[1 ]" "&%\"rG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "r[2]" "&%\"rG6#\" \"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "r[k]" "&%\"rG6#%\"kG" }{TEXT -1 21 "\}moodustatud vektori " }{XPPEDIT 18 0 "Pi" "I#PiG6\"" }{TEXT -1 5 "(x)=(" }{XPPEDIT 18 0 "x[r[1]]" "&%\"xG6#&%\"rG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 "x[r[2]]" "&%\"xG6#&%\"rG6#\"\"#" }{TEXT -1 5 ",...," }{XPPEDIT 18 0 "x[r[k]]" "&%\"xG6#&%\"rG6#%\"kG" }{TEXT -1 111 "). Antud projeksioon on \374ks\374hene v\365rel L(B) ja p\366\366 rdkujutis on arvutav on pol\374nomiaalses ajas. N\374\374d rakendades \+ " }{XPPEDIT 18 0 "B[1]" "&%\"BG6#\"\"\"" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "Pi(B)" "-%#PiG6#%\"BG" }{TEXT -1 70 " pol\374nomiaalset HNF t\344is m\365\365tmelise v\365re jaoks, saame HNF-il maatriksi " }{XPPEDIT 18 0 "B[2] " "&%\"BG6#\"\"#" }{TEXT -1 29 ". Rakendades p\366\366rdteisen dust " }{XPPEDIT 18 0 "Pi^(-1)" ")%#PiG,$\"\"\"!\"\"" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "B[2]" "&%\"BG6#\"\"#" }{TEXT -1 19 "), saame maatriksi " }{XPPEDIT 18 0 " B[3]" "&%\"BG6#\"\"$" }{TEXT -1 70 ", mis ilmselt \+ on v\365re L baasimaatriks. V\344ide (*) kindlustab selle, et " } {XPPEDIT 18 0 "B[3]" "&%\"BG6#\"\"$" }{TEXT -1 32 " on definitsiooni 1 m\365ttes HNF. " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 19 "Praktiline a lgoritm" }}{PARA 0 "" 0 "" {TEXT -1 189 "Realiseerime esmalt Gram-Schm idt'i ortogonaliseerimisprotsessi(Maple's on k\374ll olemas vastav k \344sk GramSchmidt, kuid see ei anna meile vajaminevat \374leminekumaa triksit) st. arvutame vektorid " }{XPPEDIT 18 0 "c[i]" "&%\"cG6#%\"iG " }{TEXT -1 23 " j\344rgmise reegli alusel" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "c[1]=b[1]" "/&%\"cG6#\"\"\"&%\"bG6#\"\"\"" }}{PARA 0 " " 0 "" {XPPEDIT 18 0 "c[i] = b[i]-sum(mu[i,j]*c[j],j = 1 .. i-1)" "/&% \"cG6#%\"iG,&&%\"bG6#F&\"\"\"-%$sumG6$*&&%#muG6$F&%\"jGF+&F$6#F3F+/F3; \"\"\",&F&F+\"\"\"!\"\"F;" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 5 "kus " }{XPPEDIT 18 0 "c[i]<>0" "0&%\"cG6#%\"iG\"\"!" }{TEXT -1 21 " parajasti siis, kui " }{XPPEDIT 18 0 "b[i]" "&%\"bG6#%\"iG" }{TEXT -1 146 " ei ole avaldatav eelnevate vektorite lineaarkombinatsioonina. Realiseerime Gramm-Schmidti algoritmi nii, et igal sammul oleks avald atud vektorid " }{XPPEDIT 18 0 "c[i]" "&%\"cG6#%\"iG" }{TEXT -1 76 " e sialgsete baasivektorite kaudu. Siis on lihtne hiljem leida p\366\366r dkujutust " }{XPPEDIT 18 0 "Pi^(-1)" ")%#PiG,$\"\"\"!\"\"" }}{PARA 0 " " 0 "" {MPLTEXT 0 21 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " GS_orto:=proc(B::matrix)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "local i ,j,k,T,C,M,m,n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "#maatriks C sisa ldab l\365puks B ridade ortogonaliseeritud baasi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "#maatriks T sisaldab \374lemineku kordajaid st. C=T&* B" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "#vektor M sisaldab ortogonalis eerimissammu kordajaid " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "#v\344lj undiks on maatriksid C ja T" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=r owdim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "C:=matrix(m,n,[]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "#Maple kipub otsese v\365rduse C:=B korral muutm a m\365lema maatriksi sisu " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "for i from 1 to m do for j from 1 to n do C[i,j]:=B[i,j] od:od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "T:=matrix(m,m,[]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "M:=vector(m,[seq(0,i=1..m)]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "for i from 1 to m do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " for j from 1 to i-1 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " #arvutame ort. kordajad" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " k:='k': " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " M[j ]:=sum(B[i,k]*C[j,k],k=1..n):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " \+ k:='k':" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 68 " #kui ortog onaliseeritud j-reavektor pole null, siis jagame " }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 43 " #kordaja l\344bi vektori normi ruuduga" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 " if M[j]<>0 then M[j]:=M[j]/ sum(C[j,k]^2,k=1..n): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " od : " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " #arvutame rea C[i]" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " for k from 1 to n do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " j:='j':" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " C[i,k]:=C[i,k]-sum(M[j]*C[j,k],j=1..i-1):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " od; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 " #arvutame maatriksi T i-nda rea " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from 1 to i-1 do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " j:='j':" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 43 " T[i,k]:=-sum(M[j]*T[j,k],j=1..i-1):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " T[i,i]:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 " for k from i+1 to m do T[i,k]:=0: od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " #asume j\344rgmise sammu kallale" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "RETURN( [C,T]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{PARA 0 "" 0 "" {TEXT -1 74 " N\374\374d leiame vajaliku teisendusmaatriksi, mis reali seerib p\366\366rdteisenduse " }{XPPEDIT 18 0 "Pi^(-1)" ")%#PiG,$\"\" \"!\"\"" }{TEXT -1 13 " . Kui rida " }{XPPEDIT 18 0 "c[i]=0" "/&%\"cG 6#%\"iG\"\"!" }{TEXT -1 8 ", siis " }{XPPEDIT 18 0 "0=sum(T[i,j]*b[j] ,j=1..i-1)+b[i]" "/\"\"!,&-%$sumG6$*&&%\"TG6$%\"iG%\"jG\"\"\"&%\"bG6#F -F./F-;\"\"\",&F,F.\"\"\"!\"\"F.&F06#F,F." }{TEXT -1 12 " ning seega \+ " }{XPPEDIT 18 0 "b[i]:=-sum(T[i,j]*b[j],j=1..i-1)" ">&%\"bG6#%\"iG,$- %$sumG6$*&&%\"TG6$F&%\"jG\"\"\"&F$6#F/F0/F/;\"\"\",&F&F0\"\"\"!\"\"F8 " }{TEXT -1 74 "(**). Olgu projekteeritavad ridade indeksid vektoris(h ulgas) K, siis kui " }{XPPEDIT 18 0 "c[i]<>0" "0&%\"cG6#%\"iG\"\"!" } {TEXT -1 35 " peab i kuuluma hulka K ning seega " }{XPPEDIT 18 0 "b[i] =1*b[i]" "/&%\"bG6#%\"iG*&\"\"\"\"\"\"&F$6#F&F)" }{TEXT -1 30 "(***). \+ On lihtne t\365estada, et " }{XPPEDIT 18 0 "T[i,k]=0" "/&%\"TG6$%\"iG% \"kG\"\"!" }{TEXT -1 229 ", kui k ei kuulu hulka K, seega v\365ib aval dises (**) summerida vaid \374le hulka K kuuluvate indeksite. N\374 \374d j\344rgnev protseduur eraldabki indeksite hulga K ja kasutades s eoseid (**) ja (***) konstrueerib p\366\366rdteisenduse maatriksi P. \+ " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "inverse_Pi:=proc(C,T,m) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "local P,i,j,K:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "P:=matrix(m,rank(C),0):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "K:=[]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "for i fro m 1 to m do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " if norm(row(C,i) )=0 then " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " for j from 1 to n ops(K) do P[i,j]:=-T[i,K[j]]: od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " #lisame K-sse u ue indeksi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " K:=[op(K),i]: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " P[i,nops(K)]:=1: " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "#tagastame K , Pi p\366\366rdkujutuse P" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "RETUR N([K,P]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{PARA 0 "" 0 " " {TEXT -1 38 " N\374\374d tuleb realiseerida vaid kujutus " } {XPPEDIT 18 0 "Pi" "I#PiG6\"" }{TEXT -1 1 " " }{MPLTEXT 1 0 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "project:=proc(B,K,n)" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "local L,i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "L:=[seq(i,i=1..n)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "RETURN(submatrix(B,K,L)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "e nd:" }}}{PARA 0 "" 0 "" {TEXT -1 23 "Ning algoritm ise kujul" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "mod_HNF2:=proc(B::matrix)" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "local L,P,B1,B2,m,n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=rowdim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=coldim(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "#ortogonal iseerime, et saaksime lihtsalt arvutada p\366\366rdteisenduse" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L:=GS_orto(B);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 27 "L:=inverse_Pi(L[1],L[2],m):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "P:=L[2]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "#muudam e projektsiooniga v\365re t\344ism\365\365tmeliseks" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "B1:=project(B,L[1],n);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "#leiame v\365re HNF-i modulaarse algoritmiga" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "mod_HNF1(B1);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "#tuleme p\366\366rdteisendusega tagasi" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 21 "RETURN(evalm(P&*B1));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 44 "Hermit e'i normaalkuju omadused ja rakendused" }}{PARA 0 "" 0 "" {TEXT 287 7 "Teoreem" }}{PARA 0 "" 0 "" {TEXT -1 27 "Igal v\365rel on vaid \374ks \+ HNF." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "S eega on v\365imalik kahe v\365re v\365rdsust n\344idata nii, et leiame m\365lema v\365re HNF" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "Lihtne on n\344idata vektori kuulumist v\365resse v \365i mitte." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Algoritmi sisend v ektor " }{TEXT 301 1 "x" }{TEXT -1 12 " ja baas B=(" }{TEXT 304 2 "b1 " }{TEXT -1 1 "," }{TEXT 303 2 "b2" }{TEXT -1 3 ",.." }{TEXT 302 2 "bn " }{TEXT -1 15 ")=B[i,j] HNF-s" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "V\344ljund kui x on v\365res, siis x kordinaadid baasil c [1],c[2],..c[n]" }}{PARA 0 "" 0 "" {TEXT -1 22 "vastasel korral ERROR " }}{PARA 0 "" 0 "" {TEXT -1 12 "row=1;col=1;" }}{PARA 0 "" 0 "" {TEXT -1 26 "while row<=m and col<=n do" }}{PARA 0 "" 0 "" {TEXT -1 74 " //Invariant on leitud c[1],c[2],..,c[col-1] ja x peab kuuluma v \365resse L(" }{TEXT 308 4 "bcol" }{TEXT -1 3 ",.." }{TEXT 309 3 ",bn " }{TEXT -1 1 ")" }}{PARA 0 "" 0 "" {TEXT -1 46 " while B[row,col]=0 \+ and x[row]=0 do row++;od;" }}{PARA 0 "" 0 "" {TEXT -1 158 " //et alles j\344\344nud vektor oleks v\365res peavad vastavad komponendid olema \+ nullid \+ " }}{PARA 0 "" 0 "" {TEXT -1 52 " kui B[row,col]=0 \+ siis x pole v\365res return ERROR;" }}{PARA 0 "" 0 "" {TEXT -1 29 " \+ c[col]:=x[row]/B[row,col];" }}{PARA 0 "" 0 "" {TEXT -1 56 " kui c ei ole t\344isarv, siis x pole v\365res return ERROR;" }}{PARA 0 "" 0 " " {TEXT -1 3 " " }{TEXT 305 1 "x" }{TEXT -1 1 "=" }{TEXT 306 1 "x" } {TEXT -1 3 "-c*" }{TEXT 307 4 "bcol" }{TEXT -1 28 "; //lahutame vastav a vektori" }}{PARA 0 "" 0 "" {TEXT -1 15 " col++;row++;" }}{PARA 0 " " 0 "" {TEXT -1 5 " od;" }}{PARA 0 "" 0 "" {TEXT -1 21 "if x<>0 retur n ERROR;" }}{PARA 0 "" 0 "" {TEXT -1 18 "//Seega x on v\365res" }} {PARA 0 "" 0 "" {TEXT -1 29 "return c[1],c[2],c[3],..c[n];" }}}{PARA 0 "" 0 "" {TEXT -1 19 "Praktiline algoritm" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 41 "is_in_lattice:=proc(B::matrix,x0::vector)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "local m,n,col,row,c,x,i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "m:=rowdim(B):n:=coldim(B);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "if vectdim(x0)<>m then RETURN(`Vektor pole v\365res`) ; fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "c:=[]:#olgu c tyhi list" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "x:=vector(m,[seq(x0[i],i=1..m)]): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "row:=1:col:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "while row<=m and col<=n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 " while B[col,row]=0 and x[row]=0 and row<=m do row:= row+1: od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " if B[col,row]=0 the n RETURN(`Vektor pole v\365res`); fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 " if irem(x[row],B[row,col])<>0 then RETURN(`Vektor pole v\365re s`); fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 " c:=[op(c),iquo(x[row ],B[row,col])]:#lisame vektorile uue komponendi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for i from row to m do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " x[i]:=x[i]-c[col]*B[i,col]: " }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " c ol:=col+1:row:=row+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "if dotprod(x,x)>0 then RETURN(`Vekt or pole v\365res`); fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(c );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 5 "N\344ide" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "B:=matrix (3,2,[1,0,0,1,0,1]);x:=vector(3,[1,4,5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG-%'MATRIXG6#7%7$\"\"\"\"\"!7$F+F*F," }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"xG-%'VECTORG6#7%\"\"\"\"\"%\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "is_in_lattice(B,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%2Vektor~pole~v|`zresG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 126 "Baasi \374leskirjutus on mahult h\344sti v\344ike ja sobib seega \+ v\365re s\344ilitamiseks. \325ieti on v\365rel olemas veel v\344iksema mahuga esitus," }}{PARA 0 "" 0 "" {TEXT -1 309 "milleks on k\365ige l \374hematest vektoritest koosnev Mikowski baas. Esiteks pole Mikowski baasi v\365imalik pol\374nomiaalses ajas leida. Teiseks oleks sellise baasi esimene vektor l\374him v\365res. Harilikult tahetakse l\374him at vektorit saladuses hoida, seega nende kahe p\365hjuse p\344rast Mik owski baasi praktikas ei kasutata. " }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 49 "L\374hima vektori probleemi lahendus kasutades HNF-i" }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 28 "L\374hima vektori probleem(SVP)" }} {PARA 0 "" 0 "" {TEXT 427 12 "Definitsioon" }}{PARA 0 "" 0 "" {TEXT -1 91 "V\365re nullist erinevat vektorit, mille pikkus on minimaalne, \+ nimetatakse l\374himaks vektoriks." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 353 "V\365re diskreetsus kindlustab l\374hima nullist erineva vektori olemasolu v\365res. Kasutame n\374\374d v\365 re HNF, et hinnata ja leida l\374him vektor. Kuna vektori pikkus s\365 ltub vektorruumis kasutatavast normist, siis v\365ib iga normi korral \+ saada eri vastuse. Peamiselt kasutatakse l\365pmatusnormi, Eukleidist \+ normi e. 2-normi ning p-normi. p-norm defineeritakse j\344rgnevalt" }} {PARA 0 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "abs(abs(x))[p]" "&-%$ab sG6#-F$6#%\"xG6#%\"pG" }{TEXT -1 1 "=" }{XPPEDIT 18 0 "(sum((x[i])^p,i =1..m))^(1/p)" ")-%$sumG6$)&%\"xG6#%\"iG%\"pG/F*;\"\"\"%\"mG*&\"\"\"\" \"\"F+!\"\"" }{TEXT -1 7 ", kus " }{XPPEDIT 18 0 "p>=1" "1\"\"\"%\"pG " }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 117 "Neist k\365ige n\365 rgem on l\365pmatusnorm ning k\365ige tugevam on 1-norm. K\365ik teise d p-normid j\344\344vad nende kahe normi vahele." }}{PARA 0 "" 0 "" {TEXT -1 359 "Seda illustreerib j\344rgmine joonis \374hikkeradest, k us kollane on l\365pmatusnormi \374hikkera, punane on 2-normi \374hikk era ning sinine on 1-normi \374hikkera. Kui l\365pmatusnorm ja p-normi d s\365ltuvad oluliselt baasi valikust, siis 2-norm on invariantne ort onormeeritud baasi suhtes. Selleks veendumiseks v\365ib m\365elda, mis juhtub kui kordinaattelgi keerata n\344iteks 30 kraadi." }}{PARA 13 " " 1 "" {INLPLOT "6%-%)POLYGONSG6$7&7$\"\"!\"\"\"7$F)F(7$F(!\"\"7$F,F(- %'COLOURG6&%$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$$\"1goz=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&o N')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$$!1D84 Pfc5rF:$!1?#o?\"yMJqF:7$$!1Wy6Ike[gF:$!1Jw!yeGL'zF:7$$!1@UD=%)o!*\\F:$ !1`Mh6Mil')F:7$$!1,1s\"[\"ysPF:$!1/`8S***4E*F:7$$!1yCH\"el'3EF:$!1U>(f p[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%)yb&Q)zNQF:$!1/2<#>x]B*F:7$$\"17w4w0I.]F:$!1Igb5wMe')F:7$$\"1\\#)[ *R]$4hF:$!1a*[=H2o\"zF:7$$\"1/wY'Q+$*4(F:$!1r&)eg?sUqF:7$$\"1f=s$Ry,!z F:$!12$H 2ndo*fQF:7$$\"1mGAp))oa'*F:$!1g]nRQ=0EF:7$$\"1!elf`bp!**F:$!1up91t'4O \"F:7$F6$\"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 207 "\}. V\365re diskreetsusest on seal loomu likult l\365plik arv elemente ning me saame leida v\344hima nullist er ineva pikkusega vektori. Olgu meil baas HNF-s, siis baasivektorite pik kused annavad meile esimese hinnangu " }{XPPEDIT 18 0 "d=min(norm(b[i] ))" "/%\"dG-%$minG6#-%%normG6#&%\"bG6#%\"iG" }{TEXT -1 137 " l\374hima vektori pikkusele. N\374\374d vaatame l\344bi k\365ik vektorid, mis o n keras B(0,d) ja l\374hima vektori baasis v\365tame SVP lahendi kandi daadiks " }{TEXT 428 1 "y" }{TEXT -1 241 ". Kui meil oleks suvaline ba as, siis oleks k\365igi keras B(0,d) olevate vektorite leidmine raske, aga me v\365ime kasutada HNF peamist omadust, et viimased vektorid e i m\365juta eelmise vektorite teatavaid komponente. Alustame esimese b aasivektori " }{TEXT 364 2 "b1" }{TEXT -1 115 " lineaarkombinatsioonid ega. Meil on lootust mingi kombinatsioon k*b1 suruda kerasse B(0,d) v aid siis, kui vektori " }{TEXT 365 2 "b2" }{TEXT -1 115 " pool mittem \365justatavad komponendid on absoluutv\344\344rtuselt v\344iksemad v \365i v\365rdsed d-st. Tuues sisse formalisatsiooni:" }}{PARA 0 "" 0 " " {TEXT -1 2 " " }}{PARA 0 "" 0 "" {TEXT -1 5 "Def. " }}{PARA 0 "" 0 "" {TEXT -1 18 "HNF-l oleva baasi " }{TEXT 368 2 "b1" }{TEXT -1 1 "," }{TEXT 367 2 "b2" }{TEXT -1 4 ",..." }{TEXT 366 2 "bn" }{TEXT -1 9 " v ektori " }{TEXT 369 2 "bi" }{TEXT -1 53 " s\365ltumatuteks komponentid eks nimetatakse komponente " }{XPPEDIT 18 0 "bi[j]" "&%#biG6#%\"jG" } {TEXT -1 30 ", mis ei muutu, kui vektorile " }{TEXT 370 2 "bi" }{TEXT -1 16 " liita vektor c*" }{TEXT 371 2 "bj" }{TEXT -1 23 " (j>i). T \344histame Ind(" }{TEXT 372 2 "bi" }{TEXT -1 30 ") nende indeksite j hulka ja " }{XPPEDIT 18 0 "ind[i]" "&%$indG6#%\"iG" }{TEXT -1 9 "(x)= max(|" }{XPPEDIT 18 0 "x[j]" "&%\"xG6#%\"jG" }{TEXT -1 26 "|, kus j ku ulub hulka Ind(" }{TEXT 390 2 "bi" }{TEXT -1 3 "))." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "ja tehes kolm olulist t \344helepanekut:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 377 6 "Idee 5" }}{PARA 0 "" 0 "" {TEXT -1 32 "Et mingit lineaark ombinatsiooni " }{XPPEDIT 18 0 "c[1]" "&%\"cG6#\"\"\"" }{TEXT -1 1 "* " }{TEXT 373 2 "b1" }{TEXT -1 1 "+" }{XPPEDIT 18 0 "c[2]" "&%\"cG6#\" \"#" }{TEXT -1 1 "*" }{TEXT 374 2 "b2" }{TEXT -1 5 "+...+" }{XPPEDIT 18 0 "c[k-1]" "&%\"cG6#,&%\"kG\"\"\"\"\"\"!\"\"" }{TEXT -1 1 "*" } {TEXT 375 4 "bk-1" }{TEXT -1 45 " oleks v\365imalik suruda kerasse B(0 ,d) peavad " }{TEXT 376 3 "bk-" }{TEXT -1 83 "st s\365ltumatud kompone ndid olema absoluutv\344\344rtuselt v\344iksemad v\365i v\365rdsed kui d ehk " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "ind[k-1]" "&%$indG6#,&%\"kG \"\"\"\"\"\"!\"\"" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "c[1]" "&%\"cG6#\"\" \"" }{TEXT -1 1 "*" }{TEXT 391 2 "b1" }{TEXT -1 1 "+" }{XPPEDIT 18 0 " c[2]" "&%\"cG6#\"\"#" }{TEXT -1 1 "*" }{TEXT 392 2 "b2" }{TEXT -1 5 "+ ...+" }{XPPEDIT 18 0 "c[k-1]" "&%\"cG6#,&%\"kG\"\"\"\"\"\"!\"\"" } {TEXT -1 1 "*" }{TEXT 393 4 "bk-1" }{TEXT -1 5 ")<=d." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 379 6 "Idee 6" }}{PARA 0 "" 0 "" {TEXT -1 17 "Kui baasivektori " }{TEXT 378 2 "b1" }{TEXT -1 97 " \+ \374ks s\365ltumatu komponent on suurem kui d, siis peab selle vektori kordaja lineaarkombinatsioonis " }}{PARA 0 "" 0 "" {TEXT -1 143 "olem a 0 ja selle vektori v\365ib baasist v\344lja visata, sest seda ei l \344he l\374hima vektori otsimisel tarvis. Seda ideed saab rekursiivse lt rakendada." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 380 6 "Idee 7" }}{PARA 0 "" 0 "" {TEXT -1 48 "Kui me oleme leidn ud m\365ne vektori, mille pikkus " }{XPPEDIT 18 0 "d[1]" "&%\"dG6#\"\" \"" }{TEXT -1 64 " on v\344iksem kui d, siis v\365ib vaadelda vaid vek toreid keras B(0, " }{XPPEDIT 18 0 "d[1]" "&%\"dG6#\"\"\"" }{TEXT -1 168 "), sest meil on seal l\374hima vektori kandidaat olemas. See t \344hendab tegelikult selleks ajaks leitud lineaarkombinatsioonide uut \374levaatamist kasutades ideed 5, sest B(0," }{XPPEDIT 18 0 "d[1]" " &%\"dG6#\"\"\"" }{TEXT -1 24 ") sisaldub keras B(0,d)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 425 6 "Idee 8" }}{PARA 0 " " 0 "" {TEXT -1 99 "Me v\365ime vaadelda vektoreid, mille esimene komp onent on positiivne, sest normi s\374mmeetria t\365ttu on " }{TEXT 426 2 "-u" }{TEXT -1 11 " sama pikk." }}{PARA 0 "" 0 "" {TEXT -1 106 " See idee v\344hendab vektorite arvu 2 korda. S\365ltumatute komponenti de t\365ttu on on seda ka lihtne kontrollida." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "Need ideed kokku annavad \+ algoritmi" }}{EXCHG {PARA 0 "" 0 "" {TEXT 381 12 "SVP-l\365pmatus" }} {PARA 0 "" 0 "" {TEXT -1 12 "Sisend baas " }{TEXT 382 11 "b1,b2,...bn " }{TEXT -1 14 ", mis on HNF-l" }}{PARA 0 "" 0 "" {TEXT -1 27 "V\344lj und SVP-l\365pmatus lahend" }}{PARA 0 "" 0 "" {TEXT -1 32 "//idee 6 re kursiivne rakendamine" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "d= min(norm(b[ i]))" "/%\"dG-%$minG6#-%%normG6#&%\"bG6#%\"iG" }}{PARA 0 "" 0 "" {TEXT 385 1 "y" }{TEXT -1 1 "=" }{TEXT 384 2 "bi" }}{PARA 0 "" 0 "" {TEXT -1 41 "J\344tame vaatluse alt v\344lja baasivektorid " } {XPPEDIT 18 0 "b[1]" "&%\"bG6#\"\"\"" }{TEXT -1 1 "," }{XPPEDIT 18 0 " b[2]" "&%\"bG6#\"\"#" }{TEXT -1 4 ",.. " }{XPPEDIT 18 0 "b[i]" "&%\"bG 6#%\"iG" }{TEXT -1 5 " kui " }{XPPEDIT 18 0 "ind(b[1])>=d[1]" "1&%\"dG 6#\"\"\"-%$indG6#&%\"bG6#\"\"\"" }{TEXT -1 6 ", ind(" }{XPPEDIT 18 0 " b[2]" "&%\"bG6#\"\"#" }{TEXT -1 9 "),...ind(" }{XPPEDIT 18 0 "b[i]" "& %\"bG6#%\"iG" }{TEXT -1 124 ") ja v\365tame l\374hima vektori kandidaa diks s baasivektori, mille norm on d. Olgu tulemuseks \374mberj\344rje statud vektorite s\374steem " }{TEXT 383 13 "b1',b2',..bk'" }{TEXT -1 14 " mis on HNF-s " }}{PARA 0 "" 0 "" {TEXT -1 101 "//olgu U k\365igi \+ lineaarkominatsioonide hulk, mis v\365ivad mahtuda kerasse B(0,d) ja k oosnevad vektorite " }{TEXT 386 13 "b1,b2,..bi-1 " }{TEXT -1 34 "t\344 isarvulistest kombinatsioonidest" }}{PARA 0 "" 0 "" {TEXT -1 6 "U:=[]; " }}{PARA 0 "" 0 "" {TEXT -1 13 "for i=1..k do" }}{PARA 0 "" 0 "" {TEXT -1 8 " for " }{TEXT 389 1 "u" }{TEXT -1 16 " on U element do " }}{PARA 0 "" 0 "" {TEXT -1 15 " V:=[];" }}{PARA 0 "" 0 "" {TEXT -1 52 " Vaatleme k\365iki t\344isarvulisi kombinatsioone " }{TEXT 388 1 "u" }{TEXT -1 3 "+c*" }{TEXT 387 2 "bi" }{TEXT -1 15 " , mille korral " }{XPPEDIT 18 0 "ind[i]" "&%$indG6#%\"iG" }{TEXT -1 1 "(" }{TEXT 394 1 "u" }{TEXT -1 3 "+c*" }{TEXT 395 2 "bi" }{TEXT -1 8 " )<=d ja " }{XPPEDIT 18 0 "c<>0" "0%\"cG\"\"!" }}{PARA 0 "" 0 "" {TEXT -1 110 " //et bi on olemas v\344hemalt \374ks s\365ltumatu ko mponent, mille v\344\344rtus on v\344hemalt 1, siis neid vektoreid" }} {PARA 0 "" 0 "" {TEXT -1 34 " //saab olla \374limalt 2*d+1" }} {PARA 0 "" 0 "" {TEXT -1 24 " Lisame vektori " }{TEXT 407 1 "u " }{TEXT -1 3 "+c*" }{TEXT 406 2 "bi" }{TEXT -1 9 " hulka V" }}{PARA 0 "" 0 "" {TEXT -1 18 " Kui norm(" }{TEXT 414 1 "u" }{TEXT -1 3 "+c*" }{TEXT 396 2 "bi" }{TEXT -1 13 ")<=d, siis y=" }{TEXT 415 1 "u " }{TEXT -1 3 "+c*" }{TEXT 397 2 "bi" }{TEXT -1 8 " d=norm(" }{TEXT 416 1 "u" }{TEXT -1 3 "+c*" }{TEXT 398 2 "bi" }{TEXT -1 47 ") ning vi skame hulgast U v\344lja k\365ik vektorid " }{TEXT 399 1 "w" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 23 " mille korral " } {XPPEDIT 18 0 "ind[i-1]" "&%$indG6#,&%\"iG\"\"\"\"\"\"!\"\"" }{TEXT -1 1 "(" }{TEXT 400 1 "w" }{TEXT -1 35 ")>d ning hulgast V v\344lja v ektorid " }{TEXT 404 1 "w" }{TEXT -1 17 ", mille korral " }{XPPEDIT 18 0 "ind[i]" "&%$indG6#%\"iG" }{TEXT -1 2 " (" }{TEXT 405 1 "w" } {TEXT -1 3 ")>d" }}{PARA 0 "" 0 "" {TEXT -1 76 " //selle jaoks ei pea eriti t\366\366d tegema kui vektorid on j\344rjestatud " } {XPPEDIT 18 0 "ind[i]" "&%$indG6#%\"iG" }{TEXT -1 17 " j\344rgi kasvav alt " }}{PARA 0 "" 0 "" {TEXT -1 6 " od" }}{PARA 0 "" 0 "" {TEXT -1 56 " //siiamaani v\365ib hulgas V olla |U|*(2*d+1) vektorit " }} {PARA 0 "" 0 "" {TEXT -1 50 " Vaatleme k\365iki t\344isarvulisi kom binatsioone c*" }{TEXT 401 2 "bi" }{TEXT -1 15 ", mille korral " } {XPPEDIT 18 0 "ind[i]" "&%$indG6#%\"iG" }{TEXT -1 1 "(" }{TEXT 402 1 " u" }{TEXT -1 3 "+c*" }{TEXT 403 2 "bi" }{TEXT -1 8 ")<=d ja " } {XPPEDIT 18 0 "c<>0" "0%\"cG\"\"!" }{TEXT -1 5 " " }}{PARA 0 "" 0 "" {TEXT -1 21 " Lisame vektori c*" }{TEXT 408 2 "bi" }{TEXT -1 10 " hulka V " }}{PARA 0 "" 0 "" {TEXT -1 16 " Kui norm(c*" }{TEXT 409 2 "bi" }{TEXT -1 15 ")<=d, siis y=c*" }{TEXT 410 2 "bi" }{TEXT -1 9 " d=norm(c" }{TEXT 417 3 "*bi" }{TEXT -1 47 ") ning viskame hulgast V v\344lja k\365ik vektorid " }{TEXT 412 1 "w" }{TEXT -1 1 "," }} {PARA 0 "" 0 "" {TEXT -1 19 " mille korral " }{XPPEDIT 18 0 "ind[ i]" "&%$indG6#%\"iG" }{TEXT -1 2 " (" }{TEXT 413 1 "w" }{TEXT -1 3 ")> d" }}{PARA 0 "" 0 "" {TEXT -1 45 " //n\374\374d v\365is lisanduda v eel 2*d+1 vektorit" }}{PARA 0 "" 0 "" {TEXT -1 50 " //seega halvima l juhul on hulgas V rohkem kui " }{XPPEDIT 18 0 "(2*d+1)^(i-1)" "),&*& \"\"#\"\"\"%\"dGF&F&\"\"\"F&,&%\"iGF&\"\"\"!\"\"" }{TEXT -1 10 " ja v \344hem " }{XPPEDIT 18 0 "(2*d+2)^(i-1)" "),&*&\"\"#\"\"\"%\"dGF&F&\" \"#F&,&%\"iGF&\"\"\"!\"\"" }{TEXT -1 9 " vektorit" }}{PARA 0 "" 0 "" {TEXT -1 5 "od " }}{PARA 0 "" 0 "" {TEXT -1 56 " //n\374\374d on k \365ikv\365imalikud kombinatsioonid l\344bi vaadatud" }}{PARA 0 "" 0 " " {TEXT -1 33 " //selleks kulub \374limalt rohkem " }{XPPEDIT 18 0 "( 2*d+1)" ",&*&\"\"#\"\"\"%\"dGF%F%\"\"\"F%" }{TEXT -1 1 "+" }{XPPEDIT 18 0 "(2*d+1)^2" "*$,&*&\"\"#\"\"\"%\"dGF&F&\"\"\"F&\"\"#" }{TEXT -1 4 "+..+" }{XPPEDIT 18 0 "(2*d+1)^n" "),&*&\"\"#\"\"\"%\"dGF&F&\"\"\"F& %\"nG" }{TEXT -1 20 " vektori l\344bivaatust" }}{PARA 0 "" 0 "" {TEXT -1 9 " return " }{TEXT 411 1 "y" }{TEXT -1 2 ",d" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 713 "See viitab v\344hemalt N P-t\344ielikule \374lesandele, mis on l\365pmatusnormi korral ka t\365 estatud. Teiste normide korral on tegu NP-raske \374lesandega, sest ku i meil on olemas lahendus, siis selle korrektsuses veendumiseks tuleb \+ meil see algoritm l\344bi teha(v\365ibolla on kuskil veel parem algori tm aga keerukus on garanteeritult eksponentsiaalne), milleks v\365ib k uluda eksponentsiaalne aeg. Muidugi mida t\344psem on d hinnang, seda \+ rohkem lineaarkombinatsioone saab v\344lja j\344tta ning \374ldiselt l aheneb \374lesanne paremini kui v\365iks loota. Kui l\365pmatusnormi a semel on n\344iteks 2-norm, siis tuleb ideed 5 veidi modifitseerida, k ui m\365tte \374di j\344\344b samaks: tuleb kasutada s\365ltumatuid ko mponente lineaarkombinatsiooni normi alt hindamiseks. " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 53 "Praktilised algoritmid l\365pmatusnormi j a 2-normi jaoks" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "S\365ltumatute \+ komponentide hinnang(i protseduuri l\365pust tuleb l\365pmatuse esit \344hest)" }{MPLTEXT 1 0 1 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "in d_i:=proc(x::vector,i::integer,Ind::list)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "local j,d:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "#sis end Ind peab sisaldama maksimaalseid indekseid Ind[i]," }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 70 "#mille korral baasivektor b[i+1] esimesed Ind[ i] komponenti on nullid." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "d:=0;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "for j from 1 to Ind[i] do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " if abs(x[j])>d then d:=abs(x[j]) : fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(d):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "Maksimaalsete indeksite Ind[i ] leidmine" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "ge t_Ind:=proc(B::matrix,m,n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "local i,j,Ind:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "i:=1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "if n=1 then RETURN([m]): fi:" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 39 "while B[i,2]=0 and i<=m do i:=i+1: od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Ind:=[i-1]: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "for j from 3 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " i:=Ind[j-2]+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 " whi le i<=m and B[i,j]=0 do i:=i+1: od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " Ind:=[op(Ind),i-1]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "od : " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Ind:=[op(Ind),m]:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "RETURN(Ind): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "L \365pmatusnormi arvutamine" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "norm_ i:=proc(x::vector)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "local i,m,d: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "m:=vectdim(x):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "d:=0:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "for i from 1 to m do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " if abs(x[i])> d then d:=abs(x[i]): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(d):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Kombinats ioonide " }{TEXT 418 1 "u" }{TEXT -1 2 "+c" }{TEXT 420 3 "*bi" }{TEXT -1 26 " leidmine, mille korral " }{XPPEDIT 18 0 "ind[i]" "&%$indG6#% \"iG" }{TEXT -1 1 "(" }{TEXT 419 1 "u" }{TEXT -1 2 "+c" }{TEXT 421 3 " *bi" }{TEXT -1 4 ")<=d" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "Sisendis on index1 esimese komponendi indeks, mida " }{TEXT 422 2 "bi" }{TEXT -1 47 " m\365jutab ning index2 viimase komponendi indeks. " }}{PARA 0 "" 0 "" {TEXT -1 97 "V\344ljundiks on c alumine ja \374lem ine t\365ke, kui tingimused on vastuolulised siis on v\344ljund [1,-1] " }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "find_c:=pr oc(u::vector,b::vector,index1,index2,d)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "local c1,c2,i,d1,d2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "#c1 on v\365imaliku kordaja alumine hinnang" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "#c2 on v\365imaliku kordaja \374lemine hinnang" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "#alumine hinnang on saadav v\365rra ndist u[i]+c*b[i]>=-d" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "#\374lemin e hinnang on saadav v\365rrandist u[i]+c*b[i]<=-d" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 29 "#esimese komponendi piirangud" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "#kuna baas B on HNF-s, siis on komponent positiivne" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "c1:=ceil((-d-u[index1])/b[index1] ):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "c2:=floor((d-u[index1])/b[ind ex1]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "for i from index1+1 to in dex2 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " if b[i]=0 and abs(u[ i])>d then RETURN([1,-1]): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " \+ if b[i]>0 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " d1:=cei l((-d-u[i])/b[i]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " d2:=fl oor((d-u[i])/b[i]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " elif b[i ]<0 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " d1:=ceil((d-u[i] )/b[i]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " d2:=floor((-d-u[ i])/b[i]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " fi: " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 61 " if d1>c1 then c1:=d1: fi: #kitsendame c \+ piirkonda alt " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " if d2 " 0 "" {MPLTEXT 1 0 37 " if c1>c2 then RETURN([1,-1]): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "o d: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "RETURN([c1,c2]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Kahe vektori liitmine" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 10 "V\344ljund s*" }{TEXT 423 1 "a" }{TEXT -1 3 "+t*" }{TEXT 424 1 "b" }{TEXT -1 39 ", kus a,b on n komponendilised vektorid" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 42 "addvectors:=proc(s,a:vector,t,b::vector,m)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local i:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "RETURN(vector(m,[seq(s*a[i]+t*b[i],i=1..m)])): " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Indeksi leidmine listis, nii et k\365ik eelnevad vektorid oleks ind[k] j\344rgi v\344iksemad v\365rdsed kui d" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "find_vector_index:=proc(U::lis t,d,k,Ind::list)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local i:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "i:=1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "while i<=nops(U) and ind_i(U[i],k,Ind)<=d do i:=i+1: od:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "RETURN(i)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Vektori p anemine ind[k] j\344rjestatud listi " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "put_vector:=proc(U::list,v::vector,k,Ind::list)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "local i,d,V,j,u;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "d:=norm_i(v):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "#maple eri lisest muutujate k\344sitluse t\365ttu tuleb v lahti" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "#siduda" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "u:= vector(vectdim(v),[seq(v[i],i=1..vectdim(v))]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "i:=find_vector_index(U,d,k,Ind):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 37 "V:=[op(1..i-1,U),u,op(i..nops(U),U)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(V):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "SVP lahendamine l\365p matusnormi suhtes" }}{PARA 0 "" 0 "" {TEXT -1 72 "Sisendid B on v\365r e baasimaatriks, mis on HNF-s(v\365ib sisaldada 0 veerge);" }}{PARA 0 "" 0 "" {TEXT -1 77 "x on l\374hima vektori kandidaat. Kui x on nullve ktor, siis valitakse x baasist." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " SVP_i:=proc(B::matrix,x::vector)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "local U,V,y,d,i,j,n,m,M,u,v,b,k,c,Ind,L,index:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "#M list kujul [1,2,..m] vajalik vaid vektorite eralda miseks " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "#maatriksist" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "#u on listi U vektor, b on baasivektor" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "#k on indeks baasivektorite hulgas " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "#i on indeks U vektorite hulgas 1..index" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=rowdim(B):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "M:=[seq(i,i=1..m)]:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 51 "#j\344tame 0 veerud vaatluse alt v\344lja, sii s n=rank(B)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=rank(B):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "#otsime baasist l\374hima vektori" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "y:=subvector(B,M,1): d:=norm_i(y) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 2 to n do " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 " if norm_i(subvector(B,M,i)) " 0 "" {MPLTEXT 1 0 29 " y:=subvector(B, M,i):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " d:=norm_i(y):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "if norm_i(x) >0 and norm_i(x) " 0 "" {MPLTEXT 1 0 16 " y:=x : " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " d:=norm_i(x):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "#leiame Ind " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Ind:=get_Ind( B,m,n):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "#vaatame kas baasi esios a v\365ib \344ra visata " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "k:=1:" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "while kd do k:=k+1: od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "#kui \+ k=n, siis sobiks vaid viimase baasivektori +-1 kordne," }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 56 "#mida oleme juba l\374hima vektori leidmisel a rvesse v\365tnud" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "if k=n then RET URN(y): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "#n\374\374d j\344tka me sobivate vektorite otsimist" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "# Et ei peaks eraldi proovima variante u+c*b ja c*b" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 61 "#lisame 0 vektori kombimatsioonide \374heagegseks l \344bivaatmiseks" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "U:=[vector(m,0) ]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "while k<=n do" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 19 " print(`k=`,k):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " V:=[]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " \+ #kombinatsioonid u+c*b" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " b: =subvector(A,M,k): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " index:= nops(U):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " print(`index=`,ind ex): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " print(`d=`,d);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " print(`U=`);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " for i from 1 to index do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " u:=U[i]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " print(U[i]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 " \+ #hakkame proovima kombinatsioone, leiame c t\365kked" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 58 " if k=1 then L:=find_c(u,b,1,Ind[1], d): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " else " } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 " L:=find_c(u,b,Ind[k-1]+1, Ind[k],d):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " fi:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " print(`c1=`,L[1],`c2=`,L[2 ]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " for c from L[1] to \+ L[2] do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " #need kombin atsionid vastavad tingimustele" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " \+ v:=addvectors(1,u,c,b,m):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " print(`v=`,v):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " if norm_i(v)0 then " }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 21 " y:=v: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " d:=norm_i(v):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 " #kuna U on kasvavalt j\344rjestatud, s iis tuleb indexit" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " \+ #parandada " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " inde x:=find_vector_index(U,d,k-1,Ind)-1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " #v parandus" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 72 " V:=[op(1..find_vector_index(V,d,k,Ind)-1,V)]: \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " fi:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 25 " #lisame V-sse" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 " print(`Enne V=`,seq(V[j],j=1..nops(V)) ):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " V:=put_vector(V,v ,k,Ind):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " print(`V=`, seq(V[j],j=1..nops(V))): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " \+ od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " od: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " p rint(`V=`,seq(V[i],i=1..nops(V))):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 " #igaks juhuks maple sisemise muutujak\344sitluse t\365ttu" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " U:=[seq(V[i],i=1..nops(V))]: " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "RETURN(y)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "A:=matrix(3,3,[3,0,0,5,7,0,0,0,12]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'MATRIXG6#7%7%\"\"$\"\"!F+7%\"\"&\"\"(F+7%F+F+\"#7" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "u:=vector(3,0);b:=vector(3,[ 3,5,0]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG-%'VECTORG6#7%\"\"!F )F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG-%'VECTORG6#7%\"\"$\"\"& \"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "print(SVP_i(A,u)); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#k=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'index=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#d= G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#U=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%\"\"!F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G!\"\"%$c2=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G -%'VECTORG6#7%!\"$!\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%(Enne~ V=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$VV=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V =G-%'VECTORG6#7%!\"$!\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V=G -%'VECTORG6#7%!\"$!\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-% 'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(Enne~V=G-%' VECTORG6#7%!\"$!\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%$VV=G-%'V ECTORG6#7%!\"$!\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F(F( -F%6#7%!\"$!\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6# 7%\"\"!F(F(-F%6#7%!\"$!\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G- %'VECTORG6#7%\"\"$\"\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%(Enne ~V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%$VV=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F(-F%6#7%\" \"$\"\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"! F(F(-F%6#7%!\"$!\"&F(-F%6#7%\"\"$\"\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F(-F%6#7%\"\"$\"\"&F( " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#k=G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'index=G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#d=G \"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#U=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%\"\"!F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G\"\"!%$c2=GF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'V ECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%(Enne~V=G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%$VV=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V=G-%'VECT ORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V=G-%'VECTORG6#7 %\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%!\"$!\"&\" \"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G\"\"!%$c2=G\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'VECTORG6#7%!\"$!\"&\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%(Enne~V=G-%'VECTORG6#7%\"\"!F(F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%$VV=G-%'VECTORG6#7%\"\"!F(F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$!\"&F (" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'VECTORG6#7%!\"$\"\"#\"\"! " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(Enne~V=G-%'VECTORG6#7%\"\"!F(F( " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%$VV=G-%'VECTORG6#7%\"\"!F(F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\" $\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%\"\"$\"\"&\" \"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G!\"\"%$c2=GF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'VECTORG6#7%\"\"$!\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%(Enne~V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$ \"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%$VV=G-%'VECTORG6#7%\"\"!F( F(-F%6#7%!\"$\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\" $" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6# 7%!\"$\"\"#F(-F%6#7%\"\"$!\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V =G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(-F%6#7%\"\"$!\"#F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\" $\"\"#F(-F%6#7%\"\"$!\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#k=G\" \"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'index=G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#d=G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#U= G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%\"\"!F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G\"\"!%$c2=GF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%(Enne~V=G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$VV=G" } }{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V=G-%'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#V=G-%'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%!\"$\"\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G\"\"!%$c2=GF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$ %#v=G-%'VECTORG6#7%!\"$\"\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$% (Enne~V=G-%'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%$ VV=G-%'VECTORG6#7%\"\"!F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(panem e=G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTORG6#7%\"\"!F( F(-F%6#7%!\"$\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%#V=G-%'VECTOR G6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-% 'VECTORG6#7%\"\"$!\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%$c1=G\" \"!%$c2=GF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%#v=G-%'VECTORG6#7%\"\" $!\"#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%(Enne~V=G-%'VECTORG6#7% \"\"!F(F(-F%6#7%!\"$\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%$VV=G- %'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%(paneme=G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTO RG6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(-F%6#7%\"\"$!\"#F(" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\"!F(F(-F%6#7%!\"$\"\"#F(-F%6#7% \"\"$!\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%#V=G-%'VECTORG6#7%\"\" !F(F(-F%6#7%!\"$\"\"#F(-F%6#7%\"\"$!\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%\"\"$!\"#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "norm_i(b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\" &" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "get_Ind(A,3,3);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "c:=addvectors(1,u,-1,b,3);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"\"\"#\"\"$" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"cG-%'VECTORG6#7%!\"$!\"&\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "put_vector([vector(3,[3,5,0])],vector(3,[0, 0,0]),1,[1,2,3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$-%'VECTORG6#7% \"\"!F(F(-F%6#7%\"\"$\"\"&F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "find_vector_index([vector(3,[1,2,3])],5,1,[1,2,3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{PARA 3 "" 0 "" {TEXT -1 0 "" }}}{MARK "6 2 11 51 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }