Grundlagen der Informatik: Speicher, Algorithmen & Graphen

RAM (Random Access Memory)

RAM ist eine Speicherart, auf die nach dem Zufallsprinzip zugegriffen wird. Das bedeutet, Sie können jedes Byte Speicher direkt ansteuern, ohne vorherige Bytes durchlaufen zu müssen. RAM ist die häufigste Form von Computerspeicher und wird auch in Geräten wie Druckern verwendet.

Grundlegende Arten von RAM

• DRAM (Dynamic RAM): Dynamischer RAM.
• SRAM (Static RAM): Statisches RAM.

Die beiden Typen unterscheiden sich in der Technologie zur Datenspeicherung. Dynamic RAM muss tausende Male pro Sekunde aktualisiert werden, während statisches RAM seltener aktualisiert werden muss, was es schneller, aber auch teurer macht.

Spezielle RAM-Typen

• VRAM (Video RAM): Ein Spezialspeicher für Videoadapter. Im Gegensatz zu herkömmlichem RAM kann auf VRAM von zwei Geräten gleichzeitig zugegriffen werden.
• SIMM (Single In-Line Memory Module): Eine kleine Platine mit Speicherchips, die in einen SIMM-Sockel eingesetzt wird.
• DIMM (Dual In-Line Memory Module): Eine Platine mit Speicherchips für DIMM-Steckplätze, meist mit 168-Pin-Anschluss.
• DIP (Dual In-line Package): Ein rechteckiger Speicherchip mit zwei Reihen von Anschlussstiften.
• RAM Disk: RAM, das als Festplattensimulation konfiguriert wurde (auch Vdisk genannt).
• Cache (RAM-Cache): Ein spezieller High-Speed-Speicher, der als Puffer zwischen Prozessor und Hauptspeicher dient.

Detaillierte RAM-Technologien

• SRAM: Schneller und zuverlässiger als DRAM, wird aufgrund der hohen Geschwindigkeit oft als Cache verwendet.
• DRAM: Große Kapazität, muss jedoch ständig aktualisiert werden, um den Inhalt zu halten.
• SDRAM (Synchronous DRAM): Etwa 20 % schneller als EDO-RAM; nutzt interne Speicher-Arrays für effizientere Zugriffe.
• FPM (Fast Page Mode): Häufiges Design für DRAM-Chips, bei dem der Zugriff über Zeilen- und Spaltenkoordinaten erfolgt.
• EDO (Extended Data Output): Verbessert die Leistung von Fast Page Mode um etwa 10 %.
• PB SRAM (Pipeline Burst SRAM): Nutzt Pipeline-Techniken für parallele Datenverarbeitung.
• DDR SDRAM: Sendet Daten zweimal pro Taktzyklus.
• RDRAM (Rambus DRAM): Arbeitet mit höheren Frequenzen und schmalerem Datenbus (16 Bit), um Engpässe zu vermeiden.

Rekursion und Algorithmen

Rekursive Funktionen

Eine rekursive Funktion besteht aus:

• Basisfall: Eine einfache Lösung für einen bestimmten Fall.
• Rekursiver Fall: Die Funktion ruft sich selbst mit Parametern auf, die näher am Basisfall liegen.

Stack (Stapel)

Ein Stack ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out). Die Hauptoperationen sind:

• PUSH: Element oben auf den Stack legen.
• POP: Oberstes Element vom Stack entfernen.

Datenbus und DMA

Der Data Bus dient dem Informationsaustausch zwischen Prozessor und RAM. Der DMA (Direct Memory Access) ermöglicht es Hardware-Komponenten, Daten direkt mit dem Speicher auszutauschen, ohne den Prozessor bei jedem Schritt zu belasten.

Sortier- und Suchalgorithmen

• Bubble Sort: Vergleicht benachbarte Elemente und tauscht sie bei falscher Reihenfolge.
• QuickSort: Teilt das Array basierend auf einem Pivot-Element in kleinere Teilbereiche.
• Sequentielle Suche: Durchsucht Elemente nacheinander.
• Binäre Suche: Halbiert bei jedem Schritt den Suchbereich (erfordert sortierte Daten).

Bäume und Graphen

Bäume

Ein Baum ist eine nichtlineare Struktur mit einem Wurzelknoten und Blattknoten. Ein binärer Baum hat maximal zwei Teilbäume (links und rechts).

Graphen

Ein Graph besteht aus Knoten (V) und Kanten (A). Wichtige Begriffe:

• Zyklischer Graph: Enthält mindestens einen Zyklus.
• Gewichteter Graph: Kanten enthalten zusätzliche Informationen (Kosten, Werte).
• Adjazenzmatrix: Darstellung als n x n Tabelle.
• Adjazenzliste: Liste der Knoten mit ihren jeweiligen Nachbarn.