🚀 Fortgeschrittene Algorithmen und Programmierung
Vorlesung 1: Einführung in die Algorithmen und Datenstrukturen
Prof. Dr. Alexandra Mikityuk
HTW Berlin
Wintersemester 2025/26
📞 Kontakt & Sprechstunde
Kontaktdaten
📱 Telefon: +49 30 5019-2664
🏢 Büro: Raum 308
Sprechstunde
📅 Mittwoch: 15:30 - 16:30 Uhr
💡 Bitte vorher per E-Mail anmelden!
📚 Programmierung über 2 Semester
Die Lehrveranstaltung (LV) Programmierung wird als Vorlesung mit Übung durchgeführt und gehört zum Curriculum des Bachelorstudiengangs Informations- und Kommunikationstechnik
Modul K21: Grundlagen der Programmierung
✅ 1. Semester - Keine Vorkenntnisse erforderlich
✅ C++ Grundlagen, Variablen, Schleifen, Funktionen, Pointer
Modul K22: Fortgeschrittene Algorithmen und Programmierung
✅ 2. Semester - Aufbauend auf K21
✅ Algorithmen, Datenstrukturen, Komplexität, Optimierung
📅 Wichtige Termine - Prüfungen
📝 Prüfungsformat
Die Prüfung besteht aus:
📖 Theoretische Fragen
Algorithmen verstehen, Komplexität analysieren, Datenstrukturen erklären
💻 Praktische Programmieraufgaben
Algorithmen implementieren, Code optimieren, Datenstrukturen verwenden
✅ Wichtig:
Sie dürfen alle Kursmaterialien zur Prüfung mitbringen!
(Vorlesungsfolien, Labor-Aufgaben, eigene Notizen, Code-Beispiele)
🧩 Was sind Algorithmen wirklich?
Ein Algorithmus ist nicht nur eine Folge von Anweisungen - es ist die Essenz der Problemlösung!
📊 Algorithmen sind überall:
- Google: PageRank-Algorithmus sortiert Milliarden Webseiten
- Netflix: Empfehlungsalgorithmen analysieren Ihr Verhalten
- GPS: Dijkstra's Algorithmus findet den kürzesten Weg
- Kryptowährungen: Konsensalgorithmen sichern Blockchain
- Instagram: Feed-Algorithmen bestimmen, was Sie sehen
- Spotify: ML-Algorithmen erstellen Ihre Playlists
💡 Algorithmen sind die unsichtbare Kraft, die unsere digitale Welt antreibt!
🎯 Quiz Zeit! #1
Welcher Algorithmus wird von Google verwendet, um Webseiten zu ranken?
⛓️ Blockchain: Algorithmen in Action!
Blockchain ist ein perfektes Beispiel dafür, wie Algorithmen die Welt verändern!
🔐 Kernalgorithmen in Blockchain:
- Hashing-Algorithmen (SHA-256): Sichern Datenintegrität
- Proof of Work / Proof of Stake: Konsensalgorithmen
- Merkle Trees: Effiziente Datenstruktur für Transaktionen
- Digital Signatures: Asymmetrische Kryptographie
- Smart Contract Execution: Verteilte Berechnung
💰 Reale Anwendungen:
• Bitcoin: $500+ Milliarden Marktkapitalisierung
• Ethereum: Smart Contracts - Programmierbare Geld
• DeFi: $50+ Milliarden in dezentralen Protokollen
• NFTs: Millionen in digitaler Kunst gehandelt
Ohne Algorithmen gibt es keine Blockchain! 🚀
💾 Was sind Daten?
Daten sind das Rohmaterial, mit dem Algorithmen arbeiten!
📊 Rohdaten
Einzelne Fakten ohne Kontext:
- 42
- "Berlin"
- true
- 3.14159
💎 Information
Daten mit Bedeutung:
- Temperatur: 42°C
- Stadt: Berlin
- Verfügbar: true
- Pi: 3.14159
Algorithmen transformieren Daten in Information!
Eingabe (Daten) → Algorithmus → Ausgabe (Information)
🎯 Quiz Zeit! #2
Was ist der Unterschied zwischen Daten und Information?
🏗️ Datenstrukturen: Die Basis von allem
Eine Datenstruktur ist die Art und Weise, wie wir Daten organisieren und speichern!
🎯 Warum sind Datenstrukturen wichtig?
- Performance: Richtige Datenstruktur = 1000x schneller!
- Speicher: Effiziente Nutzung von RAM und Disk
- Komplexität: Einfacher Code vs. komplexer Code
- Skalierbarkeit: 100 Elemente vs. 1 Million Elemente
📚 Fundamentale Datenstrukturen:
• Arrays - Sequentieller Zugriff
• Linked Lists - Dynamisches Wachstum
• Stacks - LIFO (Last In First Out)
• Queues - FIFO (First In First Out)
• Trees - Hierarchische Daten
• Graphs - Netzwerke & Beziehungen
• Hash Tables - O(1) Lookup!
• Heaps - Priority Queues
⚡ Beispiel: Array vs. Hash Table
Problem: Finde einen Namen in einer Liste von 1 Million Namen
📋 Array (Linear Search)
Worst Case:
1,000,000
Vergleiche nötig!
⏱️ ~1 Sekunde
# Hash Table
Worst Case:
1
Vergleich nötig!
⏱️ ~0.000001 Sekunden
Hash Table ist 1,000,000x schneller! 🚀
Die richtige Datenstruktur macht den Unterschied!
🎯 Quiz Zeit! #3
Welche Datenstruktur bietet schnellsten Zugriff für das Suchen von Elementen?
🔐 Algorithmen in Blockchain & Security
Blockchain-Technologie basiert vollständig auf cleveren Algorithmen und Datenstrukturen!
🔗 Verkettete Datenstrukturen
Jeder Block enthält den Hash des vorherigen Blocks → Linked List
Manipulation eines Blocks würde alle nachfolgenden Hashes ungültig machen!
#️⃣ Kryptographische Hash-Funktionen
SHA-256: Konvertiert beliebige Daten in einen 64-Zeichen Fingerabdruck
Deterministisch: Gleicher Input → Gleicher Output
Lawinen-Effekt: Minimale Änderung → Komplett anderer Hash
⛏️ Proof of Work: Mining-Algorithmus
Finde eine Nonce (Zahl), sodass Hash(Block + Nonce) mit X Nullen beginnt
Milliarden von Versuchen nötig → Rechenintensiv → Sicherheit!
🌳 Merkle Trees
Effiziente Datenstruktur für die Verifizierung von Transaktionen
Binärer Baum von Hashes → Schnelle Prüfung ohne alle Daten
"In blockchain, the choice of data structure is not just about performance —
it's about security, immutability, and trust."
— Vitalik Buterin, Ethereum Creator
🛡️ Algorithmen für Cybersecurity
🔐 Asymmetrische Kryptographie (RSA)
Public Key: Jeder kann verschlüsseln
Private Key: Nur Sie können entschlüsseln
Basiert auf Algorithmen der Primfaktorzerlegung (sehr schwer für große Zahlen!)
🔍 Intrusion Detection: Pattern Matching
String-Matching Algorithmen (Boyer-Moore, KMP) erkennen Angriffsmuster
Firewalls analysieren Millionen Pakete pro Sekunde → Effizienz ist kritisch!
🎲 Zufallszahlen-Generierung (CSPRNG)
Sichere Session-Keys, Salts für Passwörter, Nonces für Transaktionen
Algorithmus muss unvorhersagbar sein → Sonst Sicherheitslücke!
💡 Warum ist das wichtig?
Jede Online-Transaktion, jede verschlüsselte Nachricht, jede digitale Signatur
basiert auf den Algorithmen und Datenstrukturen, die Sie in diesem Kurs lernen werden!
💭
"Algorithms are the poetry of computation.
Data structures are the prose."
— Donald Knuth
Computer Scientist, Stanford University
🔍 Such-Algorithmen
Suchen ist die häufigste Operation in der Programmierung!
Linear Search
Komplexität: O(n)
Vorteil: Funktioniert auf unsortierten Daten
Nachteil: Langsam für große Datensätze
Beispiel: Suche in einer unsortierten Liste
Binary Search
Komplexität: O(log n)
Vorteil: Extrem schnell!
Nachteil: Daten müssen sortiert sein
Beispiel: Wörterbuch-Suche
📊 Beispiel: Suche in 1,000,000 Elementen
Linear Search: ~1,000,000 Vergleiche
Binary Search: ~20 Vergleiche
50,000x schneller! 🚀
🎯 Quiz Zeit! #5
Warum ist Binary Search so viel schneller als Linear Search?
📚 Was lernen Sie in diesem Kurs?
Weiterführung von Kurs K21: Von den Grundlagen zu komplexeren Konzepten
🔄 Komplexere Algorithmen
Aufbauend auf den Grundlagen lernen Sie fortgeschrittene Techniken
🏗️ Komplexere Datenstrukturen
Effiziente Speicherung und Verwaltung großer Datenmengen
⚙️ Fortgeschrittene Funktionen
Professionelle Programmiertechniken und Best Practices
🎯 Sie bauen auf Ihren C++ Grundlagen auf und lernen,
professionelle und effiziente Programme zu schreiben!
🚀 Warum ist das wichtig?
💼 Karriere
- Algorithmen-Kenntnisse sind entscheidend für Tech-Interviews
- FAANG (Facebook, Amazon, Apple, Netflix, Google) fragen fast nur Algorithmen!
- Höheres Gehalt für Entwickler mit starken Algorithmen-Skills
🧠 Problemlösung
- Algorithmen trainieren systematisches Denken
- Sie lernen, komplexe Probleme zu zerlegen
- Übertragbar auf alle Lebensbereiche!
💡 Innovation
Die nächste große App, die nächste Blockchain-Innovation, das nächste Startup -
alles basiert auf Algorithmen!
📋 Zusammenfassung
🎓 Wichtigste Erkenntnisse:
- ✅ Algorithmen sind überall - von Google bis Blockchain
- ✅ Daten sind das Rohmaterial, Algorithmen schaffen Information
- ✅ Datenstrukturen bestimmen die Performance Ihrer Programme
- ✅ Die richtige Datenstruktur kann 1,000,000x schneller sein!
- ✅ Big O Notation hilft uns, Algorithmen zu vergleichen
- ✅ Sortieren und Suchen sind fundamentale Operationen
- ✅ Algorithmen-Kenntnisse sind essentiell für Ihre Karriere
🎯 Nächste Schritte:
Im Labor 1 werden Sie Ihre ersten Algorithmen implementieren!
Bereiten Sie sich darauf vor, hands-on zu arbeiten! 💻
🙏 Vielen Dank!
Fragen?
Kontakt:
📧 Prof. Dr. Alexandra Mikityuk
📱 +49 30 5019-2664
🏢 Raum 308
📅 Sprechstunde: Mittwoch 15:30-16:30
Viel Erfolg beim Lernen! 🚀