Preface and Notation

As html is not suited for mathematical formulas, some additional notation is used (as used in the typographical package Latex). a_i denotes a with subscript i. a^i denotes a to the power i. <= and >= are used as in most computer languages. Curly brackets, "{" and "}", are use to group things. sum_{i = 0}^j denotes the sum for i running from 0 to j. The same may also be written sum_{0 <= i <= j}. ~= stands for "approximately equal" and ~ for "proportional to". Greek letters are written out. For logical expressions we either use the notation from C or the operators are written out in text. So, "a && !b" is the same as "a and not b". sqrt stands for the square root function and log without specifying the base number for the logarithm to basis 2. There are a few more notations, but they should be understood easily. New notions are printed bold there where they are defined. Inside the chapters particularly important ideas and short key notes are highlighted without introductory text. There are many pictures. These are intended to be self-explanatory. Typically they are placed just after the text fragment to which they belong, generally there is no direct reference to them in the text.

There are very few references to the literature. Clearly most of the presented material is not new. A large part is even common knowledge. More directly this text is based on material found in the following books:

• Computerarchitektur, Tanenbaum and Goodman, Pearson Studium, 2001.
• The Craft of Functional Programming, Thompson, Addison-Wesley, 1999.
• Foundations of Computer Science, Aho and Ullman, Computer Science Press, 1995.

Notice: the following text may be overcomplete. At the examination it is expected that the students only know all that has been presented during the lectures.

Table of Contents

1. Computer Science
   • Definition
   • Underlying Conditions
   • Domains of Application
   • Invisible Computers
2. Structured Programming: C
   • First Program: Basics
   • Composing, Compiling and Running
   • Primitive Data Types
   • Operators
   • Second Program: Loops
   • Third Program: Pointers
   • Structured Data Types
   • Fourth Program: Procedures
   • Recursion
   • Basic Instructions
   • Working with Arrays
   • Program Design
   • Exercises
3. Program Execution
   • Computers
   • Internal Representations
   • From Program to Execution
   • Efficiency Aspects
   • Exercises
4. Object Oriented Programming: Java
   • Introduction
   • Classes, Objects and Methods
   • Inheritance, Polymorfism and Encapsulation
   • Further Important Aspects
   • Summary
   • Further Code Examples
   • Exercises
5. Graphical User Interfaces and Applets
   • Class AWT
   • Class Applet
   • Embedding Applets
   • Detailed Example
   • Further Applet Examples
6. Programming Paradigms
   • Structured Programming
   • Object-Oriented Programming
   • Functional Programming
   • Logic Programming
7. Functional Programming: Haskel
   • Introduction
   • Basics of Haskell and Functional Programming
   • Tuples, Lists and Strings
   • Facts about Types
   • Higher-Order Functions
   • Infinite Lists and Lazy Evaluation
   • Efficiency and Correctness
   • Exercises
8. Logic Programming: Prolog
9. Finite Automata
   • Definitions
   • Deterministic and Non-Deterministic Automata
   • Eliminating Non-Determinism
   • Minimizing the Number of States
   • Types of Finite Automata
   • Exercises
10. Grammars
    • Definitions
    • Recursion
    • Examples
    • Backus-Naur Form (BNF)
    • Parsing
    • Structural Induction
    • Types of Grammars
    • Exercises
11. Laws and Rules
    • Expressions
    • Propositions
    • Predicates
    • Exercises
12. Algebras
    • Definition
    • Old Examples
    • Algebra of Electrical Circuits
    • Algebra of Complex Numbers
    • Algebra of Fractional Numbers
    • Algebra of Sets
    • Algebra of Regular Expressions
    • Exercises