Algorithmen und Datenstrukturen at Universität Erlangen-Nürnberg

Flashcards and summaries for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg

Arrow Arrow

It’s completely free

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

Study with flashcards and summaries for the course Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Algorithmische Eigenschaften

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Übersetzungszeit versus Laufzeit

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Variable

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Aufwand bei Zugriff auf Array

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

MinSuche Linear

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Konstanten

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Aus was besteht eine Rekursion?

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Voraussetzungen, damit rekursiver Ansatz erfolgreich

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Testansatz vs Korrektheitsbeweis

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Induktionsbeweis Etappen

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

Beweistechnik vollständige Induktion

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on StudySmarter:

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

Your peers in the course Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Flashcard Flashcard

Exemplary flashcards for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg on 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 𝑛∈ℕ

Sign up for free to see all flashcards and summaries for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Universität Erlangen-Nürnberg overview page

Systemprogrammierung

Angewandte IT-Sicherheit

Parallele und Funktionale Programmierung

Rechnerkommunikation

Mathematik C1

Softwareentwicklung in Großprojekten (SoSy3)

griechisch

english

Algorithmen & Datenstrukturen at

Hochschule Niederrhein

Grundladen Algorithmen & Datenstrukturen at

Universität Würzburg

Algorithmen & Datenstrukturen at

Hochschule Kempten

Datenstrukturen und Algorithmen at

Fachhochschule Campus 02 Graz

Datenstruktur und Algorithmentheorie at

Technische Universität Graz

Similar courses from other universities

Check out courses similar to Algorithmen und Datenstrukturen at other universities

Back to Universität Erlangen-Nürnberg overview page

What is StudySmarter?

What is StudySmarter?

StudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Algorithmen und Datenstrukturen at the Universität Erlangen-Nürnberg or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
X

StudySmarter - The study app for students

StudySmarter

4.5 Stars 1100 Rating
Start now!
X

Good grades at university? No problem with StudySmarter!

89% of StudySmarter users achieve better grades at university.

50 Mio Flashcards & Summaries
Create your own content with Smart Tools
Individual Learning-Plan

Learn with over 1 million users on StudySmarter.

Already registered? Just go to Login