MAT-INF1100 - forelesningsrapport, h?sten 2011

Her vil det komme en kort rapport om hva som ble gjennomg?tt p? hver forelesning.

Tirsdag 29/11. I dag var det tid for repetisjon. I f?rste time skrev jeg opp en innholdsfortegnelse for kurset og kommenterte de ulike delene. I andre time gjennomgikk jeg feilanalyse for den enkleste derivasjonsmetoden (uten avrundingsfeil) og midtpunktmetoden for numerisk integrasjon.

Mandag 28/11. Vi avsluttet de ordin?re forelesningene ved en rask gjennomgang av digital lyd og digitale bilder, kapitlene 8 og 16 i kompendiet. Vi s? f?rst hva lyd faktisk er, og s? at sin og cos kan brukes til ? lage s?kalte 'rene' toner. Vi lekte litt med dette, f?r vi s? p? teorem 8.8 som sier at en vilk?rlig funksjon kan bygges opp ved hjelp av sin og cos. Ut fra dette s? vi rent intuitivt p? det s?kalte samplingsteorem, og hvordan omskriving av lyd til et format med sin og cos kan utnyttes til kompresjon. 

Vi definerte s? hva et digitalt bilde er, s? hvordan vi kan konveretere en fargebilder til gr?toner og hvordan en god del andre, naturlige operasjoner kan gj?res p? bilder.

Tirsdag 22/11. Vi fortsatte med aritmetisk koding, i dag med detaljert algoritme. Vi s? f?rst hvordan vi ved hjelp av en enkel line?r funksjon kan krympe intervallet [0,1] til et vilk?rlig delintervall av [0,1]. Ved hjelp av dette er det relativt lett ? sette opp en algoritme for aritmetisk koding og utlede optimalitetsegenskapene, se seksjon 7.4.2 og 7.4.3 i kompendiet. Dekoding ble ikke forelest, men er ganske enkelt n?r man har skj?nt hovedalgoritmen.

Mandag 21/11. I dag dreide deg seg om informasjonsentropi og aritmetisk koding. Vi innf?rste f?rste informasjonsentropi som et m?l p? hvor mye vi kan komprimere en gitt tekst (seksjon 7.3 i kompendiet). Deretter gjennomgikk vi ideen bak aritmetisk koding, seskjon 7.4.1 i kompendiet.

Tirsdag 15/11. Vi begynte med noen kommentarer om forskjellen p? det ? lagre en tall ved hjelp av sin bin?re representasjon og ved ? lagre dem som tekst (de desimale sifrene). Deretter gikk vi over til ? se p? hvor mye plass en bok, en lydfil og en film tar opp n?r det lagres p? datamaskin. Ut fra dette s? vi behovet for kompresjon (se seksjon 7.1 i kompendiet). Deretter gjennomgikk vi seksjon 7.2 om Huffman-koding.

Mandag 14/11. Vi gjennomgikk i dag stoffet om representasjon av tekst og annen informasjon p? datamaskin, seksjonene 4.3 og 4.4 i kompendiet. Vi s? p? prinsippene bak ASCII, Iso Latin og Unicode i detalj og pratet ogs? om problemer ved konvertering mellom de ulike kodingene.

Tirsdag 8/11. Tema i dag var l?sning av andreordens line?re differensialligninger med konstante koeffisienter — l?sning ved formel, ikke numerisk. Vi gjennomgikk f?rst l?sningsprosedyren for homogen ligninger, seksjon 10.5 i Kalkulus, og deretter prosedyren for inhomogene ligninger. Merk at det hele er veldig likt l?sningsprosedyren for andreorden line?re differensligninger med konstante koeffisienter, s? pass p? s? du ikke blander sammen!

Mandag 7/11. I dag avsluttet vi stoffet om numerisk l?sning av differensiallignigner. Aller f?rst repetert jeg ideen bak Eulers metode og hvordan den kan utvides til Taylor metoder av h?yere orden (ved ? derivere differensialligningen) og Eulers midtpunktmetode (Runge-Kutta metodene). Deretter gikk vi over til ? se hvordan systemer av ligninger kan skrives kompakt p? vektorform, og hvordan de numeriske metodene lett kan tilpasses slike systemer, se seksjon 14.8 i kompendiet. Endelig s? vi hvordan h?yere ordens ligninger kan omskrives til et system av f?rsteordens ligninger. Til slutt gjennomgikk vi feilanalysen for Eulers metode i seksjon 14.4.

Tirsdag 1/11. Vi fortsatte i kapittel 14 med seksjon 14.5, der vi forklarte hvordan vi kunne finne de h?yere deriverte til en l?sning av en differensiallikning ved ? derivere selve likningen. Dette ga opphav til bedre tiln?rminger til l?sninger av likningen , ved at man tok med flere h?yere ledd i Taylorrekken. Vi s? spesielt p? kvadratisk Taylor, der man tar med et ekstra ledd i tiln?rmingen sammenlignet med Eulers metode. Vi s? p? algoritmer og kodeeksempler for Euler og kvadratisk Taylor, og forklarte hva den globale feilen blir for Euler, kvadratisk Taylor, og h?yere ordens Taylormetoder. Vi avsluttet med ? forklare litt om Runge-Kutta metoder, som kan gi tiln?rmingsmetoder med enda mindre global feil.

Tirsdag 25/10. Vi startet med ? avslutte kapittel 12 i kompendiet om numerisk integrasjon: F?rst gjorde vi global feilanalyse for midtpunktsmetoden, deretter motiverte og definerte vi trapesmetoden og Simpsons metode, med tilh?rende feilanalyse. Vi fortsatte med Kapittel 10 i Kalkulus, der vi s? p? f?rsteordens line?re differensiallikninger (eksistens og entydighet, l?sningsformel, eksempler, og anvendelser), og separable differensiallikninger (t.o.m 10.4). 

Mandag 17/10. Tema i dag var numerisk derivasjon, kapittel 11 i kompendiet. Vi utledet den enkleste metoden rett fra definisjonen av den deriverte, utledet trunkeringsfeilen, og studerte s? avrundingsfeil for denne metoden. Essensen i det hele er utledning av formelen 11.14. Det som kommer etterp? i seksjon 11.1.3 er egentlig bare pynting av denne formelen. Vi rakk bare fram fram til og med observasjon 11.11, resten av seksjon 11.1 tar vi i morgen. For de andre seksjonene vil vi bare nevne metodene og ikke utlede feilestimatene.

Tirsdag 4/10. Vi  startet med ? g? gjennom resten av stoffet om halveringsmetoden. Vi forbedret algoritmen for denne slik at den avsluttet etter et gitt antall iterasjoner, og avsluttet n?r den relative feilen ble liten nok. Vi testet den nye algoritmen for ? finne roten av 2, som jo kan skrives som nullpunktet til en annengradsfunksjon. Deretter forklarte vi ideen bak sekantmetoden, formulerte en algoritme for denne, og forklarte hvorfor denne konvergerte raskere enn halveringsmetoden. Til slutt gikk vi gjennom de samme trinnene for Newtons metode. Samme programmeringseksempel ble brukt for de tre metodene, for ? demonstrere at newtons metode konvergerer enda litt raskere enn sekantmetoden, som igjen konvergerer enda raskere enn halveringsmetoden. Koden for disse eksemplene er lagt ut sammen med forelesningsnotatet.

Mandag 3/10. I f?rste time repeterte vi kjapt polynominterpolasjon, og s? deretter hvordan interpolasjonspolynomet kan beregnes ved hjelp av dividerte differenser, se seksjon 9.3 i kompendiet. I andre time begynte vi p? kapittel 10 i kompendiet og presiserte f?rst forskjellen p? det ? l?se en ligning med formel og ved hjelp av det ? beregne en numerisk tiln?rming til l?sningen. Med dette p? plass utledet vi halveringsmetoden, se seksjon 10.2 i kompendiet.

Tirsdag 27/9. Vi tok f?rst slutten av eksempel 11.2.5 og deretter eksempel 11.2.6 f?r vi gikk over p? polynominterpolasjon, seksjon 9.2 i Kompendiet. Vi definerte interpolasjonsproblemet, innf?rte Newton-formen og s? at interpolasjonspolynomet er entydig. Vi s? deretter p? noen eksempler og innf?rte dividerte differenser, men rakk ikke ? gjennomg? algoritmen for ? beregne interpolasjonspolynomet.

Mandag 26/9. Vi startet med ? repetere konstruksjonen av Taylor-polynomer, og s? deretter hvordan vi kan utlede en formel for restleddet (eller feilen) vi gj?r n?r vi erstatter en funksjon med sitt Taylor-polynom, seksjon 11.2 i Kalkulus. Til slutt s? vi p? de to eksemplene 11.2.4 og 11.2.5 i Kalkulus.

Tirsdag 20/9. I dag var tredje dag med differensligninger som tema. Vi s? nok en gang at differensligninger kan 'l?ses' p? to m?ter: Ved formel eller ved eksplisitt utregning av leddene, s?kalt simulering av differensligningen. Vi formulerte en algoritme for simulering av andreordens ligninger og programmerte den i Python. Programmet ble testet p? Fibonacci-ligningen og differensligningen i eksempel 6.27 i kompendiet. For den siste ligningen observerte vi at den simulerte l?sningen etterhvert ble helt feil, og vi gjennomgikk forklaringen p? dette i seksjon 6.5.1, s?rlig sidene 135-136. Den siste halvtimen brukte vi p? Taylor-polynomer, seksjon 11.1 i Kalkulus. Vi endte opp med ? se at Eulers formel gir en forklaring p? sammenhengen mellom Taylor-polynomene for e^(ix), sin x og cos x.

Mandag 19/9. Vi fortsatte med differensligninger. Aller f?rst repeterte vi l?sningsprosedyren for andreordens homogene ligninger med konstante koeffisienter. Deretter gikk vi over p? inhomogene ligninger og hvordan disse kan l?ses, seksjon 4.2 i Kalkulus. Til slutt s? vi s? vidt p? det ? l?se differensligninger numerisk, begynnelse av kapittel 6 i kompendiet.

Tirsdag 13/9. Differensligninger var tema i dag, kapittel 4 i Kalkulus. Vi gjennomgikk hvordan andreordens, homogene differensligninger kan l?ses ved formel, og skilte mellom de tre tilfellene der det karakteristiske polynomet har to relle r?tter, en reell rot eller to kompleks konjugerte r?tter, alt hentet fra seksjon 4.1 i Kalkulus.

Mandag 12/9. Vi begynte med noe kommentarer om representasjon av heltall p? datamaskin f?r vi gikk over til ? se p? hvordan reelle tall kan representeres som s?kalte flyttall, seksjon 4.2 i kompendiet. Deretter gikk vi over til ? se hvordan aritmetikk (s?rlig addisjon) med flyttall kan gi feil, se seksjon 5.2 i kompendiet, og da s?rlig seksjon 5.2.3. Til slutt s? vi hvordan uttrykk kan omskrives for ? unng? store avrundingsfeil (seksjon 5.4) og hvordan feil m?les (seksjon 5.3).

Tirsdag 6/9. Vi begynte med et eksempel p? hvordan heltall representeres i to-tallsystemet. Deretter gikk vi over til ? se hvordan reelle tall mellom 0 og 1 kan representeres i ulike siffersystemer, seksjon 3.3 i kompendiet. Vi gjennomgikk beviset for teorem 3.15 og oppsummerte beviset i algoritme 3.16. Vi s? ogs? at lemma 3.21 fulgte fra beviset for teorem 3.15. Deretter gjennomgikk vi lemma 3.22, uten bevis. De siste ti minuttene gjennomgikk vi hvordan heltall representeres p? datamaskin, seksjon 4.1 i kompendiet.

Mandag 5/9. I dag begynte vi med ? se p? kapittel 2 i kompendiet om hvorfor 0 og 1 er de grunnleggende symbolene p? en datamaskin. Deretter gikk vi over til ? se p? hvordan heltall kan representeres i ulike siffersystemer, seksjon 3.2 i kompendiet.

Tirsdag 30/8. Vi fortsatte v?r gjennomgang av tall, og i dag var turen kommet til kompletthetsprinsippet, seksjon 2.3 i Kalkulus. Fokuset var p? intuisjon omkring tetthet, selv om mange nok synes dette er t?rt og vanskelig! Jeg snakket ogs? litt om tellbare mengder og viste at de rasjonale tallene er tellbare, og at de reelle tallene i [0,1] ikke er tellbare. Til slutt skulle vi ta for oss aksiomene for reelle tall, men det gikk ikke s? bra siden jeg ikke fikk bilde fra maskinen min opp p? veggen!

Mandag 29/8. Pascal's trekant og binomialformelen var tema for f?rste time. Vi s? p? problemet med ? ekspandere ut utrykket (a+b)^n og hvordan Pascals trekant naturlig dukker opp, seksjon 1.4 i Kalkulus. Vi innf?rte binomialkoeffisienter og s? at det er nettopp disse som dukker opp i Pascals trekant. Til slutt s? vi p? et eksempel p? bruk av binomialformelen. Etter pause gikk vi over p? reelle tall. Vi definerte intervallene og tallverdien av et tall, og utledet trekantulikheten (seksjon 2.1). Vi gjennomgikk s? setning 2.2.1 og Korollar 2.2.2, og endte med ? vise kvadratroten av 2 er et irrasjonalt tall (seksjon 2.2).

Tirsdag 23/8. Tema i dag var induksjon. Vi begynte med en sv?rt detaljert gjennomgang av induksjonsbeviset for formelen for summen av de n f?rste heltallene. Forh?pentligvis f?r det fram prinsippene for induksjon slik at du kan tilpasse induskjonsbevis til andre oppgaver. I andre timer s? vi litt p? det generelle induksjonsprinsippet, og gjennomgikk et induksjonsbevis for hvorfor n(n^2+5) alltid er delelig med 6.

Mandag 22/8. I f?rste time ga jeg en presentasjon av undervisningen og opplegget for MAT-INF1100. Etter pausen begynte vi p? pensum og gjennomgikk seksjon 1.1 i Kalkulus, inkludert summetegn og bytte av summasjonsindeks.

 

Av Knut M?rken
Publisert 2. aug. 2010 08:27 - Sist endret 29. nov. 2011 12:23