Introduction

This module (MAT3) supports the modules FND1 (Algorithms and Data Structures) and FND3 (Compiler construction). We focus on the needs of mathematical structures in Computer Science.

The current module desciption is given by the following link (in German).

Exams

An exam will take place at the end of the first quarter.
(This time this course will only runs a quarter.)

Study Materials

The study book is:Schaum's outlines: Lipschutz&Lipson (1997) Theory and problems of Discrete Mathematics, McGraw-Hill, isbn 0-07-038045-7. You can find this book here as: eBook

Outline by Chapters of Schaum's Outline Discrete Mathematics

CHAPTER 1 Set Theory

1.2 Sets and Elements
1.3 Universal Set and Empty Set
1.4 Subsets
1.5 Venn Diagrams
1.6 Set Operations
1.8 Finite Sets, Counting Principle

CHAPTER 2 Relations

2.1 Introduction
2.2 Product Sets
2.3 Relations
2.4 Pictoral Representations of Relations
2.5 Composition of Relations
2.6 Types of Relations
2.8 Equivalence Relations

CHAPTER 3 Functions and Algorithms

3.2 Functions
3.3 One-to-one, onto, and invertible functions
Dove-tailing function to enumerate computable functions
3.6 Recursively Defined Functions, exspecially Ackermann Function
3.9 Complexity of algorithms
Additional summary on complexity theory: General terms, big-Oh notation, applications, hierarchy of standard functions

CHAPTER 8 Graph Theory - Undirected Graphs

8.1 Introduction
8.2 Graphs and Multigraphs
8.3 Subgraphs (Untergraphen vs. Teilgraphen!)
8.4 Path, Connectivity
8.6 Labelled and Weighted Graphs

CHAPTER 9 Graph Theory - Directed Graphs

9.1 Introduction
9.2 Directed Graphs
9.3 Basic Definitions
Repeating terms as applied to undirected graphs, like paths, subgraphs and connectivity

CHAPTER 13 Languages, Grammars, Machines

13.1 Introduction
13.2 Alphabet, Words (and Semigroups)
13.3 Languages
13.4 Regular Expressions, Regular Languages
13.5 Finite State Automata
13.6 Grammars
13.7 Finite State Machines

Realization First Quarter 2008