<\body> \; \; \; \; \; \; \; |||>|> \; \; Olen kirjoittanut nämä muistiinpanot alunperin itselleni ja julkaisen ne nyt yksinkertaisesti siltä varalta, että niistä sattuisi olemaan jollekulle muullekin jotain iloa. Kyseessä ei ole oppikirja vaan asioita on jätetty pois, oiottu ja yksinkertaistettu sen mukaan miten olen niitä itse katsonut tarvitsevani ja kuinka hyvin olen muistanut asiat entuudestaan. Tarkoituksena on ollut lähinnä luetteloida erilaisten ongelmien ratkaisutapoja käytännön (tietotekniikka-)insinöörintyötä ajatellen eikä niinkään osoittaa tai johtaa niitä. En myöskään väitä ymmärtäväni kaikkea kirjoittamaani -- mikä on tietysti harmi, sillä matematiikka on kiinnostavaa vaikka ainakin itselläni muut työt ovat aina vieneet ajan ja energian paneutua siihen kunnolla. Tekstiä saa kopioida, muokata ja vaikka myydä vapaasti kunhan minut mainitaan alkuperäisen version toimittajana ja kerrotaan, että alkuperäinen on vapaasti kopioitavaa materiaalia. Uusin versio löytyy osoitteesta: Valituksille finglishistä ja muista muotoseikoista en luultavasti lotkauta korvaanikaan ellei valitusten mukana tule korjaustiedostoa, sillä tämän dokumentin päivittämiseen käytetty aika on aina pois muilta töiltä. Tekstiin on epäilemättä kuitenkin jäänyt myös varsinaisia asiavirheitä -- niistä saa mielellään huomauttaa sähköpostitse. GNU Diff:llä muodostetut korjaustiedostot suoraan .tm-tiedostoon ovat tietysti vieläkin tervetulleempia. -- \; <\table-of-contents|toc> |.>>>>|> Lineaarialgebra> |.>>>>|> Matriisien perusteet |.>>>>|> > Tulo |.>>>>|> > Käänteismatriisi |.>>>>|> > Lineaarialgebran derivointisääntöjä |.>>>>|> > Gaussin eliminaatio |.>>>>|> > Determinantti |.>>>>|> > Kanta |.>>>>|> > Gram-Schmidt-ortonormalisointi |.>>>>|> > Ominaisarvot ja -vektorit (eigenvalues & vectors) |.>>>>|> > Matriisifunktiot |.>>>>|> > Vektorit ja analyyttinen geometria |.>>>>|> > Vektoritulot |.>>>>|> > Suora |.>>>>|> > Taso |.>>>>|> > Tetraedri |.>>>>|> > Projektio |.>>>>|> > Homogeeniset koordinaatit |.>>>>|> > Ideaalipisteet, -suorat ja tasot |.>>>>|> > Duaalisuus ja lauseiden dualisointi |.>>>>|> > Kuvaukset (transformaatiot) |.>>>>|> > Lineaarikuvaus |.>>>>|> > Affiniteetti (affinikuvaus) |.>>>>|> > Matriisien sekalaisia sovelluksia |.>>>>|> > Pienimmän neliösumman sovitus (least squares fit) |.>>>>|> > Markovin ketjut |.>>>>|> > Differentiaalilaskentaa yleisesti> |.>>>>|> Differentiaali |.>>>>|> > Jacobian-matriisi |.>>>>|> > Monen muuttujan ketjusääntö |.>>>>|> > ODEt - ''tavalliset'' differentiaaliyhtälöt> |.>>>>|> Peruskäsitteitä |.>>>>|> > Yksittäisen ODEn tarkka ratkaiseminen |.>>>>|> > Separoituva: integrointi puolittain |.>>>>|> > Tasa-asteinen: muuttujan vaihto |.>>>>|> > Eksakti: osittaisderivointi |.>>>>|> > Eksaktiksi muuttaminen: integroiva tekijä |.>>>>|> > 1. kertaluvun lineearinen ODE: yleinen ratkaisu |.>>>>|> > Yksittäisen yhtälön likiarvoratkaisut |.>>>>|> > Suuntakenttä - erikoisratkaisu graafisesti |.>>>>|> > Picardin iteraatio - approksimoiva algebrallinen erikoisratkaisu |.>>>>|> > 2. asteen ODE |.>>>>|> > 1. asteen lineearinen homogeeninen ODE-ryhmä |.>>>>|> > Vaihekuvaaja |.>>>>|> > Laplace-muunnos |.>>>>|> > Sarjat> |.>>>>|> Suppenemisen testaus |.>>>>|> > Yleisimpiä sarjoja |.>>>>|> > Potenssisarjat |.>>>>|> > Fourier-sarja |.>>>>|> > Monen muuttujan analyysi> |.>>>>|> Avaruuspinta |.>>>>|> > Raja-arvo |.>>>>|> > Monen muttujan funktion differentiaalit |.>>>>|> > Osittaisderivaatta |.>>>>|> > Gradientti ja suunnattu derivaatta |.>>>>|> > Napakoordinaatisto |.>>>>|> > Monen muuttujan ääriarvotehtävät |.>>>>|> > Ääriarvopisteiden luokittelu (Hessian) |.>>>>|> > Rajoitetut ääriarvotehtävät (Lagrange-kertoimet) |.>>>>|> > Skalaari- ja vektorikentät> |.>>>>|> Viivaintegraali |.>>>>|> > Greenin lause (suljetun käyrän viivaintegraali) |.>>>>|> > Stokesin lause (moniulotteiset pinnat) |.>>>>|> > ''Vektoriderivaatat'' - grad, div, curl |.>>>>|> > Divergenssilause (aka. Gaussin laki) |.>>>>|> > Kompleksiluvut> |.>>>>|> Kompleksiset funktiot |.>>>>|> > Abstrakti algebra> |.>>>>|> Ryhmät (groups) ja monoidit (monoids) |.>>>>|> > Renkaat (ring) ja kunnat (field) |.>>>>|> > Polynomirenkaat |.>>>>|> > Kooditeoria |.>>>>|> > Kombinatoriikka> |.>>>>|> Permutaatiot ja kombinaatiot |.>>>>|> > Inkluusio-ekskluusio-periaate |.>>>>|> > Binomi- ja multinomikertoimet |.>>>>|> > Generoivat funktiot eli emäfunktiot |.>>>>|> > Tornipolynomit (rook polynomials) |.>>>>|> > Differenssiyhtälöt eli rekursiot |.>>>>|> > Lineaariset ja vakiokertoimiset |.>>>>|> > Ratkaisu emäfunktioilla |.>>>>|> > Permutaatioryhmät ja ekvivalenssiluokat |.>>>>|> > Jaollisuus ja moduloaritmetiikka> |.>>>>|> Jaollisuussääntöjä |.>>>>|> > Suurin yhteinen tekijä (GCD) ja pienin yhteinen jaettava (LCM) |.>>>>|> > Lineaariset Diophanteen yhtälöt |.>>>>|> > Kongruenssi eli moduloaritmetiikka |.>>>>|> > Suuret alkuluvut |.>>>>|> > RSA-salakirjoitus |.>>>>|> > Graafit> |.>>>>|> Lauseita |.>>>>|> > Algoritmeja (ei-negatiivisesti) painotetuille graafeille |.>>>>|> > Kaksijakoinen graafi (bipartite graph) |.>>>>|> > Sekalaisia laskutekniikoita> |.>>>>|> Induktiotodistus |.>>>>|> > Neliöksi täydentäminen |.>>>>|> > Osamurtokehitelmä |.>>>>|> > Tapa 1: :n valitseminen strategisesti |.>>>>|> > Tapa 2: yhtälöryhmä eri asteisista termeistä |.>>>>|> > Tapa 3: Heavisiden peittomenetelmä |.>>>>|> > Logaritmi |.>>>>|> > Raja-arvo |.>>>>|> > Trigonometristen funktioiden ominaisuuksia |.>>>>|> > Merkintätapoja> |.>>>>|> Tavalliset lukujärjestelmät |.>>>>|> > Kreikkalaiset kirjaimet |.>>>>|> > |.>>>>|> Tässä kappaleessa käsitellään lähinnä reaalisia avaruuksia > mutta suurin osa kohdista pätee myös myös kompleksisille avaruuksille tai vaikka alkiot olisivat funktioita (). Oleellista on vain, että alkiot toteuttavat , joiden mukaan mm. täytyy löytyä nolla-alkio ja ykkösalkio, jokaiselle alkiolle täytyy olla vasta-alkio, alkion kertominen skalaarilla täytyy kommutoida yms. <\itemize-dot> > on :n peilaus n (lävistäjän) suhteen vs. : on olemassa käänteismatriisi vs. ei ole olemassa. Älä sekoita säännöllistä ja (ts. >). : =M> (pystyvektorit ovat kohtisuorassa eli ortogonaaliset) : toisiaan vastaan kohtisuorassa (ortogonaalimatriisi) normit (pituus) ovat 1 tai () eli : yhtälöryhmän ratkaisun ei-vapaiden muuttujien määrä eli Gaussin eliminaation tuloksen |||>>||||>>>>>> yksikköneliömatriisin koko. on funktio, jolle a) ja b) f(x)=f(\x)> ja koska molemmat pitävät paikkansa matriisikertolaskussa: kun \>. lineaarikuvauksen () on :n ratkaisujoukko. avaruuden : vapaiden muuttujien määrä, esim. >:lle 2 ja >:lle> 3. tai -yhdistely on vektoreiden painotettu summa. Älä sekoita lineaarikombinaatiota lineaari kanssa! : kappaletta avaruuden > lineaarisesti riippumatonta vektoria (mitkä tahansa). Sanonta: " suhteen>". : avaruuden > vektorit \n>> (eli tavallinen koordinaatisto). on mikä tahansa eräät ehdot täyttävä skalaari-''mittari'' matriisille. Tässä kolme tärkeintä (vastaavista vektorinormeista johdettua) matriisinormia: A\<\|\|\>=*A))>> A\<\|\|\>=maxn>(\|a\|)=max(absolute column sum)> A\<\|\|\>>=maxn>(\|a\|)=max(absolute row sum)>> Matriisien tulo tapahtuu "" ja B=C>:ssä, :n korkeus on :n korkeus ja leveys :n leveys. Jos :n leveys >:n korkeus, tulo on määrittelemätön. Esim:\ <\eqnarray*> |>||>||>>>>|\\2>*>|>>>>|2\\>>||g+b\h>>|g+d\h>>|g+g\h>>>>>|3\1>>>|||>|||>>>>|\\3>*>|>|>>>>|3\\>>||g+b\h+c\i>>|g+e\h+f\i>>>>>|2\1>>>>> Toisin sanoen: matriisi>vektori -operaatio on siis -kokoisen vektorin kuvaus -kokoiseksi vektoriksi. Pystyvektorien pistetulo >\>=\|>\|\|>\|>cos(>,>)=a*b*=>|>|>>>>>>>|>>|>>>>>> Määritelmä: M=I \ MM=I>. Vain neliömatriiseilla voi olla käänteismatriisi ja niilläkin vain sarakkeet/rivit ovat lineaarisesti rippumattomia (sama asia). Sääntöjä: <\eqnarray*> )>||>|M)>||>M>>|B)>||B>>|)>||)>>>> Käänteismatriisin voi laskea lla (ks. alempana)... <\equation*> ||>|||>|||>>>>||>|||>|||>>>>\||>|||>|||>>>>||>|||>|||>>>> ...tai hitaasti determinantin (ks. alempana) avulla (): <\equation*> M=||>|||>|||>>>>\M=|>||>>>>>||>||>>>>>||>||>>>>>>||>||>>>>>||>||>>>>>||>||>>>>>>||>||>>>>>||>||>>>>>||>||>>>>>>>>> 2x2-kokoiselle matriisille Cramerin sääntö tosin on vielä selvästi helpompi: |>||>>>>\M=|>||>>>>>. Perussääntöjä: <\itemize> =d(A)=(d*A)> Matriisilausekkeiden derivaattoja vektorin suhteen: ||>>>>||f(x)/\x>>>>|*x=>a>>||>>>|A>>||>>|*A*x>>||(A+A)>>>|*(A*x+b)>>||*A>>>|*C*(D*x+e) >>||*C*D+(D*x+e)*C*A>>>|*A*x>>||*(A+A)+x*A*x*I>>>>>> Yhtälöryhmä x=b> kirjoitetaan matriisiksi... <\equation*> *x+A*x+A*x=b>>|*x+A*x+A*x=b>>|*x+A*x+A*x=b>>>>> \ >|>|>>|>|>|>>|>|>|>>>>> >>|>>|>>>>> ...ja väännetään sitten yläkolmiomuotoon vähentämällä "nykyinen" rivi alemmista riveistä aina kerrottuna ylänurkan sopivasti kerrotulla tukialkiolla... <\equation*> \>>|>|>>|>|>|>>|>|>|>>>>> >>|>>|>>>>> \>|>|>>||>|>|||>>>> >>|>|>>>>\>|>|>>|||>|||>>>> >>|>|>>>> ...ja soveltamalla sitten alhaalta ylöspäin tai toistamalla eliminointi alhaalta ylös, jolloin saadaan yksikkömatriisi (kuten Gauss-Jordan:ssa). Huom: <\itemize-dot> rivin vaihto ei muuta tulosta sarakkeen vaihto muuttaa muuttujien järjestystä >kirjanpito tarpeen Tulosrivi tarkoita, että ryhmä olisi ratkaisematon vaan se poistetaan ja tulkitaan jäljelle jääneitä rivejä yhtälöryhmänä tulosrivi (esim. ) tarkoittaa ratkaisematonta ryhmää Jos tuloksia on äärettömästi, esitetään ratkaisu vapaan muuttujan (tai useamman) avulla: >|>|>>>>+\>|>|>>>> eli >||>>|>||>|>||>>>>>>>>>>> Determinantti on neliömatriisin vektorien määräämän suoran/suunnikkaan/särmiön pituus/ala/tilavuus (ja vastaava luku moniulotteisemmille avaruuksille). Yksinkertaisin tapaus, 2>-determinantti on helppo laskea: |>||>>>>=|>||>>>>=a\d-b\c>. Yleisiä sääntöjä: <\itemize-dot> rivin/sarakkeen vaihto muuttaa etumerkin determinantin kertominen skalaarilla kertoo yhden rivin tai sarakkeen: *|>||>>>>=a>|b>>||>>>>> ja esim. *|>||>>>>=a>|b>>|c>|d>>>>>=|>|c>|d>>>>>>> jne. rivin/sarakkeen lisääminen toiseen skaalattuna ei muuta tulosta (>Gauss toimii) transponointi ei muuta determinanttia (ts. )>) B)=det(A)*det(B)> 0 \>sarakkeet/rivit ovat lin. riippumattomia>on olemassa käänteismatriisi Ison determinantin voi laskea vääntämällä se Gaussin algoritmilla yläkolmiomuotoon ja laskemalla lävistäjän tulo... <\equation*> ||>|||>|||>>>>=a*b*c \ ...tai hitaammin n avulla minkä tahansa rivin tai sarakkeen suhteen... <\equation*> |>|>||>|>||>|>>>>=-b\\|>||>>>>+e\\|>||>>>>-h\\|>||>>>> ...missä termien etumerkit määräytyvät elementin koordinaateista näin: <\equation*> (-1) \ \ ||>|||>|||>>>> Vektorien ristitulo >\>>=\|>\<\|\|\>>>\|sin(>,>)>=>>|>>|>>|>|>|>>|>|>|>>>>>>, missä >\>,>>. Avaruuden > (koordinaatisto) muodostuu mistä tahansa :stä, lineaarisesti riippumattomasta vektorista. on "tavallinen koordinaatisto" |||>>>>>, |||>>>>>, |||>>>>>, \}>. Kannan vaihto luonnollisesta kantaan (=b\+b\+\), b, \,b}> on... <\eqnarray*> +b+\>||>|>>|>>|>>>>>*+>>|>>|>>>>>*>||>|>|>|>>|>|>|>>|>|>|>>>>>*>>|>>|>>>>>>||>>|>>|>>>>> \ \ eli>>|>||>>|>||x>>>> ...eli tehdään kantamatriisi vektoreista n>> ja ratkaistaan > - tai jos halutaan kannanvaihtomatriisi, lasketaan :n käänteismatriisi. Kanta on , jos sen kaikki vektorit ovat kohtisuorassa toisiaan vastaan ja jokainen vektorin on :n mittainen (kuten luonnollisella kannalla). Minkä tahansa kannan voi pakottaa ortonormaaliksi -algoritmilla. Sitä käytetään erityisesti numeerisessa laskennassa hieman ''epävireeseen'' menneen kannan korjaamiseen. Merkitään alkuperäisiä vektoreita > ja uusia >: <\enumerate-numeric> merkitään ja =w> ja aloitetaan kohdasta 3 vähennetään :nnestä vektorista kaikkien jo ortonormalisoitujen vektorien projektio: =w-(w\v)*v> normalisoidaan :s vektori: =|\|v\|>> Lisätään :tä yhdellä eli siirrytään seuraavaan vektoriin. Jos n>, jatketaan kohdasta 2. Neliömatriisin ominaisarvon määritelmä: *x>, eli koska :lla transformointi ei muuta n \ suuntaa> (paitsi ehkä negatoi), transformaation voi (kaikille >:n suuntaisille vektoreille) tiivistää skalaariksi: ksi >. Koska *x \ (A-\*I)*x=o>, löytää ominaisarvot ratkaisemalla *I)=0> ja -vektorit ratkaisemalla tuloksen perusteella yhtälöryhmä *I)*x=o>. Siis: <\enumerate-numeric> laske *I)> eli >:stä riippuva :n ratkaise polynomin juuret (eli :n ominaisarvot) muodosta (nyt tunnetuista) ominaisarvoista yhtälöryhmät *I)*x=0> ja ratkaise >:t (Huom: matriisi *I)*> on singularinen, joten >:t eivät ole yksiselitteisiä, vaan ne voi skaalata mielivaltaisella vakiolla) Matriisin on , jos sillä on ominaisarvoa. Diagonalisoitu matriisi on koottu ominaisarvoista: =>||>||>|>|||>>>>>>. Vastaavasti sen (-matriisi) on koottu ominais(pysty)vektoreista >|>|>>>>>>. Matriisit ja ovat , jos on olemassa siten, että , joten ja > ovat aina similaariset: \XA*X=\>. Esimerkki ominaisarvojen laskemista, diagonalisoinnista ja similaarisuuden hyödyntämisestä on seuraavassa kappaleessa. Matriisifunktiot on määritelty n>-neliömatriisille seuraavasti: <\eqnarray*> )>||\*\>>>> ...josta >:t voi laskea ominaisarvojen avulla, sillä: <\eqnarray*> )>||\*\ \>>|||>|>>||>|>>||>|>>>>>*>>|>>|>>>>>>||)>>|)>>|)>>>>>>>>> Toisaalta, jos ominaisarvot eivät ole moninkertaisia , voi saman laskea diagonalisoinnin avullakin: <\eqnarray*> )>||)>||>||>|>|||)>>>>>>>|)>||*f(\)*\>>>> Tällä tavalla voidaan laskea esim. )=e>(=\*e>*\)>, )>, mielivaltaisen suuri matriisipotenssi > tai vaikka neliöjuurimatriisi (=\>). Esimerkki: <\eqnarray*> |>||>>>>>|>|=|>||>>>>>>|>|>||>>>>>=0>|>|=3, \=-1 >>|=|>||>>>>>|>|+2*x>||>|=x>>|+(1-3)*x>||>|=-x>>>>>\>>||>||>>>>>|>|=>|>>|>|>>>>>>>|=>|>||>>>>>>|>|>=X*\*X=|>||>>>>>>|>=>|>||>>>>>>|>|>=X*e*X\|>||>>>>>>>> Huom: ja integraali lasketaan kuitenkin ottamalla ne erikseen jokaiselle alkiolle. <\itemize-dot> eli eli b=\|a\|\|b\|>cos(*\*=>|>|>>>>>>>|>>|>>>>>>. <\itemize-dot> Yhdensuuntaisuus: b\a\b=0> Skalaariprojektio: :n pituus :llä on b|\|b\|>>. \; eli b> on määritelty vain 3-vektoreille: (Huom: sanotaan, että >> saadaan :sta lla) <\eqnarray*> b>||> \<\|\|\> >\a,b> ja >\|=1>>>|||>>|>>|>>>|>|>|>>|>|>|>>>>>>>|||>*\b=|>|>>|>||>>|>|>|>>>>\b>>>> <\itemize-dot> Suunnikkaan ala: =\|a\b\|>, = =b\||2>>. : >=a\b\c= a*\b\c>. Särmiön tilavuus: >\|>, tetraedrin tilavuus: >\||6>>>. Huom: alat voi laskea myös determinantilla: >\|=||>|>|>>|>|>|>>|>|>|>>>>>>. <\itemize-dot> : >=>+\*>>, missä >> on suoran suunta : koska jokainen >:sta pisteeseen johtava vektori on kohtisuorassa normaalia vastaan, on >:ssa: >->)\>=0> eli x+ny=>\>> eli , missä ovat >>:n komponentit ja on normaalin ja >>:n pistetulo> (eli >>:n projektio >>:lle, suoran siirto origosta). : >=a*>+b*|\>>, missä Jos 0 \ b\0>, piste on >:n ja >:n välissä. Keskipisteessä . on usemman suoran ryhmä ja kulkee tietyn pisteen läpi. Avaruudessa > suoran voi esittää parametrimuodossa tai kahden tason leikkauksena: >>>>>>\(>->|\>)=0>>|>>>>>>\(>->|\>)=0>>>>>> <\itemize-dot> : >=>+\*>+\*>>, missä tietysti >\ >> : koska jokainen >:sta pisteeseen johtava vektori on kohtisuorassa normaalia vastaan, on (>:ssa!): >->)\>=0> eli x+ny+nz=>\|\>> eli , missä ovat >>:n komponentit ja on normaalin ja >>:n pistetulo>. : vektoreilla >=a*(>->)+b*(>->)> tai >=a*>+b*|\>+c*>>, missä . Annetun pisteen sijainnin -pisteiden muodostamaan kolmioon nähden voi päätellä painokertoimien merkistä - kolmion sisällä se on "". Kolmion essä . <\itemize-dot> Tetraedrissä on 4 tahkoa ja 4 kärkipistettä ("kolmiopohjainen pyramidi"): Kun kärkipisteistä , p, p, p> johdetaan kolme särmävektoria -p), (p-p), (p-p)> saadaan sekä kanta, että auki kertomalla painopistekoordinaattiesitys: >=a*>+b*|\>+c*>+d*>>, missä . Kuten 3D-tason ja 2D-suoran tapauksissakin, painopisteessä on ja annetun pisteen paikan tetraedrin suhteen voi päätellä :n etumerkeistä -- tetraedrin sisällä se on "". <\itemize-dot> n määrittää n normaali ja suuntavektori . Laskukaava: =x-x|n\s>s> tai matriisina =P*x, \ P=I-s>s*n>. on yhdensuuntaisprojektio joss >. Jos suuntavektori on lisäksi kohtisuorassa tasoon nähden, on kyseessä (joss >). projektiivinen taso, projektiivinen avaruus, Pappuksen lause, projektiviteetti, kiintopiste \; Euklidisen tason > pistettä vastaa > piste, eli >|>|>>>>=>>|>>|>>>>>>|/P>>|/P>>>>>>>|*x>>|*y>>>>> {x/\, y/\}>. Grafiikkakirjoissa ylimääräinen ("nollas") elementti kirjoitetaan usein viimeiseksi: [x,y,w]. Sekä affinitransformaatiot (siirto, peilaus, rotaatio, skaalaus, skew) ovat homogeenisissa koordinaateissa palautettavissa (projektiossa aiheuttaa tavallisen pisteen muuttumisen idaalipisteeksi, > ideaalipisteen muuttumisen tavalliseksi ja lopuissa koodautuu :hen) -- siitäkö lienee nimi "projektiivinen taso"? Molemmat voidaan esittää esim. >:n tapauksessa 4>-matriisilla. Pystyvektorilla esitetään pisteitä ja vaakavektorilla (transponoiduilla) suoria: =>|>|>>>>>>. Suoran tavallinen yhtälö on x+\y+\=0>. et >|>>|>>>>>> ovat kuviteltuja "äärettömän kaukana sijaitsevien samansuuntaisten suorien leikkauksia", toimivat laskennassa aivan kuten muutkin pisteet ja sijaitseva lla ||>>>>> (tai > ). Projektiivisen tason pisteet ja suorat ovat eli niitä koskevissa lauseissa sanan "suora" ja "piste" (>:ssa "taso" ja "piste") voi vaihtaa keskenään (eli lause voidaan ): <\itemize-dot> suora kahdesta pisteestä: =p\p> / (leikkaus-)piste kahdesta suorasta: \w>. piste on suoralla / suora on pisteellä: *p =>\>=0> pisteet samalla suoralla: >|>|>>>>>=0> / suorat yhdensuuntaisia: >|>|>>>>>=0> tai tuttavallisesti matriisikertolasku (ilman homogeenisia koordinaatteja), on määritelty kahdella ehdolla: <\itemize-dot> f(x)=f(\x)> Lineaarikuvauksen () on :n ratkaisujoukko. Yleisiä lineaarikuvauksia: <\itemize-dot> Skaalaus: >||>||>|>|||>>>>>> tai symmetrisessä (uniform) tapauksessa ||>|||>|||>>>>>> Kierto (rotaatio): rotaatiomatriisilla >ortogonaalisella matriisilla on aina 1> (>oikeakätinen, >vasenkätinen) ja yksi ominaisarvo =1>. Kyseistä ominaisarvoa vastaava ominaisvektori on rotaatioakseli (koska :n ominaisvektori = vektori, jonka suunta ei muutu :llä kerrottaessa). Toisaalta on: <\itemize-minus> akseli + kulma: )=I+X>*sin(\)+(X>)*(1-cos(\))>, missä >=|>|>>|>||>>|>|>|>>>>>, kun kolme akselia: >|>|>>|>|>|>>|>|>|>>>>>> on kahden tason (>) tai avaruuden (>) välinen kuvaus =A*x+b>. Tasot/avaruudet, jotka saadaan affiniteetilla toisistaan ovat . Suunnikkaan pinta-ala tai tilavuus kertoutuvat affinikuvauksessa :lla. Projektiivisessa avaruudessa/tasossa affiniteetin voi kuvata matriisikertolaskulla: <\equation*> |||>>>>>|>|=|||>|>|>|>|>>|>|>|>|>>|>|>|>|>>>>>x>>|||>||||>>>>>|>|=>|>|>|>>|>|>|>|>>|>|>|>|>>||||>>>>x>>>>> Jos yritetään sovittaa -kertoiminen funktio ,\,a*)> liian moneen havaintoon y> ( kappaletta, n>), saadaan sijoittamalla havainnot polynomiin yhtälöryhmä: n>\q>=1>>, missä =sijoittamalla saadut kertoimet, >|>|>>>>>> ja funktion havaitut arvot. : haetaan :lle neliömatriisi n>=AA>, :lle pienempi vektori y> ja ratkaistaan tavalliseen tapaan. (Markov Chain) on joukko tiloja, joiden välisten siirtymien todennäköisyys ei riipu toteutuneesta siirtymä-historiasta. Yksi kätevä esitystapa on : neliömatriisi, jossa jokaisen rivin summa on 1. Esim: Lyhyt mies saa lyhyen pojan todenäköisyydellä 0.75 ja pitkän todennäköisyydellä 0.25. Pitkä taas saa lyhyen todennäköisyydellä 0.1 ja pitkän varmuudella 0.9. Lyhyitä ja pitkiä on aluksi saman verran: |>>>>>. Stokastinen matriisi |>||>>>>>. Toisen sukupolven jakauma on |>>>>*|>||>>>>*=>|>>>>>, kolmannen sukupolven jakauma on > jne.\ Stokastisella matriisilla on aina ominaisarvo 1 ja stabiili tila äärettömän monen siirtymän jälkeen voidaan laskea diagonalisoimalla. on n (yhden muuttujan funktion tapauksessa tangentin, kahden tapauksessa 3D-tason jne.) kasvun määrä muuttujansa/muuttujiensa muutoksen suhteen. Esim. (x)*\x>. Jos , saadaan kaavasta (x)*\x=1\\x> eli x>. Siksi voidaan kirjoittaa (x)*d x>. Huom: differentiaalin välttämättä tarvitse olla pieni, koska kyse on kasvusta (siis esim. (x)*\x> eikä x)>)! Kahden muuttujan tapauksessa differentiaali on määritelty osittaisderivaattojen avulla seuraavasti: f|\x>*\x+f|\*y>*\y>>> eli f|\x>*d x+f|\*y>*d y> ja samalla tavalla useammille muuttujille. (vs. derivointi) tarkoittaa differentiaalin (siis esim. (x)*d x>) laskemista ja siinä käytetään derivointia (tai osittaisderivointia) ja jos halutaan arvo, eikä kaavaa, :n muutos (x>). Esim. jos x=0.2, \y=-0.1, f(x,y)=x*y>, niin <\eqnarray*> ||f|\x>*d x+f|\x>*d x = (2*y*x)*\x+(x)*\y \>>|||3\1)\0.2+(1)\-0.1*=1.1>>>> on usean muuttujan vektoriarvoisen funktion derivaatta eli käytännössä matriisi, joka sisältää funktion tulosvektorin > jokaisen elementin ( kpl.) derivaatat jokaisen sisääntulevan vektorin > elementin ( kpl.) suhteen: <\eqnarray*> >||(\)*d\>>|>>|>>|>>>>>>||y|\x>>|>|y|\x>>>|>|>|>>|y|\x>>|>|y|\x>>>>>>>>|>>|>>>>>>>>> Jacobian-matriisille mm. pätee ketjusääntö \\)(\)=\(\(\))*D(\(\))>. Huom! älä sekoita Jacobian-matriisia yhtälöryhmien implisiittisessä derivoinnissa käytettävään Jacobian-determinanttiin (F,G)|\(x,y)>=F|\x>>|F|\y>>>|G|\x>>|G|\y>>>>>>=>|>>|>|>>>>>>. Yhden muuttujan ketjusäännön (u(x))*u(x)> yleistettyjä versioita: <\itemize-dot> Jos ja ja riippuvat molemmat muuttujasta (eli ), on:\ <\equation*> =z|\x>*+z|\y>* Jos ja riippuuvat kahdesta muuttujasta (eli ), on: <\equation*> z|\ s>=z|\x>* x|\ s>+z|\y>* y|\s>>>| z|\ t>=z|\x>* x|\ t>+z|\y>* y|\t>>>>>> Tiivistelmä: lineaariselle, 1. asteen ODElle on ratkaisukaava, samoin kuin (vakiokertoimiselle) ryhmälle niitä. Muissa tapauksissa Laplace-muunnos on usein kätevin tapa ellei likiarvoratkaisu riitä. Tässä kappaleessa käytetään vapaana muuttujana välillä :ää ja välillä :ta -- älä hämäänny. Kirjain on yleinen käytäntö, koska differentiaaliyhtälöitä käytetään usein ajasta riippuvien ilmiöiden mallintamiseen. <\itemize> : (yhden muuttujan funktio) (tässä ): ,y,y,\,y)=0>, ts. monenettako derivaattaa funktiosta löytyy : yhtälö on muodossa (x,y)> ( esim. =2*y>) : \ on differentiaali yhden muuttujan suhteen (monen muuttujan funktiossa) vs. / (eng. particular/special solution) : määritelty :n ja derivaattojen arvot yhdessä pistessä : määritelty :n ja derivaattojen arvot kahdessa pisteessä ODE on , jos ja ovat erotettavissa eri puolille yhtälöä kohtelemalla differentaalia :n \ :n osamääränä: <\eqnarray*> = \g(y)dy=f(x)dx>||>>> Kun molemmat puolet on integroitu, ratkaistaan . Toisinaan vakiofunktio > tuotta, esim. tapauksessa: =f(x)g(y)> kun )=0> >. (Huom: separoituva ODE on itse asiassa eksaktin ODE:n erikoistapaus =0=N>) ODE on , jos sen voi saattaa muotoon =f()>, jolloin sen voi ratkaista vaihtamalla >:n ja >:n seuraavasti: <\eqnarray*> \y(x)= x\z(x)>|>|(x) = 1*\z(x)+x\z(x) \ eli>>|>|>|=z+x*z>>>> Vaihdon jälkeen yhtälö on separoituva. Ratkaistaan saadusta yhtälöstä = f(z)>, sijoitetaan takaisin ja ratkaistaan . Huom. triviaaliratkaisu: >, jos )-z=0>. ODE on eksakti, jos se on muotoa eli =0> eli =-> on olemassa funktio , jolle f|\x>=M(x,y) \ f|\y>=N(x,y) >. Jos ja ovat tiedossa, eksaktiuden voi tarkistaa kaavalla =N> eli M|\y>=N|\x>> (kyllä, derivaatat "menevät ristiin" aiemman kanssa) ja ratkaista seuraavasti:\ <\eqnarray*> ||M(x,y)dx|\>|Q(x,y)>+g(y) g(y) korvaa integrointivakion>>|(x,y)>||(x,y)+g(y) \>>|||N(x,y)-Q(x,y)dy muista nyt \ + C>>>> Lopuksi ratkaistaan yhtälöstä . Ideana on siis soveltaa peräkkäin\ <\eqnarray*> *f(x,y)|\*x>>||>|||>|*f(x,y)|\*y>>||>>> Jos ODE:n voi muuttaa eksaktiksi kertomalla funktiolla , on ODE:n . Sellaisen voi löytää systemaattisesti jos se riippuu vain joko :stä tai :stä: <\eqnarray*> *du>||-N|N>*dx>>|||>|*du>||-M|M>*dy>>>> Sekä :stä että :stä riippuvia tekijöitäkin voi olla, mutta niitä ei tällä kaavalla löydä. <\itemize-dot> Homogeeninen (+p(x)\y=0>, ts. ei :stä riippumattomia termejä) separoituu. Yleinen ratkaisu: p(x)dx>> ja vakiokertoimiselle (+a*y=0>): >, missä on mielivaltainen vakio (integrointivakio). Johto: <\eqnarray*> +p(x)\y>||>>|*d*y>||>>|*d*y>||p(x)*d*x \>>|||\>>|||>=e>*e=C*e>>>> Homogeenisen (mutta epähomogeenisen) ODEn erikoisratkaisujen lineaarikombinaatio on myös ratkaisu >yleinen ratkaisu on *y+c*y>. Sanotaan, että ,y)> on kun }> ovat lineaarisesti riippumattomia. selviää, kun lasketaan (esimerkin vuoksi kolmella funktiolla): ||>|>|>|>>|>|>|>>>>>>, joka on 0 joss funktiot ovat lineaarisesti riippuvia. Ei-homogeeniselle (=p(x)\y+q(x)>) on aina integroiva tekijä: p(x)dx>>. Jos eli vakio, on yleinen ratkaisu *eq(x)*d*t+c*e>. Valitaan sopiva ruudukollinen \>, ratkaistaan ODEsta kullekin ruudukon pisteelle =f(x,y)> ja piirretään vastaava nuoli tai viiva. Alkuarvo-ongelman ratkaisun voi hahmotella seuraamalla kenttää alkuarvopisteestä. Tietokoneella voi käyttää tämän (huonon) ns. Eulerin menetelmän sijaan vaikkapa 4. asteen Runge-Kuttaa. (tasa-arvokäyrä) on jokin >:n suhteen vakioarvoinen käyrä suuntakentällä (esim. ns. eli käyrä =0>). lla saadaan tarkentuva approksimaatio alkuarvo-ongelman (x)=f(x,y(x)),y(x)=y> ratkaisulle <\eqnarray*> (x)>||>>|(x)>||+>f(t,\(t))*dt>>>> ...eli joka askeleella integroidaan välillä \x> funktiolle , missä on korvattu :llä ja edellisen iteraation tuloksella. Ratkaisun olemassaolon testaus suljetulla välillä eli : jos =f(x,y)> on jatkuva laatikon x-x\a \ y-y\b> sisällä, iteraatio suppenee yksikäsitteiseen ratkaisuun välillä x-x\min{a,b/M}>. Muotoa ,y,x)=0> oleva ODE ratkeaa muuttujaa vaihtamalla: >. Korkeamman asteen ODEn voi tällä tavalla muuttaa ensimmäisen asteen ODE-ryhmäksi jonka voi sitten ratkaista vaikka Laplace-muunnoksella tai ominaisarvojen avulla. Esim: <\equation*> a*y+b*y+c*y+d*y+e=0 \<\|\|\>y=y(x)\ <\equation*> =y>>|=y>>|=y>>|=-b*y-c*y-d*y-e*>>>>> Toisen asteen homogeenisessa tapauksessa: +b*y+c*y=0 \ >|>>>>=|>||>>>>*>|>>>>>. Ryhmä voidaan esittää matriisimuodossa:\ <\equation*> \=A*\ \ >>|>>>>>=>|>>|>|>>>>>*>>|>>>>> Matriisin > sarakkeet ovat ryhmän erikoisratkaisuja ja kun > on vektorillinen alkuarvoja, =\*e> on alkuarvo-ongelman ratkaisu. Yleinen ratkaisu saadaan myös suoraan ominaisarvoista ja -vektoreista jos ne ovat erillisiä (ei-moninkertaisia) tai on symmetrinen: <\equation*> \(t)=c*\*e*t>+c*\*e>+\+c*\*e> ...missä > ovat mielivaltaisia vakioita, > matriisin ominaisarvoja ja > niitä vastaavia ominaisvektoreita. Kaksinkertaisen ominaisarvon tapauksessa toinen ratkaisu saadaan kaavalla (t)=t*\+\*e*t>>, missä *I)*\=\> ja =\>. ( onko varmasti =\>?) Epähomogeenisessa tapauksessa (t)=A*\(t)+\(t)> ja erikoisratkaisun saa kaavalla =e*e*\(t)*d*t>. (: saako yleisen ratkaisun lisäämällä *e> ja mikä silloin on >?) Yleisen saa (muun muassa) llä: ratkaistaan ensin uuden yhtälöryhmän, =\*\+\> (> on :n diagonalisoitu versio eli ominaisarvomatriisi ja =X*\>, missä on vastaavista ominaispystyvektoreista koottu matriisi), diagonalisoinnin ansiosta nyt toisistaan riippumattomat, yhtälöt yksittäisen yhtälön ratkaisukaavalla (x)=e*x>*e*x>g(x)*d*t+c*ex>> (tai vaikka Laplace-muunnoksella) ja sitten ``epädiagonalisoidaan'' tulos: =X*\>. Kahden muuttujan lineaariselle 1. asteen ODE-ryhmälle voidaan piirtää kaksiulotteinen , jossa on parvi erikoisratkaisukäyriä: (t)>>|(t)>>>>>>. Kohtia, joissa =0, y=0> sanotaan iksi (myös: ). Homogeenisessä tapauksessa piste on aina . Tasapainopisteiden luokittelu riippuu :n ominaisarvoista: <\itemize-dot> Piste on jos molempien reaalinen osa on 0>, muuten . Jos ne reaaliosa on nolla, piste on (piste on napa tai spiraali ja lähistön ratkaisut päätyvät siihen) ja muuten (lähistön ratkaisut pysyvät pisteen lähellä kun \>). Lähiympäristön käytöksestä voidaan sanoa enemmänkin: reaaliset ja samanmerkkiset>napa (stabiili>sisäänpäin tai epästabiili>ulospäin), reaaliset ja erimerkkiset>satulapiste (kaksi käyrää sisään, kaksi ulos, muut ''hipovat''), )=Re(\)=0\>keskus (soikion tai ympyrän) ja =|\>=0\>spiraali (sisään tai ulos). mahdollistaa myös epälineaarisen ODEn tasapainopisteiden luokittelun: yhtälöiden =F(x,y), y=G(x,y)> tasapainopiste luokitellaan matriisin (a,b)>|(a,b)>>|(a,b)>|(a,b)>>>>>> mukaan em. tavalla paitsi, että 1) ympyräpisteet voivat olla myös spiraaleja ja 2) tapaus )=Im(\)=0 \ \=\> voi olla joko spiraali tai napa. Laplace-muunnoksessa differentiaaliyhtälö (tai -ryhmä) muunnetaan ensin esta on (kirjoitetaan: (f(t))=F(s)>), ratkaistaan sitten saadusta yhtälöstä F ja tehdään lopuksi käänteismuunnos (kirj. (F(s))=f(t)>). Usein käänteismuunnosta varten tarvitaan osamurtokehitelmää. Tulos pätee (tässä annetulla määritelmällä) vain alueella 0>! Alla muutamia tärkeimpiä muunnoksia: <\with|par-mode|center> ||>|>>|(f(t))=>ef(t) d*t>>|>:n määritelmä>>|>|>>|>|>|*f>>|>>|*F>>|>|(t)>>|>>|>|>|(t)>>|>>|*F-s*f(0)-f(0)>>|>|f(t)*d t>>|>>|F>>|>|>|>>|>>|>|*t)>>|>>|>F(s/\)>>|:n skaalaus>>|>|>>|G>>|f(t-z)*g(z)*d*z>>>|g>>|>>|>|>|(t)>>|>>||, >>\(t)*d*t=1>>>|1>>|>>|>>| (0>)>>|f(t)>>|>>|>|>|>|>>>|F(s)>>>|!>>|>|>>|>>>|>|*t>>|>>|>>>|0>>>|>>|>>|>>|>|*t)>>|>>||s+\>=>+>>>|>|*t)>>|>>|+w>=**i*>+>>>|>>>> Esimerkki: ratkaistaan yksinkertainen epähomogeeninen ODE: <\eqnarray*> >||>|||>>|||+3>>|||+ >>|||+ =osamurtokeh. Heavisiden menet.>>|y(t)>||*t+*e \ huom: t\0!>>>> \; <\itemize-dot> Luku , jos sillä on raja-arvo äärettömyydessä, muuten . Vaihtoehtoinen määritelmä: suppenee, jos on \>, missä > voidaan valita mielivaltaisen pieneksi, ja aina löytyy sen sisältä. on äärettömän lukujonon summa. Se , jos sen osasumista muodostettu jono suppenee. Tällöin \>a=0>. Eikö luku ei kasva äärettömäksi äärettömällä summauksella vaikka summattava pienenisikin? Vastaus: ei, koska esim. =>: 0.3+ 0.03+ 0.003+\=0.333\> Äärettömät sarjat ovat usein ratkaisuja differentiaaliyhtälöihin, joita ei voi muuten esittää alkeisfunktioilla. Koska sarja voidaan tulkita jonon osasummasarjan raja-arvoksi äärettömyydessä, saadaan raja-arvon laskusäännöistä (kun a=A> ja b=B>): <\itemize-dot> c*a=c*A> (a\b)=A\B> Jos \b> kaikille , niin B> Suppenemista voi testata helpommin kuin laskea summan, ja positiivis-termisen sarjan suppeneminen on helpompi laskea kuin vaihtelevatermisen. Jos \0>: <\description> a> suppenee joss >a(x) dx> suppenee. ( voidaan valita mielivaltaisesti, koska suppeneminen ei koskaan riipu jonon alusta.) =\>|a>>, eli perättäisten termien osamäärä =\>(a)>>, eli alkion äärettömäs juuri äärettömässä Molemmille sarja suppenee, jos 1>, saattaa hajaantua, jos ja hajaantuu varmasti, jos . Luku > on olemassa useammin kuin >, mutta kun molemmat ovat olemassa, on =r>. Jos taas summassa on sekä positiivisia että negatiivisia termejä, \ se suppenee jos \|a\|> suppenee (suppenee ), ja toisinaan muulloinkin (suppenee ). Erityisesti: (-1)*a> (eli joka toinen termi negatiivinen) suppenee, jos \>a=0> ja \a> (). <\description> a+(n-1)*d> (ts. =a+d>). Perättäisten termien erotus on vakio. Hajaantuu aina, mutta osasumma on +a|2>>. a*r>. Perättäisten termien osamäärä on vakio. Suppenee arvoon >, kun 1>. Osasumma )|1-r>>. >>. Suppenee, kun 1> ja hajaantuu muuten. \ Huomaa erityisesti, että eli (++\>), hajaantuu (vaikkakin hitaasti). Summan kaavaa ei ole, mutta >=|6>>. Potenssisarja on muotoa >a*(x-c)>, missä on sarjan . Potenssisarja suppenee aina ja vain suppenemiskeskuksensa ympäristössä säteellä ([0,\[>), missä , L=\>\||a>\|> (kts. ''osamäärätesti'' ylempää). Päätepisteet voivat joko kuulua tai olla kuulumatta :n määräämään in. Yhteenlaskettujen potenssisarjojen suppenemissäde on min{R,R}>. Sama pätee myös keskenään kerrotuille potenssisarjoille ():\ <\equation*> |n=0>|\>a*x*|n=0>|\>b*x=|n=0>|\>c*x c=|i=0>|n>a*b Huom: on potenssisarja, jolle =(c)|n!>>. Erityisen tärkeä (geometrinen/Taylorin/McLaurinin) potenssisarja on: <\equation*> =1+x+x+\x, \|x\|\1 t <\itemize-dot> Määritelmä: -jaksoisen funktion Fourier-sarja (alueella ) on: <\eqnarray*> |||2>+>a*cos **x|L>*+b*sin*x*|L>*>>|>||f(x)**cos(**x|L>)*d*x n=0,1,2,\>>|>||f(x)**sin(**x|L>)*d*x n=1,2,\>>>> ...tai kompleksimuodossa lyhyemmin: <\eqnarray*> ||>>c*en**x/L>>>|>||f(x)*e*n*x/L>d*t>>>> Jos on (eli ), =0> aina ja sarja supistuu ``ksi'': +>a*cos **x|L>*> Jos on (eli ), =0> aina ja sarja supistuu ``ksi'': >b*sin **x|L>*>. (Huom: parittomuuden seuraus: ) Kertoimien skaalaaminen vakiolla vasta :n skaalaamista Kahdella muuttujalla parametrisoitu avaruuspinta: <\equation*> \(u,v)=>|>|>>>> Normaali: <\eqnarray*> (u,v)>||(y,z)|\(u,v)>*\+(z,x)|\(u,v)>*\+(x,y)|\(u,v)>*\>>|(x,y)|\(u,v)>>||x|\u>>|x|\v>>>|y|\u>>|y|\v>>>>>> (=Jacobian)>>>> Pinta-ala lasketaan seuraavasti: <\eqnarray*> ||>>>>dA(u,v) ,>>|||(u,v)\| du dv>>>> <\itemize-dot> Monen muuttujan funktion raja-arvo määritellään -ulotteisen, rajatta pienenevän pallon avulla Yleinen raja-arvo on olemassa vain, jos se on . Esim. funktiolle +y>>, (0,0)>=0> -akselia ja -akselia pitkin lähesteyttäessä, mutta suoraa pitkin lähestyttäessä, sillä , mutta . Raja-arvo voi myös olla olemassa kaikkia suoria pitkinä lähestyttäessä, mutta muita käyriä pitkin. Esim. y|x+y>\(0,0)> f(x,k*x)\0>, mutta )=1>. Funktio on jatkuva tietyssä pisteessä joss raja-arvo on siinä sama kuin funktion arvo. Funktiosta voi siksi määrittelemällä arvo epäjatkuvassa pisteessä sopivasti, joss raja-arvo on olemassa. <\itemize-dot> Osittaisderivaatta on derivaatta jonkin muuttujan suhteen ja sitä merkitään "doo":lla, esim. f(x,y)|\x>>. voivat olla myös ns. sekaderivaattoja, esim. =f=|\x>\f(x,y)|\y>>>=f|\x*\y>> on derivoituna ensin :n ja sitten :n suhteen. itse funktio ja sen alemman kertaluvun osittaisderivaatat ovat jatkuvia tietyssä pisteessä, eri järjestyksessä otetut sekaderivaatat ovat samoja. Epäjatkuvassa tapauksessa näin ei ole. N:n muuttujan funktion on -ulotteinen vektori, joka on koottu funktion osittaisderivaatioista. Gradienttia merkitään nabla- eli del-symbolilla: <\equation*> \f(x,y,z)=f|\x>*\+f|\y>*\+f|\z>*\ <\itemize-dot> Funktio kasvaa aina nopeiten gradienttinsa suuntaan. Derivaatta k.o. suuntaan on f\|>. Gradienttivektori on aina tasokäyrän normaali (vrt. kukkula, jonka huipulta valuu vettä) Funktion derivaatta (kasvunopeus) mielivaltaiseen suuntaan > on f(a,b)=\\\f(x,y)> Liikkuvan tarkkailijan kokema kasvunopeus (nopeus > ei välttämättä yksikkövektori!) on samoin f(a,b)=\\\f(x,y)> Kahden muuttujan funktioiden tasa-arvokäyriä voi toisinaan esittää kätevästi napakoordinaateilla. Muunnokset karteesisten ja napakoordinaattien välillä sujuvat seuraavilla kaavoilla: <\eqnarray*> =x+y>||=tan>>|>||>>>> Ääriarvopisteitä voivat myös monen muuttujan tapauksessa olla derivaatan (gradientin) nollakohdat (f=\>) tai reunapisteet. Yhden muuttujan tapauksessa tyypin voi määritellä toisesta derivaatasta: <\itemize> (x)\0\>maksimi (x)\0\>minimi (x)=0\>ei tietoa (jos vaihtaa merkkiä :n kohdalla>satulapiste) Monen muuttujan tapauksessa luokittelu hoituu kyseisessä pisteessä lasketun -matriisin ominaisarvojen (*I)=0>) avulla: <\equation*> \=>|>|>>|>|>|>>|>|>|>>>>> <\itemize> kaikki \0\>maksimi kaikki \0\>minimi osa > positiivisia, osa negatiivisia > ei tietoa Jos ääriarvotehtävässä vastauksiksi kelpaa vain osa kriittisistä pisteistä, voidaan tehtävä ratkaista muotoilemalla rajoitusfunktio )=0> ja minimoimalla/maksimoimalla alkuperäisen sijaan ... <\equation*> L(\,\)=f(\)+\*g(\) ...missä \\> on nimeltään . Jos rajoituksia on enemmän, myös kertoimia ja rajoitusfunktioita voidaan ottaa mukaan enemmän. Esim: <\equation*> L(x,y,z,\,\)=f(x,y,z)+\*g(x,y,z)+\*h(x,y,z) <\itemize-dot> on )\\> ja on )\\>>. Skalaarikenttä on vektorikentän , joss S=V> kaikissa pisteissä. (On ilmeisesti olemassa myös kaikille kentille määritelty >, jolle =\\\>. Käyttötavasta ei käsitystä.) Vektorikenttä (tai esim. voima) on , jos sillä on potentiaalikenttä (kaikilla vektorikentillä ei ole). Integraalin tapaan potentiaali ei ole yksikäsitteinen, vaan siihen voi lisätä mielivaltaisen vakion. Konservatiiviselle vektorikentälle (x,y[,z])=F(x,y[,z])*\+F(x,y[,z])*\ [+F(x,y[,z])*\]> pätee: <\eqnarray*> |||\*y>F(x,y)=|\*x>F(x,y)>>||||\*y>F(x,y)=|\*x>F(x,y)>>||\*z>F(x,y)=|\*x>F(x,y)>>||\*z>F(x,y)=|\*y>F(x,y)>>>>>>>>> Tai toisaalta: curl(F)=0>. Jos kenttä on konservatiivinen, potentiaalin voi laskea seuraavasti: <\eqnarray*> ||f(t,b,c)*dt+f(x,t,c)*dt+f(x,y,t)*dt>>>> (lopuksi ilmeisesti voi merkitä ja lisätä integrointivakion C) () on vektorikentän vektoreiden ja käyrän (2D) tai pinnan (3D) normaalin pistetulon summa (ts. paljonko vektoreita ``virtaa'' käyrän/pinnan läpi sen suuntaisesti). =\\\*ds> ja =\\\*dA>. on viivan differentiaalisten tangenttivektorien (>) ja kentän tulon summa. Skalaarikentän tapauksessa tulo > ja vektorikentän tapauksessa d\>. Viivaintegraali lasketaan parametrisoimalla >:n -komponentin, derivoimalla ne :n suhteen, ottamalla tulo (piste- tai skalaari) ja integroimalla. Esim: <\eqnarray*> ||>>|||>||>|>|(t)>||*\+4*t*\ \>>|>||+4*\ dt>>|(x,y)>||+3*y*\ \>>|(t)>||*\+3*(4*t)*\\>>|\d*\>||+48*t*dt>>|\\d*\>||10*t+48*t*dt=>>>> Joskus vektorikentän yli viivaintegraalia merkitään F(x,y)*dx+F(x,y)*dy>, mikä tarkoittaa samaa kuin =F*\+F*\ \\\d*\> ja se lasketaan samalla tavalla parametrisoidun >:n ja >:n pistetulona kuin yllä. Tyypillinen esimerkki viivaintegraalista vektorinkentän yli on fysikaalinen , jonka voima > tekee kuljettaessaan pistemäistä kappaletta käyrää pitkin. Tasolla suljetun käyrän viivaintegraalin voi joskus laskea helpommin seuraavasti: <\equation*> F(x,y)*dx+F(x,y)*dy=*F|\*x>-*F|\*y>*dA ...missä on käyrän sisään jäävä alue ja käydään läpi vastapäivään. Oikea puoli on siis pinta-integraali, jossa lasketaan ensin vaakasuuntainen integraali ja sitten pystysuuntainen (tai päinvastoin). Jos on reikäinen, lasketaan reikien seintän mukaan, mutta myötäpäivään. Stokesin lause on Greenin lauseen laajennus moniulotteisille pinnoille: <\equation*> \\*d\=curl \\|^>*dS Kentille voidaan määritellä kolme eri ``derivaattaa'', joista jokainen on eri kerto-operaattorin ja -operaattorin ``formaali tulo'': <\itemize-dot> on vektorikenttä, joka osoittaa skalaarikentän nopeimman kasvun suunnan (kasvunopeus on k.o. vektorin pituus): <\equation*> \f(x,y,z)=(|\x>*\+|\y>*\+|\z>*\)*f(x,y,z)=f|\x>*\+f|\y>*\+f|\z>*\ on skalaarikenttä, joka kertoo kuinka paljon toinen vektorikenttä ``etääntyy pisteestä '' eli tarkemmin sanottuna vuo äärettömän pienen -keskisen pallon (tasossa kiekon) sisältä: <\equation*> div \=\\\=F|\x>*+F|\y>*+F|\z>* Divergenssin voi siis myös tulkita (esim. pistevarausten tapauksessa Diracin delta-funktio tai jatkvassa tapauksessa varaustiheys) voimakkuudeksi yksikkötilavuutta kohti. (karmeasti suomennettuna ) on vektorikenttä, joka kertoo kuinka paljon kenttä ``pyörii pisteen ympäri'' eli tarkemmin sanottuna kiekon reunan muodostavien äärettömän monen tangenttivektorin (>) ja vektorikentän vektorien pistetulo kerrottuna kiekon () yksikkönormaalilla (|^>>): <\eqnarray*> |^>\ curl \>||\ \ d\>>|||=\\\=*>|>|>>||\x>>||\y>>||\z>>>|>|>|>>>>>*>>|||=F|\x>*-F|\y>*\>>>> Näille pätee kaikenlaisia yhtälöitä, mm.: <\itemize-dot> eli \(\\\)=0> > eli \(\S)=\>>> ns. : S=div grad S=\\\S> tai vektorikentälle: \=(\*F)*\*+(\*F)*\*+(\*F)*\* >. Skalaarikenttä on jollain alueella, joss siellä pätee *S=0>. Vuo jonkin alueen D pinnan S läpi on yhtä suuri kuin kaikkien sen pisteiden divergenssien summa (=tilavuusintegraali): <\equation*> div \*dV=\\|^>*dS Erityisesti: jos suljetun pinnan sisällä ei ole yhtään lähdettä (positiivista tai negatiivista, tai ), on vuo sen läpi 0 kentästä riippumatta (mikä tulee sisään, menee myös ulos). Huomaa, että esim. pistevarausten tapauksessa lähteet ovat pistemäisiä Diracin delta-funktioita, joiden integraalilla on arvo vaikka niitä ympäröivä kiekko pienennettäisiin kuinka pieneksi tahansa. Variaatioita (''curl-lause'' ja ''gradienttilause''??), joiden tulos on vektori: <\eqnarray*> curl \*dV>||F\|^>*dS>>|grad S*dV>||S*|^>*dS>>>> <\itemize-dot> Imaginääriyksikkö ja =-1> = >>>, == : (cos \ + i\sin \)=r*e>> (, muistisääntö: )>) +y>> ja =atan +2*n*\> = = >:n se arvo, joka on välillä \Arg z\\> eli on >=x-i*y>. Sille pätee: +z|\>=>+>>, \ \ -z|\>=>->>, \ \ *z|\>=>*>>, \ \ /z|\>=>/>> kertolasku: *z=(x*x-y*y)+i( x*y+x*y)>= *r*[cos (\+\)+i*sin (\+\)]> jakolasku: |z>=+i*y|x+i*y> =*x+y*y|x+y>+i\*y-x*y|x+y>=+i*y)*(x-i*y)|(x+i*y)*(x-i*y)>>= |r>*[cos (\-\)+i*sin (\-\)]>. Huom. erityisesti: =-i> käänteisluku: ==+y>+i*+y>> tai *earg z>> potenssiin korotus (>) (): =r*\e>> (+i*2*k*\), k\\> :s juuri: =*\e+2*k*\|n>> \| k=0,1,\,n-1> Arvoja on siis kappaletta ja ne sijaitsevat tasaisin välein >-säteisellä ympyrällä. kolmioepäyhtälö: z\|-\|z\<\|\|\>\\|z+z\|\\|z\|+\|z\|> <\itemize-dot> Merkitään , missä Jos on differentioituva tietyssä pisteessä >(z)=U(x,y)+i*V(x,y)=U(x,y)+i*V(x,y)>. Lisäksi =V \ U=-V> (-osittaisderivaattayhtälö). Jos =V \ U=-V>>> on jatkuva > on differentioituva. on , jos se on differentioituva :n naapurustossa (>-säteisen kiekon sisällä kaikissa pisteissä). Lisäksi: on differentioituva äärettömässä jos on analyyttinen origossa. Jos on analyyttinen > ja ovat harmonisia (ks. kahden muuttujan funktiot). Ns. , a*d-b*c\0\z=> määräytyy yksiselitteisesti kolmella pisteellä: |w-w>\-w|w-w>=|z-z>\-z|z-z>> (>:n sisältävät osamäärät korvataan :llä!). K.o. kuvaus muuttaa suoria ympyröiksi ja päinvastoin. Suljetun polun viivaintegraalin laskemiseen on kasa erilaisia sääntöjä, joista residuaalimenetelmä vaikuttaa erityisen hyödylliseltä. Kun polku ei leikkaa itseään ja on ja on polun sisällä muuten analyyttinen, mutta :ssa pisteessä on singulaarinen (eng. ), pätee : <\eqnarray*> f(z)d*z>||*i>f(z)>>|>f(z)>||z>f(z-z)*(z-z)>>|||)|q(z)>, jos f=)>>>> Jos polku on negatiivisesti orientoitu, lasketaan residuaalit negatiivisina. Huom: jos singulariteettejä ei ole, on integraali . = algebrallisia rakenteita (eli alkioiden ja niihin kohdistuvien operaatioiden yhdistelmiä) aksiomaattisesti (eli pieneen määrään perusoletuksia nojaavasti) käsittelevä oppi. Joukon ja siihen vaikuttavan jonkin operaation > yhdistelmä, )>, on nimeltään: <\itemize> (semigroup), jos > on assosiatiivinen eli (b\c)=(a\b)\c> , jos lisäksi on olemassa G>, jolle a=a\e=a> <\itemize-arrow> jos > on (additiivinen ryhmä), niin merkitään jos > on > (multiplikatiivinen ryhmä), niin merk. 1. Merkitään myös b>. (group), jos lisäksi kaikille alkioille on käänteisalkio: \a=a\a=e> <\itemize-arrow> jos > on , niin käänteisalkiota nimitetään ksi ja merkitään jos > on >, niin voidaan merkitä myös => ja *b=> , jos se on lisäksi eli b=b\a> kaikille . Huom: myös puoliryhmä ja monoidi voivat olla kommutatiivisia. Jos on äärellinen niin > välttämättä ''pyörähtää ympäri'' (kongruenssin tapaan) koska kaikille G\b)\G>> . Esim. ryhmässä ({0,2,4}, +) on mutta . \; Lisää määritelmiä ja lauseita: <\itemize> alkion , n\\=a\a\a\> yhteensä kertaa. <\itemize-arrow> jos > on , niin potenssia merkitään ryhmän () on sen alkioiden määrä on :n jonkin osajoukon ja ryhmän operaattorin yhdistelmä, jos myös kyseinen osajoukko on ryhmä kyseisellä operaattorilla (joss G> on ko. alijoukko ja H\a*b\H\a\H>). on nimitys aliryhmille )> ja >) )\(H,\)>, on uusi ryhmä (jolla on uusi operaattori >) siten, että: ,h)\(g,h)=(g\g,h\h)> on funktio H> ryhmien ),(H,\)> välillä, jos kaikille G> pätee b)=f(a)\f(b)>. on homomorfismi, joka on lisäksi bijektio (eli kääntäen yksikäsitteinen, ts. on olemassa myös isomorfismi :H\G>). (esim. \> on isomorfismi ,\)\(\,+)>, koska -- ts. logaritmilla voidaan muuttaa >:n kertolasku >:n yhteenlaskuksi (kuten oli tapana ennen laskimia). ryhmiä sanotaan isomorfisiksi, jos niiden välillä olemassa isomorfismi ja ne voidaan tällöin samaistaa (rakenteellisesti). on ryhmä, jonka kaikki alkiot ovat jonkin sen alkion potensseja. Kyseinen alkio n (generates the group) ja merkitään a\\(G,\)>. Viritetyn (usein ali-)ryhmän suuruus eli on a\\|>. <\itemize-dot> jos on ääretön, syklinen ryhmä on isomorfinen ,+)>:n kanssa jos taas äärellinen ja 2>, niin ,+)>:n kanssa. virittävälle alkiolle on a\\|>=e> Syklisen ryhmän kaikki aliryhmät ovat syklisiä. on pienin ei-syklinen ryhmä (yksikäsitteinen, kertaluku 4, en piirrä tähän). Jokainen ryhmä, jonka on alkuluku, on syklinen. Syy: : jos on ryhmän aliryhmä, niin jakaa :n (eli \\>) Esimerkki: syklinen ryhmä )>, virittäjänä , on isomorfinen ,+)>:n kanssa kun määritellään: : \; |||>||||>|||||>|||||>|||||>|||||>>>>>>|||||||>|||||>|||||>|||||>|||||>>>>> ja aliryhmät -1\,\2\>: |||>||>|||>|||>>>>>\|||||>|||>|||>>>>>>> Joukon ja sen kahden operaation ja > yhdistelmä, )>, on algebrallinen , jos: <\enumerate-Roman> on kommutatiivinen ryhmä ja )>> on puoliryhmä ja pätevät: <\itemize-minus> c=a\c+b\c> (b+c)=a\b+a\c> Lisäksi: <\itemize> Renkaan (ei aina olemassa) merkitään 1 ja määritellään a=a\1=a> Alkio 0> on jos on olemassa 0>, jolle b=0> tai a=0>. (unit) on alkio , jolla on jokin käänteisalkio > (missä a=a\a=1>>).\ : ``yksikkö'' > ``ykkösalkio'' (>:n neutraalialkio, unity) on rengas, jolle b=b\a> (ei esim. matriisirenkaissa). (field ) on kommutatiivinen rengas jonka kaikki 0> ovat yksiköitä. (Esim. > on kunta, mutta > ei, koska esim. =\\> eli 4 ei ole yksikkö eli sillä ei ole kokonaisluku-käänteisalkiota.) (integral domain) on kommutatiivinen rengas, jolla ei ole nollatekijöitä (ekvivalentti ehto: y=z>). Kaikki kunnat ovat kokonaisalueita ja kaikki kokonaisalueet ovat kuntia. Jos alkiolla on käänteisalkio, se ei voi olla nollatekijä > kunnassa ei ole lainkaan aitoja nollatekijöitä. ,+,\)> on kommutatiivinen, ykkösalkiolla varustettu rengas ja sen alkiolla on käänteisluokka joss . Joss on alkuluku, on > (myös) kunta (eli kaikilla alkioilla, ts. kongruenssiluokilla, on käänteisalkio). Kaikkien äärellisten kuntien koko on muotoa >, missä on alkuluku ja \>. on rengas, jonka alkioina on jonkin toisen renkaan alkioiden osajoukko. on :n alirengas, jolle 1) kaikkien sen alkioiden erotuksetkin kuuluvat :hin (ts. I> kaikille I>) ja 2) myös kaikille R, a\I> pätee a, a\r\I>. Kaikki >:n alirenkaat ovat ideaaleja ja niiden alkiot ovat muotoa S=n*x \<\|\|\> x\\>. Tästä johtuu: =\/n*\>. Renkaan on on pienin \>, jolle +a|\>=0\R>. Jos yhtään tällaista lukua ei ole olemassa, . Jos kyseessä on kunta ja 0>, on alkuluku. Kuntien >, > ja > karasterika on , mutta on olemassa äärettömiä kuntia, joiden 0> (esim. [x])=3>). on funktio S> (missä )> ja ,\)> ovat renkaita), jos kaikille R> on f(b)> ja b)=f(a)\f(b)>. Jos on lisäksi bijektio (kääntäen yksikäsitteinen kuvaus), se on . Renkaat ovat keskenään isomorfisia jos niiden välillä on olemassa isomorfismi. `` renkaan yli'' eli (R)> on n>-neliömatriiseista koottu rengas, jonka matriisialkiot ovat :n alkioita. Matriisikertolaskun epäkommutatiivisuudesta johtuen > on harvoin kommutatiivinen vaikka olisikin. Jos )> on rengas (vaika >-kunta, tai äärellinen >-rengas tai vaikka matriisirengas): <\itemize> ''Muuttujan -polynomi'' on muotoa *x+\+ax+a*x+a*x>, missä \R>. on polynomin korkeinta astetta oleva termin kerroin >. on *x=a> (, jos =0>). Merkintätapa: = muuttujan kaikkien -polynomien (ääretön) joukko. Äärettömällekin joukolle :n polynomeja on yleisessä tapauksessa useita esitystapoja. Esim. jos ={0,1,2,3,4,5}> niin +3*x-2*x\5*x+3*x+4*x>, koska 4 (mod 6)>. Jos polynomin kertoimet ovat > ja :n kertoimet > niin g(x)>:n tulon termien kertoimet ovat =a*b>. : jos -renkaassa on aitoja nollatekijöitä, tulon aste saattaa olla pienempi kuin :n ja :n asteiden summa. '' yli '':n on rengas )>. Juuri on :n arvo, jolla polynomin arvoksi tulee nolla-alkio. : yleisessä tapauksessa (kun -rengas ei ole kokonaisalue) :n polynomeilla voi siis olla niiden astetta enemmän juuria. R[x]> on eli jaollinen, jos sen aste on 2> ja g(x)> joillekin , joiden aste on 1>. Jaoton polynomi on . redusoituvuus riippuu :stä: esim. +1)\\[x]> on jaoton, mutta +1)\\[x]> jaollinen: . Jos on kunta ja polynomi on astetta 2 tai 3, se on redusoituva/jaollinen joss sillä on juuri :ssä. Polynomien : vakio (eli astetta nolla). on tekijöihin jaetun polynomin yksikäsitteinen esitysmuoto, jossa koko lauseke on kerrottu vakiolla ja kaikkien tekijöiden (redusoimattomia, ts. jaottomia polynomeja) johtokerroin on : \(x+b*x+\+b)\\\(x+c*x+\+c).> Eri polynomirakenteiden määrä voidaan rajata (tavallisesti äärettömästä :stä) äärelliseksi kongruenssilla: valitaan jokin polynomi ja määrätään, että kaikkien renkaan operaatioiden tuloksesta otetaan lopuksi jakojäännös :llä. Merkitään: . Jos on redusoituva, tulos on rengas ja jos taas redusoimaton niin kunta. Esim. polynomikunnan [x]/(x+x+1)> operaatiot ovat: |||||||>|||||>|||||>|||||>|||||>>>>> ja |||>||||>|||||>|||||>|||||>|||||>>>>>\ Jos on ääretön, on tietysti myös ääretön vaikka eri polynomimuotoja onkin rajallisesti. Esim. [x]/(x+1)> on isomorfinen >:n kanssa. )=>polynomikunta [x]/s(x)>, missä on, kertalkua \> oleva redusoimaton, normeerattu polynomi. :n löytäminen ei ole yleensä helppoa, mutta siihen on olemassa algoritmeja. Galois-kunnan karasteristika )=p>. )>:n on sen alikunta >. Erityistapaus: > eli yksinkertaisen (siis \ ''ei-moninkertaisen'') alkuluvun Galois-kunta on oma fundamentaalikuntansa. Jokainen > kokoinen (eli ``kertalukua oleva``) kunta on isomorfinen )>:n kanssa. Boolen algebran (symbolien jonoista sekä operaatioista > koottu logiikka-algebra) sovellus: siirretään -bittisiä viestejä (\>) häiriöisellä linjalla, joka voi aiheuttaa mihin tahansa siirrettävään bittiin virheen (ts. 1>) todennäköisyydellä , bitin sijainnista ja alkuperäisestä arvosta riipumatta. <\itemize> \>:ssä on niissä kohdissa joissa siirretyssä viestissä on virhe ja niissä, joissa bitti siirtyi oikein. Kun =virhebittien (-bittien) määrä eli : <\itemize> Tietyn virherakenteen esiintymisen todennäköisyys on (1-p)> Tasan virhettä sisältävän siirron todennäköisyys on >|>>>>*p*(1-p)> - muuttaa -bittiset viestit -bittisiksi jonoksi lisäämällä niihin kpl. tarkistusbittejä jolloin on > (n>). on kahdessa bittijonossa toisistaan eroavien bittien määrä. Kun viestejä välitetään käyttäen joukkoa , kaikki painoa k> olevat virheet voidaan: <\itemize> havaita, jos eri koodisanojen minimietäisyys on vähintään korjata, jos eri koodisanojen minimietäisyys on vähintään Koodaus \\> on joss sen tuottamat koodisanat ovat ,+)>:n aliryhmä. Ryhmäkoodeilla koodisanojen Hamming-minimietäisyys on niiden nollasta eriävien koodisanojen minimipaino (eli niiden keskinäisiä etäisyyksiä ei tarvitsekaan laskea). Koodauksen \\> on jolla kertominen tuottaa viestisanoista koodisanat: \)=w\G=c\\> (missä on -vektorina esitetty viesti ja on -vektorina esitetty koodisana). Esim: eräs \\>-koodaus: <\equation*> ||>>>>*|||||>||||||>>>>=||||||>>>> Generoiva matriisi on eli jos se on muotoa \|A]> eli vasemmalla on alimatriisina yksikkömatriisi. Minkä tahansa generoivan matriisin voi normalisoida ja tuloksena on . on , jolle :n eli c=0\\> joss on jokin käytetyistä koodisanoista. Normalisoitu muoto on ]>. Huom: syndrooman laskussa vektorina esitetty viesti kerrotaan :lla . Jos vastaanotetussa viestissä on virhe vain yhdessä bitissä, i , r> on :n :s pystyrivi. (Yleisesti: syndrooma on virhebittejä vastaavien :n pystyrivien summa.) Generoivalla matriisilla esitetty koodaus on ryhmäkoodi. : tarkistusmatriisi >] eli on kokoa (2-1)> ja sen pystyrivit on koottu lukujen ,2-1> binääriesityksistä jossain järjestyksessä. Vastaava generoiva (eli koodaus-) matriisi on -1-k>\|B]>. Hamming-koodauksella siirretään -1-k> -mittaisia viestejä, sillä voidaan korjata yksi virhe ja sen tehosuhde on -1-k|2-1>=1--1>>. <\itemize> = uudelleenjärjestely/sekoitus = yhdistelmä, jossa järjestyksellä ei ole väliä iden määrä = ``montako erilaista :n pituista järjestettyä jonoa voidaan muodostaa :stä eri alkiosta`` = >>. Huom: iden määrä = ``montako erilaista :n kokoista joukkoa voidaan valita :stä eri alkiosta kun järjestyksellä ei ole väliä`` = >|>>>>==*>. Huom: iden määrä = ``monellako toisistaan erottuvalla tavalla voidaan järjestää kpl. :sta eri luokasta valittua alkiota, kun luokasta 1 valitaan > kpl, luokasta 2 valitaan > jne.'' = ,r,\,r)=!\r*!\\\r!>> (missä siis r>) : ``Jos on kyyhkystä ja pesää, yhdessä pesässä on 2 kyyhkystä'' (kaikki voivat olla myös samassa pesässä!) '':n eri alkion mahdollisten luokittelujen määrä :hon luokkaan jaettaessa kun osa luokista saa olla tyhjiä`` = ``:sta eri merkistä koottujen :n pituisten merkkijonojen pituus`` = > Yhtälön +x+\.x=n> ratkaisujen määrä, kun \> = ``Monellako tapaa voidaan järjestää pallon ja erottimen muodostama jono'' = <\math> P(n+k-1, n, k-1)=(k-1)!>= ``Monellako tavalla voidaan valita pallojen paikat'' = ``Monellako tavalla voidaan valita erotinten paikat'' = . : ``Monellako tavalla 7 eri henkilöä voi valita 4:stä eri ruokalajista?`` = ``Montako ratkaisua on positiivisella kokonaislukuyhtälöllä +x+x+x=7> ?''= ``Monellako (erottuvalla) tavalla voidaan järjestää jono '\|\|\|ooooooo'?'' = 3!>=>|>>>>> ten määrä = ``Monellako tapaa voi järjestää alkiota niin, ettei mikään ole omalla paikallaan`` = |n>|k=0>*n!|k!>\n!\e> ``:n eri alkion mahdollisten luokittelujen määrä :hon ei-tyhjään luokkaan jaettaessa'' (esim. {1}{2,3},{1,2}{3},{1,3}{2}>) eli = (-1)>|>>>>*r> (rekursiokaavana: ``:n eri alkion kaikkien mahdollisten luokittelujen määrä'' eli = S(n,k)> <\with|language|finnish> Inkluusio-ekskluusio-periaatteella lasketaan osittain päällekkäisiä ehtoja täyttävien alkioiden / tapausten määriä: ensin päällekäisten joukkojen koot lasketaan yhteen ja sitten tuloksesta vähennetään niille yhteisten alkioiden määrä (ettei sitä oteta mukaan kahteen kertaan). Ongelmia kannattaa visualisoida Venn-diagrammilla. Merkintätapoja: Joukko , jonka koko , koostuu alkioista, jotka toteuttavat kukin joitain (tai vaikka kaikki tai ei yhtään) :stä eri ehdosta ,\c> (esim. esinettä ja 4 ehtoa: >=``alkio on pallo``, >=``alkio on vihreä``, =>''alkio on sininen``, >=''alkio on painava'' jne). Vähintään yhden ehdoista ,c,\> toteuttavien alkioiden määrää merkitään *c\)> ja niitä, jotka eivät toteuta niistä mitään (mutta voivat toteuttaa jotain muita!) merkitään *|\>*|\>\)>. \; Ei yhtään ehtoa täyttäviä alkioita on: <\eqnarray*> =>>||-S+S-S+\=(-1)*S>>|||kun =N>>|=N(c)+N(c)+N(c)+\>>|=N(c*c)+N(c*c)+\+N(c*c)+N(c*c)+\>>|=N(c*c*c)+N(c*c*c)+\+N(c*c*c)+\>>>>>>>>> Yleisesti: tasan ehtoa täyttäviä alkioita on: <\eqnarray*> >||->|>>>>*S+>|>>>>*S-\>>|||(-1)*>|>>>>S=(-1)*S>>>> määrää termien kertoimet kun binomi kerrotaan auki polynomiksi: <\equation*> (x+y)=>|>>>>*x*y Kerroin :nnen asteen :lle on siis n:n k-kombinaatio. Binomikertoimia kuvataan usein lla, jonka jokainen reuna-alkio on 1 ja jokainen sisäalkio aina kahden heti sen yläpuolella olevan alkion summa. yleistää tuloksen: \; <\with|par-mode|center> Tulossa +x+\x)>>, termin >\x>\\\x>> kerroin on >|r\r>>>>>=!\r!\\\r!>> \; Joskus tarvitaan ``binomikertoimia``, joissa \> tai \>: : <\equation*> >|>>>>=(s-1)\\\(s-k+1)|k!>, s\\, k\\ ...tai jos :n tilalla onkin negatiivinen kokonaisluku (>) eikä desimaaliluku, niin: <\equation*> >|>>>>=(-1)*>|>>>>=(-1)* Emäfunktiolla voi ratkaista mekaanisesti erilaisia kombinatorisia tehtäviä (``montako erilaista / monellako tavalla`` ja jopa ``luettele kaikki`` eli ) esittämällä jonot polynomeina. Algebrallisen pyörityksen jälkeen tulos katsotaan suoraan polynomin halutun asteisteisten termien kertoimista ! <\itemize> +a*x+a*x+\=>a*x> (sopii kombinaatiolle) +a*x+a*|2!>+\=>a*|k!>> (permutaatioille) muitakin emäfunktoita on (esim. kahden muuttujan versio) Esim. (tavallinen emäfunktio): ''Montako positiivista kokonaislukuratkaisua on yhtälöllä , kun [4,8], b\[2,6]> ja [2,5]>?'' Tämä ratkeaa kertomalla auki polynomi (tavallinen emäfunktio)... <\equation*> +x+x+x+x)|\>*|a>+x+x+x+x)*|\>|b>+x+x+x)|\>|c>>=x+\+*14*x+16*x+\ ...ja ottamalla siitä >:n kerroin (14). Muuttujan potenssit esittävät :n, :n ja :n arvoja ja niiden kertoimet (>, tässä tapauksessa 1 kaikille mainituille ja muille 0) merkitsevät ``monellako tavalla kyseinen arvo voi tulla valituksi kyseiselle muuttujalle''. Ym. lauseen voi siis lukea tulkitsemalla =``tai``, >=``ja`` (kuten Boolen algebrassa): ``jos (a=4 tai a=5 tai ...) ja (b=2 tai b=3 tai ..) ja ...``. Auki kerrottu polynomi esittää näiden eri kombinaatioita ja siitä näkee myös, että esim. > ratkaisuja olisi 16 kpl. Polynomien kertominen keskenään on työlästä, joten laskemisessa hyödyllisiä ovat (Huom: suppenevuusehdoilla ei tässä ole mitään väliä, koska :ään ei oikeasti sijoiteta mitään): \; A) äärettömät jonot (sarjat): <\eqnarray*> =1,1,1,1,\) >||+x+\=>x>>|=1,-1,1,-1,\)>||-x+\=>(-1)*x>>|=1,2,3,4,\) >>||+3*x+\=>i*x=*>x=*x*>>|>>||>>|>>>>x=>(-1)>|>>>>x>>|>>||>>|>>>>(-x)=>>|>>>>x>>|(x)\g(x)>||>a*b*x \ eli jonojen konvoluutio>>>> B) äärelliset jonot: <\math> <\eqnarray*> =1|\>) |1-x>>||+\+x>>|>||>|>>>>+>|>>>>*x+>|>>>>*x+\+>|>>>>*x>>|||=1+4*x+6*x+4*x+1*x]>>|>||>|>>>>+>|>>>>*a*x+>|>>>>*a*x+\+>|>>>>*a*x>>|)>||>|>>>>+>|>>>>*x+>|>>>>*x+\+>|>>>>*x>>>> C) (permutaatioiden laskemista varten) eksponenttifunktiot: <\math> <\eqnarray*> >|||2>+|6>+\=>|k!>>>|>||*|2>+a*|6>+\=>a*|k!>>>|||>|(2k)!>>>|||>|(2k+1)!>>>|||>(-1)|(2k)!>>>|||>(-1)|(2k+1)!>>>>> Epäsäännöllisempiä sarjoja voi esittää laskemalla eri emäfunktioita yhteen tai vähentämällä yksittäisiä termejä, esim. \ +41*x-1*x-*3*x>. Ongelmassa esiintyvät jonot kirjoitetaan ensin emäfunktioiksi (eli ''siirrytään taulukossa oikealta vasemmalle''), sievennetään sitten niiden yhdistelmä (esim. summa) ja muutetaan tulos sitten takaisin sarjamuotoon (ts. ``taulukossa takaisin vasemmalta oikealle''). Menettely muistuttaa siis hieman Laplace-muunnoksen käyttöä ja myös emäfunktioissa ``käänteismuunnos'' vaatii usein osamurtokehitelmää (esimerkki differenssiyhtälöt-kappaleen lopussa). \; Joitain generoivia funktioita (Huom! nämä siis , eivätkä annan itse määriä!): <\itemize-dot> Väärinjärjestysten määrä: |1-x>> (=a+a>): >> (F=>(r-r) \<\|\|\> r>=(1\)/2>) (=a*a+a*a+\+a*a> eli esim. ``Erilaisten -kärkisten binääripuiden määrä``): |2*x>> (a=>|>>>>>) ``Luvun ten määrä '': >)>>. Ositus = luvun kokoaminen termeistä n> (esim. 4=1+3=1+1+2=2+2=4). Tekijät n> eivät vaikuta vastaukseen, joten äärettömän tulon voi katkaista ja käyttää (kertomalla versiot n> yhteen) sarjaa >=>x>. <\itemize> = emäfunktio, jolla lasketaan ``Monellako tavalla voidaan asettaa toisiaan uhkaamatonta (nontaking) tornia tietyn muotoiselle shakkilaudalle kun osa ruuduista on kiellettyjä (>)?'' ''Uhkaamaton'' = mikään nappula ei saa olla samalla rivillä eikä sarakkeella toisen kanssa. Vastausta merkitään (C)> kun on lauta. Esim. E=8> ja (E)=2>, kun ||||>|>|>>|>|>|>>|>|>|>>>>>>. Tornipolynomi generoi >:n kaikille . Esim: +2*x> (tarkoittaa: 1 tapaa asettaa 0 tornia, 6 tapaa 1 torni, 8 tapaa 2 ja 2 tapaa 3 tornia) Jos kiellettyjä ruutuja on vähemmän kuin sallittuja, voidaan laskea käänteisen (vaihdetaan kielletyt>sallitut) laudan polynomi ja solveltaa inkluusio-ekskluusio-kaavaa: <\eqnarray*> |(C)>||(-1)*\r(C)\(w-i)! ||>|>>>>>>|||>|,x)>||\>>|>||(3-0)!-3\(3-1)!+2\(3-2)!-0\(3-3)!>>|||3!-3\2!+2\1!-0\0!>>|||>>> ( miten saa >:n mielivaltaiselle eikä vain tapaukselle ??) Jos lauta koostuu erillisistä osista ,\,C> (ts. ei yhteisiä rivejä eikä sarakkeita), on koko laudan polynomi sen erillisten osien polynomien tulo: <\equation*> ,x)*\r(C,x)\\\r(C,x)>> Lautaa voidaana jakaa kahdella tekniikalla vaikka erillisiä osia ei heti näkyisikään: <\enumerate-numeric> siirtelemällä rivejä ja sarakkeita (ei vaikuta tulokseen) valitsemalla yksi rutuu jostain strategisesta paikasta ja laskemalla yhteen tapaukset, joissa siinä a) on nappula [poistetaan myös kaikki sen uhkaamat ruudut] tai b) ei ole nappulaa [poistetaan vain kyseinen ruutu] <\eqnarray*> ||,x)|\>|on nappula>+,x)|\>|ei nappulaa>>>>> Esimerkki: Johdetaan ym. :n tornipolynomi ilman käänteisen laudan temppua, sijoittamalla kokeeksi nappula vasemmalle ylös laudanjakotekniikan 2 mukaisesti: <\eqnarray*> =||||>|>|>>|>|>|>>|>|>|>>>>>>|>|=||||>|>|>>|>|>|>>|>|>|>>>>>=||||>|>|>>|>|>|>>|>|>|>>>>> (erilliset osat!)\>>|,x)=(1+2*x)>|>|,x)=(1+x)\(1+4*x+2*x)>>||>|>|||)>>|||+2*x>>>> (...eli t eli t) <\itemize> Alkion > arvo riippuu :sta edellisestä alkiosta ja :stä: =g(a, a, \., a,n), n\k>. Vakio on differenssiyhtälön . Terminologia pitkälti samaa kuin differentiaaliyhtälöissä Homogeenisten, lineaaristen yhtälöiden yleiset ratkaisut saa erityisratkaisujen lineaarikombinaationa (kuten differentiaaliyhtälöissäkin) Helpoille tapauksille on ratkaisukaavoja ja hankalampiin voi usein käyttää emäfunktioita Ratkaisukaavoja: <\itemize> Ensimmäisen kertaluvun vakiokertoimisen, lineaarisen ja homogeenisen yhtälön eli =r*a> (tai =r*a>) yleinen ratkaisu on =c*r> (kun 0>). Huom: >. Toisen kertaluvun vakiokertoiminen, lineaarinen ja homogeeninen yhtälö (kuten Fibonaccin luvut) eli *a+C*a+C*a=0> (missä 2>) ratkeaa sijoittamalla >:n tilalle ksi ensimmäisen kertaluvun ratkaisu =c*r>: <\eqnarray*> **c*r+C*c*r+C**c*r>|| : c*r\>>|*r+C*r+C>||>>> Tämä on ja rekursion ratkaisu riippuu sen juurista > ja > lineaarikombinaatiolla: <\itemize> 2 reaalista, erisuurta juurta a=cr+c*r> (> ovat mielivaltaisia vakioita) kompleksikonjugaatit >samalla tavalla (> ja > eliminoivat toistensa imaginääriosat), mutta laskeminen on vähän hankalampaa ja se kannattaa tehdä polaarikoordinaateissa kompleksiluvun potenssiin korotuksen takia kaksinkertainen juuri (eli =r>) a=(c+c*n)*r> Sama konsti toimii korkeammankin kertaluvun yhtälöille, mutta polynomin ratkaisu menee turhan hankalaksi. Epähomogeenisten versioiden ratkaisut saa kaavasta =a+a> eli homogeenisen version yleinen ratkaisu + epähomogeenisen jokin yksittäisratkaisu. Jos epähomogeeninen osa sattuu olemaan muotoa >, niin: <\itemize> Ensimmäinen kertaluku (eli +*C*a=f(n)>):\ <\enumerate-numeric> =A*r> jos se ei satu olemaan myös >:n ratkaisu tai =A*n*r>, jos sattuu Toinen kertaluku: <\enumerate-numeric> =A*r> jos se ei satu olemaan myös >:n ratkaisu tai =A**n*r>> jos sattuu, ja > on muotoa *r+c*r> tai =A**n*r>> jos sattuu, ja > on muotoa +c*n)*r> Ideana on etsiä ensin rekursiota esittävä emäfunktio suljetussa muodossa (potenssisarjojen laskusäännöillä) ja sitten etsiä toiseen suuntaan sitä vastaava sarja. \; Esimerkki: ``Mikä on sarjan =2*a+1 \<\|\|\> n\0\a=0> :s alkio?'' <\enumerate-numeric> Valitaan ja nimetään sarjaan ``sovitettava'' emäfunktio -- valitaan tässä: >a*x> (eli tavallinen emäfunktio) Esitetään molemmat puolet :n avulla (siten, ettei yhtään >:ää jää jäljelle). Aloitetaan kertomalla >:llä ja summataan sitten ]> yli. <\eqnarray*> >||0>(a*)x=0>ax-a/x=*0>ax=A(x)/x>>|+1>||0>a*x+0>x=2*A(x)+>>>> Ratkaistaan :n suhteen: <\eqnarray*> ||\\x>>|||\>>|||>>>> Etsitään saadulle emäfunktiolle sarjaesitys. Käytetään osamurtokehitelmää (Heaviside) ja potenssisarjojen laskusääntöjä: <\eqnarray*> >||+>>|||+ y=2x:\0>y=0>(2*x)>>|||-0>x+2*0>2*x=x**0>2*x-0>x>>|||0>(2-1)*x=0>(2-1)*x>>>> Viimeisestä summasta nähdään suoraan, että emäfunktion sarjaesityksen :s kerroin, eli alkuperäisen sarjan >, on -1>. Tulkitaan geometrisen objektin (esim. neliön) eri värisiksi värjättyjen kärkien kiertoja ja peilauksia/3D-rotaatiota (eli ä) permutaatioina ja lasketaan montako erinäköistä objektia voidaan tehdä jos niitä saadaan pyöritellä vapaasti. Määritelmiä: <\itemize> >on bijektioiden :A\A, kun \|A\|=n> muodostama algebrallinen ryhmä (ts. :n alkion kaikkien erilaisten permutaatiofunktioiden ryhmä) tarkoittaa >:n aliryhmää, ts. ,\,\}>, vaikka olisikin n> tulo *\> (''tyhjä operaattori'') tarkoittaa yhdistettyä (2 peräkkäin tehtyä) permutaatiota permutaatioryhmä ei ole kommutatiivinen (aabelin ryhmä), jos 3>. Suomeksi: permutaatioiden järjestyksen vaihtaminen voi muuttaa tulosta. : ''jokainen ryhmä voidaan esittää permutaatioryhmänä'' eli sille on isomorfismi viimeistään >:ään (ja usein jo >:ään, missä n>). : =>|>>>>>, josta näkee mikä alkio vaihtuu minkäkin paikalle. Toinen esitystapa: eli : =(123)(45)> (sama permutaatio > kuin edellisen esimerkin matriisissa). Tässä edellinen vaihtuu aina seuraavan paikalle ja viimeinen pyörähtää ensimmäisen tilalle. Esim: >|>>>>>. Yhden mittainen sykli = alkio ei vaihda paikkaa.\ Kun merkitään kärkien eri väritystapoja (konfiguraatioita) >:llä (neliön ja kahden värin tapauksessa niitä on yhteensä =16> kpl: ,\,c}>) ja permutaatioita >:llä (neliön tapauksessa 8 kpl, kun lasketaan erilaiset kierrot ja peilaukset: ,\,\}>, missä > = >> kierto = ''ei muutosta''), niin: <\itemize> on niiden väritystapojen > joukko, jotka voidaan muttaa toistensa näköisiksi :n permutaatioilla. Ts. ekvivalenssiluokkien määrä = ``oikeasti erilaisten'' väritysten määrä. Väritystavan S> - on niiden väritystapojen joukko, joiden näköisiksi :n permutaatiot voivat :n muuttaa. Sen >-rata (\G>) taas on niiden väritysten joukko, joiksi ryhmä \\> (eli >:n potenssien muodostama :n aliryhmä) voi sen muuttaa. Värityksen/konfiguraation on aliryhmä \G>, jonka sisältämät permutaatiot eivät muuta :stä lainkaan :n on jokin , joka ei muutu millään permutaatiolla \G>. Tasaväritykset ovat tietysti aina kiintopisteitä. : *\G>\(\)> = ekvivalenssiluokkien määrä, kun (\)> = ``>:tä sovellettaessa muuttumattomien konfiguraatioiden määrä''. Esimerkki: ``monellako tavalla 6 ihmistä voi sijoittaa pyöreän pöydän ympärille?''. \ =i\60>> kierto, kun . Erilaisia konfiguraatioita pyörittämättömälle pöydälle on , joten =0>\\(\)=6!> ja koska kukaan ei pysy paikallaan vähänkään pyöritettäessä, (\0>)=0>. Vastaus: *(6!+0+0+0+0+0)=5!=120>. (Yleisesti: voidaan valita tavalla.) helpottaa laskemista: =(1)(2)(3)(4)>:n sykli-indeksiesitys on >, =(1234)>>:n esitys on > ja esim. =(12)(3)(4)(5)>:n on *x*>. Sykli--indeksi... <\equation*> (x,\,x)=[esitysten summa]*>>> ...antaa :n eri värin värityksen ekvivalenssiluokkien määrän sijoituksella (m,m,\)>. : kun on käytettävissä eri väriä, erilaisten väritysten lle, eli eri kombinaatioiden määrien luetteloinnille, saadaan emäfunktio sijoituksella... <\equation*> P((v+\+v), (v+\+v), \,(v+\v)) ...missä > on väriä esittävä muuttuja. Huom: >:n ei sijoiteta mitään vaan tulos katsotaan kertoimista, koska kyseessä on emäfunktio. \; Esim.: ``Montako eri tapaa on värittää 3-lapainen potkuri kun väreinä on r,g ja b?'' Permutaatioryhmä eli kierrot >>, >> ja >>, joiden sykli-indeksiesitykset ovat , x> ja >. Inventaario-emäfunktio saadaan siis seuraavasti: <\eqnarray*> (x,x,x)>||(x+2*x)\>>|((r+g+b),(r+g+b),(r+g+b))>||*(r+g+b)+2*(r+g+b))>>|||+rg+rb+r*g+2*r*g*b+r*b+>>|||+g*b+g*b+b>>>> Polynomista nähdään, että on 2 eri tapaa (termi ) kun käytetään kaikkia kolmea väriä (ja 1 tapa kaikilla muilla värikombinaatioilla). Termien kertoimia voi usein laskea multinomilauseen avulla kertomatta koko polynomia auki. <\itemize-dot> Jos on jaollinen :llä, sanotaan " jakaa :n" ja merkitään: . Jos b>, jakaa sanotaan :n jakavan (vrt. "aito osajoukko (> vs. >)"). on luku, jolla ei ole yhtään :stä poikkeavaa aitoa tekijää. : jokainen positiivinen kokonaisluku \> voidaan esittää yksikäsitteisesti alkulukujen tulona (eli >\p>\\\p> \<\|\|\> s\\>) > jokainen ei-alkuluku on jaollinen jollain alkuluvu(i)lla <\itemize-dot> (b\|c)\(a\|c)> (a\|b*c)> Jos ja jakaa kaksi muuttujista, jakaa se kaikki kolme. Jos jakaa luvut \c>, jakaa se myös näiden lineaarikombinaatiot: *x+\+c*x)>. Luvut ja ovat eli keskenään jaottomia, jos niiden suurin yhteinen tekijä on eli eli on olemassa \> siten, että . ( tai , Greatest Common Denominator) merkitään ,\,a)> tai ,\,a)>> ja on suurin luku , joka jakaa kaikki > eli i : \ d\|a>. Kahdelle muuttujalle voidaan merkitä myös , missä \>. \; S.y.t löytyy lla: jaetaan joka askeleella jäljellä oleva luku edellisen askeleen jakojäännöksellä ja lopetetaan kun jäännöksestä tulee 0. Viimeinen ei-nolla jäännös on s.y.t. Algoritmi toimii myös useammalle kuin kahdelle luvulle, sillä . Esim. : <\eqnarray*> ||116298+113058>>|||113058+3240>>|||3240+2898>>|||2898+342>>|||342+162>>|||162+18>>|||\\+ 0>>>> Lineaarikombinaatioesityksen kertoimet ja (ja sen avulla Diophanteen yhtälön ratkaisun) löytää tästä peruuttamalla. Aluksi ratkaistaan ketjun toiseksi viimeinen rivi jakojäännöksen suhteen, sitten ratkaistaan edellinen rivi samalla tavalla, yhdistetään ne ja supistetaan, ratkaistaan kolmanneksi viimeinen rivi ja jatketaan samaan tapaan alkuun asti: <\eqnarray*> 162=18>||>|342=162>|>|(2898-8\342)=18>>||>|2898+17\342=18>>|2898=342>|>|2898+17\(3240-1\2898)=18>>||>|3240-19\2898=18>>|3240=2898>|>|3240-19\(113058-34\3240)=18>>||>|113058+663\3240=18>>|113058=3240>|>|113058+663\(116298-1\113058)=18>>||>|116298-682\113058=18>>|116298=113058>|>|116298-682\(461952-3\116298)=18>>||>|461952+2709\116298=18>>||>| y=-682>>>> ( tai , Least Common Multiple) merkitään ,\a]> tai ,\,a)>> ja on pienin luku, jonka kaikki > jakavat eli li i : \ a\|c>. \; <\itemize-dot> b=syt(a,b)\pyj[a,b]> >b|syt(a,b)>> on yhtälö, jonka ratkaisuksi sallitaan vain kokonaislukja. Lineaarinen kahden muuttujan versio: , jossa \>. <\itemize-dot> Ratkaisuja on olemassa (äärettömästi) joss . Yksittäisratkaisun , y=y> jälkeen yleisen ratkaisun saa kaavalla\ <\equation*> +n*b>>|-n*a>>>>> ...missä > ja > tarkoittavat s.y.t:llä jaettuja versioita kertoimista. Huom! :n kohdalla on ja :n kohdalla eikä päinvastoin! Yksittäisratkaisun saa mekaanisesti ratkomalla Euklideen algoritmin jälkeen peruutuksella :n ja :n yhtälöstä ja kertomalla ne sitten :llä. Esim: ratkaistaan : <\enumerate-numeric> Etsitään edellisen kappaleen Euklid-esimerkin mukaan Etsitään peruutustekniikalla ratkaisut y=-682> väliaikaiselle yhtälölle (myöskin edellisen kappaleen esimerkin mukaan) Todetaan, että ja sen perusteella, että (-682\461952+2709\116298)=18\153> eli 153=414477\y=-682\153=-104346> <\itemize-dot> " modulo " merkitään b (mod n)> ja tarkoittaa, että eli (eli eli ) merkitään , ja se tarkoittaa kongruenssiaritmetiikan numeroa. Esim: [8]=[6]> modulin suhteen (koska 8=24> ja ) Kongruensiluokan > on siten, että [y]=[1]>. Esim: =[5] (mod 7)>, koska 5) mod 7=1> b (mod n)> vastaa Diophanteen yhtälöä . Kongruenssiaritmetiikka tietyllä modulolla vastaa algebrallista rengasta (tai kun on alkuluku niin kuntaa) > (ks. ''renkaat ja kunnat'' kappaleesta ''abstrakti algebra''). Käänteisluokka on olemassa kaikille luokille joss (=moduli) on alkuluku. Tällöin vain 1 ja -1 ovat itsensä käänteisalkioita (ts. \1 (mod n)>). Muillakin moduleilla voi kyllä olla yksittäisiä käänteistyviä luokkia. lasketaan ottamalla välituloksista jakojäännös ja jatkamalla siitä. Tehokas tapa mod m>:n laskemiseen on laskea ensin , a, a, a,\> peräkkäisillä neliöinneillä ja kertoa niitä sitten yhteen :n binääriesityksen mukaan ottamalla joka askeleen jälkeen. : -1 (mod p)>, kun on alkuluku. Ei ole käytännöllinen alkulukutesti, koska kertoman laskeminen on hidasta. : \1 (mod p)>, kun ( joss!) on alkuluku ja a> (ts. ei ole :n tekijä, ts. ) (n)> on alkioiden \n>, joille ,n)=1>, eli :ää pienempien suhteellisten alkulukujen, määrä. Sääntöjä: <\itemize> (p)=p-1> joss on alkuluku. Tällöin myös: (p)=p-p> jos , niin (m*n)=\(m)*\(n)> (n)=n\1->\\\1->> (kun p>>) eli :n alkutekijöistä : (n)>\1 (mod n)>, kun . (Jos , saadaan \1> mod .) <\itemize-dot> Alkulukuja on äärettömän paljon. On olemassa sekä , joiden erotus on 2, että mielivaltaisen pitkiä lukujonoja joissa ei ole yhtään alkulukua. Luvun \> hajottaminen alkutekijöihin on erittäin raskas operaatio. Huomioita: <\itemize-dot> Jos pienillä alkuluvuilla testatessa tulee osuma, ts. =k\\>, hakua :lle pitää jatkaa :stä (sama tekijä voi esiintyä useita kertoja) :n alkutekijöissä voi olla max. 1 alkuluku >. Kaikki muut ovat tätä pienempiä > on alkuluku ellei > mukaan lukien ole löytynyt yhtään tekijää Tehokkain tunnettu tekijöintialgoritmi on työmäärältään log(log(n))>>)> Fermat'n pienellä lauseella (\1 (mod n)>, kun on alkuluku) voi usein todeta, että ei ole alkuluku, mutta se ei ole pitävä testi. '' kannassa '' on jaollinen luku , joka läpäisee Fermat'n pienen lauseen testin ja jolle . Niitäkin on äärettömän monta, mutta paljon harvemmassa kuin oikeita alkulukuja. on pseudoalkuluku kaikissa kannoissa 2>. Erittäin harvinaisia, mutta niitäkin oletetaan olevan äärettömästi. >Fermat'n pieni lause ei teoriassakaan ole aivan täydellinen alkulukutesti. : pariton ei ole alkuluku jos, kun \> on pariton, joko: <\enumerate-numeric> \1 (mod n)> tai 2>\-1 (mod n)> jollekin \> '' kannassa '' on jaollinen luku , joka läpäisee Millerin testin kannassa . Vain oikeat alkuluvut läpäisevät testin kaikissa kannoissa . : todennäköisyys sille, että jaollinen luku on vahva pseudoalkuluku kaikissa kannoissa \n \<\|\|\> \ i\[1,k]> on pienempi kuin >. <\itemize-dot> Avaimien luonti: valitaan kaksi alkulukua r> ja lasketaan niiden tulo r>. <\itemize-dot> Julkinen avain eli salakirjoitusavain on pari , missä on jokin luku, jolle (n))=1>>. Salainen avain eli purkuavain on pari , missä e (mod \(n))>. Viesti muutetaan/jaetaan lohkoiksi P\n> Salaus: P (mod n)> Purku: E(P) (mod n)> Allekirjoituksessa käytetään avaimia nurinperin: salataan purkuavaimella ja puretaan salausavaimella. Luvuilla ja pitää olla suuria tekijöitä ja :n ja :n on oltava jonkin verran eri pituisia, ettei (n)=(q-1)*(r-1)> ratkea liian helposti. Luvut ovat niin suuria, että käytännössä sovelletaan Rabinin todennäköisyystestiä, koska täydellisen Millerin testin ajo kestäisi liian kauan. <\itemize-dot> (loop) on sivu, joka alkaa ja päättyy samaan solmuun ( sekoita kierrokseen (cycle)!) on , jonka alku- ja loppusolmu ovat samat eli graafi on sellainen, jossa jokaista mahdollista sivua on korkeintaan yksi eikä siinä ole yhtään silmukkaa - ei-lineaarinen graafi on Kaksi solmua ovat , jos niiden välillä on sivu Kaksi solmua on , jos niiden välillä on jokin polku Graafi on , joss kaikki kärjet on yhdistetty kaikkiin muihin kärkiin Graafin ja sen aligraafin \G> > on muuten sama kuin , mutta siitä on poistettu >:n sivut Graafi on , jos kaikkien solmujen välillä on polku on suunnistamaton, lineaarinen, yhtenäinen, kierrokseton graafi, muuten sama, mutta ei yhtenäinen Suunnistamattoman graafin on siihen tulevien sivujen määrä - suunnistetulle on määritelty erikseen ja . Graafit ovat (\G)>, jos niillä on sama rakenne (eli voidaan määritellä kääntäen yksikäsitteiset funktiot, jotka mappaavat solmut ja sivut graafista toiseen) Graafin > on yleistetyn naapurimatriisin :s potenssi ja ilmaisee solmusta toiseen olevien n-pituisten polkujen määrän Graafien on sama, jos ne ovat isomorfisia kun molemmista poistetaan ne ja poistetaan astetta 2 olevat kärjet käsittää kaikki tasan kerran (vastaavasti ) käsittää kaikki tasan kerran (vastaavasti ) <\itemize-dot> Eulerin suunnistamattomassa graafissa on olemassa joss graafi on yhtenäinen ja kaikkien solmujen asteet ovat parillisia. Eulerin joss tasan kaksi paritonta kärkeä (jotka voitaisiin periaatteessa yhdistää, jolloin saadaan kierros). Hamiltonin polulle/kierrokselle ei ole yksikäsitteistä olemassaololausetta, mutta: <\itemize-minus> polkua ei ole ainakaan, jos on yli 2 kärkeä, joiden aste 1> kierros on olemassa ainakin, jos kaikkien kärkien aste > Graafi on (eli levitettävissä tasoon ilman leikkaavia sivuja) joss se ei sisällä kaksijakoisen graafin > (3+3 solmua kahdessa rivissä, ylärivin kaikki solmut yhdistetty kaikkiin alarivin solmuihin mutta ei toisiin ylärivin solmuihin, ts. 9 sivua) eikä täydellisen 5-graafin > konfiguraatiota. (=) Yhtenäinen tasograafi rajaa tasolle aluetta, ääretön alue mukaan lukien (=) Jos tasograafissa on yli 1 sivu ja tasoalueita kpl, on 2*e> ja 3*v-6>. Jos graafin kaikkien kärkien aste on , voi sivujen määrän laskea kaavalla , sillä "jokainen kärki on yhteinen :lle sivulle ja yhden sivun määräämiseen tarvitaan kaksi kärkeä". Seuraavat klassiset graafialgoritmit ovat ns. : <\itemize-dot> minimaalisen virittäjäpuun hakemiseen (eli priority first search): ensin lisätään jonoon kaikki naapureihin johtavat sivut joiden paino on pienempi kuin jo jonossa ehkä olevan, samaan solmuun johtavan sivun, sitten valitaan jonosta pienimmän painoinen sivu ja toistetaan kunnes kaikki solmut on käyty läpi. : kuin Primin algoritmi, mutta lähdetään tietystä solmusta, lisätään jonoon aina painojen (eikä pelkästään sivun omaa painoa) ja lopetetaan kun tultu kohdesolmuun. minimaalisen viritäjäpuun hakemiseen: valitaan yksitellen pienin jäljellä oleva sivu, joka ei muodosta kierrosta jo valittujen kanssa. (Kierrostarkistus voidaan tehdä merkitsemällä jokaiseen sivuun mihin tulosmetsän puuhun se kuuluu ja yhdistämällä vain eri alipuita keskenään. Alipuiden yhdistämisessä toisen puun tunnus aina hävitetään, joten lopuksi on jäljellä vain yksi puu.) <\itemize-dot> Graafi on kaksijakoinen joss se voidaan jakaa kahteen joukkoon siten, että sivuja on vain niihin kuuluvien kärkien välillä (ei siis saa olla esim. kierroksia) Kärjet piirretään yleensä kahteen riviin niin, että joukon 1 () kärjet ovat ylhäällä ja joukon 2 alhaalla. Tyypillinen käyttöesimerkki on avioliitto-/opiskelupaikkaongelma, jossa henkilöt luettelevat heille kelpaavat puolisot/koulut :stä (ts. preferenssit esitetään sivuina) ja sitten yritetään löytää kaikille sopiva järjestely. Kaksijakoisen graafin on joukko sivuja, joilla ei ole yhteisiä kärkiä Sovitus on , jos ei ole olemassa enemmän sivuja sisältäviä sovituksia. :n jonkin osajoukon X> on kaikkien siihen sivuilla kytkettyjen -kärkien joukko. Osajoukon on kokonaisluku (A)=\|A\|-\|R(A)\|>. Huom: voi olla negatiivinen! Koko (G)> on kaikkien :n osajoukkojen vajeiden maksimi. Koska niihin kuuluu myös tyhjä joukko ja (\)=0>, on (G)\0>. Graafin on sellainen, jossa jokaisesta :n kärjestä lähtee sivu ja sellainen on olemassa joss \|A\|> kaikille X> (eli (G)=0>). Täydellisen sovituksen etsimiseen on olemassa useita ns. polunlaajennusalgoritmeja. Tässä eräs: Käydään läpi kaikki kärjet X>: \ \ Jos :lle ei ole jo valittu esittäjäsivua: \ \ \ \ Käydään läpi :ään yhdistetyt kärjet Y> jotka eivät jo kuulu sovitukseen: \ \ \ \ \ \ Jos löytyy :hyn yhdistetty kärki \X> joka ei jo kuulu sovitukseen: \ \ \ \ \ \ \ \ Lisätään sivu \y> sovitukseen ja palataan uloimpaan silmukkaan Jos -kärjet korvataan joukoilla ja -kärjet niistä yhteen tai useampaan kuuluvilla alkioilla (ts. ei käsitellä enää varsinaista graafia vaan merkitään ``preferenssejä`` esim. \{y,y}, x\{y}>), puhutaan täydellisen sovituksen sijaan joukkojen n>> stä. Joskus sivuihin yhdistetään , jolloin yleinen ongelma on etsiä joko painojen summan maksimoiva (tai minimoiva) sovitus. Siihen sopii mm. , joka iteroi graafin matriisiesitystä (sivujen painot matriisialkioina). <\enumerate-numeric> Julistetaan (esim. +2+\2=2-1>) : osoitetaan, että (tai tai joku muu helppo tapaus) on tosi (esim. =1]=[2+1=2-1=1]>). : osoitetaan, että jos induktiohypoteesi (tai -oletus) on tosi, myös on tosi sijoittamalla :n toinen puoli :n sisään ja pyörittelemällä algebrallisesti. Esim. <\eqnarray*> +2+\2|\>|hypot. mukaan 2-1>+2>||-1>>|-1)+2>||-1 \<\|\|\> +1>>|+2>||>>|>|| \<\|\|\> log>>|||>>> <\equation*> x+b*x = x+- Esim. n johtaminen: <\eqnarray*> +b*x+c>||>|+*x>||>>|x+>|||4a>-|4*a>*\=-4**a*c|4*a>>>|>||-4**a*c>|>>>>|||-4**a*c>|2*a>>>>> Jokaiselle rationaalifunktiolle > ( on alempaa astetta kuin ) voi muodostaa n |P(x)>+\+|P(x)>> missä termit ovat muotoa >> tai +p*x+q)>> ja \> ja \> (jos sallitaan \>, jälkimmäistä muotoa ei tarvita). Kehitelmästä on hyötyä varsinkin integroinnissa. Aluksi faktoroidaan nimittäjä ensimmäisen tai toisen asteen termeihin kaavalla +b*x+c=a*(x-x)*(x-x)> (tai sen suoraviivaisella laajennuksella korkeamman asteen polynomeille). Hajotelman termit määräytyvät saatujen tekijöiden mukaan -- tapauksia on kolme:\ <\enumerate-numeric> reaalinen (\>), ei-toistuva juuri>lineaarinen nimittäjä, vakioarvoinen osoittaja: |\)\(x+a)\*(\*>=\++\> imaginäärinen juuri >toisen asteen nimittäjä, lineaarinen osoittaja: |\)\(x+p*x+q)\(\*>=\++p*x+q>+\> -kertainen juuri > termiä, joissa nimittäjän aste laskee: <\math> |\)\(x+a)\(\*>=\+|(x+a)>+|(x+a)>+\+|x+a> tai |\)\(x+p*x+q)\(\*>=\+x+C|(x+p*x+q)>+x+C|(x+p*x+q)>+\+x+C|x+p*x+q>> Hajotelman termien osoittajiin tulevat vakiot () eli t (eng. ) voidaan \ lasskea monella \ tavalla. Seuraavat kolme tapaa on esitetty kahden eri suuren, reaalisen juuren avulla (ts. |(x+a)*(x+b)>,a\b>), mutta ne toimivat myös korkeamman asteen tapauksissa (ts. |(x-a)*\*(x-a)>>). Heavisiden menetelmää lukuunottamatta ne toimivat myös moninkertaisille ja epälineaarisille tapauksille. :n valitseminen strategisesti> Lavennetaan osamurrot samannimisiksi alkuperäisen kanssa, eliminoidaan nimittäjät ja ratkaistaan osoittajista muodostuvan polynomin tuntemattomat () valitsemalla aina siten, että se hävittää kerrallaan yhden muuttujista: <\eqnarray*> >||+ lavennetaan oikea puoli>>|>|||(3*x-5)*>+|*(x-3)> \ \(3*x-5)*(x-3) >>|||>>> Valitaan strategisesti x=3>: <\eqnarray*> ||3-5)\>>|||>|||>>> Sama temppu B:lle: x=5/3>: <\eqnarray*> ||5/3-5)\>>|||>|||>>> Eli: <\equation*> =-+\ Etsitään murtofunktiota vastaava yhtälö kuten tavassa 1 ja ryhmitellään se :n polynomiksi (tässä esimerkin vuoksi toisen asteen, vaikka ensimmäisen asteenkin riittäisi): <\eqnarray*> ||>>|||>>|+1*x-1>||+(A+3*B)*x+(-3*A-5*B) >>>> Sitten tehdään :n eri asteisista termeistä (vakiot, :t, >:t yms) lineaarinen yhtälöryhmä: <\eqnarray*> +1*x-1>>||+(A+3*B)*x+(-3*A-5*B)> \<\|\|\> turha>>|+>1*>||+>A+3*B>>|+1*x>-1>||+(A+3*B)*x+>-3*A-5*B>>>> Ratkaistaan saatu lineaarinen yhtälöryhmä (esimerkkinä näytetty turha : 0=0> on poistettu): <\equation*> >|>>>>=||>||>>>>**>|>>>>\||>||>>>>*>|>>>>=>|>>>>=>|>>>> on helppo, mutta ei toimi moninkertaisten (>) eikä epälineaaristen (+p*x+q>) termien kanssa. Murtofunktiota ei tarvitse vääntää yhtälöksi kuten edellisissä tavoissa: Pyyhitään vain aina yksi tekijä pois nimittäjästä ja sijoitetaan sen nollaamiseen tarvittava vakio jäljelle jääneeseen kaavaan :n tilalle. Poistettua tekijää vastaava residy saadaan suoraan: <\eqnarray*> *(x-3)>>|>|x=5/3>>|>||>|>>|>|x=3>>|3-5>>||>>> <\itemize-dot> Määritelmä: x=y\a=x> eli "mihin potenssiin pitää korottaa, että saadaan " Ehdot: 0, a\1> ja 0> =r*log x> =log x - log y> x>=x>. Esim. =x>. 1=0> a=1> x=x|loga>> (eli ) <\itemize-dot> Summa, erotus, tulo ja osamäärä ovat triviaaleja: a> f(x)=L \ a> g(x)=M \ a>f(x)\g(x)=L\M>>>> \\> =0> \\> >:n raja-arvon saa jakamalla molemmat polynomit nimittäjän korkeimman asteen muuttujalla. Esim: \\> -x+3|3*x+5>=>\\> +>|3*+>>=> ääretöntä lähestyttäessä myös neliöjuuresta voi usein päästä eroon vastaavalla jakolaskulla: \> +1>>=\> (1+>)>>=\> >>>>=1>=1>>> polynomin raja-arvo(n merkki: \>) äärettömyydessä määräytyy vain ja ainoastaan korkeimman asteen tekijän mukaan, koska esim. -x+2x=3x*(1-+>)> jotain ei-määrättyä arvoa lähestyvän raja-arvon saa yleensä joko faktoroimalla polynomeja juuriensa avulla tai viimeistäänkin muuttamalla laskun raja-arvoksi äärettömyydessä: 2> -4>=2> -4)>=2> -4>|-4)>(x+2)>=2> => tai 2> -4>=>\> )-2|(2+)-4>=\> |()+4>=\> +4>=>. \> |e>=0-\> \|x\|*e=0>>> eli "eksponentti voittaa potenssiin korotuksen" \> >=00+> x*ln x=0>>>, \ eli "potenssiin korotus voittaa logaritmin" l'Hospitalin 1. sääntö: a+>f(x)=a+>g(x)=0\a+>=a+>(x)|g(x)>> . Huom: toimii -muotoisille lauseille! l'Hospitalin 2. sääntö: a+>g(x)=\\a+>=a+>(x)|g(x)>> . Huom: toimii ]>-muotoisille lauseille on käytännöllinen vain /\]>-muotoisille! Tyyppien ], [\], [1>]>-muotoiset voi kuitenkin muuttaa muotoon tai /\]> ottamalla logartimin. <\itemize> x+cosx=1> >>> >>> <\itemize> > = kokonaisluvut = ,\,-1,0,1,\,\[> > = positiiviset kokonaisluvut = ,\[> > = luonnolliset luvut = \{0}=[0,1,\,\[> > = rationaaliluvut \|q\\>> > = reaaliluvut > = kompleksiluvut = \)+i*(y\\)> (Roomalaisten kirjainten kanssa yhteiset merkit harmaalla, etsimisen helpottamiseksi.) ||>>|>>>||||>>|>>>|>|>>|>>>||||>>|>>|>|>>|>>||||>>|>>>|>|>>|>>||||>>|>>|>|>>|>>>||||>>|>>>|>|>>|>>>||||>>|>>|>|>>|>>>||||>>|>>>|>|>>|>>||||>>>|>>|>|>>|>>>||||>>>|>>>|>|>>|>>>||||>>|>>|>|>>|>>||||>>|>>|>|>>|>>>||||>>|>>|>>>> \ <\the-index|idx> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , , > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , , > , > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > , > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > > > > > > > > > > > , > > > > > > > > > > > > > > > > > > > , > > > > > > > , > , > > > > > > > > > > > > > > > > <\initial> <\collection> <\references> <\collection> > |\>|6>> > > > > > > > > > > |\>|6>> > > > |\>|12>> |\>|12>> > > > > > |\>|6>> > > > > > > > > > > |\>|6>> > > > > > > > > > > |\>|6>> > |\>|15>> |\>|15>> |\>|15>> |\>|15>> |\>|15>> |\>|15>> |\>|15>> > > |\>|6>> > > > > > > > > > > |\>|6>> |\>|16>> |\>|16>> |\>|16>> |\>|16>> > > > > > > |\>|6>> > > > > > > > > > > |\>|6>> > > |\>|17>> |\>|17>> |\>|17>> |\>|17>> |\>|18>> |\>|18>> > > |\>|6>> > > > > |\>|19>> |\>|19>> |\>|19>> |\>|19>> > > > |\>|6>> > > > > > > > > > > |\>|6>> > > > > > > > |\>|20>> |\>|20>> |\>|20>> |\>|6>> |\>|20>> > > > > > > > > > |\>|6>> > > > > > > > > > > > |\>|22>> |\>|22>> > > > > > |\>|22>> |\>|22>> |\>|22>> > |\>|22>> |\>|22>> |\>|23>> |\>|23>> |\>|23>> |\>|23>> > > > > > > > > > > > > > |\>|24>> |\>|24>> > |\>|24>> |\>|24>> |\>|24>> |\>|24>> |\>|24>> |\>|24>> |\>|24>> > > > > > > > > |\>|26>> |\>|26>> |\>|26>> |\>|26>> |\>|26>> |\>|26>> > |\>|26>> |\>|26>> > > |\>|26>> |\>|26>> |\>|26>> |\>|26>> |\>|26>> |\>|26>> > > |\>|26>> > > > |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> > |>>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> > |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|27>> |\>|28>> |\>|28>> |\>|28>> > > > > > |\>|28>> |\>|28>> |\>|28>> |\>|28>> |\>|28>> |\>|28>> |\>|28>> > |\>|28>> |\>|28>> |\>|28>> |\>|28>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> > > > > |\>|29>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> |\>|29>> > |\>|29>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> > > |\>|30>> |\>|30>> |\>|30>> |\>|8>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> |\>|30>> > |\>|30>> |\>|30>> |\>|30>> |\>|30>> > > > |\>|31>> |\>|31>> |\>|31>> > |\>|31>> |\>|31>> |\>|31>> |\>|31>> |\>|31>> > > > > > > > > > > > > > > > |\>|32>> |\>|32>> > |\>|33>> |\>|34>> |\>|34>> |\>|34>> > > > |\>|34>> > > > > > > |\>|35>> > |\>|35>> |\>|35>> > > > > > |\>|36>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> > |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> |\>|37>> > > > |\>|39>> > |\>|39>> > > |\>|39>> > > > > > > > > > > > > > |\>|40>> |\>|40>> |\>|40>> |\>|40>> > |\>|40>> |\>|40>> |\>|40>> |\>|40>> |\>|40>> |\>|40>> |\>|41>> |\>|41>> |\>|41>> > > > |\>|41>> |\>|41>> |\>|41>> |\>|41>> |\>|41>> |\>|41>> |\>|41>> |\>|41>> > > > > > |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> > > |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> > |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> |\>|42>> > > |\>|42>> |\>|42>> |\>|42>> > > > |\>|43>> |\>|43>> |\>|43>> > > > > |\>|43>> |\>|43>> |\>|43>> |\>|43>> |\>|43>> |\>|43>> |\>|43>> > > > > > > > > > > > > > > > > > > > > > > > |\>|47>> |\>|47>> |\>|47>> > > > > > |\>|48>> |\>|48>> > |\>|48>> |\>|48>> |\>|48>> > > > > > > |\>|6>> > |\>|10>> |\>|10>> |\>|10>> |\>|10>> |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|6>> |\>|11>> |\>|11>> > > |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|6>> > > |\>|11>> |\>|11>> |\>|11>> |\>|11>> |\>|11>> > > > |\>|6>> > |\>|12>> |\>|12>> |\>|12>> |\>|12>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|idx> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> <\associate|toc> |math-font-series||1Lineaarialgebra> |.>>>>|> |1.1Matriisien perusteet |.>>>>|> > |1.1.1Tulo |.>>>>|> > |1.1.2Käänteismatriisi |.>>>>|> > |1.1.3Lineaarialgebran derivointisääntöjä |.>>>>|> > |1.1.4Gaussin eliminaatio |.>>>>|> > |1.1.5Determinantti |.>>>>|> > |1.1.6Kanta |.>>>>|> > |1.1.7Gram-Schmidt-ortonormalisointi |.>>>>|> > |1.1.8Ominaisarvot ja -vektorit (eigenvalues & vectors) |.>>>>|> > |1.1.9Matriisifunktiot |.>>>>|> > |1.2Vektorit ja analyyttinen geometria |.>>>>|> > |1.2.1Vektoritulot |.>>>>|> > |1.2.2Suora |.>>>>|> > |1.2.3Taso |.>>>>|> > |1.2.4Tetraedri |.>>>>|> > |1.2.5Projektio |.>>>>|> > |1.3Homogeeniset koordinaatit |.>>>>|> > |1.3.1Ideaalipisteet, -suorat ja tasot |.>>>>|> > |1.3.2Duaalisuus ja lauseiden dualisointi |.>>>>|> > |1.4Kuvaukset (transformaatiot) |.>>>>|> > |1.4.1Lineaarikuvaus |.>>>>|> > |1.4.2Affiniteetti (affinikuvaus) |.>>>>|> > |1.5Matriisien sekalaisia sovelluksia |.>>>>|> > |1.5.1Pienimmän neliösumman sovitus (least squares fit) |.>>>>|> > |1.5.2Markovin ketjut |.>>>>|> > |math-font-series||2Differentiaalilaskentaa yleisesti> |.>>>>|> |2.1Differentiaali |.>>>>|> > |2.2Jacobian-matriisi |.>>>>|> > |2.3Monen muuttujan ketjusääntö |.>>>>|> > |math-font-series||3ODEt - ''tavalliset'' differentiaaliyhtälöt> |.>>>>|> |3.1Peruskäsitteitä |.>>>>|> > |3.2Yksittäisen ODEn tarkka ratkaiseminen |.>>>>|> > |3.2.1Separoituva: integrointi puolittain |.>>>>|> > |3.2.2Tasa-asteinen: muuttujan vaihto |.>>>>|> > |3.2.3Eksakti: osittaisderivointi |.>>>>|> > |3.2.4Eksaktiksi muuttaminen: integroiva tekijä |.>>>>|> > |3.2.51. kertaluvun lineearinen ODE: yleinen ratkaisu |.>>>>|> > |3.3Yksittäisen yhtälön likiarvoratkaisut |.>>>>|> > |3.3.1Suuntakenttä - erikoisratkaisu graafisesti |.>>>>|> > |3.3.2Picardin iteraatio - approksimoiva algebrallinen erikoisratkaisu |.>>>>|> > |3.42. asteen ODE |.>>>>|> > |3.51. asteen lineearinen homogeeninen ODE-ryhmä |.>>>>|> > |3.5.1Vaihekuvaaja |.>>>>|> > |3.6Laplace-muunnos |.>>>>|> > |math-font-series||4Sarjat> |.>>>>|> |4.1Suppenemisen testaus |.>>>>|> > |4.2Yleisimpiä sarjoja |.>>>>|> > |4.3Potenssisarjat |.>>>>|> > |4.4Fourier-sarja |.>>>>|> > |math-font-series||5Monen muuttujan analyysi> |.>>>>|> |5.1Avaruuspinta |.>>>>|> > |5.2Raja-arvo |.>>>>|> > |5.3Monen muttujan funktion differentiaalit |.>>>>|> > |5.3.1Osittaisderivaatta |.>>>>|> > |5.3.2Gradientti ja suunnattu derivaatta |.>>>>|> > |5.4Napakoordinaatisto |.>>>>|> > |5.5Monen muuttujan ääriarvotehtävät |.>>>>|> > |5.5.1Ääriarvopisteiden luokittelu (Hessian) |.>>>>|> > |5.5.2Rajoitetut ääriarvotehtävät (Lagrange-kertoimet) |.>>>>|> > |math-font-series||6Skalaari- ja vektorikentät> |.>>>>|> |6.1Viivaintegraali |.>>>>|> > |6.1.1Greenin lause (suljetun käyrän viivaintegraali) |.>>>>|> > |6.1.2Stokesin lause (moniulotteiset pinnat) |.>>>>|> > |6.2''Vektoriderivaatat'' - grad, div, curl |.>>>>|> > |6.3Divergenssilause (aka. Gaussin laki) |.>>>>|> > |math-font-series||7Kompleksiluvut> |.>>>>|> |7.1Kompleksiset funktiot |.>>>>|> > |math-font-series||8Abstrakti algebra> |.>>>>|> |8.1Ryhmät (groups) ja monoidit (monoids) |.>>>>|> > |8.2Renkaat (ring) ja kunnat (field) |.>>>>|> > |8.3Polynomirenkaat |.>>>>|> > |8.4Kooditeoria |.>>>>|> > |math-font-series||9Kombinatoriikka> |.>>>>|> |9.1Permutaatiot ja kombinaatiot |.>>>>|> > |9.2Inkluusio-ekskluusio-periaate |.>>>>|> > |9.3Binomi- ja multinomikertoimet |.>>>>|> > |9.4Generoivat funktiot eli emäfunktiot |.>>>>|> > |9.5Tornipolynomit (rook polynomials) |.>>>>|> > |9.6Differenssiyhtälöt eli rekursiot |.>>>>|> > |9.6.1Lineaariset ja vakiokertoimiset |.>>>>|> > |9.6.2Ratkaisu emäfunktioilla |.>>>>|> > |9.7Permutaatioryhmät ja ekvivalenssiluokat |.>>>>|> > |math-font-series||10Jaollisuus ja moduloaritmetiikka> |.>>>>|> |10.1Jaollisuussääntöjä |.>>>>|> > |10.1.1Suurin yhteinen tekijä (GCD) ja pienin yhteinen jaettava (LCM) |.>>>>|> > |10.1.2Lineaariset Diophanteen yhtälöt |.>>>>|> > |10.2Kongruenssi eli moduloaritmetiikka |.>>>>|> > |10.3Suuret alkuluvut |.>>>>|> > |10.3.1RSA-salakirjoitus |.>>>>|> > |math-font-series||11Graafit> |.>>>>|> |11.1Lauseita |.>>>>|> > |11.2Algoritmeja (ei-negatiivisesti) painotetuille graafeille |.>>>>|> > |11.3Kaksijakoinen graafi (bipartite graph) |.>>>>|> > |math-font-series||12Sekalaisia laskutekniikoita> |.>>>>|> |12.1Induktiotodistus |.>>>>|> > |12.2Neliöksi täydentäminen |.>>>>|> > |12.3Osamurtokehitelmä |.>>>>|> > |12.3.1Tapa 1: |x>:n valitseminen strategisesti |.>>>>|> > |12.3.2Tapa 2: yhtälöryhmä eri asteisista termeistä |.>>>>|> > |12.3.3Tapa 3: Heavisiden peittomenetelmä |.>>>>|> > |12.4Logaritmi |.>>>>|> > |12.5Raja-arvo |.>>>>|> > |12.6Trigonometristen funktioiden ominaisuuksia |.>>>>|> > |math-font-series||13Merkintätapoja> |.>>>>|> |13.1Tavalliset lukujärjestelmät |.>>>>|> > |13.2Kreikkalaiset kirjaimet |.>>>>|> > |math-font-series||Hakemisto> |.>>>>|>