Grundlagen der Informatik I+II

Vorlesung

ECTS: 4
Kategorie V+Ü, 3 SWS
Veranstalter: Dr. Stefan Bosse, Prof. Frank Kirchner

für Elektrotechniker

Inhalt der Veranstaltung

  1. Informationen und Daten

    • Darstellung und Verarbeitung von Informationen, Kodierung
    • Zahlensysteme (Binär, Dezimal, Hexadezimal), Umrechnung
    • Vorzeichenbehaftete Dualzahlen, Zweier-Komplement-Darstellung
    • Arithmetische Operationen (Binärzahlen!)
    • Reelle Zahlen (Gleit- und Fließpunktdarstellung)
    • Logische Werte, boolesche Funktionen, Logische Funktionen, Transistortechnologie
    • Boolesche Algebra, Minimierung von Digitallogiksystemen, Gesetzte der booleschen Algebra für Termumformungen, Systematische Reduktion logischer Funktionen, KV-Diagramme
    • Normalformen (disjunktiv, konjunktiv), Wakrheitstabellen
    • Texte und Zeichenketten
  2. Komponenten und Aufbau eines Datenverarbeitungssystem

    • Turing-Maschine, Definition, Bandalphabet Aufbau, Arbeitsweise, Vor- und Nachteile
    • Erweitertes Turing-Modell: Register-Maschine Beispiel: VTURI
    • Zentrale Recheneinheit, Peripherie, Ein- und Ausgabe
    • Die von-Neumann-Architektur
    • Der Mikroprozessor
    • Aufbau und Funktionsweise der zentralen Recheneinheit
    • Prinzip und Phasen der Befehlsausführung (Leitwerk, Rechenwerk)
    • Befehlskodierung
    • Bussysteme
    • Kommunikationsschnittstellen (serielle und parallele, synchrone und asynchrone Datenübertragung)
    • Datenspeicher (RAM/ROM, Haupt- und Sekundärspeicher)
    • Aufbau eines Mikrokontrollers
    • Harvard-Architektur im Vergleich zu von-Neumann
  3. Betriebssysteme

    • Aufgabe eines Betriebssystems(Abstraktion, Plattform für Anwendungsprogramme, Zuteilung von Betriebsmitteln, Bedienerschnittstelle)
    • Prozesse Prozeßmodell als Abstraktion
    • Prozeßverwaltung Multiprozeß-Systeme
    • Prozeßzustände
    • Speichermodell eines Prozesses Speichersegmente, Stack-, Text- Datensegment
    • Prozeßverwaltung: der Scheduler, Prozeßtabelle
    • Dateien und Dateisysteme, grundlegender Aufbau, Abbildung auf Datenspeicher (Festplatte)
    • Grundaufbau des Minix-Dateisystems
  4. Programme und Programmiersprachen

    • Spezifikation, Algorithmus, Programm
    • Flußdiagramm
    • Reaktive und nicht reaktive (funktionale) Programme
    • Programmerstellung, Entwurfszyklus
    • Programmiersprachen
    • Klassifizierung von Programmiersprachen (Maschinensprache, höhere Programmiersprachen, imperative, funktionale, logische P.)
    • Funktionen und Funktionale Sprachen, Funktionsparameter und Funktionsblock, Parameterübergabemechanismen (Wert- und Referenzaufruf)
    • Ausdrücke & Funktionen
    • Bedingte Ausdrücke
    • Strukturieren durch Teilausdrücke
    • Tupel von Ausdrücken
    • Funktionen höherer Ordnung
    • Rekursion
    • Datenstrukturen, Produktbildung, Summenbildung, Arrays
    • Variablen, Variablen in imperativen Sprachen und Zeigertypen
    • Schleifen und Rückwirkung
    • Bedingte Schleife
    • Zählschleife
    • Programmiersprache C: Datentypen: INT, FLOAT, CHAR, Zeichenketten (strings), Zusammengesetzte Datentypen, Sequenzielle Ablaufsteuerung in imperativen Programmiersprachen, Prozeduren und Funktionen, Funktionsparameter und Funktionsblock, Rekursion, Anweisungen, Ausdrücke (arithmetische, logische und relationale Operatoren)
  5. Compiler: Analyse und Synthese von Programmen

    • Ablauf und Phasen der Programmübersetzung
    • Lexikalische Analyse
    • Syntaktische Analyse
    • Semantische Analyse, Symboltabelle
    • Codeerzeugung, Synthese
    • Optimierung, Konstantenfaltung, schleifen-invarianter Code, Ausdruckssubstitution, toter Code,…
    • Binder, Lader und Bibliotheken H) Der GCC-Compiler
  6. Abstrakte Datentypen & Algorithmik

    • Lineare Listen: Sequenzielle Speicherung mit Feldern, Datenstrukturen, Verkettete Speicherung (einfach, doppelt), Datenstrukturen, Grundlegende Operationen (Algorithmik für Suchen, Einfügen und Löschen von Listenelementen)
    • Stapel- und Schlangenspeicher (Programmstack, FIFO, Datenstrukturen, Operationen)
    • Skip-Listen, Laufzeitanalyse
    • Hash-Verfahren: Laufzeitanalyse, Hash-Tabelle, Hash-Funktion, Datenstrukturen, Operationen, Adreßkollision, Management der Überläufer/Synonyme
    • Bäume: Grundlagen, Aufbau, Nomenklatur, Vollständige Bäume, Rang, Ordnung, Operationen mit Bäumen, Binärbäume, Datenstrukturen, Baumstruktur, Balanzierung
    • Sortierverfahren: Sortieren durch Einfügen, Shell-Sort, Bubble-Sort, Divide & Conquer-Verfahren