Martin Thoma

Die erste Hälfte des Semesters ist nun vorbei und es wird Zeit zu wiederholen, was man wissen sollte. Eventuell ist diese Liste für ein paar Kommilitonen von nutzen. Wenn man gerade eines der Module macht, sollte man alles wissen, was in den Links steht. Naja, vielleicht nicht alles, aber man sollte auf jeden Fall die Begriffe im Schlaf definieren können. Die Links sind meist deutsche Wiki-Artikel, manchmal auch englische. Je nach dem, was ich besser fand.

Einiges hätte ich bei vielen Modulen schreiben können, z.B. der Beweis durch Induktion. Ich habe mir dann einfach eines ausgesucht und es nur da hinein geschrieben. Das ist eh schon lang genug.

1. Semester

Analysis I

Fachbegriffe

• Verknüpfungseigenschaften: Kommutativgesetz, Assoziativgesetz, Distributivgesetz
• Relationen: Injektivität, Surjektivität, Bijektivität, Linkstotalität, Rechtseindeutigkeit, Reflexivität, Antisymmetrie, Symmetrie, Transitivität, Ordnungsrelation, Äquivalenzrelation
• Mengeneigenschaften: Abzählbarkeit, Überabzählbarkeit, endlich, unendlich, Beschränktheit
• Folgeneigenschaften: Supremum, Infimum, Minimum, Maximum, Konvergenz, Divergenz, Grenzwert, Limes superior, Limes inferior, Monotonie
• Beweis durch vollständige Induktion
• Teilfolgen, Häufungswerte
• Reihen: Monotoniekriterium, Dreiecksungleichung
• Umordnungen und Produktreihen
• Potenzreihen, Konvergenzradius
• g-adische Entwicklungen
• Funktionen: Grenzwerte, Häufungspunkte, Stetigkeit, abgeschlossen, offen, gleichmäßige Konvergenz, gleichmäßige Stetigkeit, Lipschitz-Stetigkeit

Sätze

• Satz von Bolzano-Weierstraß
• Cauchy-Kriterium
• Leibniz-Kriterium
• Majorantenkriterium und Minorantenkriterium
• Wurzelkriterium
• Quotientenkriterium
• Riemannscher Umordnungssatz

Formeln

• \(\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\)
• \(a^{n+1} – b^{n+1} = (a – b) \sum_{k=0}^{n} a^{n-k} b^{k}\)
• Bernoullische Ungleichung: \(x \geq -1: (1+x)^n \geq 1 + nx ~ \forall n \in \mathbb{N}\)
• Binomischer Lehrsatz: \((a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^{n-k} b^k ~ \forall n \in \mathbb{N}\)

Wichtige Grenzwerte

• \(\sqrt[n\,]{n} \rightarrow 1 (n \rightarrow \infty)\)
• \(e = \lim_{n \to \infty} (1+\frac{1}{n})^n = \lim_{n \to \infty} \sum_{k=0}{n} \frac{1}{k!}\)

Wichtige Reihen

• Harmonische Reihe: \(\sum_{n=1}^\infty \frac{1}{n}\) (Divergent)
• Geometrische Reihe: \(\sum_{n=0}^{\infty} x^n (x \in \mathbb{R})\). Konvergiert, falls |x| < 1 gegen \(\frac{1}{1-x}\)
• Alternierende Harmonische Reihe: \(\sum_{n=1}^{\infty} (-1)^{n+1} \frac{1}{n}\)
• \(e^x = \sum_{n=0}{\infty} \frac{x^n}{x!}\)
• Kosinus: \(cos(x) = \sum_{n=0}{\infty} (-1)^n \cdot \frac{x^{2n}}{(2n)!} (x \in \mathbb{R})\)
• Sinus: \(sin(x) = \sum_{n=0}^{\infty} (-1)^n \cdot \frac{x^{2n+1}}{(2n+1)!} (x \in \mathbb{R}\)
• Cosinus Hyperbolikus: \(cosh(x) = \frac{1}{2} (e^x + e^{-x}) (x \in \mathbb{R})\)
• Sinus Hyperbolikus: \(sinh(x) = \frac{1}{2} (e^x – e^{-x}) (x \in \mathbb{R})\)

Links und Materialien

• Skript
• MIT OpenCourseWare

Lineare Algebra

Algebraische Strukturen

• Gruppen:
  • Definition
  • Beispiele: alle Ringe und Körper
• Ringe:
  • Definition
  • Beispiele: alle Körper
  • Gegenbeispiele: \((\mathbb{N}, +, \cdot)\)
• Körper:
  • Definition
  • Beispiele: \((\mathbb{Q}, +, \cdot), (\mathbb{R}, +, \cdot), (\mathbb{C}, +, \cdot), (\mathbb{Z}/p\mathbb{Z}, +, \cdot)\)
  • Gegenbeispiele: \((\mathbb{Z}, +, \cdot)\)
• Vektorräume:
  • Definition
  • Beispiele: \(\mathbb{R}^2, \mathbb{R}^3, … , \mathbb{R}^n,\) Ring der Polynome

Algorithmen

• Gaußsches Eliminationsverfahren:
  • Was bedeuten Nullzeilen?
  • Wann hat das LGS keine / eine / viele Lösungen?
  • Welche Operationen erlaubt der Algorithmus?
• Matrixmultiplikation

Dies und das

• Permutationen und Transpositionen, Identische Abbildung
• Direkte Summe
• Schnitt zweier Vektorräume berechnen
• Was bedeuten die folgenden Symbole: \(\subseteq, \subset, \subsetneq, \cup, \setminus, \cap, \emptyset\)
• Regeln von de Morgan: \((A \cup B)^C = A^C \cap B^C\) und \((A \cap B)^C = A^C \cup B^C\)
• Homomorphismen, Isomorphismen (Automorphismus)
• Charakteristik, Lineare Hülle, Erzeugendensystem, Basis, Standardbasis, Basiswechsel

Links und Materialien

• MIT OpenCourseWare (Video Lectures)

Programmieren

Nur grundlagen in Java:

• Objekt
• Klasse
• Instanz
• Methode
• Getter und Setter
• Rekursion
• Zugriffsmodifikatoren: public, protected, private
• abstract
• Javadoc
• .equals, .toString

Grundbegriffe der Informatik

Aussagenlogik

• Was bedeuten die folgenden Symbole: \(\Rightarrow, \Leftrightarrow, \neg, \land, \lor, \forall, \exists\)

Formale Sprachen

• Wo ist der Unterschied zwischen \(\varepsilon\) und \(\emptyset\)?
• Alphabet, Wort, Grammatik, Sprache

Graphen

• gerichtete, ungerichtete und gewichtete Graphen
• Baum, Wurzel, Binärbaum
• Schleife, Schlinge, Kreis

Dies und das

• Zusicherungen, Schleifeninvariante
• Huffman-Codierung
• Algorithmus von Warshall, Adjazenzmatrix
• Landau-Symbole: \(\cal O, \Omega, \Theta\)
• Mealy-Automat und Moore-Automat

3. Semester

Betriebssysteme

Dies und das

• POSIX
• policy and mechanism
• multiprogramming and Batch processing
• Zombie and Orphan, fork, fork bomb
• Memory layout of a process (Stack, Heap, BSS, data, rodata, text)
• (synchroner / asynchroner) Interrupt, Excaption, Trap, System Call

Multithreaded Programming

• Deadlock
• Mutual exclusion, hold and wait, No preemption
• Critical section, semaphore, mutex, binary semaphore
• Spinlock
• Progress, Bounded waiting
• Race Condition

Cache

• Cache
• CPU cache
• Write through und write back policy
• Lokalitätseigenschaft

Scheduling

• scheduler
• Gantt chart
• turnaround time, response time, waiting time
• Starvation
• hardware requirements of preemptitive scheduling
• dispatcher

Memory Management

• TLB: Translation Lookaside Buffer
• Swapping: Roll out, Roll in
• Allocation
• Relocation
• Segmentation
• Paging
• First-fit, Best-fit, Worst-fit
• External Fragmentation, Internal Fragmentation
• Compile Time, Load time, Execution time
• Segment table

Theoretische Grundlagen der Informatik

Automaten

• DEA: \((Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, s \in Q, F \subseteq Q)\)
• NEA: \((Q, \Sigma, \delta: Q \times \Sigma \rightarrow 2^Q, s \in Q, F \subseteq Q)\), wobei \(2^Q\) die Potenzmenge von Q ist.
• Äquivalenz von DEA und NEA sowie die Konstruktion
• Turingmaschine: \((Q, \Sigma, \square, \Gamma, s \in Q, \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R, N\}, F \subseteq Q)\)
• Church’che These
• Satz von Rice
• Orakelmodul, Orakelband und Orakel-Turingmaschine

Sprachen und Probleme

• Kleene’scher Abschluss: \(L^*\)
• Positiver Abschluss: \(L^+\)
• Produktsprache: \(L_1 \cdot L_2\)
• Komplementsprache: \(L^C := \Sigma^* \setminus L\)
• Reguläre Sprachen: Alle von einem DEA erkannten Sprachen.
• Pumping-Lemma
• Nerode-Relation
• Entscheidbarkeit, Berechenbarkeit
• Diagonalsprache, Halteproblem, Universelle Sprache, Postsches Korrespondenzproblem
• Entscheidungsprobleme, Optimalwertprobleme, Optimierungsprobleme, Suchprobleme
• SAT, TSP, 3-SAT, CLIQUE, 3COLOR, EXACT COVER, SUBSET SUM, PARTITION
• Approximationen, Approximationsgüte

Komplexitätsklassen

• P und co-P
• NP und co-NP
• NPC und Satz von Cook
• P vs. NP: Wie könnte es bewiesen / wiederlegt werden?
• \(\cal NPI := NP \setminus (P \cup NPC)\)
• NP-schwer

Wahrscheinlichkeitstheorie

Hier haben wir ja die “Wahrscheinlichkeitstheorie und Statistik für Studierende der Informatik und des Ingenieurwesens” von Prof. Dr. N. Henze und Priv.-Doz. Dr. D. Kadelka. Das haben wir vermutlich auch schon durchgearbeitet. Da dieses Skript sehr ausführlich ist und in die Klausur mitgenommen werden darf, sehe ich eigentlich keinen Bedarf an weiteren Erklärungen. Es ist allerdings sehr zu empfehlen, die 11 Übungsblätter im VAB (Vorlesungsarbeitsbereich, Passwortgeschützt unter studium.kit.edu) zu machen!