Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg

Karteikarten und Zusammenfassungen für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg

Arrow Arrow

Komplett kostenfrei

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Lerne jetzt mit Karteikarten und Zusammenfassungen für den Kurs Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg.

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Testansatz vs Korrektheitsbeweis

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Definition von Rekursion

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Basisform der Induktion (Variante 2: „-1“)

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Beweistechnik vollständige Induktion

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Induktionsbeweis Etappen

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Beweise einer Rekursion, dass sie ein richtiges Ergebniss liefert

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

für Rekursion spricht

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Wie heist das Verfahren um eine Rekursion in eine Iterative Methode zu machen

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Wie kann man bestimmen ob die Rekursion keine Endlosrekursion ist ?

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Mögliche Fehler in einer Rekursion

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Definition einer Elementaroperation

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Voraussetzungen, damit rekursiver Ansatz erfolgreich

Kommilitonen im Kurs Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg. erstellen und teilen Zusammenfassungen, Karteikarten, Lernpläne und andere Lernmaterialien mit der intelligenten StudySmarter Lernapp. Jetzt mitmachen!

Jetzt mitmachen!

Flashcard Flashcard

Beispielhafte Karteikarten für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg auf StudySmarter:

Algorithmen und Datenstrukturen

Testansatz vs Korrektheitsbeweis

  • Testansatz: 
    • möglich: für jede Eingabe kann das zugehörige Ergebnis durch schrittweises Ausführen ermittelt werden
    • letzte Unsicherheit bleibt bzgl. der übrigen Eingaben
  • Variante 2: Korrektheitsbeweis
    • mit geeigneten Beweismethoden den Nachweis erbringen, dass die Methode für jede beliebige Eingabe immer das korrekte Ergebnis bzgl. der Spezifikation berechnet
    • im Zusammenhang mit rekursiven Methoden kommt dabei o

Algorithmen und Datenstrukturen

Definition von Rekursion

  • allgemeines Prinzip zur Lösung von Problemen, bei der die Berechnung auf die eigene Berechnung direkt oder indirekt zurückverweist
  • mit dieser wird auf dieselbe Weise verfahren
  • Durchführung bricht ab, wenn eine vorgegebene Abbruchbedingung erreicht wird

Algorithmen und Datenstrukturen

Basisform der Induktion (Variante 2: „-1“)

  • Bedingungen (zu beweisen):
    •  𝐴(1) ist wahr
    • Für jedes 𝑛 > 1 gilt: 𝐴(𝑛 − 1) ⇒ 𝐴(𝑛)
  • Dann gilt 𝐴(𝑛) für alle 𝑛.
    • hier: 𝑘 Anfangswerte 𝐴(1) , … , 𝐴(𝑘) gegeben
  • Strategie nun: „k parallele Pfade durch ℕ, die ℕ ganz überdecken“
  • Ziel: Nachweis der Gültigkeit einer Aussage 𝐴(𝑛) für alle 𝑛∈ℕ

Algorithmen und Datenstrukturen

Beweistechnik vollständige Induktion

  • Basisform der Induktion (Variante 1: „+1“)
  • Basisform der Induktion (Variante 2: „-1“)
  • k-Anfangsform der Induktion (Variante 1: „+k“)
  • k-Anfangsform der Induktion (Variante 2: „-k“)
  • strenge Induktion
  • Zweierpotenz-Induktion
  • Rückwärtsinduktion
  • strukturelle Induktion

Algorithmen und Datenstrukturen

Induktionsbeweis Etappen

Induktionsanfang

Induktionsschluss (oder: -schritt)

Algorithmen und Datenstrukturen

Beweise einer Rekursion, dass sie ein richtiges Ergebniss liefert

  • Variante 1: Testansatz
  • Variante 2: Korrektheitsbeweis

Algorithmen und Datenstrukturen

für Rekursion spricht

  • Elegante, intuitive, übersichtliche Problemlösungen.
  • Programmtext ist im Allg. lesbarer und weniger fehleranfällig.
  • Besonders geeignet für Algorithmen, die auf induktiv definierten Daten arbeiten, wodurch das Problem leicht in kleinere selbstähnliche Teilprobleme zerfällt.
  • Beweise von Eigenschaften, wie Übereinstimmung mit Spezifikation und Terminierung, sind oft nahe liegend per vollständiger Induktion.

Algorithmen und Datenstrukturen

Wie heist das Verfahren um eine Rekursion in eine Iterative Methode zu machen

Endrekursivierung

Algorithmen und Datenstrukturen

Wie kann man bestimmen ob die Rekursion keine Endlosrekursion ist ?

Terminierungsbeweis

Testansatz (für Auswahl von Eingaben)

Algorithmen und Datenstrukturen

Mögliche Fehler in einer Rekursion

Durch den fehlenden Basisfall, entsteht eine Endlosrekursion die zu einem StackOverflow führt

Algorithmen und Datenstrukturen

Definition einer Elementaroperation

Eine Elementaroperation entspricht genau einer Instruktion des zugrunde liegenden Von-Neumann-Rechners und hat das Kostenmaß 1.

Algorithmen und Datenstrukturen

Voraussetzungen, damit rekursiver Ansatz erfolgreich

  • Nicht direkt lösbare Teilprobleme müssen dem Ausgangsproblem ähnlich sein (Selbstähnlichkeit)
  • Teilprobleme werden bei jedem weiteren rekursiven Aufruf bzgl. einer Ordnung kleiner (Monotonieeigenschaft)
  • Größe der Teilprobleme ist nach unten beschränkt (Beschränktheit)

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang Informatik an der Universität Erlangen-Nürnberg gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Universität Erlangen-Nürnberg Übersichtsseite

Systemprogrammierung

Angewandte IT-Sicherheit

Parallele und Funktionale Programmierung

Rechnerkommunikation

Mathematik C1

Was ist StudySmarter?

Was ist StudySmarter?

StudySmarter ist eine intelligente Lernapp für Studenten. Mit StudySmarter kannst du dir effizient und spielerisch Karteikarten, Zusammenfassungen, Mind-Maps, Lernpläne und mehr erstellen. Erstelle deine eigenen Karteikarten z.B. für Algorithmen und Datenstrukturen an der Universität Erlangen-Nürnberg oder greife auf tausende Lernmaterialien deiner Kommilitonen zu. Egal, ob an deiner Uni oder an anderen Universitäten. Hunderttausende Studierende bereiten sich mit StudySmarter effizient auf ihre Klausuren vor. Erhältlich auf Web, Android & iOS. Komplett kostenfrei. Keine Haken.

Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards

So funktioniert's

Top-Image

Individueller Lernplan

StudySmarter erstellt dir einen individuellen Lernplan, abgestimmt auf deinen Lerntyp.

Top-Image

Erstelle Karteikarten

Erstelle dir Karteikarten mit Hilfe der Screenshot-, und Markierfunktion, direkt aus deinen Inhalten.

Top-Image

Erstelle Zusammenfassungen

Markiere die wichtigsten Passagen in deinen Dokumenten und bekomme deine Zusammenfassung.

Top-Image

Lerne alleine oder im Team

StudySmarter findet deine Lerngruppe automatisch. Teile deine Lerninhalte mit Freunden und erhalte Antworten auf deine Fragen.

Top-Image

Statistiken und Feedback

Behalte immer den Überblick über deinen Lernfortschritt. StudySmarter führt dich zur Traumnote.

1

Lernplan

2

Karteikarten

3

Zusammenfassungen

4

Teamwork

5

Feedback