Theoretische Informatik III an der Universität Stuttgart | Karteikarten & Zusammenfassungen

Lernmaterialien für Theoretische Informatik III an der Universität Stuttgart

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Theoretische Informatik III Kurs an der Universität Stuttgart zu.

TESTE DEIN WISSEN

Was ist die Klasse O(n) 

Lösung anzeigen
TESTE DEIN WISSEN

O(n) ist eine Klasse von Funktionen von ℕ  nach ℕ , zu der die Funktion g gehört, wenn Konstanten N0 und c > 0 existieren mit: g(n)<=c ·f (n) für alle n N0

Lösung ausblenden
TESTE DEIN WISSEN

Was ist die Klasse Omega(f)

Lösung anzeigen
TESTE DEIN WISSEN

g(n) >= c ·f (n) für alle n >= N0

Lösung ausblenden
TESTE DEIN WISSEN

Wie bildet sich die Funktionsklasse Θ(f)?

Lösung anzeigen
TESTE DEIN WISSEN

Θ(f) = O(f) ∩ Ω(f)

Lösung ausblenden
TESTE DEIN WISSEN

Was ist die klasse o(f)

Lösung anzeigen
TESTE DEIN WISSEN

o(f ) enthält die Funktion g, falls für alle c > 0 ein N0 existiert, sodass für alle n=>N0 die Ungleichung g(n)<=c ·f (n) gilt.

Lösung ausblenden
TESTE DEIN WISSEN

Wie funktioniert Devide & Conquer

Lösung anzeigen
TESTE DEIN WISSEN

Teile ein Array in unterteile auf.

  • a1... an wird in b1..bm und c1..cn-m geteilt
  • Ausführung der berechnung rekursiv auf beide Teil-Arrays. Die Ergebnisse sind LSG c und LSG b
  • Füge LSG b und LSG c zur LSG a zusammen
Lösung ausblenden
TESTE DEIN WISSEN

Nenne einen Algorithmus, der mit dem Devide & Conquer Prinzip funktioniert

Lösung anzeigen
TESTE DEIN WISSEN

z.B. Mergesort

Lösung ausblenden
TESTE DEIN WISSEN

Wie ist die Gesamtlaufzeit für Mergesort

Lösung anzeigen
TESTE DEIN WISSEN

Aufruftiefe ist log n 

Je Aufrufebene ist der Aufwand O(n) 


gesamt ist O(n log n)


Lösung ausblenden
TESTE DEIN WISSEN

Laufzeit worst-case und avg-case von Quicksort

Lösung anzeigen
TESTE DEIN WISSEN

worst-case Θ(n^2)


avg-case O(n log n)

Lösung ausblenden
TESTE DEIN WISSEN

Wie ist die Laufzeit, wenn die Aufteilung in jedem Schritt so, dass Ein Teil die Größe 100000 und N-100000 hat? 

Lösung anzeigen
TESTE DEIN WISSEN

Θ(n^2) 

Lösung ausblenden
TESTE DEIN WISSEN

Rechenzeit bei Aufteilungen bei 0,0001N und 0,9999N?

Lösung anzeigen
TESTE DEIN WISSEN

O(n log n) 


Allgemein gilt, dass bei einer Aufteilung in a · N und (1- a)N die Rekursionstiefe logarithmisch und die Laufzeit in O(n log n) ist.


Lösung ausblenden
TESTE DEIN WISSEN

Was ist das Grundprinzip für Dynamisches Programmieren

Lösung anzeigen
TESTE DEIN WISSEN

Für das Gesamtproblem wird eine Lösung aus vorher ermittelten Teil-Lösungen generiert. Dazu sollen möglichst viele Teil-Lösungen in einer Tabelle organisiert aufbewahrt werden.

Lösung ausblenden
TESTE DEIN WISSEN

Nenne ein bekanntes und einfaches Beispiel für eine Berechnung mit dynamischem Programmieren 

Lösung anzeigen
TESTE DEIN WISSEN

Ermittlung des Binominalkoeffizienten (n über k) mit dem Pascal'schen Dreieck

Lösung ausblenden
  • 66036 Karteikarten
  • 1430 Studierende
  • 47 Lernmaterialien

Beispielhafte Karteikarten für deinen Theoretische Informatik III Kurs an der Universität Stuttgart - von Kommilitonen auf StudySmarter erstellt!

Q:

Was ist die Klasse O(n) 

A:

O(n) ist eine Klasse von Funktionen von ℕ  nach ℕ , zu der die Funktion g gehört, wenn Konstanten N0 und c > 0 existieren mit: g(n)<=c ·f (n) für alle n N0

Q:

Was ist die Klasse Omega(f)

A:

g(n) >= c ·f (n) für alle n >= N0

Q:

Wie bildet sich die Funktionsklasse Θ(f)?

A:

Θ(f) = O(f) ∩ Ω(f)

Q:

Was ist die klasse o(f)

A:

o(f ) enthält die Funktion g, falls für alle c > 0 ein N0 existiert, sodass für alle n=>N0 die Ungleichung g(n)<=c ·f (n) gilt.

Q:

Wie funktioniert Devide & Conquer

A:

Teile ein Array in unterteile auf.

  • a1... an wird in b1..bm und c1..cn-m geteilt
  • Ausführung der berechnung rekursiv auf beide Teil-Arrays. Die Ergebnisse sind LSG c und LSG b
  • Füge LSG b und LSG c zur LSG a zusammen
Mehr Karteikarten anzeigen
Q:

Nenne einen Algorithmus, der mit dem Devide & Conquer Prinzip funktioniert

A:

z.B. Mergesort

Q:

Wie ist die Gesamtlaufzeit für Mergesort

A:

Aufruftiefe ist log n 

Je Aufrufebene ist der Aufwand O(n) 


gesamt ist O(n log n)


Q:

Laufzeit worst-case und avg-case von Quicksort

A:

worst-case Θ(n^2)


avg-case O(n log n)

Q:

Wie ist die Laufzeit, wenn die Aufteilung in jedem Schritt so, dass Ein Teil die Größe 100000 und N-100000 hat? 

A:

Θ(n^2) 

Q:

Rechenzeit bei Aufteilungen bei 0,0001N und 0,9999N?

A:

O(n log n) 


Allgemein gilt, dass bei einer Aufteilung in a · N und (1- a)N die Rekursionstiefe logarithmisch und die Laufzeit in O(n log n) ist.


Q:

Was ist das Grundprinzip für Dynamisches Programmieren

A:

Für das Gesamtproblem wird eine Lösung aus vorher ermittelten Teil-Lösungen generiert. Dazu sollen möglichst viele Teil-Lösungen in einer Tabelle organisiert aufbewahrt werden.

Q:

Nenne ein bekanntes und einfaches Beispiel für eine Berechnung mit dynamischem Programmieren 

A:

Ermittlung des Binominalkoeffizienten (n über k) mit dem Pascal'schen Dreieck

Theoretische Informatik III

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Theoretische Informatik III an der Universität Stuttgart

Für deinen Studiengang Theoretische Informatik III an der Universität Stuttgart gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Theoretische Informatik III Kurse im gesamten StudySmarter Universum

Theoretische Informatik

Universität Tübingen

Zum Kurs
theoretische Informatik

Universität Tübingen

Zum Kurs
Theoretische Informatik

Hochschule des Bundes für öffentliche Verwaltung

Zum Kurs
Theoretische Informatik

Hochschule Worms

Zum Kurs
Theoretische Informatik

Universität Würzburg

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Theoretische Informatik III
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Theoretische Informatik III