Sie finden in den unten beschriebenen Lehrveranstaltungen einen Überblick über Hörerkreis, Inhalt und Zweck der jeweiligen Veranstaltung. Außerdem gibt es ab dem WS 2023/24 einen Sharepoint-Link zu allen Dateien und Videos, die meine Veranstaltung begleiten (frei verfügbar). Dazu gehören auch Übungsmaterialien, Videos, Tafelbilder und Zusatzfolien.

Solange das noch möglich ist, können externe Leser dieser Webseite noch auf meiner internen Seite stöbern. Dort finden Sie zu jeder Vorlesung die Zusatzfolien und intern entstandene Referenzen wie Abschlussarbeiten und Seminararbeiten verlinkt zum Herunterladen, was von dieser Webseite technisch nicht möglich ist. Außerdem finden Sie dort auch detaillierte Materialien zu früheren Lehrveranstaltungen, die nicht mehr gehalten werden. Die noch relevanten Inhalte meiner internen Seite werden sukzessiv über Sharepoint auf einen Link auf dieser Webseite hier übertragen.

Hörerkreis:

Bachelorstudiengänge Informatik, Technische Informatik, IT-Ingenieurwesen, Medieninformatik, Computer Games Technology, Wirtschaftsinformatik, Smart Technology, IT-Management Consulting & Auditing, Data Science & Artificial Intelligence, 1. Semester

Übergangsblock für Masterstudierende, die nicht an der FH Wedel ihren Bachelor gemacht haben.

Dieser Kurs wird in jedem Semester angeboten. Im Wintersemester gibt es zusätzlich noch einen parallelen Kurs auf Englisch. Dieser eignet sich für höhere Semester (z.B. auch im Übergangsblock), für welche der verdichtete Kurs seit Einführung der Bootcamps organisatorisch ungünstig ist.

Arbeitsaufwand: 5 ECTS-Punkte

Hier finden Sie die aktuellen Materialien zur Vorlesung: Deutsche Ordnernamen enthalten Infos auf Deutsch, englische Ordnernamen auf Englisch.

Studienbedeutung und Vorlesungsinhalte

Diese Vorlesung legt das mathematische Fundament für das gesamte weitere Studium. Da hier auch elementare mathematische Konzepte integriert sind, liefert diese Vorlesung auch das tiefere Verständnis für die anderen Mathematikvorlesungen und sollte unbedingt als erste belegt werden. Es gibt in den Inhalten Querverbindungen zu vielen nachfolgenden oder gleichzeitig stattfindenden Veranstaltungen.

Das Gebiet der Diskreten Mathematik umfasst mehrere Teilgebiete der Mathematik, welche alle mit endlichen oder zumindest abzählbaren Strukturen zu tun haben (Strukturen, die nicht so dicht sind wie z.B. die Menge der reellen Zahlen; genau wird das in der Vorlesung erklärt): Lehre der endlichen und abzählbaren Mengen, Theorie der natürlichen und ganzen Zahlen (Teilbarkeit, Primzahlen, etc.), Algebra in endlichen Mengen, Kombinatorik, Graphentheorie (Theorie der Gebilde aus Knoten und Kanten). Details können der Gliederung zum Vorlesungsmaterial entnommen werden.

Die Diskrete Mathematik ist für die IT-Studiengänge so wesentlich wie die aus der Schule besser bekannte Analysis für Physik und Ingenieurwissenschaften.

Diese Vorlesung behandelt in den ersten 5 Wochen die für ein grundlegendes Verständnis aller mathematischen Überlegungen notwendigen Inhalte der Logik, allgemeinen Mengenlehre und Beweisführung. Dieser Vorlesungsteil ist für alle MINT-Studiengänge (nicht nur der IT) relevant, weil er die mathematischen Grundlagen legt, die in jedem Studiengang gebraucht werden.Vorausgesetzt wird lediglich Schulstoff bis zur 9. Klasse. Die Teilnahme an diesem Teil der Vorlesung legt nicht nur die notwendigen Fundamente für weitere IT-Inhalte wie Programmieren und Datenbanken, sondern auch für eine systematische Analysefähigkeit in vielen Anwendungsbereichen des Lebens. Der weitere Verlauf der Vorlesung geht dann mehr auf die spezifischen Gebiete der Diskreten Mathematik ein. Die Anwendungsrelevanz bleibt aber erhalten.

Vorlesungsmaterial

Es gibt zur Vorlesung Folienmaterial, das nebenstehend veröffentlicht und kontinuierlich aktualisiert wird. Außerdem gibt es ein Lehrbuch, das aus dieser Vorlesung entstanden ist und das jedes Detail dieser Vorlesung erklärt und vertieft. Inzwischen liegt es in einer 2. Auflage vor. Einige Exemplare beider Auflagen sind auch in unserer Bibliothek erhältlich. Es ist für einen erfolgreichen Besuch dieser Lehrveranstaltung nicht zwingend erforderlich, mit diesem Lehrbuch zu arbeiten. Im Prinzip reichen die Vorlesungsfolien, die Erklärungen an der Tafel und in der Übung aus. Aber für viele wird das Buch zusätzlichen Nutzen bringen, vor allem wenn Sie einzelne Lehrveranstaltungen versäumt haben. In der Zeit der Kontaktbeschränkungen wegen Corona ist das Buch ein wichtiger Studienbegleiter, weil es auch zum Selbststudium geeignet ist: Es gibt Übungsaufgaben, von denen alle aus der 2. Auflage und die meisten aus der ersten gelöst sind. Details dazu finden Sie hier.

Einige Teile des Vorlesungsinhalts werden ferner durch die Bücher von Dean, Meinel et al. und Beutelspacher et al. und Steger abgedeckt (in dieser chronologischen Reihenfolge). Allerdings decken alle anderen Bücher immer nur einen Teil dieser Lehrveranstaltung ab. Einige Exemplare dieser Bücher finden Sie ebenfalls in der Hochschulbibliothek.

In den Vorlesungseinheiten werden die auf den Folien angegebenen Inhalte hauptsächlich an der Tafel präsentiert und mit Beispielen erläutert. Die Lehrinhalte und weitere Beispiele können im Lehrbuch oder in den zu jedem Kapitel angegebenen alternativen Literaturstellen zur Vertiefung nachgelesen werden.

Gliederung der Vorlesung Diskrete Mathematik

Diese Gliederung stammt aus früheren Vorlesungszyklen, in denen diese Veranstaltung noch über 13 bzw. 14 Wochen angeboten wurde. Seit dem WS 2025/26 soll diese Vorlesung in verdichteter Form über 6 Wochen angeboten werden. Damit werden vermutlich einige Abschnitte entfallen. Es wird sich erst im Laufe der Veranstaltung zeigen, was genau gestrichen wird.

1. Logik

    1.1 Einführung

    1.2 Aussagenlogik

    1.3 Prädikatenlogik

2. Mengenlehre 

    2.1 Grundlagen

    2.2 Relationen

    2.3 Funktionen

    2.4 Boolesche Algebren

3. Beweisführung

    3.1 Strukturen der mathematischen Beweisführung

    3.2 Vollständige Induktion

    3.3 Beweisstrategien

4. Zahlentheorie

    4.1 Teilbarkeit

    4.2 Teilen mit Rest

    4.3 Primzahlen

    4.4 Modulare Arithmetik

5. Algebraische Strukturen

    5.1 Gruppen

    5.2 Körper (wird allenfalls rudimentär behandelt, Konstruktionen endlicher Körper werden entfallen)

6. Kombinatorik

    6.1 Zählformeln für Mengen

    6.2 Permutationen

7. Graphentheorie

    7.1 Terminologie und Repräsentation

    7.2 Wege in Graphen

    7.3 Bäume

    7.4 Planare Graphen

    7.5 Färbungen

Literatur

Lehrbuch zur Vorlesung:

Sebastian Iwanowski / Rainer Lang: Diskrete Mathematik mit Grundlagen, 2. Auflage, Springer 2021, Bestellinfos sowie Lösungen siehe hier.

Bücher mit (teilweisem) Bezug zur Vorlesung oder zur Vertiefung:

Martin Aigner: Diskrete Mathematik, Vieweg 2001 (4. Auflage), ISBN 3-528-37268-0

Albrecht Beutelspacher / Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg 2004 (2. Auflage), ISBN 3-528-16989-3

Norman L. Biggs: Discrete Mathematics, Oxford University Press 2002, ISBN 0-19-850717-8 

Neville Dean: Diskrete Mathematik, Pearson Studium, Reihe "im Klartext" 2003, ISBN  3-8273-7069-8

Benjamin Klopsch: Endliche Körper - Eine kurze Wiederholung, Seminarunterlagen 2001 (nur FH-Wedel-intern erhältlich)

Dirk Hachenberger: Mathematik für Informatiker, Pearson Studium 2005, ISBN 3-8273-7109-0

Hans Kurzweil: Endliche Körper, Springer 2007, ISBN 978-3-540-49081-4

Steffen Lohrke: Endliche Körper, Seminararbeit 2005 bei Prof. Dr. Lang (nur FH-Wedel-intern erhältlich)

Jiri Matousek / Jaroslav Nesetril: Diskrete Mathematik - Eine Entdeckungsreise, Springer-Verlag 2001, ISBN 3-540-42386-9

Christoph Meinel / Martin Mundhenk: Mathematische Grundlagen der Informatik, Teubner 2002 (2. Auflage), ISBN 3-519-12949-3

Angelika Steger: Diskrete Strukturen, Bd.1, Springer 2007 (2. Auflage), ISBN 3-540-46660-6 

Gerald Teschl / Susanne Teschl: Mathematik für Informatiker, Band 1: Diskrete Mathematik und Lineare Algebra, Springer 2008 (3. Auflage), ISBN 978-3-540-77431-0

Literatur zur allgemeinen mathematischen Horizonterweiterung:

Martin Aigner: Graphentheorie - Eine Entwicklung aus dem 4-Farben-Problem, Teubner 1984, ISBN 3-519-02068-8

Martin Aigner / Ehrhard Behrends: Alles Mathematik - Von Pythagoras zum CD-Player, Vieweg 2002 (2. Auflage), ISBN 3-528-13131-4

Martin Aigner / Günter Ziegler: Proofs from THE BOOK, Springer-Verlag 2010 (4. Aufl.), ISBN 978-3-642-00855-9
in der Bibliothek auch auf Deutsch erhältlich:
Das Buch der Beweise, Springer-Verlag 2004 (2. Aufl.), ISBN 978-3-540-40185-8

Benjamin Klopsch: Audio-CDs und Reed-Salomon-Codes, Seminarunterlagen 2001 (nur FH-Wedel-intern erhältlich)

You find my survey for the master programme IT Engineering for potential incomings below. This survey applies in particular to German speaking students who have to decide between different IT master programmes at FH Wedel. Wer hierzu noch Fragen hat, wende sich bitte an mich per email.

International applicants can only apply for IT Engineering among all master programmes in Wedel since this is the only programme offered in English. If you want to know further details on the study programme you should look here.

study programmes: Bachelor of Computer Science (B_Inf), Computer Engineering (B_Tinf), IT Engineering (B_ITE), Media Computer Science (B_Minf), Computer Games Technology (B_CGT), Business and Computer Science (B_Winf), e-Commerce (B_ECom), Smart Technology (B_STec), IT-Management Consulting & Auditing (B_IMCA), Data Science & Artificial Intelligence (B_DSAI), 1st semester

proparatory block for all international and some German master students coming from bachelor schools different from FH Wedel

ECTS credits: 5

lecture term: summer and winter semester

prerequesites: precalculus mathematics of secondary school

language: This class is given in German in both semesters but in English in winter semester only when it is part of the preparatory block for the Master IT engineering programme. This class is well suitable for exchange students from partner universities, since it does not require high prerequesites but leads you to a very general understanding of mathematics useful in a lot of applications.

This is the link to all material you need in order to follow class.

Focus of this class

This class gives the mathematical fundamentals for further study in all IT related programs. The contents are highly related to a lot of parallel and subsequent courses. This class does not require any knowledge of programming.

This class covers standard material such as logics and proof concepts, set theory, number theory, combinatorics, and graph theory. Furthermore, we give an introduction in group and field theory which highlights in the construction algorithm for arbitrary finite fields. For exercises of this special topic, some construction programs implemented by students of FH Wedel in a software project will be provided.

This class is complemented by exercises lead by teaching assistants.

Content of teaching

 1. Fundamentals of mathematics
    1.1 Motivation
    1.2 Propositional logic
    1.3 Predicate logic

2. Set theory
    2.1 Basics
    2.2 Relations
    2.3 Functions
    2.4 Boolean algebras

3. Proof concepts
    3.1 Glossary of mathematical structures
    3.2 Mathematical induction
    3.3 Other proof strategies

4. Number theory
    4.1 Divisibility
    4.2 Dividing with remainders
    4.3 Prime numbers
    4.4 Modular arithmetic

5. Algebraic structures
    5.1 Groups
    5.2 Fields

6. Combinatorics
    6.1 Enumeration formulae for sets
    6.2 Permutations

7. Graph theory
    7.1 Terminology und representation
    7.2 Path problems in graphs (including Dijkstra's algorithm)
    7.3 Trees (including Kruskal's algorithm)
    7.4 Planar graphs
    7.5 Graph colouring

References

Text book (in German)

Sebastian Iwanowski / Rainer Lang: Diskrete Mathematik mit Grundlagen, 2nd edition, Springer 2021, ISBN 978-3-658-32759-0 (Print), 978-3-658-32760-6 (Online)

English books with partial coverage of this lecture (see slide references) or for further in-depth exploration:

Norman L. Biggs: Discrete Mathematics, Oxford University Press 2002 (2. edition), ISBN 0-19-850717-8
This book covers nearly all material of this lecture in a slightly more mathematical manner except for some graph algorithms. This book also covers a a lot of material not discussed in this lecture.

Neville Dean: The Essence of Discrete Mathematics, Prentice Hall 1997, ISBN 0-1334-5943-8
This book covers the first 2 chapters of this lecture entirely on a more elementary level.

Susanna S. Epp: Discrete Mathematics with Applications, Brooks/Cole 1995 (2. edition), ISBN 0-534-94446-9
This book covers most of this lecture (Chapter 5 not at all), some on a more elementary level, and lays a strong focus in algorithmic applications.

Jiri Matousek / Jaroslav Nesetril: An Invitation to Discrete Mathematics, Oxford University Press 2008 (2. edition), ISBN 0-1985-7042-2
This book covers some of the material of this lecture on a more scientific level and a lot of other issues for broadening the horizon. 

Kenneth H. Rosen: Discrete Mathematics and its Applications, McGraw-Hill 2003, ISBN 0-07-242434-6
This book covers a big part of this lecture.

Literature for broadening the mathematical horizon:

Martin Aigner / Günter Ziegler: Proofs from THE BOOK, Springer-Verlag 2010 (4. edition), ISBN 978-3-642-00855-9
Martin Aigner is my teacher of Discrete Mathematics.

In WS 2016/17, proofs of this book were presented in my seminar.

study programmes: Bachelor of Computer Science (B_Inf), Computer Engineering (B_Tinf), IT Engineering (B_ITE), Media Computer Science (B_MInf), Computer Games Technology (B_CGT), Business and Computer Science (B_WInf), E-Commerce (B_ECom), Data Science & Artificial Intelligence (B_DSAI), 3/4/5th Semester

suitable make-up course for master programmes Computer Science (M_Inf), IT Security (M_ITS) and IT Engineering (M_ITE) when additional bachelor credits are required, also suitable for exchange students from partner universities.

ECTS credits: 5

lecture term: winter semester

prerequesites: discrete mathematics, programming in object-oriented languages
Exchange students from partner universities without these knowledges are welcome but may not understand all details. 

language: This lecture will always be given in English since it is part of the preparatory block for the English master's programme IT Engineering.

The first part of the course is given by Prof. Iwanowski (6 weeks), the second part is given by Prof. Annuth and Prof. Säring. The first part has a focus on symbolic AI which was the dominant part of AI in the first decades and still has a lot of practical relevance. The second part is on statistical AI including Machine Learning (e.g. neural neuworks) and Large Language Models (e.g. ChatGPT).

This is the link to all material you need in order to follow the first part of the course.

Subject

Artificial intelligence (AI) is software that deals with complex problems, whereby its approach is similar to that of a human being. Unfortunately, there is no generally accepted, more precise definition of this rather vague characterisation.

Since computer science has been recognised as an independent science, AI has been one of the driving forces in the development of innovative software concepts. Typical milestones are the development of novel programming languages such as Prolog, Lisp (predecessor of Haskell) and Smalltalk (as the first object-oriented language) as well as novel architectures such as expert systems, knowledge-based systems and multi-agent systems. Many concepts that originated in AI have now become commonplace, such as object-oriented programming, and can be realised just as well with non-AI languages (often even better).

In recent years, the success of machine learning has triggered an enormous hype, so that only this subfield of AI is perceived by the general public. It is the main focus of so-called statistical AI. The software concepts described above, on the other hand, belong to symbolic AI. This is also called classical or traditional AI and is very different from statistical AI, which is in the current public focus.

The software concepts developed in AI are both structural and algorithmic in nature.

The most successful structural concept in AI in both symbolic and statistical AI in practical applications is knowledge-based systems. These have real-world applications in very different fields, from medicine to engineering and business.

Knowledge-based systems are a systematic collection of different approaches, each of which has become popular under its own name: Expert systems emerged as early as the 1970s and are still in use and continuously maintained in many applications today. Neural networks, which are an important manifestation of machine learning and thus dominate current public attention, also belong systematically to knowledge-based systems. In addition, there is the generally not well known approach of model-based reasoning, which is particularly advantageous in technical applications, especially in electrical and mechatronic systems.

In algorithmic techniques, there is no sharp distinction between "conventional programming" and AI. AI has contributed search techniques that are usually used for problems that cannot be solved exactly or efficiently. Typical applications of these techniques are planning tools in scheduling and logistics. The A* algorithm, which forms the basis for modern routing algorithms in traffic applications as well as in computer games ("Game AI"), can be considered an AI technique because of its search strategy. However, since it is a modification of Dijkstra's efficient basic path algorithm, it can also be considered a standard (non-AI) algorithm.

For distributed applications, the structural concept of multi-agent technology has been developed within AI. Swarm intelligence is a generalization of this covering other techniques. The most prominent example is ant algorithms, which are used in computer networks and, in a research stage, also in traffic networks. In general, swarm intelligence finds its application in distributed systems with highly dynamic behaviour.

Goals and General Content of this Class

The aim of the course is to provide a basic understanding of a lot of basic technologies used in AI. An insight into as many application areas as possible will be given.

The focus of the first part of this course will be on various methods of symbolic AI as well as ant algorithms (belonging to statistical AI), because this is where I have gained my application experience. In particular, the technique of model-based reasoning, which is not well discussed at the moment, will be presented as well as its potential for technical applications.

Furthermore, I hope to be able to motivate participants to write a thesis in an area of AI. This is possible for all degrees (Bachelor and Master).

In the first part of tthis course, the following applications will be discussed in more details:

1. Routing algorithms in traffic navigation
2. Ant algorithms for dynamic road navigation and tour planning
3. Diagnosis for technical systems

Course Details

For each of the chapters and sections below, slide presentations will be given marked by the date when the lecture takes place. They will eventually be placed into the course folder once the unit has been given. The slides of the previous year when I taught all aspects of AI are given in the folder WS 2024. The following is an adaptation of previous yeart for the new limited focus and may still be updated during the course:

1. AI in general and the special field of symbolic AI

2. Logic and Rule-Based Programming as Fundamentals of Expert Systems

3. Algorithmic methods for symbolic AI

4. Knowledge-Based Systems: From Expert Systems to Model-Based Reasoning

5. Ant Algorithms and their Applications

References

The following references are available online or in our library. Their relevance for this course is the following:

The book of Russel and Norvig is nowadays considered the standard textbook in the field of AI. But it is very logic oriented and more theory than application prone. Further, its origin is in symbolic AI although newer editions also cover statistical AI. This course has little overlap with this book. More of this book is covered in the master's course of Prof. Beuster.

The German handbook of Görz and others is the only general book sketching a little the chapter knowledge-based systems as covered in this course. And it covers also a lot of chapters 2 and 3 of this course. If you want to know how model-based diagnosis really works, you should read the dissertation of Tatar. But this goes far beyond what is sketched in this course.

The book of Dorigo and Stützle is the only book on ant algorithms (from the inventors). The issues covered in this course with respect to route navigation are better explained in Thomas Walther's German master's thesis and the English summary paper. Further applications are given by papers of the FH Wedel graduates Bertram, Blöcker and Döppers. Their issues are only sketched in this course, but the papers should serve as motivation for future graduates to contribute to this list.

The book of Bratko is the standard for learning Prolog. Prolog is only sketched in this course, but not taught for programming.

List of Books / Papers:

Alexander Bertram / Sebastian Iwanowski: Dynamic Routing on OpenStreetMap Using Ant Colonies, 4th International Conference on Computational Logistics, Kopenhagen (DK) 2013, veröffentlicht in: Lecture Notes of Computer Science 8197 (2013), Springer Verlag 2013, Seiten 58 - 72

Christopher Blöcker / Sebastian Iwanowski: Utilising an Ant System for a Competitive Real-Life Planning Scenario, 3rd International Conference on Computational Logics, Algebras, Programming, Tools and Benchmarking, Computational Tools, Nizza (F) 2012, ISBN 978-1-81208-222-8, Seiten 7 - 13

Ivan Bratko: PROLOG, Programming for Artificial Intelligence,
   2nd Edition, Wiley 1990, ISBN 0-201-41606-9
   3rd Edition, Wiley 2000, ISBN 0-201-40375-7

Felix Döppers / Sebastian Iwanowski: E-Mobility Fleet Management Using Ant Algorithms, 15th Meeting of the EURO Working Group on Transportation, Paris (F) 2012, published in: Procedia - Social and Behavioral Sciences 54 (2012), Seiten 1058 - 1067

Marco Dorigo / Thomas Stützle: Ant Colony Optimization, MIT Press 2004, ISBN 0-262-04219-3

Günter Görz / Claus-Rainer Rollinger / Josef Schneeberger: Handbuch der Künstlichen Intelligenz, Oldenbourg 2000 (3. Auflage), ISBN 3-486-25049-3 (in German)

Sebastian Iwanowski / Thomas Walther: Dynamic Road Navigation with Ant Algorithms, FH Wedel 2009

Timo Jürgens: Ant algorithm and Dijsktra's algorithm compared on OpenStreetMap, Master Thesis, FH Wedel 2016 (in German)

Konstantin Ruhmann: Application of an Assumption-based Truth Maintenance System for Model-Based Diagnosis, Master Thesis, FH Wedel 2016

Stuart Russell / Peter Norvig: Artificial Intelligence - A modern approach, Pearson 2003 (2. edition), ISBN 0-13-080302-2

Mugur Tatar: Dependent Defects and Aspects of Efficiency in Model-Based Diagnosis, Dissertation for the PhD degree, Universität Hamburg 1997

Thomas Walther: Dynamische Fahrzeugnavigation auf Basis von Ameisenkolonien, Masterarbeit WS 2005/2006 (Download, in German)

Hier kommen Sie auf den Sharepoint-Ordner, wo alle Vorlesungsunterlagen stehen (nur für Hochschulangehörige zugänglich).

Vorlesungsinhalte

Unter Operations Research (OR) versteht man mathematische Verfahren zur Optimierung von Zielfunktionen in linearen Ungleichungssystemen.

Eigentlich handelt es sich also um eine Erweiterung der Linearen Algebra. Der Name Operations Reserach kommt aus der britischen Militärforschung, wo solche Verfahren für Optimierungsaufgaben eingesetzt wurden. Unter diesem Namen ist das Gebiet jetzt weltweit bekannt. Es wird in der Betriebswirtschaft auch verwendet, um Unternehmensmodellierungen vorzunehmen.

In dieser Vorlesung werden nicht nur die Verfahren vorgestellt und an Beispielen erklärt, sondern auch die Modellierung praktischer Anwendungen derart, dass man die Verfahren zur Lösung dieser Probleme anwenden kann. Der Schwerpunkt liegt aber in den mathematischen Lösungsverfahren. Für Modellierungen in der Betriebswirtschaft gibt es an der FH Wedel speziellere Vorlesungen der BWL.

In dieser Vorlesung werden im Einzelnen folgende Themen behandelt:

1) Einführung
2) Lineare Optimierung
3) Simplexverfahren
4) Sensitivitätsanalyse
5) Dualität
6) Ganzzahlige lineare Optimierung
7) Transportproblem
8) Zuordnungsproblem (Matching)
9) Zielprogrammierung

Organisation der Vorlesung

Diese Vorlesung wird bis auf Weiteres im FlippedClassroom-Modus durchgeführt. Das bedeutet Folgendes:

Sie müssen sich vorab bereits ein Video aus einer Onlinevorlesung von 2021 ansehen oder das dazugehörige Kapitel im Skript durchlesen. Es gibt dann auch noch Übungsaufgaben, welche von den Teilnehmern schon vorab gelöst werden können. Aber genau diese werden dann zur Vorlesungszeit vorgeführt. Außerdem gibt es noch weitere vertiefenden Infos, und es können beliebige Fragen zum Stoff gestellt werden. Vorlesung und Klausur werden mit 4 ECTS-Punkten versehen.

Außerdem gibt es noch eine obligatorische OR-Aufgabe, die mit 1 ECTS-Punkt versehen wird. Diese OR-Aufgabe obliegt nicht der Verantwortung von Prof. Iwanowski, sondern wird von Herrn Emre Kilic angeboten. Bei ihm muss man sich anmelden, und er wird die Lösung auch abnehmen. Anderenfalls ist das 5-ECTS-Modul Operations Research nicht vollständig absolviert. Die Details zu der OR-Aufgabe werden hier beschrieben.

Formal dürfen die Vorlesung und die Übung in verschiedenen Semestern absolviert werden. Es ist aber sinnvoll, beide im selben Semester zu absolvieren, weil die Verfahren für die OR-Aufgabe in der Vorlesung erklärt werden und weil die Lösung der OR-Aufgabe eine sehr gute Übung für die Klausur ist.

Vorlesungsunterlagen

Die Videos für den Flipped Classroom erreichen Sie über Moodle. Alle anderen Unterlagen sind im Sharepoint-Ordner (Link siehe oben).

Es gibt für diese Vorlesung einen Foliensatz und ein Skript, das von Prof. Beuster erstellt wurde und von Prof. Iwanowski in den letzten Jahren mit kleineren Änderungen und Korrekturen versehen wurde. Es könnte im Laufe der Vorlesung weiterentwickelt werden. Die Datei ORZusammenfassung enthält die wichtigsten Methoden aus der Vorlesung, welche in der Klausur abgefragt werden könnten. Sie wird während der Klausur zur Verfügung gestellt. Auf diese Weise ersparen Sie sich das Auswendiglernen und können sich ganz auf das problemlösende Denken konzentrieren.

Außerdem gibt es noch verschiedene Software-Tools, die im Laufe der Vorlesung vorgestellt werden und zu denen Beispiellösungen sukzessive in den OR-Ordner gestellt werden.

Literatur

Theodor Ellinger, Günter Beuermann, Rainer Leisten: Operations Research: Eine Einführung, 6. Auflage, Springer, Berlin 2003

Hamdy A. Taha: Operations Research: An Introduction, 9. Edition, Pearson, 2010 (auch im OR-Ordner)

Wayne L. Winston: Operations Research: Applications and Algorithms, 4. Edition, Cengage Learning Emea, 2003 (auch im OR-Ordner)

This is the public link to all class material (including videos).

study programs: Master of Computer Science (M_Inf), Data Science & Artificial Intelligence (M_DSAI), IT Engineering (M_ITE)

ECTS credits: 5

term offered: summer semester

prerequesites: qualified bachelor program in computer science (or related), no prerequesite of master courses

language: English

Focus of this class

Algorithmics is the basis for creating correct and efficient software solutions. Although this lecture is self-contained, it is assumed that participants have already seen algorithms for fundamental problems like searching, sorting and elementary graph problems in their bachelor programme. At FH Wedel, this is done in the courses Programming, Discrete Mathematics, Algorithms and Data Structures. The focus of the bachelor courses is on technical realization. Some elementary proofs have also been covered. Time and space complexity has been addressed, but not systematically proven.

This class gives a more detailed insight into the world of algorithmics. We will abstract from technical details and put more emphasis on correctness and complexity. Traditionally, the focus of algorithmics is on complexity, especially on asymptotic time complexity. However, we will also prove the correctness of many algorithms with mathematical methods.

There is another class of our master programme titled Computability and Complexity (given in German) which gives a thorough theoretical base for algorithmics. However, it is not necessary for the comprehension of this lecture. In some textbooks, computability and complexity is considered as part of algorithmics, but in even more textbooks, it is considered as part of automata theory. This is why Computability is not covered at all in this class, and complexity only with very few slides in order to enable the participants of this class to do complexity proofs on algorithms without having had the other class.

Most of the research groups on Theoretical Computer Science work in algorithmics or in specification and verification. Therefore there are a lot of future dissertation themes pending in these areas. This gives a good chance for corresponding master theses which can be written at FH Wedel under my supervision. I have myself obtained my PhD in algorithmics with a strong focus on complexity, more precisely in computational geometry. I am still in contact with my former department at FU Berlin which is specialized in the field of algorithmics.

After repeating and formalizing the above-mentioned basic topics from bachelor study, we will address additional sorting and searching algorithms. Also advanced search tree methods and graph algorithms are addressed. Finally, we focus on selected topics of computational geometry with a special focus on the efficient computation of Voronoi diagrams and their applications.

Content of teaching

1. Introduction into formal algorithmics
     1.1 Comparing basic sorting techniques
     1.2 Complexity measures for the analysis of algorithms
     1.3 Lower bound for algorithms using comparisons only

2. Advanced searching and sorting
     2.1 Order statistics
     2.2 Searching in sorted arrays
     2.3 Sorting in finite domains

3. Solutions for the dictionary problem
     3.1 Hashing and other methods for optimising the avarage case behaviour
     3.2 (2,3)-trees as example for an optimal worst case behaviour tree
     3.3 Other optimal worst case methods for search trees
     3.4 Optimal binary search trees (Bellman)

4. Graph algorithms
     4.1 Minimum spanning trees as motivation for basic algorithms
     4.2 Shortest paths (Dijkstra, Floyd-Warshall, Strassen)

     4.3 Computation of maximum flows in s/t-networks (Ford-Fulkerson, Edmonds-Karp, Dinic)
     4.4 Computation of graph matchings (bipartite, Edmonds)

5. String matching

6. Fundamentals of computational geometry
     6.1 Basic problems and the use of Voronoi diagrams for solving them
     6.2 Sweep techniques (including computation of Voronoi diagrams)

References

The text books for this lecture are the books of Cormen et al. Klein, and Turau. They are covered only in parts.

The books of Knuth and Sedgewick serve to broaden and improve the knowledge in selected topics. The book of Levitin serves as an introduction which is more suitable for the bachelor level, but still covers material relevant for this course.

The book of deBerg et al. also covers latest results in computational geometry which have been out of the scope of this lecture so far. But it serves also as an English reference for the content of chapter 6 which is taken from the German book of Klein originally. 

The book of Papadimitriou and Steiglitz covers graph algorithms much more detailed than this lecture. It is the only of the cited references describing the matching algorithm of Edmonds for arbitrary graphs.

The a bit older books of Preparata and Edelsbrunner serve as a reference for fundamentals and a lot of algorithms to discussed problems which are not directly addressed in this lecture though.

Mark de Berg / Otfried Cheong / Marc van Kreveld / Mark Overmars: Computational Geometry, Algorithms and Applications Springer 2008 (3rd ed.), ISBN 978-3-540-77973-5

Thomas Cormen, Charles Leiserson / Ronald Rivest / Clifford Stein: Introduction to Algorithms, MIT Press 2001 (2nd ed.), ISBN 978-0262032933

Herbert Edelsbrunner: Algorithms in Combinatorial Geometry, Springer 1987, ISBN 3-540-13722-X

Rolf Klein: Algorithmische Geometrie (in German), Springer 2005 (2. Aufl.), ISBN 978-3-540-20956-0

Donald Knuth: The Art of Computer Programming, vol. 1,2,3,
Addison Wesley 1997, ISBN 0-201-89683-4,  0-201-89684-2, 0-201-89685-0

Anany Levitin: Introduction to the Design and Analysis of Algorithms, Addison-Wesley 2006, ISBN 0-321-36413-9

Kurt Mehlhorn / Peter Sanders: Algorithms and Data Structures - The Basic Toolbox, Springer2008, ISBN 978-3-540-77977-3

Christos Papadimitriou / Kenneth Steiglitz: Combinatorial Optimization - Algorithms and Complexity, Dover 1998, ISBN 0-486-40258-4

Franco Preparata / Michael Shamos: Computational Geometry - An Introduction, Springer 1988 (2nd ed.), ISBN 3-540-96131-3

Robert Sedgewick: Algorithms, Addison Wesley 1983 (original version), ISBN 0-201-06672-6
This is a standard book published in several editions.
New editions are specialized for selected programming languages (Algorithms in C, Algorithms in Java, etc.).

Volker Turau, Algorithmische Graphentheorie (in German), Oldenbourg 2004 (2. Auflage), ISBN 3-486-20038-0
(in unserer Bibliothek: 1. Auflage, Addison-Wesley 1996)

Hörerkreis:
Masterstudiengänge Informatik und IT-Sicherheit als Teil des Moduls Berechenbarkeit/Verifikation

Arbeitsaufwand: 2,5 ECTS-Punkte (für diesen Modulteil)

Hier finden Sie alle Materialien zur Vorlesung. Da diese nicht nur von mir erstellt wurden, sind sie nicht öffentlich zugänglich, sondern nur Angehörigen der FH Wedel.

Vorlesungsinhalte

Berechenbarkeit untersucht, ob ein Problem durch einen Computer überhaupt berechnet werden kann. Dazu ist es erforderlich, die Begriffe Problem, Algorithmus und Computer mathematisch zu formalisieren. Im Zentrum steht das Konzept der Turingmaschine. Erst damit kann bewiesen werden, dass es überhaupt Probleme geben kann, die nicht berechenbar sind. Der Nachweis der Nichtberechenbarkeit für einzelne Probleme ist meistens sehr schwierig. Wir werden diese Eigenschaft aber für einige Probleme zeigen.

Für berechenbare Probleme wird die Komplexität als Maß für ihre Schwierigkeit definiert. Auch diese Definition verwendet das Konzept der Turingmaschine. Die zentrale Frage, die in der Komplexitätstheorie und damit auch in dieser Vorlesung gestellt wird, besteht darin, ob ein Problem in polynomialer Zeit gelöst werden kann (was als effizient gilt) oder nicht. Diese Fragestellung ist für viele Probleme nicht gelöst. Als Charakterisierung für derartige Probleme gibt es die Klasse der NP-vollständigen Probleme, welche in dieser Vorlesung ebenfalls eingehend untersucht wird.

Vorlesungsunterlagen

Dieser Vorlesungsteil richtet sich größtenteils nach einem Foliensatz, der von meinem Vorgänger Prof. Lang eingerichtet und von mir im Laufe der letzten Jahre überarbeitet wurde. Die Vorlesung wird anhand dieser Folien gehalten und an einigen Stellen an der Tafel vertieft.

Die grobe Gliederung dieses Vorlesung entspricht auch der des Foliensatzes:

1. Formalisierung von Problem und Algorithmus
    (nur Kap. 1.1 - 1.3)

2. Berechenbarkeit und Nichtberechenbarkeit von Problemen
    (mit Formalisierung über Turingmaschinen)

3. Komplexitätstheorie

Literatur

Alle aufgeführten Bücher enthalten auch das mit Berechenbarkeit eng verwandte Gebiet der Automaten und Formalen Sprachen. Die Vorlesung wird aber so gehalten, dass Vorkenntnisse aus diesem Gebiet nicht vorausgesetzt werden.

John E. Hopcroft / Rajeev Motwani / Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, Pearson Studium 2011 (3. Aufl.), ISBN 978-3-86894-082-4
(in unserer Bibliothek befinden sich auch ältere Auflagen, darunter auch das englischsprachige Original von 1979)

Juraj Hromkovic: Theoretische Informatik, Teubner 2007 (3. Aufl.), ISBN 978-3-8351-0043-5
(in unserer Bibliothek befinden sich auch ältere Auflagen)

Gottfried Vossen / Karl-Ulrich Witt: Grundkurs Theoretische Informatik, Vieweg 2006 (4. Aufl.), ISBN 978-3-8348-0153-1

You will find all the necessary descriptions in the courses described above and all material for class (slides, videos, smartboard contents, etc.) in a link via Sharepoint (valid for all courses given in WS 2023/24 and later).

Participants should also enrol in the corresponding Moodle courses in order to get current infos about the class (e.g. notifications about updates). However, all material will be publically available.

As long as this is still possible, external readers of this website can still browse my internal website which is bilingual. There you find the same information as here (could be deprecated though), detailed information about expired courses given in previous semesters.and information about other academic activities of myself.