Collegestof Fundamentele Informatica 1

Inhoudsopgave relevante hoofdstukken uit Schaum, onder voorbehoud.
Wel Niet Opmerkingen

0. Inleiding

I. Verzamelingenleer

Chapter 1 Set Theory
1.1 Introduction. 1.2 Sets and Elements, Subsets. 1.3 Venn Diagrams. 1.4 Set Operations. 1.5 Algebra of Sets, Duality. 1.6 Finite Sets, Counting Principle. 1.7 Classes of Sets, Power Sets, Partitions. 5.3 Mathematical functions. 5.4 Permutations. 5.5 Combinations. 5.7 The inclusion-exclusion principle. 		1.8 Mathematical Induction wordt uitgesteld tot bij het toegevoegde onderwerp Recursie.
Schaum doet dingen dubbel: Corollary 1.10 = Theorem 5.8.

II. Relaties en Functies

Chapter 2 Relations
2.1 Introduction. 2.2 Product Sets. 2.3 Relations. 2.4 Pictorial Representation of Relations. 2.5 Composition of Relations. 2.6 Types of Relations. 2.7 Closure Properties. 2.8 Equivalence Relations. 2.9 Partial Ordering Relations.
Chapter 3 Functions and Algorithms
3.1 Introduction. 3.2 Functions. 3.3 One-to-one, Onto, and Invertible Functions. 3.4 Mathematical Functions, Exponential and Logarithmic Functions. 3.5 Sequences, Indexed Classes of Sets. 3.8 Algorithms and Functions. 		3.9 Complexity of Algorithms.

III. Grafen
Chapter 8 Graph Theory
8.1 Introduction, Data Structures. 8.2 Graphs and Multigraphs. 8.3 Subgraphs, Isomorphic and Homeomorphic Graphs. 8.4 Paths, Connectivity. 8.5 Traversible and Eulerian Graphs, Bridges of Königsberg. 8.6 Labeled and Weighted Graphs. 8.7 Complete, Regular, and Bipartite Graphs. 		8.9 Planar Graphs. 8.10 Graph Colorings. 8.11 Representing Graphs in Computer Memory. 8.12 Graph Algorithms. 8.13 Travelling-Salesman Problem. 'Homeomorphic' hoeft niet.
Chapter 9 Directed Graphs
9.1 Introduction. 9.2 Directed Graphs. 9.3 Basic Definitions. 9.5 Sequential Representation of Directed Graphs. 9.8 Graph Algorithms: Depth-First and Breadth-First Searches. 		9.6 Warshall's Algorithm; Shortest Paths. 9.7 Linked Representation of Directed Graphs. 9.9 Directed Cycle-Free Graphs, Topological Sort. 9.10 Pruning Algorithm for Shortest Path. Computer toepassingen komen aan de orde bij vakken als Algoritmiek en Datastructuren.

IV. Bomen

8.8 Tree Graphs.
9.4 Rooted Trees.
Chapter 10 Binary Trees
10.1 Introduction. 10.2 Binary Trees. 10.3 Complete and Extended Binary Trees. 10.5 Traversing Binary Trees. 10.6 Binary Search Trees. 10.9 General (Ordered Rooted) Trees Revisited. 		10.4 Representing Binary Trees in Memory. 10.7 Priority Queues, Heaps. 10.8 Path Length, Huffman's Algorithm.

V. Recursie en Inductie

3.6 Recursively Defined Functions. 10.5 Traversing Binary Trees. 1.8 Mathematical Induction. 11.3 Mathematical Induction. 		Zie dictaat.

VI. Equivalentierelaties

2.8 Equivalence Relations. Modulo rekening 3.4 (Modular Arithmetic) 11.8 Congruence Relation. Aftelbaarheid 3.7 Cardinality. 		Thm 3.5 Schroeder-Bernstein. Zie dictaat.

VII. Talen, Eindige Automaten

Chapter 12 Languages, Automata, Grammars
12.1 Introduction. 12.2 Alphabet, Words, Free Semigroup. 12.3 Languages. 12.4 Regular Expressions, Regular Languages. 12.5 Finite State Automata. 		12.6 Grammars. Zie dictaat.