Matematik
Side 2 - Diskret matematik
Svar #21
11. februar 2006 af Sabrina (Slettet)
Jeg har læst dine svar til mine krumningsspørgsmål og har forstået dem (sad og lavede en illustrativ tegning imens).
ad #12 (10)
Så vi har altså, at
(p v r)^(non r v s)^(p v q) --> p v s
Men hvorfor må vi så blot udtage to af præmisserne og konklusionen, hvorefter vi bruger slutningsreglen på dem?
ad (15)
Har du ikke byttet om på store O og lille o?
Mange tak for dine andre svar også - til dem har jeg faktisk ikke flere uddybende spørgsmål.
19)
I min bog er en definition på en geometrisk talfølge:
En talfølge på formen
a, ar, ar^2, ... , ar^n
hvor a er "the initial term" og r er "common ratio".
I et eksempel har vi så talfølgen {c_n} med c_n=2 * 5^n
Listen med leddene c_1, c_2, ... begynder med
10, 50, 250, 1250, ...
Hvorfor er a ikke lig med 2 og r med 5? Bogen siger, at a er lig med 10 i dette tilfælde.
Min forelæser sagde, at det skyldtes forskydning af index, men hvad er det?
Du må have en god weekend!
Svar #22
12. februar 2006 af Sabrina (Slettet)
20) Hvorfor er f(n)=n^2 bijektiv?
Til ethvert kvadrattal hører vel to værdier for n?
21) Jeg har et eksempel, hvor kompleksiteten af bubble sorteringsalgoritmen udregnes.
Jeg finder ud af at antal sammenligningerne er:
Summation fra i=1 til n-1 af (2(n-i)+1)+n
= n+n-1+2 * summation fra i=1 til n-1 af (n-i)
= 2n-1+n(n-1)
Hvordan kommer man til det sidste udtryk fra det 2. udtryk?
22) Jeg skal undersøge kompleksiteten af den lineære søgealgoritme.
Best case bliver n+2 sammenligninger.
Så siger min forelæser, at (n+2) er store O af n. Skal det ikke være omega af n? Omega er vist det, du kalder lille o-notation.
Opfølger på 19)
Jeg har endnu et eksempel på forskydning af index. Det er fra et eksempel på rekursiv definition.
Fibonaccitallene 0, 1, 1, 2, 3, 5, 8
Tal 0 siges at være vores fibonaccital nr. 0
Basistrin:
fib(0):=0
fib(1):=1
Rekursivt trin:
fib(n):=fib(n-1)+fib(n-2), n >= 2
Så langt så godt. Så kommer der, at vi skal bevise vha. induktion at
fib(n) =< ((1+sqrt(5))/2)^n for n >= 0
Her siger min forelæser så, at der er forskydning af index.
Hvad menes hermed, hvordan ses det og hvorfor gøres det?
Det haster ikke med svar :)
Svar #23
12. februar 2006 af allan_sim
Jeg tillader mig lige at bryde ind i jeres interessante tråd :-)
19) Den geometrisk talfølge er på formen a*r^0, a*r^1, a*r^2..., mens den givede talfølge er på formen a*r^1, a*r^2, a*r^3....
Vi forskyder derfor indeks, så første led i din følge svarer til første led i den geometriske. Dvs. at udregningen 2*5^1=10 skal svare til a*r^0 fra den geometriske følge. Da a*r^0=a, må vi slutte, at a=10. Herefter stemmer følgerne overens ved forskydningen.
20) Mon ikke der er tale om en funktion, hvis definitionsmængde er begrænset til de naturlige tal (deraf n)? Ellers har du ret.
21) Helt generelt gælder at summen af de første n naturlige tal kan udregnes som n*(n+1)/2 (dette kan vises ved induktion). Da må summen af de første n-1 naturlige tal kunne skrives som (n-1)*n/2. Da sidste led i dit udtryk er lig med produktet af 2 og denne sum, må leddet være lig med 2*((n-1)*n/2)=(n-1)*n.
Svar #24
12. februar 2006 af fixer (Slettet)
#21
15) Nej, men til gengæld har jeg vendt et ulighedstegn forkert. Der burde retteligt stå 2n-1 >= n for n>1. Som du nævner, kaldes lille o også for Omega.
#22
19) Forskydningen er sket i opskrivningen af rekursionen. Den lyder ellers
F_(n+1) = F_n + F_(n-1), n >= 1 (*)
og den er sikkert foretaget for at få det pæne udtryk F_n =
Tages udgangspunkt i (*) gælder nemlig
F_n =
og induktionen forløber som følger:
Kald formel (**) P(n). Hvis n = 1 så er F_1 = 1 = phi^0 = phi^(1-1) så P(1) er sand. Dernæst bemærkes at også P(2) er sand idet F_2 = 1 < 1.6 < phi^1 = phi^(2-1). Antag så at alle P(1), P(2),...,P(n) er sande og n > 1. Så er specielt P(n-1) og P(n) sande, så F_(n-1) =
F_(n+1) = F_(n-1) + F_n =
Men 1+phi=phi² og derfor er F_(n+1) =< phi^n, hvilket er P(n+1). Af induktionsaxiomet følger så, at P(n) er sand for alle n>1.
Svar #25
12. februar 2006 af Sabrina (Slettet)
Du skal være velkommen til at blande dig igen, hvis du får lyst :)
ad 21)
Jeg forstår ikke helt, hvor summationen af (n-i) forsvandt hen.
Derudover så er jeg ikke helt med på, at summen af de første n-1 tal er (n-1)n/2? Burde det ikke være n^2/2?
#24 Atter mange tak for dine svar (også omkring mit C-spørgsmål)!
ad 15)
Nu har jeg så, at der står
"Idet f(n)=2n-1 er f(n) tydeligvis O(n), thi 2n-1 >= n for n>=1. Men der gælder også, at f(n) er o(n), thi 2n-1 >= n for n>1. Derfor er f(n) Theta(n)."
Hvor er forskellen på O og o nu blevet af?
ad 22)
Hvorfor fås pænere udtryk ved at forskyde index?
Er det den eneste idé, der er i at forskyde index?
Hvis vi har
F_(n+1) = F_n + F_(n-1), n >= 1
og
F_n =
Hvordan kan det så blive til
F_n = F_(n-1) + F_(n-2) n >= 2
og
F_n =< phi^n
Svar #26
12. februar 2006 af allan_sim
Er du med på, at
n
sum i = n*(n+1)/2
i=1
Summererer vi kun op til n-1, får vi da, at vores liste af tal er (n-1), (n-2), (n-3), ..., (n-(n-1)) (som er lig med 1) - dvs. vi har en liste af tallene 1 op til n-1 (blot i omvendt rækkefølge). Følgeligt kan vi bruge ovenstående summation, hvor n erstattes af n-1 og får da, at
n-1
sum (n-i) = (n-1)*(n-1+1)/2 = (n-1)*n/2
i=1
Giver det mening? Hvis ikke, så prøv at starte med at vise den første summation ved hjælp af induktion.
Svar #27
12. februar 2006 af allan_sim
"Summerer vi kun op til n-1" -> "Summerer vi kun op til n-1 i summationen af n-i"
Svar #28
12. februar 2006 af fixer (Slettet)
ad 15)
Nej, det er bestemt ikke det der står. Sammenlign #19 (15) med den korrektion jeg selv kom med i #20 og som jeg gentager i #24.
ad 21)
Som nævnt kan det ved induktion vises, at
sum[i=1->n]{i} = ½n(n+1)
Med m = n-1 fås derfor
sum[i=1->m]{i} = ½m(m+1) = ½n(n-1)
I deltaljer haves for dit udtryk
n+sum[i=1->n-1]{2(n-i)+1} =
n+1*(n-1)+2*sum[i=1->n-1]{n-i} =
2n-1+2(n(n-1)-½n(n-1)) =
2n-1+2(n²-n+-½n²+½n) =
2n-1+n(n-1)
ad 22)
Som vist gælder F_n =< phi^(n-1) kun for alle positive heltal n (d.v.s. n>0). Såfremt den skal gælde for n>=0 skal grænsen være F_n =
Svar #29
12. februar 2006 af Sabrina (Slettet)
#26+28 Nu gav det mening med summationen (og også de andre spørgsmål) :)
Kan jeg lokke en af jer til at se på mit spørgsmål 22 og ad #12 (10) i tråd #21?
Svar #30
13. februar 2006 af fixer (Slettet)
f(n)=n+2 er O(n) idet f.eks n+2 =0. Men f er også o(n) idet f.eks. n+2 >= ½n, n>0. Derfor er f faktisk Theta(n).
#12(10)
Når der er sandt at
(p v r) ^ (non r v s) ^ (p v q)
sluttes af de to første præmisser, at p v s også er sand. Der er ikke noget forkert i denne slutning. Hvis præmisserne er sande, så kan vi faktisk slutte at p v s. Men det tredie præmis er jo også sandt, så vi kan faktisk drage den mere omfattende slutning, at p v (s ^ q).
Så hvis præmisserne er sande, så slutter vi
p v (s ^ q) = (p v s) ^ (p v q) (*)
hvoraf, da (*) er sand, vi både kan slutte at p v s og at p v q.
Svar #31
16. februar 2006 af Sabrina (Slettet)
Jeg har læst og forstået #30.
Jeg har faktisk lige pt. ikke flere spørgsmål.
I får mange tak for jeres hjælp! :)
Og et specielt tak til fixer for din fantastiske tålmodighed!
Skriv et svar til: Diskret matematik
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.