Winter 2021/22
Algorithmentheorie
Algorithm Theory
03-IBGT-THI1-AT (03-BE-699.11)
Vorlesung
ECTS: 4,5
Termine:
w?chentlich Mo 12:00 - 14:00 MZH 1090 ?bung
w?chentlich Mo 12:00 - 14:00 MZH 1100 ?bung
w?chentlich Do 10:00 - 12:00 MZH 1380/1400 Vorlesung
w?chentlich Do 12:00 - 14:00 MZH 1450 ?bung
w?chentlich Do 12:00 - 14:00 MZH 1470 ?bung
Einzeltermine:
Mo 21.02.22 12:00 - 15:00 MZH 1380/1400
Mo 21.02.22 12:00 - 15:00 NW1 H 1 - H0020
Algorithmentheorie
Algorithmen bilden eine der wichtigsten Grundlagen der
Informatik. Anschaulich beschreibt ein Algorithmus eine Vorgehensweise
um ein Problem zu l?sen. Somit bilden Algorithmen eine Grundlage der
Programmierung, sind aber unabh?ngig von der konkreten
Programmiersprache und Umsetzung. Algorithmen sind so vielf?ltig wie
ihre Anwendungen, darum ist es umso wichtiger die fundamentalen
Prinzipien des effizienten Algorithmenentwurfs und in den wichtigsten
Problembereichen die grundlegenden L?sungsverfahren zu kennen.
Die Vorlesung hat zum Ziel diese fundamentalen Prinzipien des
Algorithmenentwurfs zu vermitteln. Die Prinzipien werden anhand
klassischer Algorithmen für wichtige Probleme illustriert und
eingeübt. Auf der theoretischen Seite werden die Grundlagen
abstrakter Maschinenmodelle, formale Korrektheitsbeweise und
Laufzeitanalyse vermittelt. Das erworbene Wissen erm?glicht es den
Studierenden für ein gegebenes algorithmisches Problem verschiedene
L?sungsans?tze bezüglich ihrer Effizienz zu beurteilen, den am besten
geeigneten Ansatz zur L?sung auszuw?hlen und seine Korrektheit zu
beweisen.
? Algorithmenparadigmen: Greedy, Divide-and-Conquer, Dynamische Programmierung
? Sortierverfahren
? String Matching
? Grundlegende Begriffe der Graphentheorie
? Graphenprobleme: Kürzeste-Wege, minimale aufspannende B?ume, maximale Netzwerkflüsse, Matchings
? Lineare Programmierung
Set Theory and Model Theory (in englischer Sprache)
03-IMAT-STMT
Vorlesung
ECTS: 6
Termine:
w?chentlich Mi 14:00 - 16:00
w?chentlich Fr 14:00 - 16:00
Profil: SQ
Schwerpunkt: SQ
Die Veranstaltung findet online synchron statt. Eine Terminabstimmung erfolgt bei Semesterbeginn.
Set theory and model theory
Intuitively, a set is a collection of all elements that satisfy a certain property. This intuition, however, is false! The following example is known as Russell's Paradox. Consider the set S whose elements are exactly those that are not members of themselves: S = { X : X is not element of X }. Is S an element of S? If S is an element of S, then S is not an element of S. On the other hand, if S is not an element of S, then S belongs to S. In either case we have a contradiction. We must revise our intuitive notion of a set. In the first part of the lecture we develop axiomatic set theory (ZFC) in the framework of first-order logic, which forms the foundation of modern mathematics. We cover the axioms of set theory, ordinal numbers and induction and recursion over well-founded relations, cardinal numbers and the axiom of choice.
In the second part of the lecture we turn to classical topics of first-order model theory. Model theory studies classes of mathematical structures, such as groups, fields, or graphs, from the point of view of mathematical logic. Many notions, such as homomorphisms, substructures, or free structures, that are commonly studied in specific fields of mathematics are unified by the general approach of model theory. We study ways to construct models with desired properties from first-order theories and the expressive power of first-order logic.
Projekt GraPA
(WiSe 21/22 bis SoSe 2022)
03-IMPJ-GRAPA
Projektplenum
ECTS: 12
Termine:
w?chentlich Fr 08:00 - 10:00 MZH 3150 Projekt Plenum