-
Rekursive Verfahren sind nicht nur in der Mathematik, sondern auch in der Informatik von großer Bedeutung. Sie werden nicht nur zum Errechnen rekursiver Folgen, die zum Beispiel bei der Darstellung von Wachstumsprozessen oder Fraktalen Anwendung finden, sondern auch zum schrittweisen und effektiven Lösen komplizierter und langwieriger Aufgaben (zum Beispiel bei Sortieralgorithmen oder Backtrackingprogrammen) verwendet.
Während früher solche Ve ...
mehr
-
Die Programmiersprache Pascal ermöglicht die Verwendung von sogenannten Unterprogrammen in Form von Prozeduren und Funktionen. Der einzige Unterschied zwischen den beiden ist, daß Funktionen nach dem Aufruf einen Wert besitzen und Prozeduren nicht. Unterprogramme sind eigenständige Programmabschnitte, die aus dem Hauptprogramm, aber auch aus anderen Unterprogrammen, aufgerufen werden können. Ihre Verwendung ist von großem Vorteil, da sie das ...
mehr
-
Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a1 absolut zu bestimmen, indem man ihm einen Zahlenwert zuweist. Auch bei der Programmierung rekursiver Unterprogramme muß es eine Abbruchbedingung geben, bei der die Rekursion stoppt und kein neuerlicher Selbstaufruf mehr erfolgt. Beim Fehlen einer Abbruchbedingung ruft sich das Unterprogramm so lange selbst auf, bis der Stack- ...
mehr
-
Die Anwendungen der rekursiven Unterprogrammtechnik lassen sich in vier verschiedene Gruppen gliedern. Es sei nochmals darauf hingewiesen, daß heute fast alle Programme iterativ programmiert sind, um sie übersichtlicher zu gestalten, da die rekursiven Varianten manchmal ein schlechteres Laufzeitverhalten besitzen. Dennoch ist die rekursive Programmierung bei vielen Projekten von großem Vorteil, da sie oft eine leichtere und schnellere Verwirkli ...
mehr
-
Das wohl naheliegendste Einsatzgebiet ist das Berechnen von Gliedern rekursiver Folgen. Hier bietet sich der Eisatz von rekursiven Funktionen an, die selbst einen Wert annehmen können. Beim Aufruf der Funktion muß überprüft werden, ob die als Parameter übergebene Nummer des Gliedes Eins ist. Wenn dies der Fall ist, wird der Funktion der Wert für a1 übergeben und die Funktion beendet. Andernfalls wird der Funktion ein Wert zugewiesen, der aus ei ...
mehr
-
Oft werden Rekursionen dazu eingesetzt, um ein komplexes Problemlösungsverfahren in viele kleine, einfach zu lösende, Teilschritte aufzuspalten, durch deren Ausführung die gestellte Aufgabe schließlich gelöst werden kann.
Das Aufspalten erfolgt in mehreren Stufen, sodaß dieser Prozeß am besten mit einem Baumdiagramm darzustellen ist. Diese Baumstruktur verästelt sich, vom gegebenen Problem ausgehend, schrittweise in immer mehr und kleinere P ...
mehr
-
Bei dieser Anwendung der Rekursion macht man sich die Eigenschaft des Pascalcompilers zunutze, daß lokale Variablen bei jedem Selbstaufruf neu angelegt werden, die Werte der vorigen Rekursionsebenen aber noch im Speicher vorhanden sind. So ist es möglich, Lösungen nach dem "Trial and Error" - Prinzip zu suchen. Dabei wird immer die selbe Vorgangsweise verwendet: Von einer gegebenen Ausgangsstellung aus wird nach gewissen Regeln ein Lösungsversu ...
mehr
-
Ein weiteres riesiges Anwendungsgebiet der Rekursion ist die Darstellung von Fraktalen am Computer. Unter diesem Punkt sollen aber nicht wie in Punkt 3.1. einfach rekursive Folgen oder Funktionen dargestellt werden. Vielmehr geht es darum, geometrische Formen nach einer Transformation immer wiederholt darzustellen, sodaß sich ein sinnvolles Gebilde ergibt.
3.4.1 Der fraktale Baum
Der fraktale Baum ist ein recht einfaches, aber sehr schö ...
mehr
-
Grafikformate sind gerade im Bereich Multimedia oft von entscheidender Bedeutung. Dabei spielen meist sehr viele Faktoren eine Rolle bei der Wahl eines bestimmten Formats. Unkomprimiert sind Bilddaten meist zu groß und unhandlich. Verschiedene Datenformate bieten aber nicht nur unterschiedliche Kompressionen, sondern auch unterschiedliche Qualität des gespeicherten Bildes. Nicht zuletzt spielt auch der Verbreitungsgrad eines Dateiformates eine wi ...
mehr
-
Das GIF-Format wurde speziell für den Online Bereich entwickelt. Seine Vorteile liegen in der hohen Komprimierungsdichte (bei gleichem Inhalt zehn- bis dreißigmal höher als bei Windows-Bitmaps). Es ist neben JPEG das am meisten verbreitete Format im Internet. Es besitzt eine Farbpalette, die bis zu 256 Farben oder 8 Bit pro Pixel (Bildpunkten) enthalten kann.
Die höchst mögliche Auflösung eines Bildes in diesem Format beschränkt sich auf 16000 ...
mehr
-
xJPEG wurde von der Joint Photographic Experts Group (daher der Name) entwickelt. In JPEG-Dateien werden ähnliche Farbflächen zusammengefasst. Dabei kann die Kompressionsdichte variiert werden, wodurch die Qualität des Bildes besser oder schlechter wird. Je stärker die Kompression desto schlechter wird die Bildqualität.
Das JPEG-Kompressionsverfahren ist ein verlustreiches Verfahren. Es eignet sich kaum für Strichzeichnungen, da harte Kanten s ...
mehr
-
BMP ist unter dem Betriebsystem MS-Windows 3.0 entstanden und dadurch ein sehr häufig verwendetes Bildformat geworden. Die Daten können optional mit Komprimierung abgelegt werden, was allerdings selten vorkommt.
Das Format ist unabhängig vom verwendeten Ausgabegerät definiert (device-independent), es kann auf verschiedenen Bildschirmen oder Druckern ausgegeben werden und wird auch von Programmen anderer Betriebsysteme unterstützt.
Dem BMP-F ...
mehr
-
TIFF (Tag Image File-Format) wurde von der Firma Aldus Corporation entwickelt. Das Format hat sich in den letzten Jahren zu einem der wichtigsten Formate für Rasterdateien entwickelt. Es wurde von Anfang an sehr umfangreich konzipiert und bietet eine Vielzahl von Speichermöglichkeiten und neben den eigentlichen Grafikdaten auch Angaben wie den Namen der benutzten Grafiksoftware oder den Scannertyp.
TIFF ist in der Lage, Schwarz/Weiß-, Grauwert ...
mehr
-
PNG bedeutet Portable Network Graphic (ausgesprochen: PING). Es handelt sich um ein Grafikformat, das eigens für den Einsatz im WWW konzipiert wurde. PNG soll alle Vorteile von GIF und JPEG in sich vereinen:
. PNG komprimiert verlustfrei wie das GIF-Format
. PNG unterstützt 16,7 Mio. Farben wie das JPEG-Format
. PNG ist wie GIF und JPEG plattformunabhängig
. PNG unterstützt transparente Hintergrundfarben wie das GIF-Format
. PNG erlaub ...
mehr
-
Aus Gründen der Kapazität von Speichermedien (besonders im WWW)ist es notwendig Bildinformationen im Volumen zu reduzieren.
Es gibt drei Kategorien in die sie sich einteilen lassen:
1. Statistische Verfahren (Entropy Coding) suchen im Eingabestrom nach statistischen Verteilungen welche zur Reduktion der Daten ausgenutzt werden. Dabei wird die Eingabe als reiner Bitstrom betrachtet, ohne die inherente Semantik zu beachten.
2. Semantische ...
mehr
-
Die Huffman-Codierung geht auf das Prinzip des Morsealphabets zurück. Dort werden häufig vorkommende Symbole (in diesem Fall Buchstaben) kürzeren Codes zugeordnet als die seltener vorkommenden. Der Code für ein \"e\" z.B. besteht nur aus einem einzigen Morsezeichen. Dagegen sind zur Übertragung des selten vorkommenden y\' 4 Morsezeichen nötig. Diese Methode wird als Entropie-Codierung bezeichnet. Entropie-Codierungen codieren nicht die zu übertra ...
mehr
-
Das RLE-Verfahren (Run Lenght Encoding) ist das einfachste unter den hier vorgestellten. Bei diesem Verfahren werden Folgen gleicher Bytes durch ein Paar (Zeichen, Anzahl) dargestellt: AAABBBBBBCCCDDDD also durch A3B6C3D4. In diesem Beispiel ergibt sich eine Reduktion von 50% (16:8 Byte).
Run Length Encoding eignet sich besonders für Dateien mit langen Folgen gleicher Zeichen, z. B. Schwarz/Weiß-Grafiken. Aus diesem Grund wird dieses Verfahren a ...
mehr
-
Das LZW-Verfahren ist nach seinen Entwicklern Lempel, Ziv und Welch benannt. Diese Kompressionsmethode wird von vielen Grafikformaten (z. B. Gif) genutzt. Bei dieser Codierung wird nach Folgen einzelner Bytes gesucht und diese durch eine Angabe von Anzahl und Wert ersetzt. Das LZW Verfahren sucht nach sich wiederholenden Zeichenketten und ersetzt diese durch einen Verweis auf die identische Zeichenfolge.
Dieses Verfahren arbeitet mit einer Zuord ...
mehr
-
JPEG ist ein standardisiertes Bildkompressionsverfahren, das von der Joint Photographic Experts Group entwickelt wurde. Es ist ein zusammengesetztes Verfahren.
Die Komprimierung der Grafikdaten erfolgt in mehreren Schritten:
1. Schritt: Datenreduzierung
Das Auge ist in der Lage mehr Unterschiede in der Helligkeit als Farbdetails zu sehen. Deshalb reduziert man die Farbinformation durch das Weglasssen einzelner Punkte. Dieses Verfahren w ...
mehr
-
Der Scanner ist ein Bildtransformator. Er wandelt analoge Bilder in digitale Daten um. Der entscheidende Vorgang dabei: Bei der Abtastung der Vorlage zerlegt der Scanner das Bild in einzelne Punkte. Diese Bildelemente oder Pixel (picture elements) sind für den Computer verarbeitbare "Bildbröckchen".
...
mehr
