Diskret matematik

Hej Sabrina.

Jeg kom til at tænke på denne gamle tråd, hvor vi diskusterede noget af det samme, jvf. mine indlæg #15 og # 20.

https://www.studieportalen.dk/forum/viewtopic.php?t=127331.

I dit nye eksempel her, tror jeg notationen afviger i forhold til hvad vi plejer at bruge i forummet. I hvert fald vil jeg mene, at dit symbol '-->' i virkeligheden er '=>', altså implikationspilen.

Det ser nu ud som om du (igen) bakser med at notere logiske udsagn på en formaliseret måde. Jeg tror at stram præcision vil dig hjælpe i starten. Senere bliver alt det formelle ikke til at holde ud - men i starten er det ofte en hjælp.

Det er vigtigt, at du ved hvilke x'er du arbejder med, og hvis det er nødvendigt, så også noterer det. Domænet er alle personer - godt, lad så P betegne mængden af alle personer (i hele verden). Dit udsagn kan så gøres mere komplet, hvis du skriver:

A x€P: ( S(x) => C(x) )

("For enhver person gælder, at HVIS x er medlem af dette hold, SÅ har x (også) studeret analyse").

I lyset af denne præcisering må man spørge, hvad alternativet er til at sætte parenteserne på den måde, som du har angivet? Den alternative mulighed er, så vidt jeg kan se:

( A x€P: S(x) ) => C(x)

Men dette giver ingen mening, for i dette udtryk er det ikke angivet hvor 'x' i 'C(x)' kommer fra! Meningsløsheden træder frem, hvis du prøver at forklare i ord, hvad der står:

"HVIS ( for enhver person (i hele verden!) gælder, at personen er medlem af dette hold ) SÅ gælder ..." - ja, hvad gælder så? At et eller andet x har studeret analyse, javel ja, men kvantoren ("omvendt A") blev brugt inde i betingelsen og gælder ikke for konklusionen. Så det er ikke angivet hvilke x'er, der har studeret analyse. Det giver ingen mening. Parenteserne kan derfor kun meningsfuldt sættes sådan som du har gjort i dit indlæg. Eller også må man angive for hvilke x'er, man kan drage den konklusion at de har studeret analyse, ud fra den (drastiske ) antagelse at alle personer i hele verden går på holdet(!)

Bemærk i øvrigt, at dit udsagn kan udtrykkes således: For enhver person er medlemskab af dette hold en tilstrækkelig betingelse for at vedkommende har studeret analyse.

#1 Mange tak, Brian :)

Du har helt ret i, at jeg atter bakser med at notere logiske udsagn. I dag har jeg brugt 6 timer på at læse i min diskrete matematik bog og har kun fået læst 35 sider.
Jeg 'konsulterede' faktisk den gamle tråd, og det hjalp da også, men jeg skal bare hele tiden virkelig koncentere mig for at prøve at hitte rede på, hvornår noget er hhv. en nødvendig og en tilstrækkelig betingelse. Bogen bruger "only if" og "if and only if", hvilket godt kan virke forvirrende. Men jeg vil prøve at følge dit råd med at pensle tingene helt ud.

Grunden til jeg brugte --> var, at det gør min bog. Så jeg blev i tvivl om, man blot skrev sådan i diskret matematik.

Jeg har skimmet dit indlæg, men vil vente med at læse det mere grundigt til i morgen, hvor jeg kan se med friske øjne på det.

Undervejs i min læsning stødte jeg på et spørgsmål mere:
Hvorfor bygger slutningsreglerne (the rules of inference) på tauntologier?


Jeg har et andet eksempel, som jeg også har brugt lang tid på. Hvis du mener, at du svarer på det gennem det andet eksempel, er det helt fint - men nu skriver jeg det op, så kan du evt. se på det, hvis du orker.

"For every x in this class, x has the property that x has visited Mexico or x has visited Canada"

M(x): x has visited Mexico
C(x): x has visited Canada

Bogen siger så, at det kan skrives

A x (C(x) or M(x))

hvor domainet for x er eleverne i klassen.

Hvorfor kan vi ikke stadig udtrykke sætningen på den måde, hvis domainet var alle personer (i hele verden)? Så vil sætningen vel blive falsk, hvis vi prøvede at indsætte personer, som ikke gik i klassen, da følgende del af sætningen så ikke vil passe: "For every x in the class".


Pyh - det er godt nok indviklet :)

Jeg er virkelig taknemmelig for, at du gider hjælpe!

Inden for førsteordens prædikatlogik siger vi, at hvis udsagnet

p => q (*)

er en tautologi, da følger q logisk af p. Hvis altså (*) er sand uanset hvilke logiske værdier vi tilforordner prædikaterne, så slutter vi q.

På samme måde siger vi, at hvis

(p1/\\p2/\\.../\\pn) => q

er en tautologi, så følger q logisk af p1,p2,...,pn.

Et argument baseret på tautologier kaldes slet og ret en slutningsregel - 'rule of inference'.

Som eksmepel kan tages udsagnet

((p=>q)/\\(q=>r))=>(p=>r) (**)

som er en tautologi. Prøv evt at ovrebevise dig om dette. Da (**) er en tautologi er følgende argument gyldigt

p=>q
q=>r
-----
p=>r

Populariseret:

Hvis du investerer i aktiemarkedet, bliver du rig.
Hvis du bliver rig, bliver du lykkelig.
-------------------------------------------------
Hvis du investerer i aktier, bliver du lykkelig.

At slutningsreglerne må baseres på tautologier skyldes kun da kan drage konklusioner om q's sandhedsværdi i (*). De andre alternativer er, at (*) er en absurditet (altid falsk) eller en eventualitet (sand eller falsk afhængigt af præmisserne). Hvorledes skal vi i disse to sidstnævnte tilfælde kunne drage slutninger vedrørende q's sandhed?

Angående dit sidste spørgsmål i #2:

Alkvantoren anvendes som universel kvantisering til at udtrykke at et logisk prædikat er _sandt_ for alle "ting" (eller alle relevant "ting"). Du kan således ikke anvende det foreslåede domæne, thi det er jo netop _ikke_ sandt for alle x, kun dem fra klassen.

Iøvrigt slog det mig, at din notation i #0 fra lærebogen måske kunne indikere, at din lærebog anvender subjunktioner og bisubjunktioner, fremfor implikationer og biimplikationer.

Jeg skrev engang et indlæg desangående; at dømme på responsen blev det vist forbigået i tavshed. Du kan måske som den første lokkes til at læse det.

Se indlæg #10:
https://www.studieportalen.dk/forum/viewtopic.php?t=137387&h=subjunktion

Så fik jeg endelig læst begge jeres indlæg dybtegående. Det hjalp mig utrolig meget!

#1 Takket være din lange forklaring om, hvorfor A xeP skal stå uden for parantesen, giver det fuldt ud mening.


#3 Mange tak for dit udpenslende svar!
Hvis vi har slutningsreglen
p=>q
q=>r
-----
p=>r
For at bruge den er det så nødvendigt, at p=>q er sand, og at q=>r er sand? Eftersom reglen bygger på en tautologi, er den jo sand uanset hvad vi vælger udsagnene inde i tautologien til at være.
Men hvad kan vi så slutte, hvad q=>r og p=>q er falske? - at p=>r er falsk? Eller hvad hvis q=>r er sand, men p=>q falsk?

Til gengæld forstod jeg nu, hvorfor jeg ikke kan anvende mit forslag til et domaine i #2.

Jeg har læst dit indlæg i den tråd, som du henviser til.
Du skriver på et tidspunkt: "Subjunktionen A->B tilordner udsagnet C værdien sand undtagen når udsagn A er sand og udsagn B samtidigt falsk."
Gælder at C: A->B? Så C er udsagnet A->B?



I løbet af i går dukkede der 'lidt' flere spørgsmål op - nogle hurtigere besvaret end andre, men håber I gider tage jer tid til at se på nogle af dem.


1) p <-> q
Her skriver lærebogen, at "p hvis og kun hvis q".
Det betyder, at "p er sand, hvis og kun hvis q er sand", men kan vi på samme måde indsætte ordet falsk, så der står "p er falsk, hvis og kun hvis q er falsk"?
Jeg er ved at prøve at tænke mig til, hvorfor p<->q er sand, hvis p og q begge er falske.


Dette hænger nok også samme med, at jeg har svært ved at se, at det giver mening, at implikationen p->q kun er falsk, når p er sand, og q er falsk?

2) I forbindelse med et eksempel tilknyttet slutningsreglerne skrev min forelæser følgende:
r->p, not r->s, s->t er opfyldt
Ønsker at slutte at t er opfyldt

Menes med opfyldt at implikationerne og t er sande?

I min lærebog står der eksempelvis også "when the statement p->q is proved,..."
Med proved menes da sand?

3) Vi har haft om forskellige bevismetoder. De fleste af dem gav mening, men lige modstridsbeviset har jeg problemer med. Forelæseren skrev:
"Skal vise at P er sand.
Antag not P og find modstrid Q, så not P->Q
Hermed kan vores antagelse not P ikke være sand, dvs. P må være sand."

Hvilken modstrid Q er der tale om?
Hvordan kommer vi fra vores antagelse ned til P->Q?

4) I forbindelse med beviser delt op i flere tilfælde skriver bogen:
"When we prove that a group of statements are equivalent, we can establish any chain of implications we choose as long as it is possible to work through the chain to go from any one of these statements to any other statement. For example, we can show that p_1, p_2 and p_3 are equivalent by showing that
p_1 -> p_3, p_3->p_2 and p_2->p_1"

Hvorfor kan vi frit vælge, hvilke udsagn, der skal gå hen til hvilke?


Det var vist alt for denne gang ;)


Jeg ved virkelig ikke, hvad jeg skulle stille op, hvis ikke det var for jeres hjælp. Både forelæseren og hjælpelærerne tilknyttet dette kursus forstår ikke at give et uddybende, men samtidig pædagogisk svar. Dertil kommer, at vi har 200 siders læsning til hver uge (heraf 100 af siderne i diskret matematik) samt et projekt, der skal laves. Så jeg bruger så mange timer på at læse, fordi jeg gerne vil forstå alting.

Jeg skal prøve at forklare lidt om logiske argumenter sådan som jeg fik det ind med modermælken.
Jeg skal beklage hvis jeg kommer til at bruge oldnordiske termer, men jeg skal gøre mit bedste
for at forklare dem.

Når man evaluerer argumenter betragter man adskilt sandhedsværdien af præmisserne og de logiske
relationer mellem præmisserne og konklusionen. Man er kun interesseret i argumenter som er
sandhedsbevarende, hvormed menes, at hvis præmisserne er sande så er konklusionen også sand. Vi
siger, at et argument med denne egenskab er validt. Et validt argument er altså et argument hvor
der af sande præmisser _ikke_ kan følge en falsk konklusion. Med andre ord: Hvis argumentet er
validt, så medfører præmisserne konklusionen.

At et argument er validt sikrer ikke at dets enkeltudsagn er sande. Man skelner mellem sunde og
usunde argumenter.

Et logisk argument siges at være sundt hvis og kun hvis det er validt og alle dets præmisser er
sande. Et validt argument i hvilket et eller flere af præmisserne er falske kaldes et usundt
argument.

Som et eksempel på et validt, usundt argument haves:

Alle dyr har vinger.
Elefanter er dyr.
Ergo, elefanter har vinger.

Argumentet er validt, thi _hvis_ det er sandt at alle dyr har vinger og at elefanter er dyr,
så er det også sandt at elefanter har vinger. Men argumentet er usundt, for præmisset 'alle
dyr har vinger' er falsk.

Et eksempel på et validt, sundt argument er (klassiker):

Alle mennesker er dødelige.
Jeg er et menneske.
Ergo, jeg er dødelig.

Igen er argumentet validt, for hvis præmisserne er sande så er konklusionen ligeså. Men det
er også sundt, for præmisserne _er_ virkeligt sande.

En slutningsregel - 'rule of inference' - er et system til at konstruere _valide_ slutninger.
En slutningsregel skal derfor læses således, at hvis alle dens præmisser er sande, så er dens
konklusion ligeså.

Tager vi eksemplet

p=>q
q=>r
----
p=>r

skal det altså læses således, at hvis det er sandt at p=>q og sandt at q=>r så kan vi drage den
konklusion, at det også er sandt at p=>r. Men bemærk nu, at systemet er fremkommet af tautologien
((p=>q)/\\(q=>r))=>(p=>r) som jo er sand uanset p, q og r. Specielt er udsagnet sandt hvis det er
falsk at p=>r. Tag f.eks. (p,q,r)=(S,S,F). Så er p=>q sand, q=>r falsk, p=>r falsk. Men heraf ses
at eet af præmisserne er falske, og derfor er der ikke længere tale om et sundt argument. Det at
((p=>q)/\\(q=>r))=>(p=>r) er en tautologi betyder altså ikke at vi altid kan slutte, at p=>r er sand.

Du skal skelne mellem tautologien

(p1/\\p2…/\\pn) => q

som eet udsagn, der altid er sandt, og så den deraf afledte slutningsregel

p1
p2
:
pn
--
q

som tillader dig at slutte at _enkeltudsagnet_ q er sandt forudsat alle _enkeltudsagnene_
p1,p2,…,pn er sande. Tautologien tillader dig ikke at slutte noget om enkeltudsagnene for
det er jo sandt uanset disses sandhedsværdier.

Så kort og klart: hvis præmisserne i en slutningsregel ikke er opfyldt (=sande) kan du
ikke tillade dig at slutte noget om konklusionen.

I øvrigt kan dit eksempel q=>r og p=>q begge falsk ikke lade sig gøre, thi p=>q er kun falsk
dersom p er sand og q falsk. Men da q er falsk er q=>r sand uanset sandhedsværdien af r.

Angående subjunktioner:

En logisk operation (sandhedsfunktion) er en funktion der sammenknytter et eller flere logiske
udsagn. Dens resultat afhænger af om enkeltudsagnene er sande eller falske. Operatorerne, der
benyttes til at knytte udsagnene sammen, kaldes junktorer og én af dem er subjunktionen ->.
Det tredje udsagn jeg nævner er netop funktionsværdien A->B som du rigtigt nævner. Men bemærk
altså at implikationer formelt set kun anvendes om sande subjunktioner, d.v.s. tilfældet A sand
og B falsk forekommer ikke. Man ser dog ofte subjunktioner og implikationer benyttet i flæng trods
dette.

Subjunktioner er altid sande når præmisset er falsk. Udsagnet 'hvis solen skinner, er det varmt'
kan ikke modbevises hvis solen ikke skinner. For hvis solen ikke skinner følger det ikke at det
er koldt.

Bisubjunktionen p<->q er ækvivalent med (p->q)/\\(q->p). Dette udsagn er kun sandt dersom både
p->q og q->p er sande, hvilket kun er tilfældet hvis p og q begge er sande eller p og q begge
er falske. For hvis p er sand, men q er falsk, så er p->q falsk, men q->p sand og konjunktionen
dermed falsk. Tilsvarende hvis p er falsk og q sand.

Hermed burde til og med spørgsmål 2) være besvaret. Bemærk dog til spørgsmål 2, at du må have
skrevet forkert. Vi må have opfyldt (=sandt!) at r->t, ikke r->p som du skriver - den information
tillader os nemlig ikke at slutte t.

Håber det hjalp på det. Jeg skal nok besvare de øvrige spørgsmål når jeg får mere tid; hvis
ikke en anden når at komme mig i forkøbet.

3)
Beviser baseret på modstrid benytter en slutningsregel, der hedder modul tollens.

Den lyder:

p->q
non q
-----
non p

Som eksempel kan tages et bevis for at sqrt(2) er irrational. Vi antager da det modsatte af det, vi ønsker at vise og lader da p være udsagnet

p : sqrt(2) er rational

Med denne antagelse findes der heltal, a og b, således at (a/b)² = 2 og dermed a² = 2b². Lader vi q være udsagnet

q : a² = 2b²

har vi dermed redegjort for at p->q.

Vi benytter så aritmetikkens fundamentalsætning, der siger, at ethvert heltal kan repræsenteres ved et produkt af primtal. Tallene a og b faktoriseres nu i primtal. Da a² faktoriseres i et produkt af de samme primtal som a, men hvert primtal forekommende to gange, har a² et lige antal primfaktorer. Samme argument for b². Derfor har 2b² et ulige antal primfaktorer (tallet 2 er een ekstra primfaktor). Men a² kan ikke være lig 2b² hvis der ikke er samme paritet af primfaktorer på begge sider af lighedstegnet. Vi har altså opnået modstriden non q.

Af modus tollens slutter vi så non p, d.v.s. sqrt(2) er irrational.

4)
Det følger blot ved gentagen anvendelse af din regel fra tidligere

p->q
q->r
----
p->r

Hvis det er godtgjort at p1->p3 og p3->p2 så følger at p1->p2. Men det er også godtgjort at p2->1. Heraf p1<->p2. Det samme for de andre to ækvivalenser. Men bemærk at det væsentlige er, at implikationerne danner en "kæde".

#6
Korrektion:

"modul tollens"

->

"modus tollens"

Det er simpelthen fantastisk, at du gider blive ved med så uddybende en hjælp :)

Jeg har lige et par spørgsmål til #5 og #6:

5) "En slutningsregel - 'rule of inference' - er et system til at konstruere _valide_ slutninger."
Valide vil i denne sammenhæng betyde slutninger, der er sande (bare for at være helt sikker)?

6) "Det at
((p=>q)/\\(q=>r))=>(p=>r) er en tautologi betyder altså ikke at vi altid kan slutte, at p=>r er sand."
Hvordan kan vi så bygge slutningsreglen på denne tautologi?
Så kan vi jo ikke vide, at hvis p=>q og q=>r er sande, så betyder det, at p=>r er sand?

7) "Bemærk dog til spørgsmål 2, at du må have
skrevet forkert. Vi må have opfyldt (=sandt!) at r->t, ikke r->p som du skriver - den information
tillader os nemlig ikke at slutte t."
Jeg har tjekket det og har faktisk skrevet korrekt af. Vi bruger slutningsreglerne simplifikation, hyoptetisk syllogisme og modus ponens, hvorefter vi kan slutte t.

8) "Men det er også godtgjort at p2->1. Heraf p1<->p2."
Hvorfor er det vigtigt, at p1<->p2?
Hvad menes helt præcist med en kæde? Er det, at konklusionen for den første implikation bliver præmis for den næste implikation osv.?

Vi er kommet til O-notation i kurset. Definitionen på det, var
|f(x)|
for x>k
Vi får så at vide, at hvis vi har en værdi for C og k, så kan vi også finde to andre værdier, som passer ind (C' og k'), så længe CBurde det ikke være k>k'?

Du skal endelig sige til, når du ikke orker at svare på flere spørgsmål - det vil jeg fuldt ud forstå!

Nu glemte jeg lige et enkelt spørgsmål:

10) Vi er givet funktionen f(x) = x2+2x+1 og skal vise at denne
er O(x2), dvs. vi skal finde C og k, så følgende bliver sandt:
x^2 + 2x + 1 </= Cx^2 for x>k

Hvordan kan vi allerede nu se bort fra numerisk-stregerne?

ad 5)
Som nævnt er en slutning valid hvis der af sande præmisser følger en sand konklusion. Slutningsreglernes udforming afhænger af, hvilken kalkyle (logisk system) de opstilles for. I første ordens prædikatlogik definerer man en følgeslutning som sandhedsbevarende (af sandt følger kun sandt). Slutningsregler er derfor således beskafne, at de af bestående udsagn danner sådanne udsagn som er sande når (men ikke nødvendigvis kun når) de bestående udsagn er sande. For at gentage mig selv; en slutningsregel er en formel regel, som anvendt på sande præmisser fører til en sand konklusion.

For at tage eksemplet fra før:

Alle dyr har vinger.
Elefanter er dyr.
Derfor har elefanter vinger.

er der som nævnt tale om en validt argument. Slutningen 'elefanter har vinger' er valid, thi det er stadig således, at _hvis_ præmisserne er sande, så _er_ konklusionen sand, uagtet at i dette tilfælde er et af præmisserne falsk. En slutning kan altså være valid selvom den har en falsk præmis. Sådanne slutninger fører i regelen til falske konklusioner.

ad 6)
Det, at udtrykket er en tautologi, er netop det der tillader os at slutte, at hvis præmisserne er sande, så er konklusionen ligeså. Forestil dig at udsagnet ((p=>q)/\\(q=>r))=>(p=>r) var en eventualitet, d.v.s. sandt eller falsk afhængigt af p, q og r. Ville det så være muligt at slutte, at hvis p=>q er sand OG q=>r er sand SÅ er p=>r sand? Nej, det ville det ikke, for det kunne jo netop være eet af de tilfælde, hvor p=>r var falsk og hele udsagnet dermed falsk. Som antydet i svaret til (5) baserer man slutningsregler man tautolgier, udsagn der altid er sande, idet man så med sikkerhed kan slutte, at hvis præmisserne er sande så er konklusionen ligeså. Det kan godt være, konklusionen er sand også i tilfælde hvor eet eller flere præmisser er falsk, men det er ikke en universel egenskab ved alle udsagn. Derfor kan det ikke udnyttes. Men det _er_ en universel egenskab, at hvis præmisserne i udsagnet (p1/\\.../\\pn)=>q er sande, så er q sand.

ad 7)
Ja, hvad tænker jeg dog på, naturligvis. Undskyld.

ad 8)
Du skriver, at med en kæde af implikationer (og ja, kæde har du opfattet rigtigt), kan man slutte at vilkårlige af udsagnene er ækvivalente. Men at to udsagn, p og q, er ækvivalente skrives også p<->q. Tænk f.eks. på hvor mange gange du sikkert har benyttet biimplikationspilen <=> ved ensbetydende (= ækvivalente) regninger.

Med hensyn til de øvrige spørgsmål forstår jeg ikke symbolet <\\=.

Ahh, du mener sikkert 'mindre end eller lig med". Standardnotationen herinde er =<.

Mange tak endnu en gang :)

#11 Godt gættet - lige netop det jeg mente med mit mystiske tegn.

Jeg har selv fundet ud af svaret til #10, men mangler dog stadig at finde ud af det nederste i #9.


9) Hvis vi har f(x)=x^2+2x+1 og finder ud af, at f(x) er O(x^2), så siger bogen, at vi i stedet for x^2 også vil kunne skrive x^3 eller x^+x+7
Men gælder det ikke kun, såfremt x>=0? (hvor jeg med >= mener "større end eller lig med")


Jeg har helt overset et spørgsmål, som igen går på logik. Det er virkelig kun noget, du skal svare på, hvis du kan gøre det nogenlunde hurtigt (du har allerede hjulpet mig mere end jeg havde turdet forestille mig).

10) "Show that the hypotheses (p and q) v r and r -> s imply the conclusion p v s. (v: eller)

"We can rewrite the hypothesis (p and q) v r as two clauses, p v r and q v r.
We can alså replace r -> s by the equivalent clause non r v s. Using the two clauses p v r and non r v s, we can use the resolution to conclude p v s."

Hvorfor kan vi blot vælge at se på p v r og non r v s? Hører p v r og q v r ikke sammen som et samlet udtryk?

Er (p and q) v r også en "clause"?
Umiddelbart vil jeg mene, at det er, eftersom bogen siger, at "a clause is a disjunction of variables".

Jeg har nu læst afsnittet om O-notation i vores bog. Jeg har dog svært ved at se, hvad O-notation egentlig siger?
Ifølge bogen bestemmer det funktionens vækst, men hvorledes?

Vi har, at f(x) er O(g(x), når
|f(x)| =< C |g(x)| for x>k

Men hvad siger det om funktionen f's vækst?

Argh, here I go again.

Nu håber jeg, at dette er mine sidste spørgsmål. Hvis du skulle have overskud til at svare på mine spørgsmål i #12, #13 og nu dette indlæg, så gør det slet ikke noget, at det ikke bliver samtidigt.

11) Et ganske kort spørgsmål:
C_1 * |g_1(x)| * C_2 * |g_2(x)|
=

Skal der ikke kun være lighedstegn her?

12) Jeg har funktionen f(n)=(n^2+3)*log(n) og skal give et big-O estimat.

n^2+3 er O(n^2)

Heraf siger bogen, at f(n)=(n^2+3)log(n) er O(n^2 * log(n))
Hvorfor skal der ikke gøres noget ved log(n)?

13) "When f(x) is O(g(x)) we have an upper bound, in terms of g(x), for the size of f(x) for large values x"
Hvorfor kun for store værdier af x?

Hvad har du forresten gjort undervejs i dit studie, når du havde problemer med matematikken? Eksempelvis hvis du stødte ind i noget, du ikke forstod.

Jeg bliver nogle gange lidt i tvivl om, jeg går for meget op i detaljerne. Det tager mig utrolig lang tid at læse de antal sider, vi skal læse til hver forelæsning. Det skyldes, at jeg prøver at forstå alting - og stiller ofte "hvorfor"-spørgsmål til det, bogen skriver.

Suk! Det er ved at være pinligt. Du må altså ikke tro, at hver gang jeg støder på noget, som jeg ikke forstår, så smider jeg bare et spørgsmål herind. Jeg bruger meget tid på at tænke over svaret inden, men lige det her har jeg svært ved.

14) Hvordan kan det være muligt at have to funktioner f(x) og g(x), hvorom der gælder, at

f(x) er O(g(x))
og
g(x) er O(f(x))

Hvis g(x) er den øvre grænse af f(x), kan f(x) vel ikke være g(x)'s øvre grænse?

De næste spørgsmål går på tidskompleksiteten af algoritmer (målt i antal sammenligninger, som algoritmen skal udfører)

15) Vi har en algoritme, som bruger 2n-1 antal sammenligninger, hvis input er n elementer. Det er en algoritme for at finde det maksimale element i en mængde.
Hvorfor gælder der så, at tidskompleksiteten er theta(n)?

16) I en binær søgningsalgoritme har vi, at der er n=2^k elementer, hvor k >= 0. Hvorfor gælder så, at k=log(n)? Bliver det ikke k=log(n)/log(2)?

17) Vi har en algoritme, som finder det højeste af de første 100 tal i en følge af n elementer, hvor n >= 100. Dvs. at algoritmen har en konstant kompleksitet, da den bruger 99 sammenligninger uanset hvad.
Bør der så ikke gælde, at O(99)?
I stedet står der i en tabel nederst på siden, at en konstant kompleksitet svarer til O(1).

18) Der står, at "big-O estimates of time complexity cannot be directly translated into the actual amount of computer time used. A reason is that a big-O estimate f(n) is O(g(n)), where f(n) is the time complexity of an algorithm and g(n) is a reference function, means that f(n) =< Cg(n) when n>k."
Kan vi så ikke blot finde to værdier for C og k, som gør uligheden sand?


Jeg har blot skrevet ovenstående spørgsmål op, i det tilfælde at du skulle forbarme dig over mig endnu engang ;) Ellers er det fuldt forståeligt, idet du med garanti også har rigtig travlt.

#8
Nedereste del af (8):

Nej, man er nødt til at kræve k'>k. Såfremt f(x) er O(g(x)) er |f(x)| =< C|g(x)| for x > k. Antag at f(k)=g(k) og at f(x) > g(x) for x < k og vælg et C'>C. Da gælder naturligvis at |f(x)| =< C'|g(x)| for x > k' men man kan ikke vælge k' < k. Ifølge antagelsen er nemlig f(x) > g(x) for ethvert x
sig tilfælde hvor man kan vælge et k'
#12 (9), #13, #14 (12) + (13)
O-notationen anvendes til a beskrive den asymptotiske opførsel af funktioner. Med den angiver man en asymptotisk øvre grænse for de værdier, en funktion f kan antage, i forhold til en anden funktion.

Lad f(x) og g(x) være funktioner defineret på (en delmængde af) R. Man siger at f(x) er O(g(x)) for x->infty hviss der findes tal k og C, således at |f(x)|= k.

Ovenstående definition er den eneste der anvendes ved analyse af algoritmer. Men der findes en helt analog definition der anvendes ved beskrivelsen af f nær et tal a. Den finder specielt anvendelse i kompleks analyse [jeg overspringer den her].

Betydningen af O-notationen ligger lige for: at en funktion f(x) er O(g(x)) betyder, at for tilstrækkeligt store x antager f numerisk ikke større værdier end en eller anden konstant gange g(x) numerisk. At f(x) er O(g(x)) indebærer således, at C|g(x)| er en øvre grænse for f(x). Udser man sig eet x0 > k gælder så med sikkerhed, at |f(x0)| =

Løst sagt, f(x) vokser for store x ikke "mere" end g(x).

Til dit spørgsmål i #12 (9) skal du derfor huske, at O-notationen udtaler sig om en funktions asymptotiske opførsel, d.v.s. for x->infty.

Til #14 (12) forstår jeg ikke hvad du vil gøre ved log(n). Generelt når man bruger O-notationen, f(x) er O(g(x)), sørger man for at g er en simplere funktion end f. Funktionen g behøver skam ikke at være et polynomium. Bemærk, at definitionen ikke forudsætter nogetsomhelst om beskaffenheden af g. Den kan være hvadsomhelst.

Iøvrigt findes der også en o-notation ('little o'). Den er analog til O-notationen idet den udtaler sig om en asymptotisk nedre værdi af en funktion. Man siger at f(x) er o(g(x)) hviss der findes tal C og k, således at |f(x)| >= C|g(x)| for x > k. Der gælder altså at f(x) er O(g(x)) <=> g(x) er o(f(x)).

Løst sagt, hvis f(x) er o(g(x)) vokser f for store x "mere" end g(x)).

Hvis der om to funktioner, f og g, gælder, at f(x) er O(g(x)) og at f(x) er o(g(x)) siger man at f(x) er Theta(g(x)). Så kan du vist selv regne ud hvad det betyder for f's asymptotiske opførsel.

O og o kaldes iøvrigt også Landau-symboler.

#12 (10)
Efter de angivne operationer haves udsagnet

(p or r) and (q or r) and (non r or s)

som er ækvivalent med

(p or r) and (non r or s) and (q or r)

idet konjunktioner og disjunktioner er kommutative. Det er ikke tilfældet at (p or r) samt (q or r) hører sammen fordi de udspringer af (p and q) or r.

Ja, (p and q) or r er også en 'clause'. Alle disjunktioner er 'clauses'.

#14 (11)
Om der skal være lighedstegn eller ej kan jeg ikke svare på, men det er ikke forkert hvad der står. Da de to udtryk er lig hinanden er venstresiden derfor også mindre end eller lig med højresiden (og vice versa). Jeg skal ikke kunne sige hvilken sammenhæng, det er taget udfra. Kanske man er interesseret i at finde en maksimalværdi - et 'bound'.

#15
Det skal du ikke være foruroliget over. Den tid, der investeres nu, vil være givet godt ud senere. Det er sundt at stille spørgsmål til det læste. Det tester ens forståelse og afslører nådesløst alle huller.

Jeg brugte selv ofte det princip, når jeg havde læst nyt stof, at forestille mig at skulle forklare det for en anden, som ikke kendte til det. Det var ikke det pædagogiske element, der interesserede mig, men fremlæggelsen af stoffet som et sammenhængende hele. Derudover søgte jeg supplerende litteratur når jeg fandt noget særligt interessant eller eventuelt mindre godt beskrevet i lærebøger.

Svarene på de øvrige når jeg får tid.

Iøvrigt har jeg besvaret dine krumingsspørgsmål.

#17
Rettelse:
"At f(x) er O(g(x)) indebærer således, at C|g(x)| er en øvre grænse for f(x). Udser man sig eet x0 > k gælder så med sikkerhed, at |f(x0)| =

->

At f(x) er O(g(x)) indebærer således, at C|g(x)| er en øvre grænse for |f(x)|. Udser man sig eet x0 > k gælder så med sikkerhed, at |f(x0)| =< C|g(x0)|.

#16

(14)
Jo, det kan sagtens lade sig gøre. Når f(x) er O(g(x)) er det jo ikke g(x) der begrænser f opadtil for x->infty, men derimod C|g(x)|. Derfor kan det godt forekomme at g(x) også er O(f(x)), dvs |g(x)|=
f(x) = x^2+2x+7

g(x) = x^2-6

så er f(x) O(g(x)), men tillige er g(x) O(f(x)).

(15)
Idet f(n)=2n-1 er f(n) tydeligvis O(n), thi f(n) =< 2n for alle n. Men der gælder også at f(n) er o(n), thi 2n-1 =< n for n>1. Derfor er f(n) Theta(n).

(16), (17)
Det lader til, at du ikke er på det rene med regnereglerne for O-notationen. Der gælder bl.a., at hvis f(x) er O(Kg(x)), K konstant, så er f(x) O(g(x)). Det ses umiddelbart idet konstanten K jo blot kan indlemmes i konstanten C i definition på O. Der er defor ingen forskel på at sige, at en funktion er O(log(x)/log(2)) eller O(log(x)) og heller ingen forskel på at sige at en funktion er O(99) eller O(1).

(18)
At f(n) er O(g(n)) betyder jo blot at beregningstiden er opadtil begrænset (for store n) af g(n). Vi kan kun sige, at beregningstiden ikke overstiger en eller anden konstant gang g(n), ikke hvad den eksakt bliver.

#19
Korrektion:

thi 2n-1 =< n for n > 1

->

thi 2n-1 >= n for n >= 1