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, E-Commerce, 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.

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.

Zur Übung mit endlichen Körpern (Kap. 5.2) gibt es mehrere Programme, die im Rahmen eines Softwareprojekts entstanden sind und von internen Servern der FH Wedel heruntergeladen werden können (genauere Infos: siehe aktueller Moodlekurs).

Gliederung der Vorlesung Diskrete Mathematik

Die im Folgenden angegebenen Vorlesungswochen sind ein Richtwert, von dem der tatsächliche Vorlesungsablauf um maximal eine Woche abweichen kann.

1. Grundlagen der Mathematik (1.-2. Woche)

    1.1 Einführung

    1.2 Aussagenlogik

    1.3 Prädikatenlogik

2. Mengenlehre (3.-5. Woche)

    2.1 Grundlagen

    2.2 Relationen

    2.3 Funktionen

    2.4 Boolesche Algebren

3. Beweisführung (5.-6. Woche)

    3.1 Strukturen der mathematischen Beweisführung

    3.2 Vollständige Induktion

    3.3 Beweisstrategien

4. Zahlentheorie (7.-8. Woche)

    4.1 Teilbarkeit

    4.2 Teilen mit Rest

    4.3 Primzahlen

    4.4 Modulare Arithmetik

5. Algebraische Strukturen (8.-9. Woche)

    5.1 Gruppen

    5.2 Körper 

6. Kombinatorik (10. Woche)

    6.1 Zählformeln für Mengen

    6.2 Permutationen

7. Graphentheorie (11.-12.Woche)

    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.

This is the link to all material you need in order to follow 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 so well known approach of model-based reasoning, which is particularly advantageous in technical applications.

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.

In the meantime, algorithmic techniques of AI have also become increasingly important in computer games ("game AI").

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.

In business applications - especially in e-commerce - unique descriptions and automatic identifications are of great importance. This is done through speech recognition and semantic web technologies, which are also counted as AI.

Goals and General Content of this Class

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

However, the focus of the details will be on methods of symbolic AI as well as statistical AI outside of machine learning, because this is where I have gained my application experience. In particular, the technique of model-based reasoning, which is not so well known at the moment, will be presented as well as its potential for technical applications.

Of course, the basic principles of machine learning, which are currently in the foreground in AI applications, are also taught. In recent years, many theses have been written in this field at Wedel University of Applied Sciences, including some under my supervision. These applications are presented here. Further courses on machine learning are offered in our DSAI degree programme.

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).

The following applications are discussed in more details:

1. Routing algorithms in traffic navigation and computer games
2. Neural networks: Types and application areas
3. Ant algorithms for dynamic road navigation and tour planning
4. Model-based diagnosis for technical systems (in particular: car electric)

At FH Wedel there are more classes on soft computing resp. machine learning normally offered in German. If you pass this course and are interested in deepening your knowledge you may inquire which of the additional courses are given in English eventually.

Course Details

For each of the chapters and sections below, slide presentations will be given marked by the date when the lecture takes place. The current slides are from previous semester. In the course of a new semester, they may be updated which will be indicated in red.

This is the link to the handout server (only available for members of FH Wedel) where further supplements are given. In particular, there will be course assignments in order to practice the matters discussed.

1. Introduction and Survey

2. Logic and Rule-Based Programming

3. AI algorithmic methods

4. Knowledge-Based Systems

4.1 Representation and Classification of Knowledge
4.2 Rule-Based Reasoning
4.3 Model-Based Reasoning
      Details
4.4 Case-Based Reasoning (Machine Learning)
4.5 Concluding Comparison of the Different Reasoning Techniques

5. Ant Algorithms and their Applications

    5.1 Natural and Artificial Ant Systems for Dynamic Routing

    5.2: Dynamic Routing: Putting Ant Systems into Practice

    5.3: How Ant Solve Problems of Logistics

6. Ontology Management

    6.1: Motivation and Example with the Tourist Information System

    6.2: Ontologies in the Semantic Web

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, it covers only what is called symbolic AI now (in contrast to statistical AI like machine learning or ant algorithms). This course has little overlap with this book. More of this book is covered in the master's course of Prof. Beuster.

The field of machine learning is very well covered in the deep learning book of Goodfellow and others. This book is available via an own website.

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.

Regarding the topic Semantic Web in section 6.2, a survey about some chapters of the book of Yu is given. The books of Allemang and Hendler, Hebeler et al., and Sagaran et al. give much more details into different aspects about the Semantic Web which are not covered in this course.

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

The book of Wooldridge gives an introduction into AI agent oriented programming. Due to its little application in these days, the issue is just mentioned for completeness in this course, but not really covered.

List of Books / Papers:

Dean Allemang / Jim Hendler: Semantic Web for the Working Ontologist - Effective Modeling in RDFS and OWL, Morgan Kaufmann 2011 (2nd ed.), ISBN 978-0-12-383965-5

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

Ian Goodfellow, Yoshua Bengio, Aaron Courville: Deep Learning, MIT Press 2016, link, handout link (for FH Wedel members only)

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)

John Hebeler / Matthew Fisher / Ryan Blace / Andrew Perez-Lopez: Semantic Web Programming, Wiley 2009, ISBN 978-0-470-41801-7

Maximilian Herold: State-of-the-Art Semantic Web Services - Evaluation and Advancement in Context of a Tourist Information System, Master's thesis WS 2008/2009 (Download)

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

Tobi Sagaran / Colin Evans / Jamie Taylor: Programming the Semantic Web, O'Reilly 2009, ISBN 978-0-596-15381-6

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)

Michael Wooldridge: An Introduction to MultiAgent Systems, Wiley 2009 (2nd ed.), ISBN 978-0-470-51946-2

Liyang Yu :  A Developer's Guide to the Semantic Web , Springer 2011, ISBN 978-3-642-15969-5

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

In dieser Vorlesung werden auch Beispielaufgaben vorgeführt. Am Ende jeder Vorlesungswoche gibt es Übungsaufgaben als Hausaufgaben, deren Lösung teilweise beim nächsten Termin besprochen werden. Die Klausuraufgaben sind dann ähnlicher Natur. 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

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 wird im Laufe der Vorlesung weiterentwickelt werden. Skript und Foliensatz werden aus diesem Grund nicht sofort, sondern fortlaufend auf dem Handoutserver (nur für Studierende und Mitarbeiter der FH Wedel zugänglich) vor der jeweiligen Vorlesung zur Verfügung gestellt. 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.

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

Wayne L. Winston: Operations Research: Applications and Algorithms, 4. Edition, Cengage Learning Emea, 2003

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.