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:

Algorithmische Eigenschaften

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

Übersetzungszeit versus Laufzeit

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

Variable

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

Aufwand bei Zugriff auf Array

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

MinSuche Linear

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

Konstanten

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

Aus was besteht eine Rekursion?

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

Voraussetzungen, damit rekursiver Ansatz erfolgreich

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:

Induktionsbeweis Etappen

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:

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

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

Algorithmische Eigenschaften

  • Endlichkeit:

    • Die Beschreibung ist endlich lang.

  • Terminierung:

    • Nach Durchführung endlich vieler Operationen kommt das Verfahren zum Stillstand.

  • eindeutige Reihenfolge:

    • Die Reihenfolge, in der Operationen anzuwenden sind, ist festgelegt.

  • eindeutige Wirkung:

    • Die Wirkung jeder Anweisung der Anweisungsfolge und damit der gesamten Folge ist eindeutig festgelegt.

  • Hinweis: die Eigenschaft der Terminierung wird manchmal auch weggelassen, um auch z. B. auch nicht abbrechende Server- Prozesse zu umfassen

Algorithmen und Datenstrukturen

Übersetzungszeit versus Laufzeit

Übersetzungszeit = bei der Übersetzung;

Laufzeit = Während das Programm läuft;

Algorithmen und Datenstrukturen

Variable

- Muss deklariert werden

- Hat Namen und Datentyp

- Verweist bei Objekt nur auf Objektreferenz

Algorithmen und Datenstrukturen

Aufwand bei Zugriff auf Array

O(1)

Algorithmen und Datenstrukturen

MinSuche Linear

- O(n)

- Iteration mit jeweils Merken des kleinsten Elements

Algorithmen und Datenstrukturen

Konstanten

- Schlüsselwort final

- nur lesender Zugriff

- Konvention: Groß geschrieben

Algorithmen und Datenstrukturen

Aus was besteht eine Rekursion?

In der rekursiven Methode muss ein Rekursionsschritt und einen Basisfall.

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)

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

Induktionsbeweis Etappen

Induktionsanfang

Induktionsschluss (oder: -schritt)

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

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 𝑛∈ℕ

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 Algorithmen und Datenstrukturen 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

Softwareentwicklung in Großprojekten (SoSy3)

griechisch

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
X

StudySmarter - Die Lernplattform für Studenten

StudySmarter

4.5 Stars 1100 Bewertungen
Jetzt entdecken
X

Gute Noten in der Uni? Kein Problem mit StudySmarter!

89% der StudySmarter Nutzer bekommen bessere Noten in der Uni.

50 Mio Karteikarten & Zusammenfassungen
Erstelle eigene Lerninhalte mit Smart Tools
Individueller Lernplan & Statistiken


Lerne mit über 1 Millionen Nutzern in der kostenlosen StudySmarter App.

Du bist schon registriert? Hier geht‘s zum Login