Grundgebiete der Informatik

1. Semester Wirt. Ing. RWTH AACHEN

1. Semester Wirt. Ing. RWTH AACHEN

121

0.0 (0)

L. E.

Study

L. E.

About these flashcards

Diese Lernkarten bieten einen umfassenden Überblick über grundlegende Konzepte der Informatik auf Universitätsniveau. Sie decken Themen wie Algorithmen, Graphen, Datenstrukturen und deren Laufzeiten ab, wobei Schwerpunkte auf Suchalgorithmen, Sortierverfahren und dynamischer Programmierung liegen. Besonders nützlich für Studierende der Informatik, die sich auf Prüfungen vorbereiten oder ihr Verständnis von grundlegenden Algorithmen und Datenstrukturen vertiefen möchten.

Flashcards

121

Students

1

Language

German

Category

Computer Science

Level

University

Created / Updated

23.02.2016 / 25.02.2016

Wie ist die Laufzeit des Dijkstra Algorithmus?

O(|V|²)

Definiere Adjazenzmatrix

Ist G=(V,E) ein Graph mit Knotenmenge V={v1,..,vn}, so heißt die (n X n)Matrix A= (aij) mit aij=1, falls {vi, vj} \(\in\) E aij=0, sonst

Adjazenzmatrix zu G

Erkläre Adjazenzlisten

Bei dieser Datenstruktur werden nur die Graphenkanten explizit abgespeichert. Jeder Knoten besitzt eine Liste seiner Nachbarn.

-> Bei wenigen Kanten platzsparend

Wie ist der Platzbedarf bei Adjazenzlisten?

O(|V| + |E|)

Erkläre garbage collection

Es werden alle Speicherblöcke als "nicht mehr benötigt" markiert. Ist ein Block über einen Zeiger erreichbar wird er als "benötigt" markiert. Alle übrigen können freigegeben werden.

Erkläre Depth first search

ausgehend vom Startknoten möglichst lange Pfade verfolgen

Erkläre Breadth first search

ausgehend vom Startknoten weitere Knoten in der Reihenfolge wachsenden Abstands vom Startknoten besuchen

Definiere Spannbaum

Ein Spannbaum in einem ungerichteten, zusammenhängenden und kantengewichteten Graphen G=(V,E,w) ist ein zyklenfreier, zusammenhängender Teilgraph G'=(V',E',w) mit V' = V und E' \(\subseteq\) E

Definiere minimaler Spannbaum

Ein minimaler Spannbaum in einem ungerichteten, zusammenhängenden und kantengewichteten Graphen G=(V,E,w) ist ein Spannbaum mit minimaler Kantengewichtssumme unter allen Spannbäumen zu G

Erkläre den Kruskal Algorithmus

Der Kruskal Algorithmus ist ein greedy Algorithmus. Er betrachtet stets die nächste Kanten mit dem geringsten Gewicht.

Wie ist die Laufzeit des Kruskal Algorithmus?

O(|E| log |E|)

Erkläre Iteration

- Berechnung einer Funktion f durch einzelne Schritte auf bestimmter Datenstruktur

- Typischerweise als Schleife realisiert

- Vor- und Nachteile wie Rekursion

Wie hoch ist die Laufzeit der Berechnung der Fibonacci Zahlen bei Rekursion?

O(2^n) -> exponentielles Wachstum

Wie hoch ist die Laufzeit der Berechnung der Fibonacci Zahlen bei Iteration?

O(N)

Erkläre Backtracking

- Rücksetzverfahren

- Teillösungen führen zur Gesamtlösung

- Raten und korrigieren

Erkläre Kombinatorische Optimierung

Konstruktion einer Lösung eines Problems durch Auswahl einer Teilmenge einer Menge von diskreten Elementen

Erkläre Heuristik

Kompromis zwischen Laufzeit und Qualität der Lösung

Erkläre Approximationsalgorithmen

Bei Approximationsalgorithmen gibt es keine Ausreißer, denn man kann nachweisen, dass eine bestimmte Güte nie unterschritten wird

Erkläre Dynamische Programmierung

Effizientes exaktes Lösen von Optimierungsproblemen mit folgender Eigenschaft:

Die opt. Lösung des Gesamtproblems kann effizient aus opt. Lösungen von Teilproblemen berechnet werden

Erkläre Branch und Bound

Durch eine geschickte Beschneidung des Lösungsraumes kann erhebliche Zeit eingespart werden.

Definition von Informatik (Computer Science)

Keyboard commands:

= turn,

= for-/backward,

= scroll

Informatik ist die Wissenschaft, die sich mit der Entwicklung und Nutzung von Computersystemen beschäftigt.

Nenne zwei Vorteile von höheren Programmiersprachen gegenüber dem Maschinencode

lesbar und wartbar

portierbar

Keyboard commands:

= turn,

= for-/backward,

= scroll

lesbar und wartbar

portierbar

Definiere Imperative Sprachen

Keyboard commands:

= turn,

= for-/backward,

= scroll

konkrete Beschreibung eines Algorithmus als Folge von Anweisungen (Beispiel C oder PASCAL)

Definiere Deklarative Sprachen

Keyboard commands:

= turn,

= for-/backward,

= scroll

Beschreibung eines erwünschten Programmverhaltens, konkrete Umsetzung erfolgt teilweise durch den Compiler und Laufzeitsystem (LISP oder Prolog)

Definiere Objektorientierte Sprachen

Keyboard commands:

= turn,

= for-/backward,

= scroll

Zusammenfassung von Algorithmen und Daten zu Objekten, dadurch einfachere Programmwartung (C++ und JAVA)

Nenne die sechs Schritte für den Software Life Cycle

Keyboard commands:

= turn,

= for-/backward,

= scroll

1. Problem (-> Analyse + Definition)

2. Spezifikation (-> Implementierung)

3. Dokumentiertes Programm (-> Test)

4. Modifiziertes Programm (-> Installation)

5. Software Produkt (-> Wartung und Kundensupport)

6. Verschrottung

Erkläre Algorithmus

Keyboard commands:

= turn,

= for-/backward,

= scroll

- Abstrakte Handlungsanweisung, um ein Problem zu lösen

- Ausgabe als Funktion der Eingabe

- endlicher Zeit, eindeutig und deterministisch

Erkläre Programm

Keyboard commands:

= turn,

= for-/backward,

= scroll

Codierung eines Algorithmus in Programmiersprache

Erkläre Datenstruktur

Keyboard commands:

= turn,

= for-/backward,

= scroll

- Mathematisches Objekt zur Speicherung von Daten

- angeordnet und zusammengefasst

Nenne die drei Kriterien für einen Algorithmus

Korrektheit

Effizienz (Laufzeit)

Eleganz, Programmierstil

Keyboard commands:

= turn,

= for-/backward,

= scroll

Korrektheit

Effizienz (Laufzeit)

Eleganz, Programmierstil

Erkläre Bibliotheken (Libraries)

Von vielen Programmen häufig wiederverwendeter Code wird in Bibliotheken abgelegt

- keine selbst ausführbaren Programme / sondern Funktionen die abgerufen werden

Erkläre Schleifen

Code wird so lange wiederholt, bis die Bedingung nicht mehr erfüllt ist

Nenne die zwei Parameter, welche stets der printf Funktion übergeben werden.

1. die Art der Ausgabe der Daten (ganzzahlig, Fließkomma)

2. die auszugebenen Daten

Erkläre C-Präprozessor

Der C-Präprozessor läuft vor dem Compiler über den Quellcode

- cpp-Anweisung #..

- cpp-Verwendung erhöht die Lesbarkeit

Nenne zwei Arten von fehlerhaften Programmen

Möglichkeit 1: Programm entspricht nicht dem C Standard (Compiler findet die Fehler)

Möglichkeit 2: Programm ist gültig, führt aber nicht die gewünschte Funktion aus (Debugging)

Definition Datentyp

Ein Datentyp (DT) ist eine Menge von Werten und eine Sammlung von Operationen auf diesen Werten.

Definition abstrakter Datentyp

Ein abstrakter Datentyp (ADT) ist ein Datentyp der nur über eine Schnittstelle zugänglich ist.

Was ist ein Objekt?

Ein Objekt ist ein benannter Speicherbereich

Wie viel Speicherplatz benötigt der Datentyp char?

1 Byte (8bits)

Wie viel Speicherplatz benötigt der Datentyp int?

short int: mind. 16bit

long int: mind. 32bit

1 / 121

Cartes-fiches

Erkläre Branch und Bound

Durch eine geschickte Beschneidung des Lösungsraumes kann erhebliche Zeit eingespart werden.

1
2
3
4

Étudier