Algorithmen & Datenstrukturen

Julian Huber & Matthias Panny

UML - Activity Diagramme

🎯 Lernziele

  • Studierende wissen was Activity Diagramme (dt. AktivitĂ€tsdiagramme) sind
  • Studierende können Activity Diagramme fĂŒr simple Probleme erstellen

Activity und Fluss-Diagramme

Bedarf

  • Algorithmen und Software sind komplexe Gebilde mit verschiedenen ZustĂ€nden
  • In der Anfangsphase der Entwicklung muss das Know-How verschiedener Personen mit eingebunden werden

Grafische Darstellung von ProgrammflĂŒssen

  • Es haben sich verschiedene grafische Darstellungsformen entwickelt:
    • Nicht-standardisierte Flussdiagramme
    • AktivitĂ€tsdiagramme der Unified Modeling Language (UML) in Version 1 und 2
    • Verwandte Darstellungsformen sind auch Petri-Netze und ZustandsĂŒbergangsdiagramme

AktivitÀtsdiagramm nach UML1

AktivitÀtsdiagramm

  • dynamische Verhalten eines Software-Systems
  • AktivitĂ€ten haben die Struktur eines Graphen
  • Knoten dieses Graphen sind Aktionen sowie Punkte, an denen die FlĂŒsse zwischen den Aktionen kontrolliert werden
  • Kanten stehen fĂŒr Daten- und KontrollflĂŒsse

AktivitÀtsdiagramm nach UML1

  • AktivitĂ€tsdiagramme bestehen aus AktivitĂ€ten und Kontrollknoten
  • AktivitĂ€ten sind Aktionen, die ausgefĂŒhrt werden
  • Kontrollknoten steuern den Fluss der AktivitĂ€ten
    • Decision: Verzweigung basierend auf Entscheidungsalternativen auf den Pfeilen
    • Join: Vereinheitlichung paralleler Prozesse (wartet)
    • Merge: FĂŒhrt alternative Prozesse wieder zusammen
  • ausfĂŒhrliche Beschreibung

đŸ€“ Werkzeuge zum Erstellen von AktivitĂ€tsdiagrammen

PlantUML

  • Auszeichnungssprache fĂŒr Diagramme
@startuml

start
note left
  Nudeln zubereiten
  Parameter: Nudeln, Salz, Wasser
  Anforderung: Nudeln roh
  Zusicherung: Nudeln gekocht
  HilfsgrĂ¶ĂŸen: Sieb, Topf
end note

:Wasser im Topf kochen;
:Salz und Nudeln in kochendes Wasser geben;

repeat
  :30 Sekunden warten;
  :einzelne Nudel probieren;
repeat while (Konsistenz der Nudel) is (noch zu hart) not (al dente)

:Nudeln abgießen;
stop

@enduml

Beispiel - Reverse Complement eines DNA-Strangs

  • der genetische Code einer Zelle ist als doppelstrĂ€ngige Helix in der DNA gespeichert
  • Dabei ist die Information der beiden StrĂ€nge redundant gespeichert, da sich immer nur zwei bestimmte Basenpaare von vier gegenĂŒber liegen können (A-T bzw. C-G)
  • Zudem haben die beiden StrĂ€nge eine gegensĂ€tzliche Lese-Richtung (5'-3')

Beispiel - Reverse Complement eines DNA-Strangs

  • Ein hĂ€ufiges Problem der Bio-Informatik ist es das Reverse-Complement einer Nukleotid-Folge zu finden
  • Complement bedeutet, dass die Basen A und T sowie C und G ersetzt werden um den zweiten Strang zu erhalten
  • Reverse bedeutet, dass die Reihenfolge der Basen umgekehrt wird, um die Lese-Richtung zu erhalten
>Sample Sequence
ATGATCTCGTAA

>Complement
TACTAGAGCATT

>Reverse Complement
TTACGAGATCAT

✍ Aufgabe - Reverse Complement eines DNA-Strangs

  • Klonen Sie das Repository example_reverse_complement

  • Im README.md finden Sie eine Beschreibung des Problems und der Aufgabenstellung → Arbeiten Sie diese Schritt fĂŒr Schritt durch

  • Begonnen wird mit dem Zeichnen eines UML-AktivitĂ€tsdiagramm zur Lösung dieses Problems
    → gehen sie davon aus, dass Sie nur binĂ€re Fallunterscheidungen treffen können

Beispiel - Reverse Complement eines DNA-Strangs

Musterlösung fĂŒr das AktivitĂ€tsdiagramm

Beispiel - Reverse Complement eines DNA-Strangs

  • Auch fĂŒr dieses Beispiel sind Musterlösungen vorhanden

Musterlösung - reverse_complement.py

  • Diverse unterschiedliche Implementierungen
    • ohne Fehlerbehandlung
    • mit Fehlerbehandlung
    • mit list
    • mit dict

Musterlösung - test_reverse_complement.py

  • Unit Test fĂŒr die Implementierungen ohne Fehlerbehandlung
  • Unit Test fĂŒr die Implementierungen ohne Fehlerbehandlung
  • AusfĂŒhren im Terminal: python -m unittest .\test_reverse_complement.py bzw. den ganzen test Ordner ĂŒber python -m unittest discover test

Beispiel - Reverse Complement eines DNA-Strangs

  • Im 4. Schritt der Aufgabenstellung wird die Erweiterung der Implementierung um Fehlerbehandlung gefordert

Problem

  • Fehlerbehandlung bei unbekannten Buchstanden

    DNA Sequence:         ATGATCTCGTAA
Reverse Complement:   TTACGAGATCAT

    DNA Sequence:         AXGATCTCGTAA
Reverse Complement:   TTACGAGATCT

Lösung

  • Es soll jedes ungekannte Nukleotid durch _ ersetzt werden
  • Welche alternativen LösungsansĂ€tze fallen Ihnen ein?

Beispiel - Reverse Complement eines DNA-Strangs

Musterlösung

Beispiel: Übersetzer fĂŒr lĂ€ngere Alphabete

  • Wie gehen wir damit um, dass es auch lĂ€ngere Mappings (also mehr als fĂŒnf Möglichkeiten) geben kann?

Problem

  • Wir wollen nicht fĂŒr jedes Mapping eine neues Paar an if-Bedingung implementieren

Lösung

  • Stattdessen können wir ein Mapping ĂŒber zwei Listen mit gemeinsamen Index anlegen
    original_alphabet = ['A', 'T', 'G', 'C']
replace_alphabet  = ['T', 'A', 'C', 'G']
  • ⚠: Auch dieses Vorgehen hat Nachteile ĂŒber welche wir zu spĂ€terem Zeitpunkt sprechen

Beispiel: Übersetzer fĂŒr lĂ€ngere Alphabete

Musterlösung

✍ Aufgabe

  • Passen Sie die Implementierung von reverse_complement(dna_sequence) an, da dass zwei Listen mit Alphabete verwendet werden und nicht erkannte Nukleotide durch _ ersetzt werden
  • Optional: Passen Sie den unit-Test an, damit diese FunktionalitĂ€t auch getestet wird und fĂŒhren Sie den unit-Test erneut aus
  • Welche alternativen Implementierungen fallen Ihnen ein?

--- ``` @startuml start :Start; while (Noch mehr Nukleotide?) is (Ja) :Nukleotid aus der Sequenz holen; if (Nukleotid ist 'A') then (Ja) :Ersetze durch 'T'; elseif (Nukleotid ist 'T') then (Ja) :Ersetze durch 'A'; elseif (Nukleotid ist 'G') then (Ja) :Ersetze durch 'C'; else (Nein) :Ersetze durch 'G'; endif :Ergebnis speichern; endwhile (Nein) :Reverse; :Ausgeben; stop @enduml ```

--- ``` @startuml start :Start; while (Noch mehr Nukleotide?) is (Ja) :Nukleotid aus der Sequenz holen; if (Nukleotid ist 'A') then (Ja) :Ersetze durch 'T'; elseif (Nukleotid ist 'T') then (Ja) :Ersetze durch 'A'; elseif (Nukleotid ist 'G') then (Ja) :Ersetze durch 'C'; elseif (Nukleotid ist 'C') then (Ja) :Ersetze durch 'G'; else (Nein) :Ersetze durch '_'; endif :Ergebnis speichern; endwhile (Nein) :Reverse; :Ausgeben; stop @enduml ```

--- ``` @startuml start :Start; partition "Initialization" { :original_alphabet = ['A', 'T', 'G', 'C']; :replace_alphabet = ['T', 'A', 'C', 'G']; :reverse_comp_sequence = []; } while (nucleotide left in dna_sequence) is (true) :nucleotide = Get next nucleotide; if (nucleotide is in original_alphabet) then (Yes) :index = Index of nucleotide in original_alphabet; :replacement = Get element from replace_alphabet using index; :Add replacement to reverse_comp_sequence; else (No) :Add '_' to reverse_comp_sequence; endif endwhile (false) :Reverse reverse_comp_sequence; :return Concatenate reverse_comp_sequence as string; @enduml ```