{"id":1743,"date":"2019-10-16T19:29:01","date_gmt":"2019-10-16T19:29:01","guid":{"rendered":"https:\/\/rentabilitet.dk\/opgaver\/?page_id=1743"},"modified":"2019-10-16T19:29:01","modified_gmt":"2019-10-16T19:29:01","slug":"datalogiens-matematiske-grundlag-diskret-matematik","status":"publish","type":"page","link":"https:\/\/rentabilitet.dk\/opgaver\/diverse-eksamensopgaver\/datalogiens-matematiske-grundlag-diskret-matematik\/","title":{"rendered":"Datalogiens matematiske grundlag (diskret matematik)"},"content":{"rendered":"\n

Karakter: 12<\/h2>\n\n\n\n

(mundtlig eksamenen og trak nr. 5 – induktion. Men er 99 % p\u00e5 at resten af notaterne ogs\u00e5 st\u00e5r til et 12 tal)<\/p>\n\n\n

<\/a>\n \n<\/p>\n

\n \n<\/p>

p<\/strong>\n<\/p><\/td>

q<\/strong>\n<\/p><\/td>

(p ^ q)<\/strong>\n<\/p><\/td>

(p ^ q) -> p<\/strong>\n<\/p><\/td><\/tr>

\n true\n<\/p><\/td>

\n true\n<\/p><\/td>

\n true\n<\/p><\/td>

\n true\n<\/p><\/td><\/tr>

\n true\n<\/p><\/td>

\n false\n<\/p><\/td>

\n false\n<\/p><\/td>

\n true\n<\/p><\/td><\/tr>

\n false\n<\/p><\/td>

\n true\n<\/p><\/td>

\n false\n<\/p><\/td>

\n true\n<\/p><\/td><\/tr>

\n false\n<\/p><\/td>

\n false\n<\/p><\/td>

\n false\n<\/p><\/td>

\n true\n<\/p><\/td><\/tr><\/table>\n

\n Tegn ovenst\u00e5ende\n<\/p>\n

\n ^ = conjunktion\n<\/p>\n

\n V = disjunktion\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Forklaring:\n<\/p>\n

\n \"https:\/\/scontent-arn2-1.xx.fbcdn.net\/v\/t1.15752-9\/53576383_413431796090647_1315203970553085952_n.jpg?_nc_cat=100&_nc_ht=scontent-arn2-1.xx&oh=64e17bd3330d7f0c7b24c6e939fd1fc4&oe=5D192C68\"\n<\/p>\n

\n Ovenfor ses hans forklaring.\n<\/p>\n

\n En tautalogi betyder at den altid er sand.\n<\/p>\n

\n Som vist f\u00f8r er en implikation kun falsk, hvis f\u00f8rste del er sand og anden del er falsk.\n<\/p>\n

\n Dvs. at (p ^ q) skal v\u00e6re sand og p skal v\u00e6re falsk.\n<\/p>\n

\n Men det er jo et paradoks, fordi hvis p skal v\u00e6re sand kan den jo ikke ogs\u00e5 v\u00e6re falsk. S\u00e5 det kan ikke ske, s\u00e5 derfor er den altid sand. \n<\/p>\n

\n \n<\/p>\n

\n Grundm\u00e6ngde = univers\n<\/p>\n

\n A og b:\n<\/p>\n

\n \n<\/p>\n

\n A: der eksisterer en x-v\u00e6rdi, hvor p(x) er sand.\n<\/p>\n

\n B: For alle x-v\u00e6rdier g\u00e6lder det at p(x) er sand.\n<\/p>\n

\n C: Der eksisterer en x-v\u00e6rdi hvor p(x) ikke er sand. \n<\/p>\n

\n D: ikke alle x, g\u00f8r at p(x) er sand\n<\/p>\n

(s\u00e5 d betyder det samme som c)<\/em>\n<\/p>\n

<\/a>\n C: \u00acp(1) V \u00acp(2) V \u00acp(3) V \u00acp(4)\n<\/p>\n

\n F: \u00ac(p(1) ^ p(2) ^ p(3) ^ p(4))\n<\/p>\n

\n Yderligere forklaring:\n<\/p>\n

\n Her bruger vi bare de morgans lov. (s\u00e5 det til venstre er det samme som det til h\u00f8jre)\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Forklaring: Uden negation ville s\u00e6tningen v\u00e6re: For alle x g\u00e6lder det at p(x) er sand. Dvs. negationen er jo bare at det ikke er g\u00e6lden for alle x-v\u00e6rdier. Dvs. at der skal mindst eksistere en x-v\u00e6rdi, hvor p(x) ikke er sand. Og det er jo det samme som i opgave c. \n<\/p>\n

\n Hj\u00e6lpel\u00e6rer forklaring: (n\u00e5r vi s\u00e6tter negation til er det det samme som at s\u00e6tte parentes rundt om s\u00e6tningen til h\u00f8jre og s\u00e6tte negation til det. \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Kvantor = \n<\/p>\n

\n Logiske konnektiver = ^, V, \n<\/p>\n

b<\/strong>):<\/em> <\/strong> \u00ac\u2200y\u2203xP(x, y) \n<\/p>\n

\n forklaring: Det er ikke for alle y-v\u00e6rdier at der eksisterer en x-v\u00e6rdi, hvor p(x, y) er sand. \n<\/p>\n

\n Vi bruger de morgans lov:\n<\/p>\n

\n \n<\/p>\n

\n \u00ac\u2200y\u2203xP(x, y) \u2203y\u00ac\u2203xP(x, y) \u2203y\u2200x\u00acP(x, y) \n<\/p>\n

\n Der eksisterer en y-v\u00e6rdi, hvor alle x-v\u00e6rdier, g\u00f8r p(x, y) usand. \n<\/p>\n

c) <\/strong>\n<\/p>\n

\n Det er ikke for alle -v\u00e6rdier, der for alle -v\u00e6rdier g\u00e6lder at er sand. \n<\/p>\n

\n \n<\/p>\n

\n Der eksisterer en y-v\u00e6rdi for en -v\u00e6rdi, som g\u00f8r ikke er sand. \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Potensm\u00e6ngden er m\u00e6ngden af alle delm\u00e6ngder. Dvs. i m\u00e6ngden A er potensm\u00e6ngden alle delm\u00e6ngder af A.\n<\/p>\n

A = {1, 2}<\/strong>\n<\/p>\n

\n P(A) = {\u00f8, {1}. {2}, {1, 2}}\n<\/p>\n

\n F\u00f8rst har vi \u00f8, idet \u00f8 altid er et subset til m\u00e6ngder, da den passer ind i alle. (\u00f8 er nemlig den tomme m\u00e6ngde, dv.s {}.) Herefter har vi {1} og {2} og s\u00e5 har vi {1, 2} idet et set altid er et subset til sig selv. (fordi et set jo passer ind i sig selv).\n<\/p>\n

\n For at tjekke om jeg har fundet alle delm\u00e6ngder s\u00e5 udregner jeg kardinaliteten af potensm\u00e6ngden, og hvis den stemmer overens med det antal subsets jeg har fundet, s\u00e5 ved vi at altallet i potensm\u00e6ngden hvert fald er rigtig. \n<\/p>\n

\n Kardinaliteten kan udregnes s\u00e5ledes:\n<\/p>\n

\n \n<\/p>\n

\n I A er der 2 elementer (1 og 2), og er 4. Derfor ved vi at vi har alle elementerne i potensm\u00e6ngden nu, da vi har 4. \n<\/p>\n

B = {a, b, c}<\/strong>\n<\/p>\n

\n P(B) = {\u00f8, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}\n<\/p>\n

\n Her g\u00f8r vi det samme som forrige gang. Forskellen her er bare at der er lidt flere m\u00e6ngder i. Kardinaliteten er 2^3 = 8. Vi har ogs\u00e5 8 delm\u00e6ngder i vores powers\u00e6t s\u00e5 antallet er hvert fald rigtigt. \n<\/p>\n

\n \n<\/p>\n

\n
\n det er 1 og 0, fordi de enten er medlem af m\u00e6ngden eller ikke medlem af m\u00e6ngden. \n<\/p>

A<\/strong>\n<\/p><\/td>

B<\/strong>\n<\/p><\/td>

C<\/strong>\n<\/p><\/td>

B \u2229 C<\/strong>\n<\/p><\/td>

A U (B \u2229 C)<\/strong>\n<\/p><\/td>

A U B<\/strong>\n<\/p><\/td>

A U C<\/strong>\n<\/p><\/td>

(A U B) \u2229 (A U C)<\/strong>\n<\/p><\/td><\/tr>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td><\/tr>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td><\/tr>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td><\/tr>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td><\/tr>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 1\n<\/p><\/td><\/tr>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td><\/tr>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 1\n<\/p><\/td>

\n 0\n<\/p><\/td><\/tr>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td>

\n 0\n<\/p><\/td><\/tr><\/table>\n

\u2229 = <\/strong>f\u00e6llesm\u00e6ngden (dvs. Der hvor de overlapper) (Der hvor begge er 1)\n<\/p>\n

\n U = foreningsm\u00e6ngden (dvs. b\u00e5de den enes og den andens m\u00e6ngde) (Der hvor den ene eller den anden er 1)\n<\/p>\n

\n (minder lidt om sandhedstabeller)\n<\/p>

A<\/strong>\n<\/p><\/td>

B<\/strong>\n<\/p><\/td>

C<\/strong>\n<\/p><\/td>

B \u2229 C<\/strong>\n<\/p><\/td>

A U (B \u2229 C)<\/strong>\n<\/p><\/td>

A U B<\/strong>\n<\/p><\/td>

A U C<\/strong>\n<\/p><\/td>

(A U B) \u2229 (A U C)<\/strong>\n<\/p><\/td><\/tr>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td><\/tr>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td><\/tr>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td><\/tr>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td><\/tr>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td><\/tr>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td><\/tr>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

1<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td><\/tr>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td>

0<\/strong>\n<\/p><\/td><\/tr><\/table>\n

\n Som vi kan se er de lig med hinanden. \n<\/p>\n

Venn-diagrammer:<\/strong>\n<\/p>\n

\n \n \n<\/p>\n

\n Og s\u00e5 bare lav venn diagrammerne. \n<\/p>\n

\n \n<\/p>\n

\n Som det kan ses p\u00e5 billederne er begge sider af lighedstegnet alts\u00e5 ens. \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Bare tegn graferne ligesom det her:\n<\/p>\n

\n \"FIGURE\n<\/p>\n

\n A: er injektiv fordi ingen af funktionerne har samme resultat. Dvs. resultaterne er b, a, c og d. Og er derfor one-to-one. \n<\/p>\n

\n C: er ikke injektiv, fordi b\u00e5de f(a) og f(d) giver d. Det er alts\u00e5 ikke one-to-one. \n<\/p>\n

\n \n<\/p>\n

\n Dvs: Alle s og alle a tilh\u00f8rer settet A. Og hvis s er forskellig fra t jamen s\u00e5 skal f(s) ogs\u00e5 v\u00e6re forskellig fra f(t). \n<\/p>\n

\n \n<\/p>\n

\n Definitionsm\u00e6ngden er her: Adam, chou osv..\n<\/p>\n

\n \n<\/p>\n

\n A: er onto fordi v\u00e6rdim\u00e6ngden og dispositionsm\u00e6ngden er ens. Dvs. alle medlemmer af dispositionsm\u00e6ngden er et billede af et element i definitionsm\u00e6ngden. Derfor er den onto. (dvs. den er faktisk bijektiv fordi den b\u00e5de er onto og one-to-one)\n<\/p>\n

\n B: Er ikke onto fordi resultaterne er d, b, c, d. Dispositions var jo fra a, b, c, d og a er ikke et billede af af et element i definitionsm\u00e6ngden. Derfor er den ikke onto. \n<\/p>\n

\n \"FIG\n<\/p>\n

\n Onto: v\u00e6rdim\u00e6ngde = dispositionsm\u00e6ngde\n<\/p>\n

\n For some functions the range (v\u00e6rdim\u00e6ngde)(1, 3, 4, 5) and the codomain (dispositionsm\u00e6ngde) (1-5)are equal. That is, every member of the\n<\/p>\n

\n codomain is the image of some element of the domain (definitionsm\u00e6ngde) (a-d). Functions with this property are called onto <\/strong>functions \n<\/p>\n

\n \n<\/p>

\n A\n<\/p><\/td>

\n B\n<\/p><\/td>

\n C\n<\/p><\/td><\/tr>

\n \n<\/p><\/td>

\n \n<\/p><\/td>

\n \n<\/p><\/td><\/tr>

\n bijektiv\n<\/p><\/td>

\n Ingenting\n<\/p><\/td>

\n Onto\n<\/p><\/td><\/tr>

\n Injektiv fordi at der ikke er 2 x-v\u00e6rdier der har samme y-v\u00e6rdi (strengt voksende)\n<\/p><\/td>

\n Ikke onto, for den ikke g\u00e5r til -uendelig.\n<\/p><\/td>

\n Onto fordi alle v-v\u00e6rdier bliver ramt\n<\/p><\/td><\/tr>

\n Onto fordi alle y-v\u00e6rdier bliver ramt.\n<\/p><\/td>

\n Ikke injektiv, fordi flere x-v\u00e6rdier har samme y-v\u00e6rdi.\n<\/p><\/td>

\n Ikke injektiv, fordi flere x-v\u00e6rdier har samme y-v\u00e6rd\n<\/p><\/td><\/tr><\/table>\n

Yderligere hj\u00e6lp<\/em>: y-akse: dispositionsm\u00e6ngden x-akse: definitionsm\u00e6ngde graf: v\u00e6rdim\u00e6ngde\n<\/p>\n

\n \n<\/p>\n

\n En strengt voksende funktion er altid injektiv (one-to-one).\n<\/p>\n

\n Funktionen er surjektiv (onto) hvis dispositionsm\u00e6ngden er lig v\u00e6rdim\u00e6ngden. (dvs. der skal v\u00e6re noget der peger p\u00e5 samtlige mulige v\u00e6rdier).Dvs. for ethvert element b i B eksisterer der et element i A som er tildelt b.\n<\/p>\n

\n Bijektiv er bare begge dele. Dvs. for hvert element i B er der pr\u00e6cis et element i A som er tildelt det element.\n<\/p>\n

\n \t \n<\/p>\n

\n A: \n \n<\/p>\n

\n Denne funktion er bijektiv, fordi der for hvert element i dispositionsm\u00e6ngden (alle reelle tal) er der pr\u00e6cist et element i definitionsm\u00e6ngden som er tildelt det element. \n<\/p>\n

\n B:\n<\/p>\n

\n \n<\/p>\n

\n Definitionen for injektiv var jo det her:\n<\/p>\n

\n \n<\/p>\n

\n Denne graf er alts\u00e5 ikke injektiv, fordi at der er situationer, hvor s og t er forskellig fra hinanden men f(s) og f(t) er ens. Fx er f(1) og f(-1) jo det samme.\n<\/p>\n

\n Definitionen for onto var:\n<\/p>\n

\n \tDvs. for ethvert element b i B eksisterer der et element i A som er tildelt b.\n<\/p>\n

\n Grafen g\u00e5r nemlig op til uendelig, men den g\u00e5r ikke ned til -uendelig. Den g\u00e5r kun ned til -5. Derfor er v\u00e6rdim\u00e6ngden alts\u00e5 ikke lig med dispositionsm\u00e6ngden, s\u00e5 derfor er den heller ikke onto. \n<\/p>\n

\n C: tredje grads polynomium \n<\/p>\n

\n \n<\/p>\n

\n Denne graf er onto men ikke injektiv. \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Med line\u00e6r s\u00f8gning: (bare g\u00f8r s\u00e5dan her)\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Bin\u00e6r:\n<\/p>\n

\n Deler den op p\u00e5 midten, sammenligner med sidste element i f\u00f8rste del, hvis st\u00f8rre, hvis mindre ved man at elementet er i f\u00f8rste del. S\u00e5 forts\u00e6tter man bare med at dele op. \n<\/p>\n

\n Listen hed: 1, 3, 4, 5, 6, 8, 9, 11\n<\/p>\n

\n Eks:\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Bin\u00e6rs\u00f8gning fungerer kun p\u00e5 sorterede lister.\n<\/p>\n

\n Det fungerer s\u00e5ledes at man deler listen op i midten og s\u00e5 sammenligner vi s\u00f8genummereret med sidste element i f\u00f8rste del.\n<\/p>\n

\n Listen hed: 1, 3, 4, 5, 6, 8, 9, 11\n<\/p>\n

\n Og vi vil s\u00f8ge efter 9.\n<\/p>\n

\n Derfor deler vi den op i 1, 3, 4, 5 og 6, 8, 9, 11\n<\/p>\n

\n Herefter sammenligner vi 9 med sidste element i f\u00f8rste del, dvs. 5. \n<\/p>\n

\n 9 er st\u00f8rre end 5 s\u00e5 derfor ved vi at 9 er i sidste del. \n<\/p>\n

\n Derfor deler vi listen op igen s\u00e5 vi har 6, 8 og 9, 11\n<\/p>\n

\n Sammenligner igen med sidste element i f\u00f8rste del, dvs. 8. 9 er st\u00f8rre end 8 s\u00e5 derfor ved vi at elementet er i sidste del (hvis det overhovedet er der). \n<\/p>\n

\n Vi deler 9 og 11 op i to lister og sammenligner igen med sidste element i f\u00f8rste del, dvs. 9. \n<\/p>\n

\n Nu er i lig med j, s\u00e5 derfor stopper loopet. \n<\/p>\n

\n X er lig med ai (a7), s\u00e5 derfor ved vi at 9\u2019s placering i listen er nummer 7. \n<\/p>\n

\n Derfor er den nu f\u00e6rdig. \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Algoritment har flere iterationer. Den f\u00f8rste iteration s\u00e6tter det st\u00f8rste element p\u00e5 den sidste plads, den anden iteration s\u00e6tter det n\u00e6stst\u00f8rste element p\u00e5 den n\u00e6stsidste position osv. \n<\/p>\n

\n I hver iteration er der flere trin, hvor vi bare bytter rundt p\u00e5 elementer, hvis de ikke er i den rigtige r\u00e6kkef\u00f8lge. \n<\/p>\n

\n \n<\/p>\n

\n Listen hed: 6, 2, 3, 1, 5, 4\n<\/p>\n

\n \n<\/p>\n

\n \"https:\/\/scontent-arn2-1.xx.fbcdn.net\/v\/t1.15752-9\/62065824_408314990020115_2677840284317908992_n.jpg?_nc_cat=102&_nc_ht=scontent-arn2-1.xx&oh=f1c7b4112e637a645eaf25131dad7e9a&oe=5D8BE087\"\n \n<\/p>\n

\n Listen hed: 6, 2, 3, 1, 5, 4\n<\/p>\n

\n \n<\/p>\n

\n I en k\u00f8 (queue) slettes elementerne if\u00f8lge FIFO. (First in, first out). (dvs. Bare en normal k\u00f8 ligesom mcdonalds fx).\n<\/p>\n

\n Der fjernes 2 elementer. De f\u00f8rste 2 der blev sat ind var 3 og 5. S\u00e5 derfor er det de 2 der bliver fjernet. \n<\/p>\n

\n Dvs. k\u00f8en s\u00e5 bliver: 7, 10, 9\n<\/p>\n

\n S\u00e5 bliver der indsat 8 og 12, s\u00e5 k\u00f8en er nu: 7, 10, 9, 8, 12.\n<\/p>\n

\n Stack: \n<\/p>\n

\n Stack er en datastruktur hvor de enkelte elementer slettes if\u00f8lge LIFO. (last in, first out). (at slette elementer kaldes generelt for pop).\n<\/p>\n

\n Dvs. stack er bare ligesom en stak tallerkener, hvor du er n\u00f8dt til at fjerne de \u00f8verste f\u00f8r at du kan fjerne de nederste tallerkener. \n<\/p>\n

\n Stacken var: 3, 5, 7, 10, 9\n<\/p>\n

\n Der fjernes 2 elementer, dvs. dem der sidste blev tilf\u00f8jet bliver fjernet. Derfor fjerner vi nu 10 og 9.\n<\/p>\n

\n Stakken er derfor nu: 3, 5, 7\n<\/p>\n

\n Herefter inds\u00e6tter vi 8 og 12. Derfor er stakken: 3, 5, 7, 8, 12.\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Vi ved at formlen er g\u00e6ldende for n = 1,2,3,4 men vi vil gerne vise at den er g\u00e6ldende for alle positive heltal s\u00e5 derfor bruger vi induktion (svag) . \n<\/p>\n

\n Her s\u00e6tter vi 1, 2, 3, 4 ind p\u00e5 n\u2019s plads i forskriften. \n<\/p>\n

\n Som det ses p\u00e5 resultaterne er t\u00e6lleren alts\u00e5 det samme som n\u00e6vneren minus 1. \n<\/p>\n

\n Og n\u00e6vneren starter p\u00e5 2 og bliver herefter ganget op i takt med at n stiger. Derfor m\u00e5 n\u00e6vneren v\u00e6re 2^n. Formlen bliver derfor:\t \n<\/p>\n

\n Nu vil vi bruge svag induktion til at bevise den formel vi fandt frem til:\n<\/p>\n

\n Formlerne er: og \n<\/p>\n

\n Vi vil nu vise at de er ens for n = 1.\n<\/p>\n

\n Basistrin: f(1) = S\u00e5 den er hvert fald korrekt. \n<\/p>\n

\n Vi antager at for n = k er f\u00f8lgende sandt:\n<\/p>\n

\n = \n<\/p>\n

\n Baseret p\u00e5 denne antagelse vil vi nu bevise formlen ogs\u00e5 er sand for n = k + 1\n<\/p>\n

Udskifter k med k +1<\/em>\n<\/p>\n

\n = \n<\/p>\n

(Vi arbejder nu p\u00e5 venstre side, s\u00e5 h\u00f8jre side lader vi bare st\u00e5 her)<\/em>\n<\/p>\n

If\u00f8lge vores antagelse kan f\u00f8rste del af venstre side skiftes ud s\u00e5ledes:<\/em>\n<\/p>\n

\n \n<\/p>\n

(forklaringerne st\u00e5r ude til h\u00f8jre)<\/em>\n<\/p>\n

\n \tHer inds\u00e6ttes 2 i f\u00f8rste del for at f\u00e5 f\u00e6lles n\u00e6vner p\u00e5 begge br\u00f8ker (+1 tilf\u00f8jes, da den ganges med sig selv en gang mere – regnereglen ). \n<\/p>\n

\n \t2 ganges p\u00e5 i parentesen. \n<\/p>\n

\n \t+1 tilf\u00f8jes, da den ganges med sig selv en gang mere og resten udregnes. \n<\/p>\n

\n vil derfor v\u00e6re sand, idet \n<\/p>\n

\n Derfor er g\u00e6ldende for alle positive heltal (integers). \n<\/p>\n

\n \n<\/p>\n

A:<\/strong>\n<\/p>\n

\n Dette er basistrinnet for induktionen. Her ser vi om vi kan f\u00e5 henholdsvis 18, 19, 20 og 21 cent ved en kombination af 4-cents og 7-cents.\n<\/p>\n

\n 18 cent: 2*7-cent + 4-cent\n<\/p>\n

\n 19 cent: 3*4-cent + 7-cent\n<\/p>\n

\n 20 cent: 5*4-cent\n<\/p>\n

\n 21 cent: 3*7-cent.\n<\/p>\n

\n Vi har nu bevist at udsagnene p(18), p(19), p(20) og p(21) er sande. \n<\/p>\n

B:<\/strong>\n<\/p>\n

\n Induktionshypotesen for beviset:\n<\/p>\n

er sand for ,<\/strong> hvor er en integer defineret .\n<\/p>\n

\n (n er det vi ved, og k er det vi vil finde.)\n<\/p>\n

Vi antager at p(18), p(19, p(20), p(21) \u2026 P(k) er sand, og derfor kan man f\u00e5 frim\u00e6rke v\u00e6rdier for 21 og opefter med 4- og 7- cents frim\u00e6rker. <\/em>\n<\/p>\n

C:<\/strong> I beviset skal vi bevise f\u00f8lgende:\n<\/p>\n

\n hvis p(18), p(19), p(20), \u2026, p(k) er sand, s\u00e5 er p(k+1) ogs\u00e5 sand.\n<\/p>\n

\n D: fuldend induktionstrinnet\n<\/p>\n

m\u00e5ske tegn noget alla det her <\/em>\n<\/p>\n

\n \n<\/p>\n

\n Ved at benytte induktionshypotesen, kan vi antage at er sand, da hvis vil . vil derfor v\u00e6re sand og der kan benyttes 4-cents og 7-cents til danne denne v\u00e6rdi, hvilket er bevist i basistrinnet. \n<\/p>\n

\n For at lave frim\u00e6rker af vil der derfor kun skulle tilf\u00f8jes en 4-cent til det, der skulle benyttes ved . Alts\u00e5 der skal tilf\u00f8jes 4 til 18 for at f\u00e5 22. \n<\/p>\n

\n P(22) er sand fordi vi i basistrinnet ved at p(18) var sand, og derfor kan vi tilf\u00f8je en 4-cent og f\u00e5 22.\n<\/p>\n

\n P(23) er sand fordi vi i basistrinnet ved at p(19) var sand, og derfor kan vi tilf\u00f8je en 4-cent og f\u00e5 23.\n<\/p>\n

\n P(24) er sand fordi vi i basistrinnet ved at p(20) var sand, og derfor kan vi tilf\u00f8je en 4-cent og f\u00e5 24.\n<\/p>\n

\n P(25) er sand fordi vi i basistrinnet ved at p(21) var sand, og derfor kan vi tilf\u00f8je en 4-cent og f\u00e5 25.\n<\/p>\n

\n P(k+1) – vi kan blive ved at med tilf\u00f8je 4-cent.\n<\/p>\n

S\u00e5 s\u00e5 l\u00e6nge p(k-3) er sand, s\u00e5 er p(k+1) ogs\u00e5 sand. (idet vi bare kan tilf\u00f8je en 4-cent)<\/strong>\n<\/p>\n

\n Og vi ved jo at , s\u00e5 p(k-3) er derfor altid indenfor begr\u00e6sningerne i hypotesen. \n<\/p>\n

\n Vi er nu f\u00e6rdige med beviset. \n<\/p>\n

\n \n<\/p>\n

\n E:\n<\/p>\n

\n Det beviser at det er sandt, idet det illustrerer at n\u00e5r vi kan f\u00e5 18, 19, 20 og 21 cent bed brug af 4-cents og 7-cents, s\u00e5 kan vi f\u00e5 alle cent p\u00e5 et brev derfra, idet vi bare kan tilf\u00f8je en 4-cent frim\u00e6rke. \n<\/p>\n

\n Note:\n<\/p>\n

\n The difference between weak induction and strong indcution only appears in induction hypothesis. In weak induction, we only assume that particular statement holds at k-th step, while in strong induction, we assume that the particular statment holds at all the steps from the base case to k-th step. \n<\/p>\n

\n <\/strong>\n<\/p>\n

(opgave)\tGiv en rekursiv definition for her af de to talf\u00f8lger hvor og hvor \t<\/strong>\n<\/p>\n

\n Rekursion bruges til at definere nye v\u00e6rdier til elementer p\u00e5 baggrund af v\u00e6rdier fra tidligere elementer. \n<\/p>\n

\n Her opskrives og og relateres til hinanden. Hvis det kan g\u00f8res med det samme, s\u00e5 er vi allerede ved rekursionstrinnet. \n<\/p>\n

\n Basistrin\n<\/p>\n

\n Det er givet at . Herefter udregnes den mindste v\u00e6rdi for s\u00e6ttet for at finde . \n<\/p>\n

\n \n<\/p>\n

\n Tilf\u00f8j flere eksempler\n<\/p>\n

\n Rekursionstrin\n<\/p>\n

\n Nu inds\u00e6ttes som definitionen p\u00e5 , derfor (alts\u00e5 n-1 i stedet for n i )<\/em>\n<\/p>\n

\n \n<\/p>\n

\n Derfor er og deraf (idet an<\/sub> jo var det samme som 4*n, alts\u00e5 )<\/em> \n<\/p>\n

\n \n<\/p>\n

\n De to v\u00e6rdier er nu i relation til hinanden. \n<\/p>\n

\n , da vi har f\u00e5et opgivet kriteriet i opgaven, og derfor ikke kan g\u00e5 under 1. \n<\/p>\n

\n Evt. s\u00e6t et eksempel ind, som fx a5<\/sub> = a4<\/sub> + 4\n<\/p>\n

\n Basistrin\n<\/p>\n

\n Det er givet at . Herefter udregnes den mindste v\u00e6rdi for s\u00e6ttet for at finde .\n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n \n<\/p>\n

\n Rekursionstrin\n<\/p>\n

\n \"https:\/\/scontent-arn2-1.xx.fbcdn.net\/v\/t1.15752-9\/62124500_458742514684722_549858785728921600_n.jpg?_nc_cat=100&_nc_ht=scontent-arn2-1.xx&oh=c9f032e01872ede758f1e628f32dd7b2&oe=5D87799D\"\n<\/p>\n

\n potens er jo hvor man ganger tallet med sig selv. Fx 23<\/sup> = 2*2*2, 23-1<\/sup> er derfor 2*2 \u2013 alts\u00e5 det samme som at dividere med 2.<\/em>\n<\/p>\n

\n Da inds\u00e6ttes dette i ovenst\u00e5ende\n<\/p>\n

\n , derfor vi vil have bn<\/sub> til at st\u00e5 alene og kan derfor finde den ved at gange med 2 p\u00e5 begge sider<\/em>\n<\/p>\n

\n \n<\/p>\n

\n De to v\u00e6rdier er nu i relation til hinanden. \n<\/p>\n

\n , da vi har f\u00e5et opgivet kriteriet i opgaven, og derfor ikke kan g\u00e5 under 1. \n<\/p>\n

(5.3, 29)\tLad v\u00e6re m\u00e6ngden af heltalspar defineret rekursivt ved<\/strong>\n<\/p>\n

\tBasistrin: <\/strong>\n<\/p>\n

Rekursionstrin: Hvis , s\u00e5 vil og <\/strong>\n<\/p>

  1. Hvilke elementer i kan f\u00e5s ved h\u00f8jst at benytte basistrin samt det rekursive trin h\u00f8jst to gange?<\/strong>\n<\/li><\/ol>\n

    \n i s\u00e6ttet, derfor benyttes de oplyste udregninger i rekursionstrinnet til at finde flere talpar.\n<\/p>\n

    \n \n<\/p>\n

    \n – Her s\u00e6ttes det ind i et tr\u00e6, for at vise hvor mange forskellige v\u00e6rdier der kan blive g\u00e5 igennem 2 gange.\n<\/p>\n

    \n F\u00f8rste rekursionstrin\n<\/p>\n

    \n Ud fra basistrinnet vil vi kunne finde f\u00f8lgende v\u00e6rdier ud fra til m\u00e6ngden ved at benytte udregningerne i rekursionstrinnet:\n<\/p>\n

    \n \n<\/p>\n

    \n Andet rekursionstrin\n<\/p>\n

    \n Disse giver os muligheden for at finde flere elementer p\u00e5 baggrund af de allerede fundne:\n<\/p>\n

    \n giver f\u00f8lgende elementer til m\u00e6ngden: \n<\/p>\n

    \n giver f\u00f8lgende elementer til m\u00e6ngden: \n<\/p>\n

    \n giver f\u00f8lgende elementer til m\u00e6ngden: \n<\/p>\n

    Nogle af elementerne g\u00e5r dobbelt – de sorteres fra ved nedskrivningen (de er der kun for gennemgangens skyld).<\/em>\n<\/p>\n

    \n Elementerne, der kan f\u00e5s ved h\u00f8jst at benytte basistrin og rekursionstrinnet to gange, er derfor:\n<\/p>\n

    \n I det f\u00f8rste trin f\u00e5s: \n<\/p>\n

    \n I det andet trin f\u00e5s: \n<\/p>\n

    (b) Benyt strukturel induktion til at vise, at der for alle talpar (a, b) \u2208 S g\u00e6lder, at a \u2264 2b.<\/strong>\n<\/p>\n

    Basis:<\/strong> (0,0)\n<\/p>\n

    \n 0 \u2264\u00a02 \u00b7 0\n<\/p>\n

    Rekursiv del:<\/strong>\n<\/p>\n

    \n Step 1: Fra det rekursive trin (a og b) s\u00e6ttes det ind i udsagnet a \u2264 2b\n<\/p>\n

    \n Step 2: Antag at a \u2264 2b altid er korrekt. Her \u00e5bnes () ved at gange 2 ind.\n<\/p>\n

    \n – Hvis det holder for (a, b), s\u00e5 holder det ogs\u00e5 for alle nye elementer der laves i (a, b) i den rekursive del\n<\/p>\n

    \n (a, b+1) \u2208 S = a \u2264 2 (b+1)\t = a \u2264 2b+2 st\u00f8rre\n<\/p>\n

    \n (a+1, b+1) \u2208 S = a+1 \u2264 2 (b+1) = a+1 \u2264 2b+2 st\u00f8rre\n<\/p>\n

    \n (a+2, b+1) \u2208 S = a+2 \u2264 2 (b+1) = a+2 \u2264 2b+2 lig med\n<\/p>\n

    \n I forhold til tr\u00e6et der giver det ogs\u00e5 mening. Det sted hvor a er st\u00f8rst forhold til b, er i h\u00f8jre side af tr\u00e6et. Her vil a altid v\u00e6re dobbelt s\u00e5 stor som b, og derfor vil a \u2264 2b <\/strong>jo ogs\u00e5 holde, idet det vil v\u00e6re lig med hinanden. (vis evt. p\u00e5 tr\u00e6et) \n<\/p>\n

    \n Forskellen op hver side af ligningen vil altid stige (med mindre man bruger sidste, som jo er lig med), derfor vil det altid v\u00e6re g\u00e6ldende n\u00e5r man g\u00f8r det rekursivt. Det sted, hvor forskellen er mindst er jo i basistrinnet. \n<\/p>

    Sp\u00f8rgsm\u00e5l 7. \tEmne: Rekursive algoritmer (se dmg 14)<\/h1>\n

    Litteratur: \t\tAfsnit 5.4<\/strong>\n<\/p>\n

    (opgave)\tSorter f\u00f8lgende liste vha. Merge Sort:<\/strong>\n<\/p>\n

    \t7, 1, 5, 2, 11, 6, 8, 9, 3, 10<\/strong>\n<\/p>\n

    \n Rekursionstrinnet i Merge sort er, hvor de input-listen deles op i to mindre lister. F\u00f8rst anvendes MergeSort proceduren til sortere de sm\u00e5 lister (splitte dem op). Herefter anvendes Merge til at flette listerne sammen igen i output-listerne. \n<\/p>\n

    \n \n<\/p>\n

    \n P\u00e5 den f\u00f8rste del af sorteringen benyttes nedenst\u00e5ende procedure for at adskille de forskellige tal for at sortere dem i input-listen (de bliver sm\u00e5 sorterede lister). Dette g\u00f8res for hvert skridt i sorteringen. Hvis der er et ulige antal af tal, s\u00e5 er det lige meget hvilken liste den bliver tilf\u00f8jet til.\n<\/p>\n

    \n \n<\/p>\n

    Forklaring MergeSort: Listen med en usorteret talr\u00e6kke. <\/em>\n<\/p>\n

    Antallet af elementer i talr\u00e6kken = . <\/em>\n<\/p>\n

    = halvdelen af talr\u00e6kken (da ). <\/em>\n<\/p>\n

    = den f\u00f8rste del af talr\u00e6kken frem til . <\/em>\n<\/p>\n

    =anden del af talr\u00e6kken, hvor hvert tal er afh\u00e6ngig af placering. <\/em>\n<\/p>\n

    \n P\u00e5 den sidste halvdel benyttes nedenst\u00e5ende til at sorterer r\u00e6kkef\u00f8lgen i listerne. Den vil sammenligne de to lister og derved sortere dem i output-listen (samles i en sorteret liste). Dette sker for hvert trin i den nederste del – f.eks. ved 7 og 1, som sorteres til 1, 7, s\u00e5 tages 1,7 og 5 osv. \n<\/p>\n

    \n \n<\/p>\n

    (5.4, 50)\tSorter f\u00f8lgende liste vha. Quick Sort:<\/strong>\n<\/p>\n

    \t3, 5, 7, 8, 1, 9, 2, 4, 6<\/strong>\n<\/p>\n

    \n Ved quicksort udpeges et element i listen til at v\u00e6re et \u201ddelelement\u201d (pivot), hvor de andre elementer sorteres i forhold til det. Det er lige meget hvilket element, der er delelement. \n<\/p>\n

    \n \n<\/p>\n

    \n \n<\/p>\n

    \n Hvis listen er lig eller mindre end 1, s\u00e5 er listen sorteret p\u00e5 forh\u00e5nd. \n<\/p>\n

    \n Hvis ikke, s\u00e5 sorteres listen ud fra f\u00f8rste element i listen (pivot), hvor sorteringen starter fra andet element i listen til listen slutter . Derefter sorteres listen ud fra det f\u00f8rste element til to forskellige lister afh\u00e6ngig af om de forskellige elementer er mindre eller st\u00f8rre end . Derefter sorteres de fundne lister p\u00e5 samme m\u00e5de indtil alle listerne er sorteret og de kan samles i en sorteret liste. \n<\/p>\n

    \n Hvis der sorteres manuelt, s\u00e5 kan der bare v\u00e6lges et eller andet tal og sortere ud fra. \n<\/p>\n

    \n Det er ikke til at sige, hvor mange gange det kr\u00e6ver at lave en quicksort. \n<\/p>\n

    \n 3, 5, 7, 8, 1, 9, 2, 4, 6\n<\/p>\n

    \n Pivot 3.\n<\/p>\n

    \n 1 2 3 5 7 8 9 4 6\n<\/p>\n

    \n Delelementer 1 og 5 sorteres ud fra:\n<\/p>\n

    \n 1 2 3 4 5 7 8 9 6 \n<\/p>\n

    \n Sorteres ud fra delelementerne 4 og 7. \n<\/p>\n

    \n 1 2 3 4 5 6 7 8 9\n<\/p>\n

    \n Sorteres ud fra delelementet 8.\n<\/p>\n

    \n 1 2 3 4 5 6 7 8 9\n<\/p>\n

    \n Listen er hermed sorteret. \n<\/p>\n

    \n \n<\/p>\n

    A:<\/strong> Her er matrix repr\u00e6sentationen af R.\n<\/p>\n

    \n De steder der har en relation er 1 og resten er 0.\n<\/p>\n

    \n (husk at fx (1, 2) betyder r\u00e6kke 1, kolonne 2 – ikke omvendt)\n<\/p>
    <\/td>

    1<\/strong>\n<\/p><\/td>

    2<\/strong>\n<\/p><\/td>

    3<\/strong>\n<\/p><\/td>

    4<\/strong>\n<\/p><\/td><\/tr>

    1<\/strong>\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 1\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 1\n<\/p><\/td><\/tr>

    2<\/strong>\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 1\n<\/p><\/td>

    \n 0\n<\/p><\/td><\/tr>

    3<\/strong>\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 1\n<\/p><\/td><\/tr>

    4<\/strong>\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 0\n<\/p><\/td>

    \n 1\n<\/p><\/td><\/tr><\/table>\n

    B:<\/strong> Her er den orienterede graf som repr\u00e6senterer R.\n<\/p>\n

    \n (fx (1, 2) bliver bare vist som en pil fra 1 til 2)\n<\/p>\n

    \n \n<\/p>\n

    \n \n<\/p>\n

    Orienteret graf:<\/strong>\n
    \n – Er reflektiv hvis alle punkterne har en loop p\u00e5 sig selv. Alts\u00e5 ligesom nummer 4 har. \n<\/p>\n