Datenstrukturen, Algorithmen und Programmierung 1 at TU Dortmund

Flashcards and summaries for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund

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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Zusammenhänge von Datenstrukturen und Algorithmen

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Technische Voraussetzungen

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

konzeptionelle Voraussetzungen
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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Reduktion

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Speichern von Zwischenständen

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion: 

Backtracking

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Ausführung von Teilen
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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Analyse

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Zusammenfassung

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Definition

Exemplary flashcards for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Rekursion:

Backtracking-Algorithmus
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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Compiler    ​​​   

Your peers in the course Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund 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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund on StudySmarter:

Datenstrukturen, Algorithmen und Programmierung 1

Zusammenhänge von Datenstrukturen und Algorithmen
Die Gestaltung von Datenstrukturen und Algorithmen hängt zusammen und hat nichts mit Programmieren zu tun.Hat eine Datennstruktur bestimmte Eigenschaften, können Algorithmen diese nutzen.

Bei der Konzeption von Datenstrukturen und dara uf arbeitenden Algorithmen muss daher der Gesamtaufwand betrachtet werden


Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Technische Voraussetzungen
Java-Konzept:
  • Jede Ausfühurng einer Methode ist unabhängig von anderen Ausführungen von Methoden
  • Insbesondere: Jede Ausführung einer Methde ist unabhängig von anderen Ausführungen derselben Methodendeklaration
  • Jeder Aufruf einer Methode erhält f+r seine Ausführung neuen Speicherplatz für alle Parameter und alle Variablen zugeteilt.
  • Gleichzeitig bleibt der Speicherplatz von Parametern und Variablen erhalten, der für bereits laufende Auführung derselben Methodendeklaration benutzt wird.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

konzeptionelle Voraussetzungen
Damit ein rekursiv formulierter Algorithmus korrekt arbeitet, müssen immer drei Eigenschaften vorhanden sein:

Selbstaufruf:
Die Ausführung einer Methode führt zu einer weiteren Ausführung derselben Methode.

Abbruchkriterium für den Selbstaufruf:
Der Algotithmus einer rekursiven Methode muss in ausgewählten Situationen ein Ergebnis ohne erneuten rekursiven Aufruf berechnenen können. (Nu dann kann die Folge der rekursiven Ausführung irgendwann abbrechen)

Reduktion der Problemstellung:
Der Selbstaufruf einer rekursiven Metode muss immer für ein verkleinertes Problem erfolgen, das "näher" an dem Abbruchkriterium für die Rekursion liegt. (Nur dann wird das Abbruchkriterium irgendwann erreicht).

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Reduktion
Entscheidenden für die Entwicklung eines rekursiven Algorithmus war nur die Reduktion des Problems.
Da rekursive Algorithmen immer eine Reduktion des Problems für den rekursiven Aufruf enthalten müssen, ist es naheliegend, über einen passenden Denkansatz zu einem Algorithmus zu kommen.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Speichern von Zwischenständen
  • Jede Instanz einer rekursiven Methode enthält einen eigenen Satz von Variablen mit Werten.
  • Wird dieser Satz von Variablen dazu genutzt, um den Zwischenstand der Beladung festzuhalten, so kann einfach durch das Beenden von jüngeren Instanzen der Methode zu den älteren Instanzen und damit zu einem älteren Zwischenstand zurückgekehrt werden
  • Die aufeinander folgenden rekursiven Aufrufe bilden also ein Gedächtnis der bisher vorgenommenen Entscheidungen.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion: 

Backtracking
Hier wird zunächst versucht, eine Lösung zu finden.
Scheitert der Versuch, so wird die Rekursion eigesetzt, um zurückgehen zu können.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Ausführung von Teilen
unmittelbares Anstreben des gewünschten Ergebnisses. Die Rekursion dient dazu, die Ausführung von Teilen der Algorithmen zu koordnieren.
Bsp. 1: QuickSort: Zerlegen in 2 Abschnitte, Sortieren des einen Abschnitts, dann des anderen Abschnitts
Bsp.2 : Umstapeln von Töpfen: Stapeln auf dem Hilfsplatz, von dort Umstapeln zum Ziel.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Analyse
Der rekursive Lösungsansatz kann intuitiv gefunden werden.
Die Formulierung der rekursiven Lösung ist einfach.
Der Berechnungsaufwand der rekursiven Lösung ist hoch und nimmt schnell zu
Die Analyse des rekursiven Lösungsansatzes kann als Ausgangspunkt für die Entwicklung einer iterativen Lösung dienen

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Zusammenfassung
  • Rekursion ist ein brauchbares Konzept zur Entwicklung und Implementierung von Algorithmen.
  • Rekursive Algorithmen können dafür sorgen, dass kaskadenartige Werte abgearbeitet werden
  • Rekursive Algorithmen können ausnutzen, dass nach Ausführung der rekursiven Aufrufe die Werte von Parametern und lokalen Variablen noch verfügbar sind. So kann ein zweiter rekursiver Aufruf mit vernünftigen Parametern erfolgen.
  • Rekursive Algorithmen können wir andere Methoden Werte zurückgeben, Seiteneffekte erzeugen oder Ausgaben vornehmen.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Definition
Ein rekursiver Algorithmus ist dadurch gekennzeichnet, dass eine Lösung für eine Problemsituation durch erneutes Anwenden des gleichen Algorithmus auf eine etwas veränderte SItuation ermittelt wird (rekursiver Aufruf).

Ein Ende der Ausführung wird dadurch sichergestellt, dass für ausgezeichnete Situationen die Lösungen direkt ohne rekursiven Aufruf bestimmt werden können und die rekursiven Aufrufe letztlich immer zu einer solchen Situation hinführen.

Datenstrukturen, Algorithmen und Programmierung 1

Rekursion:

Backtracking-Algorithmus
Ein Backtracking-Algorithmus ist ein rekursiver Algorithmus, bei dem die Schachtelung der rekursiven Aufrufe genutzt wird, um einen Zwischenzustand der Lösungsentwicklung abzuspeichern, um gegebenenfalls zu diesem Zustand zurückkehren zu können und eine andere Fortsetzung der Lösungsentwicklung vorzunehmen.

Datenstrukturen, Algorithmen und Programmierung 1

Compiler    ​​​   
  • ist selbst ein Programm, das auf einem Rechner ausgeführt wird
  • einen Text in einer Programmiersprache als Eingabe nimmt und
  • einen Text in Maschinensprache als Ausgabe erzeugt, der auf Rechnern ausgeführt werden kann.
  • Problem:
    • Für eine Programmiersprache wird für jede Maschinensprache ein eigener Compiler benötigt

Sign up for free to see all flashcards and summaries for Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to TU Dortmund overview page

Datenstrukturen, Algorithmen und Programmierung 1

Algorithmen und Datenstrukturen at

TU München

Algorithmen und Datenstrukturen at

Universität Düsseldorf

Algorithmen und Datenstrukturen at

Hochschule Stralsund

Algorithmen und Datenstrukturen at

TU Berlin

Algorithmen und Datenstrukturen at

Hochschule Flensburg

Similar courses from other universities

Check out courses similar to Datenstrukturen, Algorithmen und Programmierung 1 at other universities

Back to TU Dortmund 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 Datenstrukturen, Algorithmen und Programmierung 1 at the TU Dortmund 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