Algorithmen in der Informatik: Übersicht und Lernzettel

Informatik Q1 - Grundlagen

Du startest jetzt in die spannendste Phase der Informatik! In Q1 beschäftigst du dich mit den fundamentalen Konzepten, die jeder Informatiker beherrschen muss.

Hier geht es um Algorithmen, Datenstrukturen und Komplexität - alles Themen, die auch in der Abiturprüfung eine wichtige Rolle spielen. Das Beste daran: Du lernst zu verstehen, warum manche Programme blitzschnell laufen und andere ewig brauchen.

💡 Tipp: Die Konzepte aus Q1 sind die Basis für alles, was danach kommt. Einmal verstanden, wird Programmieren viel logischer!

Algorithmen und Komplexität

Algorithmen sind wie Kochrezepte für Computer - eine exakte Anleitung zur Problemlösung. Sie bestehen aus endlich vielen Schritten und berechnen aus Eingabedaten eindeutige Ausgabedaten.

Die binäre Suche ist ein perfektes Beispiel: Statt eine Million Einträge einzeln zu durchsuchen (lineare Suche), halbiert sie bei jedem Schritt den Suchbereich. Das Ergebnis? Nur etwa 27 Schritte statt einer Million!

Mit der O-Notation können Informatiker die Effizienz von Algorithmen vergleichen. O(1) bedeutet konstante Zeit, O(log n) logarithmische Zeit und O(n²) quadratische Zeit. Die dominante Größe ist entscheidend.

💡 Merkhilfe: Bei einer Million Datensätzen braucht lineare Suche eine Million Schritte, binäre Suche nur 27!

Sortierverfahren und Rekursion

Sortierverfahren ordnen Daten nach bestimmten Kriterien. Selection Sort sucht immer das kleinste Element und tauscht es an die richtige Position - einfach zu verstehen, aber mit O(n²) nicht besonders schnell.

Rekursion bedeutet, dass sich eine Funktion selbst aufruft. Das klingt kompliziert, ist aber oft der eleganteste Weg zur Problemlösung. Beispiel: sum(4) = 4 + sum(3) = 4 + 3 + sum(2) usw.

Ein wichtiger Unterschied: Stabile Sortierverfahren behalten die ursprüngliche Reihenfolge gleicher Elemente bei, instabile nicht. Das kann bei der Sortierung von Objekten wichtig werden.

💡 Faustregel: Rekursion funktioniert immer mit einem Basisfall (Stopp-Bedingung) und einem Rekursionsschritt.

Such-Algorithmen in Baumstrukturen

Tiefensuche (DFS) und Breitensuche (BFS) sind zwei grundverschiedene Strategien, um in baumartigen Strukturen zu suchen - wie in euren Dateiordnern!

Bei der Tiefensuche gehst du sofort in die Tiefe: von "Musik" direkt zu "Konzepte", dann zu "Algorithmen" usw. Das ist wie wenn du jeden Ordner sofort komplett durchsuchst.

Die Breitensuche arbeitet systematischer: Erst alle Hauptfächer (Musik, Informatik, Deutsch), dann alle Unterordner der ersten Ebene, dann die zweite Ebene. Dafür brauchst du eine Warteschlange.

💡 Praxistipp: Tiefensuche braucht weniger Speicher, Breitensuche findet oft schneller den kürzesten Weg!

Erweiterte Sortierverfahren

Mergesort arbeitet nach dem "Teile-und-herrsche"-Prinzip: Es zerlegt Listen in kleinste Teile und fügt sie sortiert wieder zusammen. Mit O(n log n) ist es deutlich effizienter als die einfachen Verfahren.

Quicksort wählt ein Pivot-Element und teilt die Liste in kleinere und größere Werte auf. Im Durchschnitt ist es sehr schnell (O(n log n)), kann aber im schlechtesten Fall O(n²) werden.

Datenstrukturen organisieren Daten für effizienten Zugriff. Sie sind das Fundament jeder Software - von einfachen Arrays bis zu komplexen Hashtabellen.

💡 Wichtig fürs Abi: Mergesort ist immer O(n log n), Quicksort nur im Durchschnitt!

Grundlegende Datenstrukturen

Arrays sind wie nummerierte Schließfächer - direkter Zugriff über den Index in O(1) Zeit. Perfekt wenn du weißt, wo deine Daten stehen.

Verkettete Listen verknüpfen Elemente durch Zeiger. Flexibler als Arrays beim Einfügen/Löschen, aber langsamerer Zugriff da du durchlaufen musst.

Der Stack (Stapel) funktioniert nach dem "Last-In-First-Out"-Prinzip - wie ein Tellerstapel. Push fügt oben hinzu, Pop nimmt oben weg. Ideal für Rekursion und Rückgängig-Funktionen!

💡 Eselsbrücke: Stack = Tellerstapel, Queue = Warteschlange an der Kasse!