Algortihmen & Datenstrukturen an der Hochschule Für Technik Und Wirtschaft Berlin | Karteikarten & Zusammenfassungen

Lernmaterialien für Algortihmen & Datenstrukturen an der Hochschule für Technik und Wirtschaft Berlin

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algortihmen & Datenstrukturen Kurs an der Hochschule für Technik und Wirtschaft Berlin zu.

TESTE DEIN WISSEN

Erkläre den Vorgang Suchen in einer verketteten Liste.

Lösung anzeigen
TESTE DEIN WISSEN

Suchen

Bei der Suche innerhalb einer einfach verketteten Liste, muss jedes einzelne Element nacheinander durchlaufen werden, bis das tatsächlich gesuchte Objekt gefunden wird, oder wir bereits am Ende der Liste angekommen sind. Entsprechend zeigt die Laufzeitkomplexität ein langsames Ergebnis von O(n)  auf.

Lösung ausblenden
TESTE DEIN WISSEN

Nenne den Vor- und Nachteil einer doppelt verketteten Liste gegenüber einer einfach verketteten Liste.

Lösung anzeigen
TESTE DEIN WISSEN

Doppelt verkettete Listen haben gegenüber einfach verketteten einerseits den Vorteil, dass sie sich auch von hinten nach vorne durchsuchen lassen. Außerdem lässt sich ein Knoten schneller löschen, weil der Vorgängerknoten bekannt ist – bei einfach verketteten Listen kennt ein Knoten ja nur den Nachfolger! Andererseits muss der Vorgängerzeiger zusätzlich gespeichert und beim Löschen und Einfügen angepasst werden.  

Lösung ausblenden
TESTE DEIN WISSEN

Unterschied von balancierten und unbalancierten Bäumen



Lösung anzeigen
TESTE DEIN WISSEN

Balancierte Bäume haben auf jeder Seite dieselbe Tiefe.

Unbalancierte Bäume haben unterschiedliche Tiefen auf jeder Seite

Lösung ausblenden
TESTE DEIN WISSEN

Was ist Semaphoren ?

Lösung anzeigen
TESTE DEIN WISSEN

Ein Semaphor ist eine Datenstruktur, die aus einer Ganzzahl und den atomaren Nutzungsoperationen „Reservieren/Probieren“ und „Freigeben“ besteht. Sie eignet sich insbesondere zur Verwaltung beschränkter (zählbarer) Ressourcen, auf die mehrere Prozesse oder Threads zugreifen sollen, wie etwa Erzeuger und Verbraucher, sowie zur Koordination asynchroner Abläufe. Im Gegensatz zu einem Lock bzw. einem Mutex müssen die Aktivitätsträger, die „reservieren“ und „freigeben“, nicht identisch sein.
 

Lösung ausblenden
TESTE DEIN WISSEN

Warum spricht man im Komprimierverfahren  png und jpeg von "Entropie"?  Erklären Sie dies anhand von Huffman Coding

Lösung anzeigen
TESTE DEIN WISSEN

Die Entropie gibt uns Auskunft darüber, wie stark wir maximal durch Reduktion von Signalredundanz komprimieren 

können. Dabei gilt: je geringer die Entropie, desto besser

die zu erwartende Kompressionsrate. Und durch die Huffman Kodierung wird nach der Häufigkeit der verwendeten Buchstaben sortiert und je nachdem werden die Bytes gekürzt.

Lösung ausblenden
TESTE DEIN WISSEN


Erklären Sie bitte von Queue verschiedene Typen und geben jeweils einen Anwendungsfall aus der Informatik und einen "aus dem echten Leben" an.



Lösung anzeigen
TESTE DEIN WISSEN

Typische Anwendungen für Warteschlangen in der Informatik sind:
• Druckerschlange
• Tastatureingabe
• Multitask-Systeme
• Breitensuche

 Beispiel nach FIFO Prinzip:

Stell dir eine Perlenkette vor. Wenn du Perlen auffädeln oder entfernen willst, geht das immer nur von den beiden Enden aus ohne die Kette zu zerstören. Genauso ist es auch mit den Datensätzen in einer Queue. Aus genau diesem Grund arbeitet eine solche Datenstruktur auch nach dem First-in-first-out-Prinzip. Das limitiert den Zugriff auf diese Elemente noch stärker, da wir nun nur noch in derselben Reihenfolge auf sie zugreifen können, in der wir sie „eingereiht“ haben.  





Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Queue in der Informatik?

Lösung anzeigen
TESTE DEIN WISSEN

Eine Art von Datenstruktur, die nur eingeschränkten Eingriff auf die in ihr gespeicherten Werte gewährt. Konkret bedeutet das, dass wir immer nur auf das erste oder das letzte Element der Schlange Zugriff haben.


Stack und Queue unterscheiden sich also nach dem Auswahlprinzip für das zu löschende Element:   

Stapel (Stack)                 Warteschlange(Queue) 
last in first out                          first in first out  

      LIFO                                             FIFO

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein Quad tree und wofür wird es verwendet


Lösung anzeigen
TESTE DEIN WISSEN

Ein Quadtree ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat.

Anwendungsbereiche: Komprimierung von Rasterbildern, Bildverarbeitung und Computergrafik 

Lösung ausblenden
TESTE DEIN WISSEN

Was ist Backtracking?

Lösung anzeigen
TESTE DEIN WISSEN

1. Definitionsmöglichkeit

Backtracking (Rückverfolgung) ist eine allgemeine algorithmische Technik, die die Suche nach jeder möglichen Kombination berücksichtigt, um ein Optimierungsproblem zu lösen. Backtracking wird auch als Tiefensuche oder Verzweigen und Binden bezeichnet.


2. Definitionsmöglichkeit

Ein Backtracking - Algorithmus gehört zur Gruppe der trial-and-error-Verfahren (versuchen und nachprüfen). Es wird

versucht, eine Teillösung systematisch zu einer Gesamtlösung auszubauen. Es werden alle möglichen Lösungswege untersucht.

Falls zwischendurch ein weiterer Ausbau einer Teillösung nicht mehr möglich ist (Sackgasse), werden Teilschritte rückgängig

gemacht. Die reduzierte Teillösung wird versucht, auf anderem Wege wieder auszubauen. Diese Wiederholung erfolgt, bis eine

Lösung gefunden wurde, oder erkannt wird, daß keine Lösung existiert. Typisch für Backtracking ist das Laufen in Sackgassen

und wieder herausfinden. 


Zurückgeführt wird das Verfahren auf Walker (1958). Es sollte dann angewandt werden, wenn kein besseres Verfahren zur
Lösung bekannt ist, als alle Kandidaten systematisch zu prüfen. 

Lösung ausblenden
TESTE DEIN WISSEN

Was bedeutet die Bachmann-Landau-Notation?

Lösung anzeigen
TESTE DEIN WISSEN

 In der Informatik werden die Symbole bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an.("schwer, leicht")

Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine einfach verkettete Liste?

Lösung anzeigen
TESTE DEIN WISSEN

Eine einfach verkettete Liste besteht aus Knoten und Zeigern. In den Knoten werden die Daten hinterlegt – also zum Beispiel Zahlen oder Zeichenketten. In den Zeigern wird auf den unmittelbaren Nachfolger des Elements verwiesen. Das heißt dann auch, dass ein Knoten nur Kenntnisse über diesen einen Nachfolger hat und der Durchlauf entsprechend nur in eine Richtung funktioniert.

Lösung ausblenden
TESTE DEIN WISSEN

 Was sind Komprimierverfahren in der Informatik?

Lösung anzeigen
TESTE DEIN WISSEN

Ist ein Vorgang, bei dem die Menge digitaler Daten verdichtet oder reduziert wird. Dadurch sinkt der benötigte Speicherplatz, und die Übertragungszeit der Daten verkürzt sich.

Lösung ausblenden
  • 18427 Karteikarten
  • 757 Studierende
  • 23 Lernmaterialien

Beispielhafte Karteikarten für deinen Algortihmen & Datenstrukturen Kurs an der Hochschule für Technik und Wirtschaft Berlin - von Kommilitonen auf StudySmarter erstellt!

Q:

Erkläre den Vorgang Suchen in einer verketteten Liste.

A:

Suchen

Bei der Suche innerhalb einer einfach verketteten Liste, muss jedes einzelne Element nacheinander durchlaufen werden, bis das tatsächlich gesuchte Objekt gefunden wird, oder wir bereits am Ende der Liste angekommen sind. Entsprechend zeigt die Laufzeitkomplexität ein langsames Ergebnis von O(n)  auf.

Q:

Nenne den Vor- und Nachteil einer doppelt verketteten Liste gegenüber einer einfach verketteten Liste.

A:

Doppelt verkettete Listen haben gegenüber einfach verketteten einerseits den Vorteil, dass sie sich auch von hinten nach vorne durchsuchen lassen. Außerdem lässt sich ein Knoten schneller löschen, weil der Vorgängerknoten bekannt ist – bei einfach verketteten Listen kennt ein Knoten ja nur den Nachfolger! Andererseits muss der Vorgängerzeiger zusätzlich gespeichert und beim Löschen und Einfügen angepasst werden.  

Q:

Unterschied von balancierten und unbalancierten Bäumen



A:

Balancierte Bäume haben auf jeder Seite dieselbe Tiefe.

Unbalancierte Bäume haben unterschiedliche Tiefen auf jeder Seite

Q:

Was ist Semaphoren ?

A:

Ein Semaphor ist eine Datenstruktur, die aus einer Ganzzahl und den atomaren Nutzungsoperationen „Reservieren/Probieren“ und „Freigeben“ besteht. Sie eignet sich insbesondere zur Verwaltung beschränkter (zählbarer) Ressourcen, auf die mehrere Prozesse oder Threads zugreifen sollen, wie etwa Erzeuger und Verbraucher, sowie zur Koordination asynchroner Abläufe. Im Gegensatz zu einem Lock bzw. einem Mutex müssen die Aktivitätsträger, die „reservieren“ und „freigeben“, nicht identisch sein.
 

Q:

Warum spricht man im Komprimierverfahren  png und jpeg von "Entropie"?  Erklären Sie dies anhand von Huffman Coding

A:

Die Entropie gibt uns Auskunft darüber, wie stark wir maximal durch Reduktion von Signalredundanz komprimieren 

können. Dabei gilt: je geringer die Entropie, desto besser

die zu erwartende Kompressionsrate. Und durch die Huffman Kodierung wird nach der Häufigkeit der verwendeten Buchstaben sortiert und je nachdem werden die Bytes gekürzt.

Mehr Karteikarten anzeigen
Q:


Erklären Sie bitte von Queue verschiedene Typen und geben jeweils einen Anwendungsfall aus der Informatik und einen "aus dem echten Leben" an.



A:

Typische Anwendungen für Warteschlangen in der Informatik sind:
• Druckerschlange
• Tastatureingabe
• Multitask-Systeme
• Breitensuche

 Beispiel nach FIFO Prinzip:

Stell dir eine Perlenkette vor. Wenn du Perlen auffädeln oder entfernen willst, geht das immer nur von den beiden Enden aus ohne die Kette zu zerstören. Genauso ist es auch mit den Datensätzen in einer Queue. Aus genau diesem Grund arbeitet eine solche Datenstruktur auch nach dem First-in-first-out-Prinzip. Das limitiert den Zugriff auf diese Elemente noch stärker, da wir nun nur noch in derselben Reihenfolge auf sie zugreifen können, in der wir sie „eingereiht“ haben.  





Q:

Was ist eine Queue in der Informatik?

A:

Eine Art von Datenstruktur, die nur eingeschränkten Eingriff auf die in ihr gespeicherten Werte gewährt. Konkret bedeutet das, dass wir immer nur auf das erste oder das letzte Element der Schlange Zugriff haben.


Stack und Queue unterscheiden sich also nach dem Auswahlprinzip für das zu löschende Element:   

Stapel (Stack)                 Warteschlange(Queue) 
last in first out                          first in first out  

      LIFO                                             FIFO

Q:

Was ist ein Quad tree und wofür wird es verwendet


A:

Ein Quadtree ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat.

Anwendungsbereiche: Komprimierung von Rasterbildern, Bildverarbeitung und Computergrafik 

Q:

Was ist Backtracking?

A:

1. Definitionsmöglichkeit

Backtracking (Rückverfolgung) ist eine allgemeine algorithmische Technik, die die Suche nach jeder möglichen Kombination berücksichtigt, um ein Optimierungsproblem zu lösen. Backtracking wird auch als Tiefensuche oder Verzweigen und Binden bezeichnet.


2. Definitionsmöglichkeit

Ein Backtracking - Algorithmus gehört zur Gruppe der trial-and-error-Verfahren (versuchen und nachprüfen). Es wird

versucht, eine Teillösung systematisch zu einer Gesamtlösung auszubauen. Es werden alle möglichen Lösungswege untersucht.

Falls zwischendurch ein weiterer Ausbau einer Teillösung nicht mehr möglich ist (Sackgasse), werden Teilschritte rückgängig

gemacht. Die reduzierte Teillösung wird versucht, auf anderem Wege wieder auszubauen. Diese Wiederholung erfolgt, bis eine

Lösung gefunden wurde, oder erkannt wird, daß keine Lösung existiert. Typisch für Backtracking ist das Laufen in Sackgassen

und wieder herausfinden. 


Zurückgeführt wird das Verfahren auf Walker (1958). Es sollte dann angewandt werden, wenn kein besseres Verfahren zur
Lösung bekannt ist, als alle Kandidaten systematisch zu prüfen. 

Q:

Was bedeutet die Bachmann-Landau-Notation?

A:

 In der Informatik werden die Symbole bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an.("schwer, leicht")

Q:

Was ist eine einfach verkettete Liste?

A:

Eine einfach verkettete Liste besteht aus Knoten und Zeigern. In den Knoten werden die Daten hinterlegt – also zum Beispiel Zahlen oder Zeichenketten. In den Zeigern wird auf den unmittelbaren Nachfolger des Elements verwiesen. Das heißt dann auch, dass ein Knoten nur Kenntnisse über diesen einen Nachfolger hat und der Durchlauf entsprechend nur in eine Richtung funktioniert.

Q:

 Was sind Komprimierverfahren in der Informatik?

A:

Ist ein Vorgang, bei dem die Menge digitaler Daten verdichtet oder reduziert wird. Dadurch sinkt der benötigte Speicherplatz, und die Übertragungszeit der Daten verkürzt sich.

Algortihmen & Datenstrukturen

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten Algortihmen & Datenstrukturen Kurse im gesamten StudySmarter Universum

Grundladen Algorithmen & Datenstrukturen

Universität Würzburg

Zum Kurs
Datenstrukturen und Algorithmen

Fachhochschule Campus 02 Graz

Zum Kurs
Aminosäuren / Strukturformeln

LMU München

Zum Kurs

Die all-in-one Lernapp für Studierende

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