Datenstrukturen und Algorithmen

 Die Klau­sur be­han­delt ge­ne­rell alle The­men, die auch in der Vor­le­sung oder der Übung be­han­delt wur­den. Nicht Prü­fungs­re­le­vant sind:

• Dy­na­mi­sche Pro­gram­mie­rung
• Ein­fü­gen / Lö­schen / Re­kon­struk­ti­on eines Rot-Schwarz Bau­mes. Je­doch soll die Rot-Schwarz Ei­gen­schaft be­kannt sein.
• Per­sis­ten­te Da­ten­struk­tu­ren
• Die ge­nau­en (wört­li­che) De­fi­ni­tio­nen der Abs­trak­ten Da­ten­ty­pen. Je­doch müs­sen die wich­ti­gen Ope­ra­tio­nen auf den ADTs be­kannt sein!

Wich­tig: Es gibt kei­nen zwei­ten Klau­sur­ter­min im Win­ter­se­mes­ter. Die nächs­te Klau­sur fin­det im Som­mer­se­mes­ter statt.

Die Vorlesung bietet eine Einführung in die Konstruktion von Datenstrukturen und Algorithmen. Ziele sind das Kennenlernen und Vergleichen alternativer Implementierungen für abstrakte Datentypen, die Analyse der Korrektheit und des Zeit- und Speicherbedarfs und das Kennenlernen und Anwenden von Entwurfsparadigmen für Algorithmen

Die Übun­gen sind für kei­nen Stu­di­en­gang ver­pflich­tend und zäh­len nicht als Stu­di­en­leis­tung. Die Stu­di­en­leis­tung wird mit dem Be­ste­hen der Klau­sur er­bracht. Der Übungs­be­trieb ist eine Vor­be­rei­tung auf die Klau­sur und als sol­che er­mög­licht er auch das Er­lan­gen eines Klau­sur­bo­nus. Die­ser Bonus ist nur für die Klausuren im Wintersemester und das darauffolgenden Sommersemester an­re­chen­bar.

Die Übung besteht aus einer großen Abgabe in der der praktische Umgang mit dem Stoff geübt wird. Material dazu finden Sie im StudIP. Bewertet wird die Leistung dann im persönlichen gespräch mit einer/m Tutor/in.

Lineare Datentypen

• ADT Liste
• ADT Stack
• ADT Queue

Bäume

• Definition und Eigenschaften
• ADT Tree
• Sequentielle Darstellung
• Verkette Darstellung

Anwendungen für Bäume

• Prioritätswartenschlangen und Heaps
• Suchbäume
• AVL-Bäume
• Rot-Schwarz-Bäume

Gra­phen

• De­fi­ni­ti­on und Ei­gen­schaf­ten
• Im­ple­men­ta­ti­on von Gra­phen
• Kno­ten­durch­lauf
• To­po­lo­gi­sches Sor­tie­ren
• Mi­ni­ma­le Spannbäume
• Kur­zes­te Pfade in ge­rich­te­ten Gra­phen

Da­ten­struk­tu­ren zur Dar­stel­lung von Men­gen

• Im­ple­men­ta­ti­on von Ta­bel­len als li­nea­re Lis­ten
• Implementation von Tabellen als Suchbäume
• Im­ple­men­ta­ti­on von Ta­bel­len mit Zu­griff über Hash­funk­ti­on
• B+-Bäu­me

Sor­tie­rung von Men­gen

• Ele­men­ta­re Sor­tier­ver­fah­ren
• Ef­fek­ti­ve Sor­tier­ver­fah­ren für Fel­der
• Op­ti­ma­les Sor­tie­ren
• Sor­tie­ren mit li­nea­rer Kom­ple­xi­tät