ADS an der Fachhochschule Bielefeld

Karteikarten und Zusammenfassungen für ADS an der Fachhochschule Bielefeld

Arrow Arrow

Komplett kostenfrei

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

Lerne jetzt mit Karteikarten und Zusammenfassungen für den Kurs ADS an der Fachhochschule Bielefeld.

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Algorithmus

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Algorithmen Ausdrucksfähigkeit

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Algorithmenspezifikation

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Programmspezifikation

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Beispiele unlösbare Probleme

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Aufwand des Algorithmus

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Laufzeitmessung Idee

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

O-Notation

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

O- Kalkül Fallunterscheidung

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Algorithmenmuster

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

Top-Down arbeiten

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

dynamisches Programmieren

Kommilitonen im Kurs ADS an der Fachhochschule Bielefeld. erstellen und teilen Zusammenfassungen, Karteikarten, Lernpläne und andere Lernmaterialien mit der intelligenten StudySmarter Lernapp. Jetzt mitmachen!

Jetzt mitmachen!

Flashcard Flashcard

Beispielhafte Karteikarten für ADS an der Fachhochschule Bielefeld auf StudySmarter:

ADS

Algorithmus

  • Allgemein:
    Ein Algorithmus ist eine präzise (d.h. in einer festgelegten Sprache abgefasste) endliche Beschreibung eines allgemeinen (Bearbeitungs-)Vorganges unter Verwendung ausführbarer elementarer Schritte.
  • In der Informatik speziell: Berechnungsvorgänge statt Bearbeitungsvorgänge, Schwerpunkt auf Ausführbarkeit durch eine (abstrakte) Maschine.


Ein Prozessor führt einen Prozess (Arbeitsvorgang, Programm) auf Basis einer eindeutig interpretierbaren Beschreibung (dem Algorithmus) aus.


Ein Algorithmus kann terminierend sein: Lieferung des Ergebnisses nach endlich vielen Schritten, ansonsten ist er nicht-determinierend.


ADS

Algorithmen Ausdrucksfähigkeit

Mit der gewählten Notation müssen alle notwendigen Element in Algorithmen ausgedrückt werden können.


Notwendige Elemente:

  • Sequenz
  • Fallunterscheidung
  • Schleife


Unser Mittel der Wahl: Pseudocode

ADS

Algorithmenspezifikation

  • exakte Beschreibung der Aufgabenstellung
    • Eingabewerte
    • Ausgabewerte
    • Randbedingungen / Sonderfälle
    • Fehlerbehandlung
  • evtl. Schnittstellen
    • Name des Algorithmus
    • formale Parameter
    • globale Daten
    • Ein- Ausgabegeräte
    • . . .
  • evtl. nicht-funktionale Anforderungen
    • Laufzeitverhalten
    • . . .

ADS

Programmspezifikation

  • exakte Beschreibung der Aufgabenstellung
  • Schnittstellen
  • evtl. nicht-funktionale Anforderungen
  • Dateinamen (Programmname...) und Speicherorte
  • evtl. Angaben zur Genauigkeit, Zahlendarstellung, Betriebssystem, ...


Eine Programmspezifikation muss alles beinhalten, was der Programmierer braucht, um sofort loslegen zu können. Sie schreibt normalerweise vor, welches Problem zu lösen ist, nicht wie.


ADS

Beispiele unlösbare Probleme

  • Schon theoretisch nicht lösbar
    • Hält ein Algorithmus immer an?
    • Berechnen zwei Algorithmen dieselbe Funktion?
    • Berechnet ein Algorithmus die gewünschte Funktion?
  • Theoretisch schon, aber praktisch meist nicht lösbar
  • Ist eine Zahl eine Primzahl?
  • Das Rucksackproblem

ADS

Aufwand des Algorithmus

Kriterien

  • zeitlicher Aufwand
  • Speicherbedarf
  • . . .


hier: Abschätzung des Aufwands

  • bzgl. der benötigten Zeit
  • unabhängig von konkreter Hardware
  • in Abhängigkeit von der Problemgröße
  • für den schlechtesten Fall


ADS

Laufzeitmessung Idee

Wir suchen eine Funktion, die die Laufzeit in Abhängigkeit der Eingabegröße n (Menge an Eingabedaten, Höhe der Eingabezahl) angibt.


  • über besten, mittleren, schlechtesten Fall
  • für große n unter Vernachlässigung von Befehlen, die von n unabhängig sind
  • relativer Art über die Skalierbarkeit des Algorithmus 
    • z. B.: Verdopplung der Anzahl der Eingabewerte führt zu vierfacher Laufzeit


Gedanken:

  • Benchmarking ist ungeeignet
  • Unabhängig von Hardware, Sprache, Compiler, Betriebssystem . . .
  • Die Befehlsfolge als Einzelschritt betrachten, die am häufigsten durchgeführt wird (Zuweisung, Vergleich, Addition . . .) 
  • Eine komplette Schleife ist kein Einzelschritt, wohl aber vielleicht deren Inhalt
  • Einzelschritte als abstrakte Zeiteinheit zählen
  • Verhalten abhängig von der Größe der Eingabe (Anzahl Objekte, Größe einer Zahl) beschreiben Konkrete Werte der Eingabeobjekte nicht betrachten

ADS

O-Notation

Sei f (n) die Anzahl der elementaren Rechenschritte eines Algorithmus. Sei O(g(n)) die "Menge aller Funktionen, die nicht schneller wachsen als die Funktion g(n)". Wir sagen:
"f (n) ist in O(g(n))"

ADS

O- Kalkül Fallunterscheidung

<A>

if <condition>

    <B>


<A> und <condition> werden immer ausgeführt, <B> nur im schlechtesten Fall.

Rechnung: O(<A>) + O(<cond>) + O(<B>)

=> max(O(<A>), O(<cond>), O(<B>))

ADS

Algorithmenmuster

Design pattern


Anpassung von generischen Algorithmenmustern für
bestimmte Problemklassen an eine konkrete Aufgabe


Grundgedanken von Mustern

  • Dokumentation des Lösungsverfahrens am Beispiel eines einfachen Vertreters der Problemklasse
  • Bibliothek von Mustern ("Design Patterns“) zur Ableitung eines abstrakten Programmrahmens
  • Programmiersprachenunterstützung durch parametrisierte Algorithmen und Vererbung

ADS

Top-Down arbeiten

grobe Implementierung (Funktionen mit funktionsaufrufen)


dann immer spezieller werden


(gegenteil: bottom up)

ADS

dynamisches Programmieren

Idee

Kleinere Teilprobleme zuerst lösen, dann daraus größere Teillösungen zusammensetzen


Merkmale

  • Problemlösen “auf Vorrat” ) möglichst nur Teilprobleme lösen, die bei der Lösung der großen Probleme auch tatsächlich benötigt werden
  • Gewinn, falls identische Teilprobleme in mehreren Lösungszweigen betrachtet werden
  • Iteration und abgespeicherte Teillösungen


Vor-/Nachteile

  • liefert optimale Lösung
  • meist effektiv berechenbar
  • Optimierung durch Vermeidung mehrfacher Berechnungen (Zwischenspeicherung der Ergebnisse)
  • Zwischenspeicherung kann viel Platz benötigen

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für ADS an der Fachhochschule Bielefeld zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang ADS an der Fachhochschule Bielefeld gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Fachhochschule Bielefeld Übersichtsseite

Was ist StudySmarter?

Was ist StudySmarter?

StudySmarter ist eine intelligente Lernapp für Studenten. Mit StudySmarter kannst du dir effizient und spielerisch Karteikarten, Zusammenfassungen, Mind-Maps, Lernpläne und mehr erstellen. Erstelle deine eigenen Karteikarten z.B. für ADS an der Fachhochschule Bielefeld oder greife auf tausende Lernmaterialien deiner Kommilitonen zu. Egal, ob an deiner Uni oder an anderen Universitäten. Hunderttausende Studierende bereiten sich mit StudySmarter effizient auf ihre Klausuren vor. Erhältlich auf Web, Android & iOS. Komplett kostenfrei. Keine Haken.

Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
X

StudySmarter - Die Lernplattform für Studenten

StudySmarter

4.5 Stars 1100 Bewertungen
Jetzt entdecken
X

Gute Noten in der Uni? Kein Problem mit StudySmarter!

89% der StudySmarter Nutzer bekommen bessere Noten in der Uni.

50 Mio Karteikarten & Zusammenfassungen
Erstelle eigene Lerninhalte mit Smart Tools
Individueller Lernplan & Statistiken


Lerne mit über 1 Millionen Nutzern in der kostenlosen StudySmarter App.

Du bist schon registriert? Hier geht‘s zum Login