Grundgebiete der Informatik
1. Semester Wirt. Ing. RWTH AACHEN
1. Semester Wirt. Ing. RWTH AACHEN
-
- 1 / 121
-
Cartes-fiches
Die for-Schleife würde für jede Form von Schleifenkonstrukt ausreichen, warum gibt es dann drei?
- Aus Gründen der Programm-Lesbarkeit
- strukturierte Schleifen in Verbindung mit dem Verzicht auf gotos führt oft zu besserem Maschinencode
Definiere Zeiger
Ein Zeiger (pointer) ist eine Variable, die die Speicheradresse einer Variablen enthält
Deklaration von Zeigern mittels *. Was bedeutet dann int** p?
Zeiger auf einen Zeiger auf int
Wozu dienen Zeiger?
- Zeiger sind sinnvoll bei dynamischen Datenstrukturen (Datenbanken)
- Datenobjekte, deren Größe während der Programmentwicklung noch nicht feststehen
Erkläre Heap-Speicher
- Programmcode und Variablen im statischen Speicherbereich
- Funktion malloc greift auf einen Heap-Speicher zu
Erkläre Arrays
int V [10]
Arrays definieren zusammengesetzte Datentypen, deren Elemente durch einen Index zugegriffen werden.
Die Indizierung beginnt bei 0!
Mathematisches Äquivalent zu Vektoren / können aber auch mehrdimensional programmiert werden
Arrays und Schleifen -> Erkläre den Vorteil der Verwendung von Arrays.
Eine Menge "gleichartiger" Objekte kann mit einem Namen und variablen Index zugegriffen werden. So vermeidet man die Code-Duplizierung in Schleifen.
Erkläre Pre-/Post-Inkrement
Beim Pre-Inkrement wird der Ausdruck zunächst erhöht und dann ausgewertet. Im Post-Inkrement genau anders herum.
Post: *p++
Pre: ++*p
Erkläre String
String ist ein Array mit char Elementen
Merke: Die Verwendung der 0, NULL, leere Zeiger, sind unzulässig. Die 0 ist das letzte Element eines Strings.
Erkläre Strukturen (Struct, record)
Zusammenfassung einer Gruppe von Variablen zu einer Einheit. Adressierung innerhalb einer Struktur per Namen.
Definiere kartesisches Produkt
Das kartesische Produkt A X B zweier Mengen A und B ist definiert durch: A X B = {(a,b) | a ∊ A, b ∊ B}
Definiere Relation
Eine (binäre) Relation R ist eine Teilmenge des kartesischen Produktes zweier Mengen: R \(\subseteq\) A X B
Definiere Funktion
Eine Funktion F: A -> B ist eine rechtseindeutige Relation, d.h. jedem a \(\in\) A ist höchstens ein b \(\in\) B zugeordnet.
Nenne die vier Hauptgründe eine Funktion zu benutzen
Was bedeutet Rekursion?
Funktionen rufen sich selbst auf.
Unterscheide Globale und lokale Variablen
Globale Variablen sind im gesamten Programm gültig lokale Variablen sind nur in einer bestimmten Funktion gültig.
Erkläre call by value
Alle Parameter, die an Funktionen übergeben werden, werden grundsätzlich kopiert, dieses Konzept heißt Call by value
Erkläre die Auswirkungen von Call by Value
1. Änderungen an einem Parameter in einer Funktion erscheinen nicht in der aufgerufenen Funktion
2. Man kann einen Wert in einer Funktion nur via Zeiger dauerhaft verändern
3. Großer Zeitaufwand beim kopieren von Structs
Erkläre call by reference
Bei call by reference werden keine Werte kopiert, sondern es wird eine Referenz auf den Wert angelegt.
Erkläre Module
Module sind selbstständig übersetzbare Programmiereinheiten. Sie bestehen auf einen Interfaceteil und einem Implementationsteil.
Nenne zwei Kriterien für die Komplexitätsanalyse von Algorithmen.
1. Laufzeit
2. Speicherplatzbedarf
Welche Möglichkeiten gibt es für das Messen der Effizienz eines Algorithmus?
1. Zählen der Rechenschritte
2. Abstrakte Analyse
Definiere O-Notation
Sind f: N -> N und g: N -> N zwei Funktionen, so ist f \(\in\) O(g), falls \(\exists n0 \in N, \exists c \in R \), so dass \(\forall n \geq n0: f(n) \leq c* g(n)\)
Wobei hilft die O-Notation?
- sinnvoll vor der Implementierung
- Maß der Qualität kann verglichen werden, Speicherbedarf abgeschätzt
- gibt Auskunft ob es überall sinnvoll ist nach einem neuen Algorithmus zu suchen
Rechenregeln für das Zusammenrechnen der Laufzeiten von Teilalgorithmen
- "O" im Ausdruck vernachlässigen
- Umformen des Ausdrucks wie gewohnt
- Nur den führenden Term behalten
Ist es effizienter mehr Rechenleistung zu entwickeln oder neue Algorithmen zu programmieren?
Algorithmen, denn selbst eine Vertausendfachung der Rechenleistung bringt bei Algorithmen mit exponentieller Laufzeit keine wesentliche Verbesserung.
Erkläre die lineare Suche
Die lineare Suche ist der einfachste Suchalgorithmus. Um einen Schlüssel in einer Menge von Datensätzen zu finden, werden diese der Reihe nach verglichen.
Wie ist die Gesamtlaufzeit bei linearer Suche für eine Menge von M Suchschlüsseln in einem Array der Länge N?
Gesamtlaufzeit beträgt: O(M*N)
Erkläre die binäre Suche
Vorausgesetzt die Elemente im Array sind aufsteigend sortiert, agiert der Algorithmus nach dem Prinzip "Teile und Herrsche". Das mittlere Element wird mit dem Schlüssel verglichen, ist das Element kleiner sucht der Algorithmus im linken Teil und untersucht wieder das mittlere. Bis das Element gefunden wird.
Wie ist die Gesamtlaufzeit bei binärer Suche für eine Menge von M Suchschlüsseln in einem Array der Länge N?
Gesamtlaufzeit: O(M*log2N)
Warum sortiert man Datensätze?
- effizientere Suchalgorithmen (binäre Suche)
- die Datensätze können leichter auf Duplikate untersucht werden
- für Menschen leichter zu lesen
Wann heißt ein Sortieralgorithmus stabi?
wenn die ursprüngliche Reihenfolge bei gleichem Schlüssel beibehalten wird
Erkläre Selection Sort
Eine Menge an Datensätzen wird nach seinem Minimum durchsucht. Dieser Datensatz wird mit dem ersten vertauscht. Danach wird das Minium das sortierte Teilmenge betrachtet und in der übrigen Menge wird das nächst kleinste Element gesucht und mit der zweiten Stelle vertauscht. Dann gehts immer so weiter
Wie ist die Laufzeit von Selection Sort?
O(N²)
Erkläre Insertion Sort
Die Grundidee ist jeweils ein Element herauszunehmen und durch Nach-Rechts-Schieben von größeren Elementen die richtige "Lücke" für das entnommene Element zu finden und es dort einzufügen.
Erkläre Insertion Sort
Die Grundidee ist jeweils ein Element herauszunehmen und durch Nach-Rechts-Schieben von größeren Elementen die richtige "Lücke" für das entnommene Element zu finden und es dort einzufügen.
Wie ist die Laufzeit von Insertion Sort?
O(N²)
Erkläre Bubblesort
Elemente mit kleinem Schlüssel sind leicht und steigen durch paarweises Vertauschen der Elemente von rechts nach links auf.
Wie ist die Laufzeit von Bubblesort?
O(N²)
Erkläre Quicksort
"Divide et impera" -> Mehrere kleinere Probleme sind leichter zu lösen als ein großes.
Der Quicksort wäht ein Element der Menge A A[k] und nutzt dieses als Trennelement. Die beiden Teilmengen werden mittels Rekursion wieder geteilt, so erhalten wir viele kleine Teilmengen.
