Sie befinden sich hier:

Informationen zu Einführung in die Informatik 2

Umfang:  2V 1Ü 1P

Studiengänge: Informatik, Medizinische Informatik, Wirtschaftsinformatik, SWT-dual - 2. Semester

Inhalt:  

Algorithmen

  • Algorithmen und ihre Eigenschaften
  • Algorithmen und Datenstrukturen
  • Vom Algorithmus zum Programm
  • Exkurs Pseudocode
  • Beurteilung von Algorithmen
  • Nachweis von Korrektheit

Aufwand und Komplexität

  • Was sind Aufwand und Komplexität?
  • Beispiel einer Aufwandsberechnung: Mischen
  • Asymptotische Zeitkomplexität
  • Zeitaufwand von Algorithmen und Programmen
  • Maximaler Problemumfang
  • Aufwandsberechnung und Java
  • Speicherkomplexität

Rekursion

  • Beispiele zur Rekursion
  • Prinzip der Rekursion
  • Rekursiv Programmieren
  • Türme von Hanoi
  • Probleme einer Rekursion
  • Iterative Lösung oder Rekursion
  • Anwendungen der Rekursion

Listen 1

  • Einführung
  • Lineare Listen
  • Verkettete Listen
  • Einfach verkettete Liste
  • Klassifikation von Listen

Listen 2

  • Einführung
  • Collections in der Java-Klassenbibliothek
  • Iteratoren
  • Listen in der Java-Klassenbibliothek
  • Vergleich: ArrayList vs. LinkedList

Binärbäume

  • Allgemeine Bäume
  • Binäre Bäume
  • Struktur eines binären Suchbaums
  • Methoden eines binären Suchbaums
  • Binäre Suchbäume in Java

AVL-Bäume, B-Bäume

  • AVL- Bäume
    1. Definition AVL-Bäume
    2. Suchen und Einfügen
    3. Effizienz
  • B-Bäume
    1. Warum B-Bäume?
    2. Definition B-Bäume
    3. Suchen und Einfügen
    4. Entfernen
    5. Effizienz

Suche

  • Einführung
  • Elementare Suchverfahren
  • Schlüssel-Transformationen

Graphen

  • Definition Graphen
  • Wege und Zusammenhang
  • Repräsentation von Graphen
  • Traversierungen
  • Topologisches Sortieren
  • Weitere Algorithmen auf Graphen

Sortieren 1

  • Sortieren:
    1. Problemstellung
    2. Klassifikation von Sortierverfahren
  • Sortieren durch Einfügen
  • Sortieren durch Auswahl
  • Sortieren durch Austauschen
  • Sortieren durch Mischsortieren

Sortieren 2

  • Überblick
  • Quicksort
  • Heapsort
  • Klassifikation von Sortierverfahren

Sets und Maps

  • Collections in der Java-Klassenbibliothek
  • Collections des Typs Set<E>
  • Collections des Typs Map<K,V>
  • Sortierte Collections
  •         Sortierte Collections des Typs TreeSet<E>
  •         Sortierte Collections des Typs TreeMap<K,V>
  • Commons Collections (Jakarta)

Problemklassen von Algorithmen

  • Berechenbarkeitt
  • Problemkomplexität
  • Komplexitätsklassen
  • Einordnen eigener Problemstellungen
  • Backtracking
  • Heuristik


Vorkenntnisse:

  • Inhalte der Vorlesung Informatik 1