Algorithmen und Datenstrukturen 1,

Wolfgang Weck, +41 56 202 78 36, wolfgang.weck@fhnw.ch

basic

Im Modul Algorithmen und Datenstrukturen 1 erhalten die Studentinnen und Studenten einen vertieften Einblick in die maschinennahe Programmierung. Im Fokus stehen die Sprachmittel der Programmiersprache Java für die maschinennahe Datenmanipulation und Algorithmen, welche auf Arrays bzw. Strings operieren. Ein wichtiger Teil dieses Moduls ist die Analyse von Algorithmen bezüglich Effizienz und Korrektheit.

Inhaltsübersicht
• maschinennahe Datenmanipulation
• interne Zahlendarstellung und Typkonvertierung
• Zeichencodes, Zeichenketten und Suchen in Texten
• Suchen in und Sortieren von Arrays
• Schleifeninvariante, Programmverifikation, Assertions
• Komplexitätsbegriff und Gross-O-Notation
• Rekursion und Backtracking

• Die Studentinnen und Studenten kennen die einfachen Datentypen und den Datentyp String in Java detailliert und können mit Bit- und logischen Operationen selbständig umgehen.
• Sie verstehen das Prinzip der Datentypkonvertierung.
• Sie kennen wichtige exemplarische Algorithmen zum Suchen in und Sortieren von Arrays und können diese gezielt anwenden.
• Sie können eine einfache Programmverifikation durchführen und sind in der Lage Vor- und Nachbedingungen in Java gewinnbringend einzusetzen.
• Sie können rekursive Programme entwickeln und analysieren und verstehen das Konzept von „Teile und Herrsche“.
• Sie können das Backtracking-Prinzip für die erschöpfende Suche einsetzen.
• Sie sind in der Lage, den Zeit- und Speicheraufwand von Algorithmen bzw. Datenstrukturen abzuschätzen, und können die Gross-O-Notation anwenden.

• Objektorientierte Programmierung 1 (oop1)
• Mathematische Grundlagen der Informatik (mgli)
• Einführung in die Analysis (eana)

Erfahrungsnote