5023.10 - Mathematics 2 for Information Technology

5023.10

Mathematics 2 for Information Technology

7.5

To give the students a further introduction to discrete mathematics with respect to applications in computer science.

(1) Matrices, systems of linear equations, Gauss-Jordan elimination, matrix computations, subspaces, nullity and rank of a matrix; (2) algebraic structures (semigroup, monoid, group, field, vector space), morphism, congruence, quotient structures; (3) phrase structure grammars, BNF, syntax diagrams, language generated by a grammar, Chomsky hierarchy, Moore machines, language recognized by a Moore machine; (4) Turing machines, Turing computability, recursive functions, Church's thesis; introduction to Petri Nets, concurrency, interaction, P vs. NP, Halting problem and its negative solution; (5) natural, integer, rational and real numbers, countable sets, countability of the rational numbers, uncountability of the real numbers, Cantor's theorem, uncountability of the integer functions in an integer variable; (6) undirected trees, spanning trees, minimal spanning trees, Prim's algorithm, Kruskal's algorithm, graphs, graph morphisms, subgraphs, quotient graphs, Euler paths and circuits, Fleury's algorithm, Hamiltonian paths and circuits; flow networks, Ford - Fulkerson algorithm, graph coloring, chromatic number, Welsh-Powell algorithm; (7) self-referentiality of utterances, language vs. meta language, truth, well-formed-formula (wff) of first order predicate logic, truth of wff

Lectures, problem solving sessions and written assignments.

6 written assigments and one 2 hours written test without helping aids, calculators, reference material etc. In the final grade, each assignment contributes with the weight 5% while the test contributes with the weight 70%. The existing grade scale will be used.

Gunnar Restorff