Laborationen ger träning på
grundläggande programmering,
repetitionssatser, villkorssatser, vektorer.
Inspektera gärna vektorerna, men tänk på att du har att göra med rätt stora datamängder. Du vill t.ex. inte skriva ut alla elementen i vektorerna. Även om du packar sifrorna tätt och t.ex. skriver 91 siffror per rad och 67 rader per sida och använder rätt litet typsnitt (10 punkters Courier) så krävs 1640 A4-sidor.
Lite matematik:
Ett tal är normalt (med avseende på en given bas, i denna lab har vi basen 10) om varje siffra (dvs. något av talen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) förekommer med ungefär samma relativa frekvens (1 / 10, för decimala tal). Man vet inte (enligt denna MathWorld-artikel) huruvida pi och e är normala tal, så din uppgift kommer att vara att undersöka de 5000000 första siffrorna i pi och e för att forma en hypotes. Verkar pi och e vara normala?
Vi vill undersöka ytterligare några egenskaper.
>> pi5(710100:710108)' % sju treor i rad
ans =
7 3 3 3 3 3 3 3 8
Man undrar då kanske:
Nu till uppgifterna:
Hur man testar sitt program:
Det finns många teorier kring hur man bäst testar sitt program. Först några citat:
Program testing can be used to show the presence of bugs, but never to show their absence!
Edsger Dijkstra
A bug-free program is an abstract. theoretical concept.
Dennie Van Tassel
All sufficiently complex programs have bugs.
Anonymous
An effective way to test code is to exercise it at its natural boundaries.
Brian Kernighan
Normalt kan vi inte vara helt säkra på att ett program fungerar i alla detaljer. De flesta program fungerar nog under normal drift, men kan nog räkna fel vid ovanliga indata. Här finns många skräckhistorier: Collection of Software Bugs, Software horror stories. Programmen i denna lab är dock tämligen enkla och vi kan genom omsorgsfull programmering och testning övertyga oss om att de (nog) är bugfria. Absolut säkerhet uppnår vi aldrig. Även om vårt program är korrekt, så körs det ju i Matlab (som är ett stort komplicerat program), på en mycket komplex apparat (en dator) som styrs av Linux (eller Windows), ännu ett stort programsystem.
När man testar sitt program bör man ha med några typiska fall, men även undantagsfall (som Brian Kernighan förordar i sitt citat). Man gör nog ofta rätt på normalfallet, men tänker sig inte för vid ovanliga fall. Slumpdata är inte så användbara som skulle kunna tro, eftersom de brukar vara rätt så snälla. Om man t.ex. vill testa en rutin för att beräkna egenvärden till en matris, så ger slumpdata snälla matriser. Svåra problem har t.ex. multipla egenvärden, ett undantagsfall.
Några typiska testdata för sekvensproblemet (den andra uppgiften):
tal = 1; % vektorlängd ett, dessutom finns inte alla siffror med
tal = [1, 1, 1, 1, 1]; % en sekvens som avslutas med att vektorn "tar slut"
tal = [1, 1, 1, 1, 1, 2]; % här avslutas sekvensen med annan siffra
% sekvenser av olika längder (med samma siffra), den längsta sekvensen kommer inte sist
tal = [2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 2, 4, 5, 5, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1];
% slumpdata är normalt enkla, och därmed inte så intressanta ur testsynpunkt
tal = floor(10 * rand(50, 1));
I denna lab kör vi programmet i en kontrollerad omgivning. Om programmet skall användas av andra personer, eller anropas av ett annat program vill man nog bygga in mer säkerhet i koden. Den bör kunna hantera felaktiga indata, t.ex. en tom vektor, tal = []; eller en vektor som inte innehåller enbart decimala siffror, tal = [2, -5, 14]; . Skilj mellan felaktiga indata och ovanliga fall (ett ensiffrigt tal).
Introduktion:
På mat-filen /chalmers/groups/thomas_math/MATL/pie.mat
(en mat-fil innehåller data i Matlabs eget binära format)
hittar du två
vektorer, pi5
samt e5,
med de 5000000 första
siffrorna i pi respektive e. Du kan också hämta filen via denna HTML länk.
(Om du sitter i Windows-salen hittar du filen i katalogen:
\\sol.ita.chalmers.se\groups\thomas_math\MATL)
Kopiera filen till katalogen där du har dina andra Matlabfiler. Ladda sedan in innehållet (vektorerna pi5 och e5) till Matlab med kommandot load
>> load pie.mat
Inspektera gärna vektorerna, men tänk på att du har att göra med rätt stora datamängder. Du vill t.ex. inte skriva ut alla elementen i vektorerna. Även om du packar sifrorna tätt och t.ex. skriver 91 siffror per rad och 67 rader per sida och använder rätt litet typsnitt (10 punkters Courier) så krävs 1640 A4-sidor.
Om du
vill inspektera
en del av vektorn i Matlab, skriv t.ex.
>>
pi5(1:32)' % '
= transponat
ans =
Columns 1
through 16
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9 3
Columns
17 through 32
2
3
8
4
6
2
6
4
3
3
8
3
2
7
9 5
>>
pi5(1000000:1000005) %
siffror
nummer 1000000
till och
med 1000005
ans =
5
1
3
0
9
2
>>
pi5(end-5:end)' %
de sex sista
siffrorna
ans =
4
6
1
9
7 1
>>
e5(1:16)'
% analogt för e
ans =
2
7
1
8
2
8
1
8
2
8
4
5
9
0
4 5
Anledningarna till att labben innehåller så stora datamängder
är bland andra:
- Det gör programskrivandet lite mer realistiskt, eftersom det är vanligt med stora datamängder i beräkningar. Skriver man alltför ineffektiva program blir exekveringstiden för lång.
- Eftersom man inte kan skaffa sig facit (genom handräkning),
så
måste man skriva en kod som man kan lita på. Detta gör
det nödvändigt att
testa koden.
Lite matematik:
Ett tal är normalt (med avseende på en given bas, i denna lab har vi basen 10) om varje siffra (dvs. något av talen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) förekommer med ungefär samma relativa frekvens (1 / 10, för decimala tal). Man vet inte (enligt denna MathWorld-artikel) huruvida pi och e är normala tal, så din uppgift kommer att vara att undersöka de 5000000 första siffrorna i pi och e för att forma en hypotes. Verkar pi och e vara normala?
Vi vill undersöka ytterligare några egenskaper.
>> pi5(710100:710108)' % sju treor i rad
ans =
7 3 3 3 3 3 3 3 8
Man undrar då kanske:
- Vilken är den längsta sekvensen av treor (eller
någon annan
siffra)?
- Hur vanliga är långa sekvenser?
Nu till uppgifterna:
 |
Uppgift 1: Skriv en
Matlabfunktion som
räknar ut antalet gånger siffrorna 0 till 9 förekommer i pi5 (eller
e5). Låt funktionen ha en inparameter, en vektor.
Det skall räcka att anropa funktionen en
gång för att få ut alla resultat. Man anropar lämpligen funktionen från
ett huvudprogram som sköter utskrifter och liknande. Tips: när du skall gå igenom en så pass lång vektor är det effektivt att gå igenom den en gång istället för att gå igenom den upprepade gånger. Detta gäller inte bara i denna uppgift. Frivilligt: Om du vill kan du studera följande kvantitet. Låt f(n, d) vara antalet gånger siffran d förekommer bland de n första siffrorna i talet. Plotta f(n, d) / n (för olika d). Detta liknar ett gränsvärde, relativa andelen när antalet siffror ökar. Gränsvärdet är 0.1 om talet är normalt. |
|
Uppgift 2: Skriv en
Matlabfunktion som
räknar ut längsta sekvensen av siffran d, när d = 0, 1,
..., 9, i en talvektor. Programmet skall också tala om var i talet
dessa längsta sekvenser finns. I exemplet ovan finns siffran tre,
sju gånger i rad. Denna sekvens hittar man från siffra
710101 till och med siffra 710107. Det räcker att skriva ut de första gränserna,
710101,
710107, ifall det skulle finnas flera sekvenser med sju treor. Det
skall räcka att anropa funktionen en
gång för att få ut alla resultat (man skall inte behöva anropa den tio
gånger, vilket inte hindrar att du kan ha ytterligare en funktion som
anropas för en enstaka siffra, d). Man anropar lämpligen
funktionen från ett huvudprogram som sköter utskrifter och liknande. Testa din funktion på följande vektorer (så att du ser att den fungerar): tal = 1; % vektorlängd ett, dessutom finns inte alla siffror med tal = [1, 1, 1, 1, 1]; % en sekvens som avslutas med att vektorn "tar slut" tal = [1, 1, 1, 1, 1, 2]; % här avslutas sekvensen med annan siffra % sekvenser av olika längder (med samma siffra), den längsta sekvensen kommer inte sist tal = [2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 2, 4, 5, 5, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1]; |
|
Uppgift 3: Skriv en
Matlabfunktion som
räknar ut antalet sekvenser av längd ett, antalet sekvenser
av längd två etc. Ex: tal = [1, 2, 2, 1, 1, 1, 4, 4, 4, 4, 5, 5, 5, 1, 7, 9] har fyra sekvenser av längd ett, en av längd två, två av längd tre och en av längd fyra. Det skall räcka att anropa funktionen en gång för att få ut alla resultat. Man anropar lämpligen funktionen från ett huvudprogram som sköter utskrifter och liknande. |
Hur man testar sitt program:
Det finns många teorier kring hur man bäst testar sitt program. Först några citat:
Program testing can be used to show the presence of bugs, but never to show their absence!
Edsger Dijkstra
A bug-free program is an abstract. theoretical concept.
Dennie Van Tassel
All sufficiently complex programs have bugs.
Anonymous
An effective way to test code is to exercise it at its natural boundaries.
Brian Kernighan
Normalt kan vi inte vara helt säkra på att ett program fungerar i alla detaljer. De flesta program fungerar nog under normal drift, men kan nog räkna fel vid ovanliga indata. Här finns många skräckhistorier: Collection of Software Bugs, Software horror stories. Programmen i denna lab är dock tämligen enkla och vi kan genom omsorgsfull programmering och testning övertyga oss om att de (nog) är bugfria. Absolut säkerhet uppnår vi aldrig. Även om vårt program är korrekt, så körs det ju i Matlab (som är ett stort komplicerat program), på en mycket komplex apparat (en dator) som styrs av Linux (eller Windows), ännu ett stort programsystem.
När man testar sitt program bör man ha med några typiska fall, men även undantagsfall (som Brian Kernighan förordar i sitt citat). Man gör nog ofta rätt på normalfallet, men tänker sig inte för vid ovanliga fall. Slumpdata är inte så användbara som skulle kunna tro, eftersom de brukar vara rätt så snälla. Om man t.ex. vill testa en rutin för att beräkna egenvärden till en matris, så ger slumpdata snälla matriser. Svåra problem har t.ex. multipla egenvärden, ett undantagsfall.
Några typiska testdata för sekvensproblemet (den andra uppgiften):
tal = 1; % vektorlängd ett, dessutom finns inte alla siffror med
tal = [1, 1, 1, 1, 1]; % en sekvens som avslutas med att vektorn "tar slut"
tal = [1, 1, 1, 1, 1, 2]; % här avslutas sekvensen med annan siffra
% sekvenser av olika längder (med samma siffra), den längsta sekvensen kommer inte sist
tal = [2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 2, 4, 5, 5, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1];
% slumpdata är normalt enkla, och därmed inte så intressanta ur testsynpunkt
tal = floor(10 * rand(50, 1));
I denna lab kör vi programmet i en kontrollerad omgivning. Om programmet skall användas av andra personer, eller anropas av ett annat program vill man nog bygga in mer säkerhet i koden. Den bör kunna hantera felaktiga indata, t.ex. en tom vektor, tal = []; eller en vektor som inte innehåller enbart decimala siffror, tal = [2, -5, 14]; . Skilj mellan felaktiga indata och ovanliga fall (ett ensiffrigt tal).