No title

INFORMATIKA Soustavy line rnch rovnic a potae

;

ANTON N JANA K Pedagogick fakulta UK, Praha

vod

een soustav linernch rovnic pat mezi lohy, s nimi se seznamuj ci ji na zkladnch kolch. Nsledn na stedn a pedevm vysok kole je toto tma zasazeno do irho rmce linern algebry. Postup, kter ci pouvali pro een jednoduch ch soustav: Gaussova, resp. Gauss-Jordanova eliminan metoda, je zobecn n a pouit i pro een dalch typ loh: v poet determinantu, inverzn matice, vlastnch vektor i bze linernho obalu. Vechny tyto typy loh pat historicky mezi klasick partie matematiky. Pokud jde pouze o dosaen sprvnho v sledku, lze soustavu linernch rovnic zadat a nsledn vyeit i za pomoci vhodnho v poetnho software, nejlpe Computer Algebra systm (CAS). Vechny CAS systmy um lohy tohoto typu eit, a to jak numericky, tak i algebraicky (tedy formln , vetn parametr), zpravidla za pomoci pkazu Solve (vce viz nap. 1]). CAS programy maj, vzhledem k pouit pi v uce, i n kolik nev hod. Zaprv robustnost, kter pesahuje poteby k v tiny nejenom zkladnch, ale i stednch kol. Zadruh to, e tyto programy prezentuj v sledn een lohy a v naprost v tin ppad (nap. Maple 13, Mathematica 7) neumouj zobrazit postup een. Tyto programy lze tedy pi v uce pout pouze pro kontrolu v sledku, ale nikoli pro demonstraci postupu een (srovnej 2]). Matematika - fyzika - informatika 20 2010/2011

301

Clem tohoto lnku je pedstavit n kolik potaov ch nstroj, pomoc nich lze pro lohy s pouitm Gauss-Jordanovy eliminan metody nejenom nalzt v sledek een, ale tak zaznamenat a v n kter ch ppadech i dit prb h een. V lnku budou pedstaveny dva on-line dostupn nstroje pro een soustav linernch rovnic a dopln k do programu Excel, kter nabz provd n Gauss-Jordanova eliminan metody krok za krokem.

Nstroje na Webu Ob ukzky nstroj dostupn ch na Internetu pochzej z dlny esk ch autor. Jedn se o nstroj zveejn n na portlu Mathematical Assistant on Web a aplikaci vyuvanou v rmci e-learningov podpory kurzu linern algebry na PedF UK v Praze. V obou ppadech se jedn o nstroje, kter jsou uivatelm nabzeny bezplatn . Ani jeden z pedstavovan ch nstroj nee soustavy linernch rovnic automaticky. Oba nstroje vak poskytuj uivateli, kter je s principem Gaussovy eliminace seznmen, prosted pro pohodln een soustav rovnic bez numerick ch chyb, s monost vst prb h celho een.

Mathematical Assistant on Web (MAW) Projekt MAW { Matematick v poty online (http://user.mendelu.cz/ /~marik/maw/) autor Roberta Maka a Miroslavy Tihlakov pat mezi nejkvalitn j projekty, kter lze na sti Internet nalzt. Portl, za jeho webov m rozhranm se ukr v v konn CAS Maxima, nabz on-line v poty, vetn postupu een, pro irokou klu loh z diferencilnho a integrlnho potu. V souasn dob jsou na tomto portle nabzeny aplikace Michala Novka pro prci s maticemi, a to vetn nstroje pro een soustav linernch rovnic. Tato aplikace, vytvoen v jazyce PHP a JAVA script, umouje pracovat s maticemi zpsobem obdobn m normlnmu een. eitel manuln zadv jednotliv operace, kter jsou nsledn provd ny na zadan matici. Program umouje vechny ti zkladn kony { vynsoben dku konstantou, prohozen dvou dk i piten k-nsobku jednoho dku k druhmu. Vzhledem ke zvolen technologii je pi v potu nutn nepetrit pipojen k internetu, protoe vechny operace jsou provd ny na serveru. 302

Matematika - fyzika - informatika 20 2010/2011

; ; ; ; Obr. 1 Line rn algebra na MAW

Obr. 2 een soustav line rnch rovnic na MAW

een z kurzu Linern algebra na PedF UK

Jin een bylo zvoleno autorem v rmci internetovho kurzu Linern algebra (http://moodle.pedf.cuni.cz/, heslo pro hosta Algebra). Autorem aplikace je Martin Adamec. Jako programovac jazyk byl zvolen Adobe Matematika - fyzika - informatika 20 2010/2011

303

Flash. Tato aplikace, stejn jako PHP aplikace z pedchoz ukzky, nabz zkladn dkov pravy matice. Na rozdl od pedchoz ukzky vak poskytuje uivatelm n kter v hody: 1. V sledky v pot jsou zobrazovny ve formtu, kter je obvykl v uebnicch linern algebry (maticov zpis). 2. Pi v potu aplikace nabz uivateli koecienty, vhodn pro dal krok v Gaussov eliminaci. 3. Pouit technologie (Adobe Flash) umouje staen aplikace a provd n v pot bez poteby nepetritho pipojen k Internetu.

; ;; ;; Obr. 3 een soustav line rnch rovnic

V razn m vylepenm je pedevm automatick nvrh vhodn ch koecient pro dkov pravy, dky tto funkci je mon soustavy eit poloautomaticky, ale tak porovnvat vlastn nvrhy se zabudovanou funkc, a tak se lpe seznmit s algoritmem Gaussovy eliminace.

MS Excel

Pro een soustav linernch rovnic vak lze pout i tak obyejn nstroj, jako je tabulkov procesor { spreadsheet. Tabulkov procesory obvykle nenabzej monost zobrazit postup een. Existuj ale zpsoby, jak cel postup een soustavy linernch rovnic zskat i za pomoci tabulkov ch procesor. 304


;; ; ;

;; ;; ; Obr. 4 Dopl ky v programu MS Excel

Obr. 5 Pou it n stroje eitel


305

Jako ukzkov prosted pouijeme asi nejrozen j tabulkov procesor { MS Excel, a to v jeho posledn verzi 2007 (vce o vyuit programu MS Excel pro een nron jch matematick ch loh viz 4]). Pro zskn een soustavy linernch rovnic lze pout dopln k eitel (vce viz 5]). Tmto postupem vak nezskme postup een.

Doplnk Matrix and Linear Algebra Functions for Excel

Dky integraci VBA (Visual Basic for Applications) do programu MS Excel lze nyn v tto aplikaci naprogramovat nov funkce. Velice asto se vak setkvme s tm, e poadovan nov funkce jsou ji vytvoen. Mnoh dleit funkce jsou ji v programu MS Excel peddenovan, nebo je lze doinstalovat jako soust voln dostupn ch Add-In komponent. Seznam dostupn ch Add-In komponent lze nalzt napklad na serveru Mathtools.net 6]. V dalm textu budeme krom vestav n ch funkc MS Excelu vyuvat i funkce z komponenty MATRIX 2.3 { Matrix and Linear Algebra Functions for Excel (vce viz 7]) Pomoc funkc z toho voln iitelnho doplku programu MS Excel meme eit cel spektrum loh z linern algebry v relnm i komplexnm oboru. een soustavy pomoc toho doplku je velice jednoduch a intuitivn. V prvnm kroku zadme koecienty soustavy rovnic do jednotliv ch bun k tabulky.

;; ; ;; ; Obr. 6 Doplnk Matrix 2.3

306


Nsledn z nabdky Doplky vybereme ze submenu Macros doplku MATRIX 2.3 nabdku Gauss step-by-step. V tomto doplku nejprve nastavme zkladn parametry pro een soustavy a nsledn spustme makro klepnutm na tlatko Run. Makro pro-

;; ; ;

Obr. 7 Nastaven parametr makra Gauss step-by-step

Obr. 8 een soustavy


307

vede kompletn Gaussovu eliminaci krok za krokem, piem v kadm kroku na konec dku uvd, kter dky matice byly pouity a jak m zpsobem. Nap. v uvedenm ppad v prvnm kroku pit makro ;1=2 { nsobek prvnho dku k druhmu dku a v druhm kroku je od prvnho dku odeten dvojnsobek druhho dku. Informace o determinantech jsou v tomto ppad pon kud matouc a nesouvis s eenm soustavy linernch rovnic. Determinanty poskytuj dleitou informaci v ppad , kdy pouvme makro na v poet determinantu tvercov matice. dek s determinanty ns informuje, jak souvis determinant nov zskan matice s determinantem matice pvodn, tedy zda proveden prava m i nem vliv na determinant matice.

Zvr

Softwarov nstroje, pedstaven v lnku, nm nabzej mnoho monost, jak nalzat een soustavy linernch rovnic. Ponaje numerick m eenm pomoc doplku eitel v programu MS Excel, pes algebraick een v CAS systmech a sten manuln een v on-line nstrojch, a po pln automatizovan een v programu MS Excel pomoc doplku Matrix 2.3. Pedstaven t chto nstroj ve v uce pedstavuje dobr propojen matematiky a v poetn techniky. Gaussova eliminace je zrove i algoritmem, kter me b t pouit ve v uce programovn, kdy si ci mohou naprogramovat vlastn makra a doplky do tabulkovho procesoru, kter ve sv prci pouvaj. Literatura 1] Schneiderov, R.: een soustav line rnch rovnic s vyu itm programu Maple (bakal sk pr ce), 2008, on-line: http://mant.upol.cz/soubory/OdevzdanePrace/B08/b08-42-rs.pdf 2] Kutzler, B.: CAS jako pedagogick prostedky ve vyuov n a uen se matematice. Uitel matematiky. 2004, ro. 12, . 50 a 51. 3] Mak R. { Tihlakov, M.: Systm pro online vpoty v prosted WWW. Sbornk 5. ronku konference o elektronick podpoe vuky SCO 2008, 2008. 4] Trvn ek, S. { Maty , V.: Derivace v Excelu, MFI, 19/2, 2009. 5] Prak, P.{ Prakov, B.: Z kladn pou it eitele v Excelu, MFI, 18/7, 2009. 6] Mathtools. net: Link Exchange for the Technical Computing Community, Dostupn online: http://www.mathtools.net/Excel/Mathematics/ 7] Foxes Team: Tutorial of Numerical Analysis with Matrix.xla { Vol. 1 and 2, PDF, Dostupn online: http://digilander.libero.it/foxes/Documents.htm#MatrixTutorial Autorkou vodn ilustrace je Mgr. Jaroslava ermkov

308


lohy novho typu na IOI PAVEL T PFER Matematicko-fyzik ln fakulta UK, Praha

Gar

(Dokon en)

Ve velk gari je N parkovacch mst, kter jsou oslovna od 1 do N vetn . Gar se otvr kad rno przdn a je b hem dne provozovna v nsledujcm reimu. Kdykoliv do gare pijede auto, hlda zkontroluje, zda je n kter parkovac msto voln. Pokud nen, auto mus pokat u vjezdu do gare, dokud se n jak msto neuvoln. Je-li v gari vce voln ch mst, auto zaparkuje na volnm mst s nejmenm slem. Jestlie do gare pijedou dal auta v dob , kdy n jak auto ek na uvoln n msta, vechna tato auta se ad u vjezdu do fronty v tom poad, v jakm pijela. Kdy se pak uvoln v gari n jak parkovac msto, zaparkuje na n m prvn auto z fronty (tzn. to z ekajcch aut, kter pijelo nejdve). Cena za parkovn (v dolarech) se pot jako souin hmotnosti auta (v kilogramech) a koecientu, jeho hodnota zvis na pouitm parkovacm mst . Cena nezvis na tom, jak dlouho auto zstane v gari. Sprvce gare v, e dnes pijede do gare celkem M aut, a zn tak poad jejich pjezd a odjezd. Pomozte mu spotat, kolik dolar dnes celkov vybere za parkovn. loha Napite program, kter na zklad znalosti cenov ch koecient jednotliv ch parkovacch mst v gari a daj o pijd jcch autech (hmotnosti aut, poad jejich pjezd a odjezd) ur celkovou cenu v dolarech, kterou idii parkujcch aut zaplat. Omezen 1 N 100 poet parkovacch mst 1 M 2 000 poet aut 1 Rs 100 koecient parkovacho msta s v dolarech za kilogram 1 Wk 10 000 hmotnost auta k v kilogramech Matematika - fyzika - informatika 20 2010/2011

309

Vstup V program mus pest ze standardnho vstupu nsledujc daje: Prvn dek obsahuje cel sla N a M odd len mezerou. Dalch N dk udv koecienty parkovacch mst. V poad s-t z t chto dk obsahuje jedno cel slo Rs , koecient parkovacho msta slo s v dolarech za kilogram. Nsledujcch M dk uruje hmotnosti aut. Auta jsou oslovna od 1 do M vetn , a to bez ohledu na poad jejich pjezdu do gare nebo odjezdu. V poad k-t z t chto M dk obsahuje jedno cel slo Wk , hmotnost auta slo k v kilogramech. Poslednch 2M dk popisuje chronologicky, jak probhaj pjezdy a odjezdy jednotliv ch aut. Kladn cel slo i znamen, e auto slo i pijd do gare. Zporn cel slo ;i znamen, e auto slo i odjd z gare. %dn auto nebude odjd t z gare dve, ne pijelo, a slo kadho auta od 1 do M vetn se objev v tto posloupnosti prv dvakrt { jednou pi pjezdu a podruh pi odjezdu. %dn auto neodjede z gare ped zaparkovnm (tzn. dn auto neopust pedasn frontu, v n ek na parkovn). Vstup V program mus zapsat na standardn v stup jeden dek obsahujc jedno cel slo { celkovou stku v dolarech, kterou dnes utr sprvce gare. Hodnocen V testovacch datech, za kter lze zskat hodnocen 40 bod, bude mt kad pijd jc auto k dispozici vdy alespo jedno voln parkovac msto v gari. V t chto ppadech tedy dn auto nebude muset ekat na uvoln n msta. Pklady Vstup V stup 34 2 3 5 200

310

5300


100 300 800 3 2 ;3 1 4 ;4 ;2 ;1

Auto slo 3 zaparkuje na mst 1 a zaplat 300 2 = 600 dolar. Auto slo 2 zaparkuje na mst 2 a zaplat 100 3 = 300 dolar. Auto slo 1 zaparkuje na mst 1 (kter se uvolnilo po odjezdu auta slo 3) a zaplat 200 2 = 400 dolar. Auto slo 4 zaparkuje na mst 3 (posledn zb vajc msto) a zaplat 800 5 = 4 000 dolar. Vstup 24 5 2 100 500 1000 2000 3 1 2 4 ;1 ;3 ;2 ;4

V stup 16200


311

Auto slo 3 zaparkuje na mst 1 a zaplat 1 000 5 = 5 000 dolar. Auto slo 1 zaparkuje na mst 2 a zaplat 100 2 = 200 dolar. Auto slo 2 pijede a mus ekat u vjezdu. Auto slo 4 pijede a mus ekat u vjezdu za autem slo 2. Kdy auto slo 1 opust sv parkovac msto, auto slo 2 na n m zaparkuje a zaplat 500 2 = 1 000 dolar. Kdy auto slo 3 opust sv parkovac msto, auto slo 4 na n m zaparkuje a zaplat 2 000 5 = 10 000 dolar. ???

Jednoduch simulan een nevyaduje pouit dn datov struktury krom dvou jednorozm rn ch pol pevn velikosti. Jedno z nich je indexovno sly aut a pro kad auto je v n m uloena hmotnost tohoto auta (vstupn daj), informace o jeho aktulnm stavu (zda parkuje, ek ve front na zaparkovn, nebo zda momentln nen v gari), na kterm parkovacm mst parkuje (pokud je zrovna zaparkovno) a as jeho pjezdu do gare (pokud ek ve front ). Druh pole je indexovno sly parkovacch mst a obsahuje informaci, jak cenov koecient plat pro pslun parkovac msto (vstupn daj) a zda je toto parkovac msto momentln voln, nebo zda je obsazeno n jak m zaparkovan m autem. Na zatku v potu nateme do uveden ch pol vstupn daje (hmotnosti aut, koecienty parkovacch mst) a nastavme dal poten hodnoty obou pol tak, aby odpovdaly v chozmu stavu, e v gari nen dn auto. Nyn budeme postupn zpracovvat jednotliv udlosti ze vstupu. Pi pjezdu auta projdeme parkovac msta v poad podle jejich sel a hledme prvn voln msto. Pokud ho najdeme, pijd jc auto na n j zaparkujeme a k v sledku piteme cenu za jeho parkovn. V opanm ppad musme nechat auto stt ve front a poznamenme si as pjezdu. Pi odjezdu auta z gare projdeme seznam vech aut a hledme auto ekajc ve front s nejnim asem pjezdu. Kdy takov auto najdeme, zaparkujeme ho na prv uvoln n msto (poznamenme si, e toto auto ji parkuje a kde, piteme k v sledku cenu za jeho parkovn). Jestlie dn auto neek ve front , parkovac msto uvoln n odjd jcm autem zstane przdn (poznamenme si, e toto parkovac msto je voln). Popsan een m asovou sloitost O(M 2 + M N ). Takovto een stailo v sout i k zisku plnho potu bod, je ovem mon vylepit ho a urychlit tak v poet programu. Jestlie pro uloen fronty ekajcch aut pouijeme samostatn pole, v n m budou zaazena sla ekajcch 312


aut v poad podle svho pjezdu do gare, najdeme pi odjezdu auta z gare nejdle ekajc auto v konstantnm ase, bez nutnosti prochzet vdy cel pole aut. V poet programu se tm urychl na as O(M N ). Vyhledvn volnho parkovacho msta s nejmenm slem meme sten urychlit tm, e si budeme v pomocn prom nn stle pamatovat aktuln nejni slo volnho parkovacho msta. Tento daj lze pom rn snadno aktualizovat (viz ukzkov program). Podstatn jho zrychlen doshneme, jestlie si budeme ukldat sla voln ch parkovacch mst do binrn haldy. Pi pjezdu auta do gare potom zskme slo prvnho volnho parkovacho msta v logaritmickm ase. V sledn program vyuvajc frontu ekajcch aut i binrn haldu voln ch parkovacch mst bude mt asovou sloitost pouze O(M log N ). Na zv r si ukeme jeden mon zpsob naprogramovn lohy o gari. Pro ukzku jsme zvolili sten optimalizovan een s asovou sloitost O(M N ), kter m krtk a pehledn k(d. Zaveden samostatnho pole pro uloen fronty ekajcch aut umonilo zjednoduit pole s evidenc stavu jednotliv ch aut { pro kad auto bude nyn stait evidovat si pouze jeho hmotnost a slo parkovacho msta. Celkov pam )ov nroky programu tak oproti pvodnmu neoptimalizovanmu een nevzrostly. Pln optimalizovan een s ukldnm voln ch parkovacch mst do binrn haldy je ji pouze technickou modikac, kterou si mete zkusit naprogramovat sami. program Garaz const MaxN = 100 MaxM = 2000

{maximln poet parkovacch mst} {maximln poet aut}

var N: integer {poet parkovacch mst} M: integer {poet aut} Cena: array 1..MaxN] of integer {cena parkovacho msta} Volno: array 1..MaxN] of boolean {voln parkovac msta} Hmotnost: array 1..MaxM] of integer {hmotnost auta} Parkovani: array 1..MaxM] of integer {kde auto parkuje} Fronta: array 1..MaxM-MaxN] of integer {ekajc auta} Prijezd, Odjezd: integer {ukazatel do Fronty} Prvni: integer {prvn voln msto} Suma: longint {vsledn celkov stka}


313

A: integer i, j: integer

{slo aktulnho auta}

begin {Inicializace datovch struktur:} read(N, M) {poet mst a poet aut} for i:=1 to N do begin read(Cenai]) {cenov koeficienty parkovacch mst} Volnoi] := true {vude v gari je volno} end for j:=1 to M do read(Hmotnostj]) {hmotnosti aut} Prijezd := 0 Odjezd := 1 {fronta ekajcch aut je przdn} Prvni := 1 {vechna msta jsou voln} Suma := 0 {dosud nikdo neplatil} {Simulace pjezdu a odjezdu aut:} for j:=1 to 2*M do begin read(A) {aktuln auto} if A > 0 then {pjezd auta A} begin if Prvni > N then {nen dn voln msto} begin inc(Prijezd) FrontaPrijezd] := A {auto A bude ekat ve front} end else {mme prvn voln msto} begin ParkovaniA] := Prvni {auto A tam zaparkuje} VolnoPrvni] := false Suma := Suma + HmotnostA]*CenaPrvni] {...a zaplat} while (Prvni <= N) and (not VolnoPrvni]) do inc(Prvni) {najdeme dal voln msto} end end else {odjezd auta A - uvoln se jeho msto}

314


if Prijezd >= Odjezd then {njak auto ek ve front} begin ParkovaniFrontaOdjezd]] := Parkovani-A] {auto z fronty zaparkuje} Suma := Suma + HmotnostFrontaOdjezd]]*Cena Parkovani-A]] {...a zaplat} inc(Odjezd) end else {ve front nikdo neek} begin VolnoParkovani-A]] := true {uvolnn msto zstane przdn} if Parkovani-A] < Prvni then Prvni := Parkovani-A] {ppadn opravme prvn voln msto} end end writeln(Suma) end.

ZPR VY Dlny Heurky 2010 { neformln konference uitel fyziky s mezinrodn ast Ji od roku 2002 se na pelomu z a jna sch z nkolik destek uitel na Jir skov gymn ziu v N chod na konferenci Dlny Heurky. V letonm roce se tato tradin akce konala o vkendu 1. { 3. 10. za !asti vce ne devades ti uitel z praxe, poslucha uitelstv fyziky i pracovnk a doktorand fakult vzdl vajcch budouc uitele fyziky. V tomto potu

je i osm !astnk ze zahrani (piem slovensk !astnky nepot me mezi zahranin). Projekt Heurka asi nen teba vtin ten pedstavovat, zmnme pouze odkaz na webov str nky: http://kdf.m".cuni.cz/heureka. Pro ty, kte se s nm nikdy nesetkali, snad jen velmi strun { Heurka vznikla ji tm ped dvaceti lety #zespodu$, kdy se nkolik uitel fyziky rozhodlo, e by chtli uit tak, aby to ky bavilo a nco si z vuky odnesli. V tuto chvli m Heurka pes sto aktivnch len { pev n uitel ze kol, ale i pracovnk fakult vzdl vajcch budouc uitele fyziky a dalch z jemc. %lenov se mohou ka doron !astnit nkolika typ semin { #kolky$ pro nov


315

No title

Recommend Documents