Algorithmen Und Datenstrukturen an der Hochschule Weserbergland | Karteikarten & Zusammenfassungen

Lernmaterialien für Algorithmen und Datenstrukturen an der Hochschule Weserbergland

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen und Datenstrukturen Kurs an der Hochschule Weserbergland zu.

TESTE DEIN WISSEN

Was ist eine Datenstruktur?

Lösung anzeigen
TESTE DEIN WISSEN

• Eine Datenstruktur ist eine bestimmte Art, Daten zu verwalten und miteinander zu verknüpfen, um in geeigneter Weise auf diese zugreifen und diese manipulieren zu können 

- Die Mechanismen der erlaubten Operationen (Einfügen, Löschen, Ändern) sind Teil der Struktur! 

• Einfache Beispiele 

- Listen 

- Arrays

Lösung ausblenden
TESTE DEIN WISSEN

Wozu werden gute Algorithmen benötigt?

Lösung anzeigen
TESTE DEIN WISSEN

Computer werden zwar immer schneller und Speicher immer größer und billiger, aber 

• Geschwindigkeit und Speicher werden immer begrenzt sein 

• Die Problemstellungen werden immer komplexer 

• Die Datenmengen werden immer umfangreicher 

Daher muss auch heute mit den Ressourcen Zeit und Speicher geschickt umgegangen werden.

Lösung ausblenden
TESTE DEIN WISSEN

Erklären  Sie die Aufwandskriterien eines Algorithmus: Zeit- und Platzbedarf

Lösung anzeigen
TESTE DEIN WISSEN

• Das wichtigste Maß für die Geschwindigkeit von Algorithmen nennt man ihre Zeitkomplexität 

   - Dabei geht es nicht um exakte Aussagen, sondern nur um Größenordnungen. Man gibt an, wie sich die Laufzeit eines Algorithmus ändert, wenn sich das Datenvolumen ändert 


• Platzbedarf 

   - Ebenso wie der Zeitbedarf lässt sich der Platzbedarf eines Algorithmus messen. Dieses Maß nennt man die Speicherplatzkomplexität eines Algorithmus.

Lösung ausblenden
TESTE DEIN WISSEN

Was ist die O-Notation?

Lösung anzeigen
TESTE DEIN WISSEN

Mit Hilfe der O-Notation kann eine Abschätzung des Zeitverhaltens von Algorithmen abgegeben werden. Dabei werden bei Die Laufzeitfunktionen (z.B. 17 n² + 155 n + 3.157 ) vereinfacht durch:

  • Vereinheitlichen durch Bilden oberer Schranke
  • Weglassen von Summanden niedriger Ordnung
  • Ignorieren von Konstanten

für das obige Beispiel also O(n²).

Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Folge?

Lösung anzeigen
TESTE DEIN WISSEN

• Synonym: Sequenz, Liste 

• Eigenschaften 

   - Besitzt eine Länge, die durch die Anzahl Elemente in der Folge bestimmt ist 

   - Elemente der Folge haben den gleichen Grundtyp 

   - Elemente der Folge haben eine Ordnung 

- Vorgänger, Nachfolger 

- Duplikate erlaubt

  •  Grundlage zur Implementierung •
  •  Einfach oder doppelt verkettete Liste 
  • • Array
Lösung ausblenden
TESTE DEIN WISSEN

Was sind Stacks und Queues?

Lösung anzeigen
TESTE DEIN WISSEN

• Stack: Stapel 

   • Fixierung auf „oberstes“ Element 

   • Nur dieses sichtbar 

   • Nur dieses entnehmbar 

   • Einfügen eines neuen Elementes durch „darauf legen“ 

➢ LIFO – Struktur (last-in-first-out). 

   - Anwendungsfall: z.B. invertieren von Listen


• Queue: (Warte-)Schlange 

   • Entnahme von Elementen nur an einem Ende („vorne“) 

   • Anhängen von Elementen nur am anderen Ende („hinten“) 

   ➢ FIFO – Struktur (first-in-first-out).

   - Anwendungsfall: z.B. Druckerwarteschlange

Lösung ausblenden
TESTE DEIN WISSEN

Was ist die sequenzielle Suche und wie groß ist ihr Aufwand?

Lösung anzeigen
TESTE DEIN WISSEN

• Sequenzieller Durchlauf aller Listenelemente, beginnend mit dem ersten 

• Wird auch lineare Suche bezeichnet 


• Anzahl der Suchdurchläufe (die Liste habe die Länge n): 

• im besten Fall: 1 

• im schlechtesten Fall: n 

• durchschnittlich bei erfolgreicher Suche: n/2 

• bei erfolgloser Suche: n

Lösung ausblenden
TESTE DEIN WISSEN

Wie funktioniert die binäre Suche und wie groß ist ihr Aufwand?

Lösung anzeigen
TESTE DEIN WISSEN

• Schritte 

1. Wähle den mittleren Eintrag und prüfe, ob gesuchter Wert in der ersten oder der zweiten Hälfte der Folge ist 

2. Fahre analog 1. mit der Hälfte fort, in der sich der Eintrag befindet 

(Ende, wenn entweder der Eintrag gefunden oder wenn der Suchbereich keine Elemente mehr enthält) 


Aufwand = Anzahl der benötigten Schleifendurchläufe bis Element gefunden.


• Aufwand (n sei wiederum die Länge der Liste) 

• Im besten Fall: 1 

• Im schlechtesten Fall: log2 n 

➢ Finden des Elements erst „ganz am Schluss“ bzw. Element nicht in Liste 

• Nach dem ersten Teilen der Folge bleiben noch n/2 Elemente, nach dem zweiten Schritt noch n/4, nachdem dritten noch n/8 usw. 

• Allgemein: im i-ten Durchlauf sind maximal n/(2i) Elemente zu durchsuchen 

• Entsprechend werden log2 n Schritte benötigt 

• Im durchschnittlichen Fall: 0,5 * log2 n

Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine einfach verkettete Liste?

Lösung anzeigen
TESTE DEIN WISSEN

• Menge von Knoten, die untereinander „verzeigert“ sind 

• Ohne explizite Position • Jeder Knoten besitzt Verweis auf Nachfolgerknoten sowie das zu speichernde Element 

• Listenkopf: spezieller Knoten head ohne Inhalt, nur Zeiger

• Listenende: null-Zeiger.

Lösung ausblenden
TESTE DEIN WISSEN

Wie wird in einer verketteten Liste eingefügt?

Lösung anzeigen
TESTE DEIN WISSEN

1. Einfügeposition suchen 

2. Neuen Knoten anlegen 

3. Zeiger vom neuen Knoten auf Knoten an Einfügeposition 

4. Zeiger vom Vorgänger auf neuen Knoten

Lösung ausblenden
TESTE DEIN WISSEN

Erläutern Sie das Lösungsprinzip Divide-and-Conquer

Lösung anzeigen
TESTE DEIN WISSEN

Rekursive Rückführung eines zu lösenden Problems auf ein identisches Problem mit kleinerer Eingabemenge 

• Zerlege Problem P in Teilprobleme P1 ... Pn 

• Finde Lösungen L1 ... Ln der Teilprobleme 

• Setze Lösung L von P als Kombination aus L1 ... Ln zusammen

Lösung ausblenden
TESTE DEIN WISSEN

Nennen Sie die Eigenschaften eines Algorithmus.

Lösung anzeigen
TESTE DEIN WISSEN

• Spezifikation 

− Eingabespezifikation: Eingabegrößen 

− Ausgabespezifikation: Ausgabegröße 

• Durchführbarkeit 

− Endliche Beschreibung: Verfahren muss vollständig beschrieben sein 

− Effektivität: jeder Schritt muss effektiv ausführbar sein 

− Determiniertheit: bei jeder Ausführung für gleiche Eingabewerte auch immer die selben Ausgabewerte 

• Korrektheit 

− Partielle Korrektheit: jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Spezifikation entsprachen (ggf. keine Problemlösung) 

− Terminierung: Halt nach endlich vielen Schritten mit einem Ergebnis, sofern die Eingaben der Spezifikation entsprachen 


=> Wenn beide Bedingungen erfüllt, dann liegt „totale Korrektheit“ vor.

Lösung ausblenden
  • 6375 Karteikarten
  • 94 Studierende
  • 3 Lernmaterialien

Beispielhafte Karteikarten für deinen Algorithmen und Datenstrukturen Kurs an der Hochschule Weserbergland - von Kommilitonen auf StudySmarter erstellt!

Q:

Was ist eine Datenstruktur?

A:

• Eine Datenstruktur ist eine bestimmte Art, Daten zu verwalten und miteinander zu verknüpfen, um in geeigneter Weise auf diese zugreifen und diese manipulieren zu können 

- Die Mechanismen der erlaubten Operationen (Einfügen, Löschen, Ändern) sind Teil der Struktur! 

• Einfache Beispiele 

- Listen 

- Arrays

Q:

Wozu werden gute Algorithmen benötigt?

A:

Computer werden zwar immer schneller und Speicher immer größer und billiger, aber 

• Geschwindigkeit und Speicher werden immer begrenzt sein 

• Die Problemstellungen werden immer komplexer 

• Die Datenmengen werden immer umfangreicher 

Daher muss auch heute mit den Ressourcen Zeit und Speicher geschickt umgegangen werden.

Q:

Erklären  Sie die Aufwandskriterien eines Algorithmus: Zeit- und Platzbedarf

A:

• Das wichtigste Maß für die Geschwindigkeit von Algorithmen nennt man ihre Zeitkomplexität 

   - Dabei geht es nicht um exakte Aussagen, sondern nur um Größenordnungen. Man gibt an, wie sich die Laufzeit eines Algorithmus ändert, wenn sich das Datenvolumen ändert 


• Platzbedarf 

   - Ebenso wie der Zeitbedarf lässt sich der Platzbedarf eines Algorithmus messen. Dieses Maß nennt man die Speicherplatzkomplexität eines Algorithmus.

Q:

Was ist die O-Notation?

A:

Mit Hilfe der O-Notation kann eine Abschätzung des Zeitverhaltens von Algorithmen abgegeben werden. Dabei werden bei Die Laufzeitfunktionen (z.B. 17 n² + 155 n + 3.157 ) vereinfacht durch:

  • Vereinheitlichen durch Bilden oberer Schranke
  • Weglassen von Summanden niedriger Ordnung
  • Ignorieren von Konstanten

für das obige Beispiel also O(n²).

Q:

Was ist eine Folge?

A:

• Synonym: Sequenz, Liste 

• Eigenschaften 

   - Besitzt eine Länge, die durch die Anzahl Elemente in der Folge bestimmt ist 

   - Elemente der Folge haben den gleichen Grundtyp 

   - Elemente der Folge haben eine Ordnung 

- Vorgänger, Nachfolger 

- Duplikate erlaubt

  •  Grundlage zur Implementierung •
  •  Einfach oder doppelt verkettete Liste 
  • • Array
Mehr Karteikarten anzeigen
Q:

Was sind Stacks und Queues?

A:

• Stack: Stapel 

   • Fixierung auf „oberstes“ Element 

   • Nur dieses sichtbar 

   • Nur dieses entnehmbar 

   • Einfügen eines neuen Elementes durch „darauf legen“ 

➢ LIFO – Struktur (last-in-first-out). 

   - Anwendungsfall: z.B. invertieren von Listen


• Queue: (Warte-)Schlange 

   • Entnahme von Elementen nur an einem Ende („vorne“) 

   • Anhängen von Elementen nur am anderen Ende („hinten“) 

   ➢ FIFO – Struktur (first-in-first-out).

   - Anwendungsfall: z.B. Druckerwarteschlange

Q:

Was ist die sequenzielle Suche und wie groß ist ihr Aufwand?

A:

• Sequenzieller Durchlauf aller Listenelemente, beginnend mit dem ersten 

• Wird auch lineare Suche bezeichnet 


• Anzahl der Suchdurchläufe (die Liste habe die Länge n): 

• im besten Fall: 1 

• im schlechtesten Fall: n 

• durchschnittlich bei erfolgreicher Suche: n/2 

• bei erfolgloser Suche: n

Q:

Wie funktioniert die binäre Suche und wie groß ist ihr Aufwand?

A:

• Schritte 

1. Wähle den mittleren Eintrag und prüfe, ob gesuchter Wert in der ersten oder der zweiten Hälfte der Folge ist 

2. Fahre analog 1. mit der Hälfte fort, in der sich der Eintrag befindet 

(Ende, wenn entweder der Eintrag gefunden oder wenn der Suchbereich keine Elemente mehr enthält) 


Aufwand = Anzahl der benötigten Schleifendurchläufe bis Element gefunden.


• Aufwand (n sei wiederum die Länge der Liste) 

• Im besten Fall: 1 

• Im schlechtesten Fall: log2 n 

➢ Finden des Elements erst „ganz am Schluss“ bzw. Element nicht in Liste 

• Nach dem ersten Teilen der Folge bleiben noch n/2 Elemente, nach dem zweiten Schritt noch n/4, nachdem dritten noch n/8 usw. 

• Allgemein: im i-ten Durchlauf sind maximal n/(2i) Elemente zu durchsuchen 

• Entsprechend werden log2 n Schritte benötigt 

• Im durchschnittlichen Fall: 0,5 * log2 n

Q:

Was ist eine einfach verkettete Liste?

A:

• Menge von Knoten, die untereinander „verzeigert“ sind 

• Ohne explizite Position • Jeder Knoten besitzt Verweis auf Nachfolgerknoten sowie das zu speichernde Element 

• Listenkopf: spezieller Knoten head ohne Inhalt, nur Zeiger

• Listenende: null-Zeiger.

Q:

Wie wird in einer verketteten Liste eingefügt?

A:

1. Einfügeposition suchen 

2. Neuen Knoten anlegen 

3. Zeiger vom neuen Knoten auf Knoten an Einfügeposition 

4. Zeiger vom Vorgänger auf neuen Knoten

Q:

Erläutern Sie das Lösungsprinzip Divide-and-Conquer

A:

Rekursive Rückführung eines zu lösenden Problems auf ein identisches Problem mit kleinerer Eingabemenge 

• Zerlege Problem P in Teilprobleme P1 ... Pn 

• Finde Lösungen L1 ... Ln der Teilprobleme 

• Setze Lösung L von P als Kombination aus L1 ... Ln zusammen

Q:

Nennen Sie die Eigenschaften eines Algorithmus.

A:

• Spezifikation 

− Eingabespezifikation: Eingabegrößen 

− Ausgabespezifikation: Ausgabegröße 

• Durchführbarkeit 

− Endliche Beschreibung: Verfahren muss vollständig beschrieben sein 

− Effektivität: jeder Schritt muss effektiv ausführbar sein 

− Determiniertheit: bei jeder Ausführung für gleiche Eingabewerte auch immer die selben Ausgabewerte 

• Korrektheit 

− Partielle Korrektheit: jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Spezifikation entsprachen (ggf. keine Problemlösung) 

− Terminierung: Halt nach endlich vielen Schritten mit einem Ergebnis, sofern die Eingaben der Spezifikation entsprachen 


=> Wenn beide Bedingungen erfüllt, dann liegt „totale Korrektheit“ vor.

Algorithmen und Datenstrukturen

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 Algorithmen und Datenstrukturen an der Hochschule Weserbergland

Für deinen Studiengang Algorithmen und Datenstrukturen an der Hochschule Weserbergland 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 Algorithmen und Datenstrukturen Kurse im gesamten StudySmarter Universum

Algorithmen & Datenstrukturen

Hochschule Niederrhein

Zum Kurs
Algorithmen & Datenstrukturen

Hochschule Kempten

Zum Kurs
Datenstrukturen und Algorithmen

Fachhochschule Campus 02 Graz

Zum Kurs
Algorithmen & Datenstrukturen

Duale Hochschule Baden-Württemberg

Zum Kurs
Datenstrukturen und Algorithmen

RWTH Aachen

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Algorithmen und Datenstrukturen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Algorithmen und Datenstrukturen