coma

Question 1

Relation

Question 2

Funktion

Question 3

bijektive abblidung

Question 4

BIG O 3 def

Question 5

sieb erathosphen

Question 6

geometrische Summe, t die Summe der ersten n ungeraden Zahlen gleich n
2

Question 7

induktion (2)

Question 8

module definitionen

Question 9

e b-adische Darstellung

Question 10

b-Komplement und Eigenschaften

Question 11

b-Komplementdarstellung
ganzer Zahlen

Question 12

Karazubas Multiplikation

Question 13

Euklidischer Algorithmus

Question 14

Definition
Ein ungerichteter Graph G

Question 15

Definition
Ein gerichteter Graph

Question 16

δ(v)

Question 17

Einfache Graphen

Question 18

Handschlaglemma

Question 19

Reguläre Graphen

Question 20

Teilgraphen, Wege, Kreise

Question 21

6.4 Zusammenhang und Zusammenhangskomponenten

Question 22

Die Relation R ⊆ V × V ist
i reflexiv, d.h. (u, u) ∈ R für alle u ∈ V;
ii symmetrisch, d.h. für alle u, v ∈ V gilt: (u, v) ∈ R =⇒ (v, u) ∈ R;
iii transitiv, d.h. für alle u, v, w ∈ V gilt: (u, v) ∈ R ∧ (v, w) ∈ R =⇒ (u, w) ∈ R

Question 23

Zusammenhang für gerichtete Graphen

Question 24

Eulersche Graphen

Question 25

6.6 Graphen mit Eulertour

Question 26

6.7 Wälder, Bäume, Blätter

Question 27

Sei G ein Wald mit n Knoten und m Kanten, der aus p Bäumen besteht. Dann ist n = m + p.

Question 28

6.8 Charakterisierung von Bäumen (7 st)

Question 29

6.9 Charakterisierung zusammenhängender Graphen

Question 30

6.10 Branchings und Arboreszenzen

Question 31

Adjazenzmatrix/Inzidenzmatrix/Adjazenz- / Inzidenzlisten

Question 32

Vorteile und Nachteile von Adjazenzlisten und -matrizen

Question 33

7.1 Algorithmus zur Graphendurchmusterung (python julia)

Question 34

Der Algorithmus zur Graphendurchmusterung ist korrekt. Er kann so implementiert werden, dass seine Laufzeitfunktion in O(|V| + |E|) ist.

Question 35

Bemerkungen zu Breitensuche und Tiefensuche

Question 36

8.1 Partielle und totale Ordnungen

Question 37

Topologische Sortierung

Question 38

8.2 Selection-Sort (python julia )

Question 39

3 Insertion-Sort

Question 40

5 Merge-Sort

Question 41

Aufteilungs-Beschleunigungs-Satz

Question 42

Satz Jeder auf paarweisen Vergleichen basierende Algorithmus benötigt zum Sortieren einer n-elementigen Menge im Worst-Case Ω(n log n) Vergleiche. gilt nur determinishtische

Question 43

Quick-Sort

Question 44

Verfeinerte Laufzeitanalyse von Quick-Sort

Question 45

Erwartete Laufzeit mit zufälligem Pivot-Element (quicksort )

Question 46

Nützliche Eigenschaften von Sortierverfahren (tabelle)

Question 47

Definition i Ein Sortierverfahren heißt stabil, falls Elemente mit demselben Wert im Output in derselben Reihenfolge wie im Input auftauchen. ii Ein Sortierverfahren arbeitet in-place (oder in situ), falls es zusätzlich zum Eingabearray nur konstant viel Speicher zum Zwischenspeichern der zu sortierenden Elemente benötigt

Question 48

Median und i-te geordnete Statistik

Question 49

Satz (Verallgemeinerter Aufteilungs-Beschleunigungs-Satz)

Question 50

Counting radix bucket sort

Question 51

Kapitel 10 lesen ende

Question 52

Unabhängigkeitssystem

Question 53

Unabhängigkeitssystem Weitere Beispiele und Terminologie

Question 54

Matroide: Definition

Question 55

Graphische Matroide

Question 56

Lineare Matroide / Vektormatroide

Question 57

Charakterisierung von Matroiden mithilfe von Basen

Question 58

matroide (Basisaustauschsatz)

Question 59

Greedy-Algorithmus/Greedy-Algorithmus II/ Worst-Out-Greedy-Algorithmus

Question 60

duale Unabhängigkeitssystem (E, F ∗ )

Question 61

Laufzeitanalyse der Greedy-Algorithmen

Question 62

Minimum Spanning Tree (MST) Problem

Question 63

Kruskals Algorithmus python julia O(|E| · |V|) Bemerkung: Geeignete Datenstruktur (Union-Find) liefert Laufzeit O(|E| log |V|) – siehe CoMa II. Martin Skutella et al. Computerorientierte Mathematik TU Berlin 2024/25

Question 64

Prims Algorithmus für minimal aufspannende Bäume

Question 65

Gültige Regeln für Auswählen / Löschen von MST-Kanten

Question 66

linked list