Select your language

Suggested languages for you:
Log In App nutzen

Lernmaterialien für AuD an der Fachhochschule Wedel

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen AuD Kurs an der Fachhochschule Wedel zu.

TESTE DEIN WISSEN

Worin besteht die Schwachstelle der klassischen Laufzeitanalyse?

Lösung anzeigen
TESTE DEIN WISSEN

Es werden die einzelnen Operationen isoliert über einer Datenstruktur betrachtet.

Lösung ausblenden
TESTE DEIN WISSEN

Wie erfolge die Berechnung der Aggregats-Methode?

Lösung anzeigen
TESTE DEIN WISSEN
  1. Es wird die Laufzeit der im worst case berechnet 
  2. Die Laufzeit wird durch die Länge der Folge geteilt
Lösung ausblenden
TESTE DEIN WISSEN

Beschreibe die Funktion der Accounting-Methode.

Lösung anzeigen
TESTE DEIN WISSEN

Bei der Accounting-Methode sparen die Methoden mit geringer Laufzeit Laufzeit auf einem Konto Laufzeit an, mit der im späteren Verlauf teurere Methoden bezahlt werden. (die teuren Methoden leeren das Konto wieder)
Dabei darf die Laufzeit auf dem Konto allerdings niemals negativ werden.

Lösung ausblenden
TESTE DEIN WISSEN

Warum ist das Traversieren einer Liste ineffizienter als das Traversieren eines Arrays?

Lösung anzeigen
TESTE DEIN WISSEN
  • Bei einer Liste werden die Speicheradressen der Knoten zufällig gewählt (sind also verteilt) hoher Cache miss
  • Bei einem Array sind die Speicheradressen alle hintereinander da die ja zusammen gehören (für den Prozessor vorhersehbar welcher Speicher benötigt wird, daher auch Kopieren eines Arrays effizienter als das Traversieren einer Liste) geringer Cache miss
Lösung ausblenden
TESTE DEIN WISSEN

Was sind die Stärken und Schwächen der Array-List (MyDSFastArrayList)

Lösung anzeigen
TESTE DEIN WISSEN
  • Stärken:
    - Indizierte Operationen, Zugriff, Einfügen, Entfernen, aufgrund weniger Cache misses
    - Suchen nach Elementen
    - Operationen, Zugriff, Einfügen, Entfernen am Listenanfang und Ende (nur der DSArrayList)
  • Schwächen:
    - Die Verarbeitung von Elementen während der Iteration (also bei jedem Element wird geguckt, ob hier was eingefügt oder gelöscht werden soll) ineffizient daher, dass dort das jedes mal das Array geprüft werden oder verändert werden muss Werte umkopieren O(N^2)


Lösung ausblenden
TESTE DEIN WISSEN

Was sind die Stärken und Schwächen der Veketteten Liste (Doppelt verkettete Ringliste)

Lösung anzeigen
TESTE DEIN WISSEN
  • Stärken:
    - Die Verarbeitung von Elementen während der Iteration O(N)
    - Operationen, Zugriff, Einfügen, Entfernen am Listenanfang und Ende (nur der DoppeltenRingListe)
  • Schwächen:
    - Indizierte Operationen, da ja trotz alle dem Iteriert werden muss zwar nur halb so viel aber Iterationen bei Listen sehr ineffizient, da die Elemente Zufällig im Speicher hinterlegt sind, viele Cache misses
    Suchen nach Elementen da die Traversierung ineffizient ist
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine typische Operation von abstrakten Datentypen?

Lösung anzeigen
TESTE DEIN WISSEN
  • Die Suche
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Lineare Suche?

Lösung anzeigen
TESTE DEIN WISSEN

Eine Suche die in Linearer Zeit erfolgt

Lösung ausblenden
TESTE DEIN WISSEN

Was sind die Eigenschaften Binärer Suchbäume?

Lösung anzeigen
TESTE DEIN WISSEN
  • Wenn x ein Knoten ist und y ist der linke Unterbaum, so gilt das y < x ist
  • Wenn x ein Knoten ist und z ist der rechte Unterbaum, so gilt das z > x ist
Lösung ausblenden
TESTE DEIN WISSEN

Was ist das Problem bei einem Binären Suchbaum?

Lösung anzeigen
TESTE DEIN WISSEN
  • Eine O(ld(N)) kann nicht garantiert werden bei der Suche oder dem Einfügen, da ein entarteter Suchbaum eine Laufzeitkomplexität einer Liste Aufweist O(N) 
  • Entartete Suchbäume entstehen, wenn eine vorsortierte Einfügung erfolgt
  • Bei einer Zufälligen einfüfung ist die Laufzeit dann bei 1,39* ld(N)
Lösung ausblenden
TESTE DEIN WISSEN

Was ist der Unterschiede zwischen Tries und der Binären Suche und Binärer Baume?

Lösung anzeigen
TESTE DEIN WISSEN
  • Bei der Binären Suchen und den Binären Bäumen gibt es über die Schlüssel eine Totale Ordnung, welche für die Suche per Vergleichsoperation benötigt wird, die Schlüssel sind Teil eines Knotens
  • Bei den Tries handelt es sich bei den Schlüsseln um Zeichenketten (String) diese sind auf den Kanten enthalten und bilden so ein Schlüsselwort um das entsprechende Element zu erreichen
Lösung ausblenden
TESTE DEIN WISSEN

Wie kann umgangen werden beim Einfügen oder Löschen eines Elementes in einer ArrayList das kopieren des Kompletten Arrays zu verhindern?

Lösung anzeigen
TESTE DEIN WISSEN
  • Es kann das Array beim Einfügen um mehrere Elemente vergrößert werden so das das kopieren nicht bei jedem Einfügen erfolgen muss. 
Lösung ausblenden
  • 13197 Karteikarten
  • 250 Studierende
  • 22 Lernmaterialien

Beispielhafte Karteikarten für deinen AuD Kurs an der Fachhochschule Wedel - von Kommilitonen auf StudySmarter erstellt!

Q:

Worin besteht die Schwachstelle der klassischen Laufzeitanalyse?

A:

Es werden die einzelnen Operationen isoliert über einer Datenstruktur betrachtet.

Q:

Wie erfolge die Berechnung der Aggregats-Methode?

A:
  1. Es wird die Laufzeit der im worst case berechnet 
  2. Die Laufzeit wird durch die Länge der Folge geteilt
Q:

Beschreibe die Funktion der Accounting-Methode.

A:

Bei der Accounting-Methode sparen die Methoden mit geringer Laufzeit Laufzeit auf einem Konto Laufzeit an, mit der im späteren Verlauf teurere Methoden bezahlt werden. (die teuren Methoden leeren das Konto wieder)
Dabei darf die Laufzeit auf dem Konto allerdings niemals negativ werden.

Q:

Warum ist das Traversieren einer Liste ineffizienter als das Traversieren eines Arrays?

A:
  • Bei einer Liste werden die Speicheradressen der Knoten zufällig gewählt (sind also verteilt) hoher Cache miss
  • Bei einem Array sind die Speicheradressen alle hintereinander da die ja zusammen gehören (für den Prozessor vorhersehbar welcher Speicher benötigt wird, daher auch Kopieren eines Arrays effizienter als das Traversieren einer Liste) geringer Cache miss
Q:

Was sind die Stärken und Schwächen der Array-List (MyDSFastArrayList)

A:
  • Stärken:
    - Indizierte Operationen, Zugriff, Einfügen, Entfernen, aufgrund weniger Cache misses
    - Suchen nach Elementen
    - Operationen, Zugriff, Einfügen, Entfernen am Listenanfang und Ende (nur der DSArrayList)
  • Schwächen:
    - Die Verarbeitung von Elementen während der Iteration (also bei jedem Element wird geguckt, ob hier was eingefügt oder gelöscht werden soll) ineffizient daher, dass dort das jedes mal das Array geprüft werden oder verändert werden muss Werte umkopieren O(N^2)


Mehr Karteikarten anzeigen
Q:

Was sind die Stärken und Schwächen der Veketteten Liste (Doppelt verkettete Ringliste)

A:
  • Stärken:
    - Die Verarbeitung von Elementen während der Iteration O(N)
    - Operationen, Zugriff, Einfügen, Entfernen am Listenanfang und Ende (nur der DoppeltenRingListe)
  • Schwächen:
    - Indizierte Operationen, da ja trotz alle dem Iteriert werden muss zwar nur halb so viel aber Iterationen bei Listen sehr ineffizient, da die Elemente Zufällig im Speicher hinterlegt sind, viele Cache misses
    Suchen nach Elementen da die Traversierung ineffizient ist
Q:

Was ist eine typische Operation von abstrakten Datentypen?

A:
  • Die Suche
Q:

Was ist eine Lineare Suche?

A:

Eine Suche die in Linearer Zeit erfolgt

Q:

Was sind die Eigenschaften Binärer Suchbäume?

A:
  • Wenn x ein Knoten ist und y ist der linke Unterbaum, so gilt das y < x ist
  • Wenn x ein Knoten ist und z ist der rechte Unterbaum, so gilt das z > x ist
Q:

Was ist das Problem bei einem Binären Suchbaum?

A:
  • Eine O(ld(N)) kann nicht garantiert werden bei der Suche oder dem Einfügen, da ein entarteter Suchbaum eine Laufzeitkomplexität einer Liste Aufweist O(N) 
  • Entartete Suchbäume entstehen, wenn eine vorsortierte Einfügung erfolgt
  • Bei einer Zufälligen einfüfung ist die Laufzeit dann bei 1,39* ld(N)
Q:

Was ist der Unterschiede zwischen Tries und der Binären Suche und Binärer Baume?

A:
  • Bei der Binären Suchen und den Binären Bäumen gibt es über die Schlüssel eine Totale Ordnung, welche für die Suche per Vergleichsoperation benötigt wird, die Schlüssel sind Teil eines Knotens
  • Bei den Tries handelt es sich bei den Schlüsseln um Zeichenketten (String) diese sind auf den Kanten enthalten und bilden so ein Schlüsselwort um das entsprechende Element zu erreichen
Q:

Wie kann umgangen werden beim Einfügen oder Löschen eines Elementes in einer ArrayList das kopieren des Kompletten Arrays zu verhindern?

A:
  • Es kann das Array beim Einfügen um mehrere Elemente vergrößert werden so das das kopieren nicht bei jedem Einfügen erfolgen muss. 
AuD

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 AuD an der Fachhochschule Wedel

Für deinen Studiengang AuD an der Fachhochschule Wedel 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 AuD Kurse im gesamten StudySmarter Universum

AuO

Universität Kassel

Zum Kurs
Audio

Fachhochschule Oberösterreich

Zum Kurs

Die all-in-one Lernapp für Studierende

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