Norges teknisk-naturvitenskapelige universitet Fakultet for informasjonsteknologi, matematikk og elektroteknikk Institutt for matematiske fag

Sentrale begreper i MA0301

Her følger en liste over det i pensum det virkelig er essensielt å huske, forstå og kunne bruke. Dette er de begrepene, fenomenene, setningene og annet som får sine egne nummere på forelesningene. Lista blir kontinuerlig oppdatert etterhvert som forelesningene skrider frem.

1. Summeregelen, blå boks, side 3

2. Produktregelen, blå boks, side 4

3. Fakultet, def 1.1

4. Permutasjoner, def 1.2

5. P(n,r), blå boks, side 7

6. Formel for arrangement av n objekter av r typer, blå boks, side 9

7. C(n,r), blå boks, side 15

8. Binomial teoremet, teorem 1.1, side 21

9. Teorem 1.2, side 23

10. Formel for antall utvalg med repetisjon, blå boks, side 27

11. Forskjellige utvalg med tilbakelegging, blå boks, side 29

12. Tautologi og kontradiksjon, def 2.1, side 53

13. Logisk ekvivalens, def 2.2, side 56

14. De logiske lover, blå boks, side 58-59

15. Substitusjons-lover for logikk, punkt 1) og 2) rett under tabellen på side 60

16. Logisk implikasjon, def 2.4, side 69

17. Slutningsreglene, tabell 2.19, side 78

18. Åpent utsagn, def 2.5, side 86

19. Undermengder og ekte undermengder, def 3.1, side 124

20. Likhet av mengder, def 3.2, side 125

21. Den tomme mengden, def 3.3, side 127

22. Om størrelse av potensmengder o.l, blå boks 128

23. Union, snitt og symmetrisk differanse av mengder, def 3.5, side 136

24. Disjunkte mengder, def 3.6, side 137

25. Komplement, def 3.7, side 138

26. Mengdelovene, blå boks, side 139

27. Om størrelse på mengder I, blå boks, side 148

28. Om størrelse på mengder II, blå boks, side 149

29. Vel-ordnings prinsippet, blå boks, side 194

30. Matematisk induksjon, teorem 4.1, side 194

31. Rekursiv defininsjon, inne i øverste avsnitt, side 211

32. Kryss-produkt, eller Cartesisk produkt, def 5.1, side 248

33. Relasjon, def 5.2, side 250

34. Antall relasjoner, blå boks, side 250

35. Funksjon, def 5.3, side 252

36. Definisjonsmengde(domain), verdimengde(codomain) og bilde(range/image), def 5.4/def 5.6, side 253/256

37. Antall funksjoner, blå boks, side 255

38. En-til-en (1-1) funksjon, def 5.5,side 255

39. Antall 1-1 funksjoner, blå boks, side 256

40. På (onto) funksjon, def 5.9, side 260

41. Antall på funksjoner, blå boks, side 262

42. Stirling-tall, blå boks, side 263

43. Duehullsprinsippet, blå boks, side 273

44. Potenser av språk, def 6.1, side 310

45. Den tomme strengen, def 6.2, side 310

46. Pluss og stjerne av et alfabet, def 6.3, side 310

47. Likhet av strenger, def 6.4, side 311

48. Lengden av en streng, def 6.5,side 311

49. Konkatenering/sammenføyning av strenger, def 6.6, side 311

50. Potenser av en streng, def 6.7, side 312

51. Prefiks/ekte prefiks/suffiks/ekte suffiks, def 6.8, side 312

52. Substreng/ekte substreng, def 6.9, side 313

53. Språk, def 6.10, side 313

54. Konkatenering/sammenføyning av språk, def 6.11, side 313

55. Potenser av språk, positiv tillukning, Kleene tillukning, def 6.12, side 315

56. Endelig tilstands-maskin, def 6.13, side 320

57. Nåbar tilstand, transient, sluk, submaskin, sterkt sammenhengende, def 6.14, side 330

58. Overføringssekvens, def 6.15, side 331

59. Refleksiv relasjon, def 7.2, side 338

60. Symmetrisk relasjon, def 7.3, side 339

61. Transitiv relasjon, def 7.4, side 339

62. Antisymmetrisk relasjon, def 7.5, side 340

63. Delvis ordning (partial ordering), def 7.6, side 341

64. Ekvivalensrelasjon, def 7.7, side 342

65. Sammensatt relasjon, def 7.8, side 344

66. Potens av relasjoner, def 7.9, side 345

67. Spesielle relasjons-matriser, blå boks, side 347

68. Rettet(directed) graf + diverse terminologi, def 7.14, side 349

69. Sterkt sammenhengende, def 7.15, side 351

70. Partisjon av en mengde, def 7.21, side 366

71. Ekvivalensklasse, def 7.22, side 367

72. x-y gange(walk), lengde av slik, åpen/lukket, def 11.2, side 515

73. Vei/krets(trail/circuit), sti/sykel(path/cycle), def 11.3, side 516

74. Undergraf(subgraf), def 11.7, side 521

75. Utspennende(spanning) undergraf, def 11.8, side 521

76. Indusert undergraf, def 11.9, side 522

77. Grafer som fåes ved sletting av hjørne/kant, def 11.10, side 522

78. Komplementet til en graf, def 11.12, side 523

79. Graf-isomorfi/isomorfe grafer, def 11.13, side 526

80. Graden(degree) av hjørne, def 11.14, side 530

81. Euler-krets/-sti, def 11.15, side 534

82. Inn- og ut-grad, def 11.16, side 535

83. Planar graf, def 11.17, side 540

84. Bipartitt(delbar) graf, def 11.18, side 541

85. Elementær underdeling/graf homeomorfi, def 11.19, side 542

86. Hamiltonsykel/Hamiltonkrets, def 11.21, side 556.

87. Tre, def 12.1, side 581.

88. Rettet(directed) tre, tre med rot(rooted tree), def 12.2, side 587.

89. Universal adress system, blå boks, side 589.

90. m-ære og komplett m-ære trær, def 12.5, side 600.

91. Preorder og postorder travers, def 12.3, side 592.

92. Inorder travers, def 12.4, side 594.

93. Dybde først søk, blå boks, side 597.

94. Bredde først søk, blå boks, side 598.

95. Høyde(height) av et tre, def 12.6, side 601.

96. Vekt/vektet graf(weight/weigthed graph), første avsnitt i 13.1, side 631.

97. Dijkstras algoritme, blå boks, side 633/644.

98. Kruskals algoritme, blå boks, side 639.

99. Prims algoritme, blå boks, side 641.
Hovedside


Redaktør: Instituttleder    Kontaktadresse: Webmaster    Sist oppdatert: 2002-01-07