Informatik 1 Theorie

Ein Algorithmus (algorithm) ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu berechnen. Diese Beschreibung ist eine endliche Folge aus elementaren, eindeutigen und ausführbaren Anweisungen.

Dabei müssen folgende Bedingungen erfüllt sein:

• Spezifikation

-> Eingabespezifikation: Welche Eingabegrößen sind erforderlich und welchen Anforderungen müssen diese Größen genügen, damit das Verfahren funktioniert

-> Ausgabespezifikation: Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften berechnet werden

• Durchführbarkeit

-> Endliche Beschreibung: das Verfahren muss in einem endlichen Text vollständig beschrieben sein

-> Effektivität: Jeder Schritt des Verfahrens muss effektiv (d.h. tatsächlich) „mechanisch“ ausführbar sein

-> Determiniertheit: Der Verfahrensablauf ist zu jedem Zeitpunkt fest vorgeschrieben

• Korrektheit

-> partielle Korrektheit: Jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Eingabespezifikation genügt haben

-> Terminierung: Der Algorithmus hält nach endlich vielen Schritten mit einem Ergebnis an, sofern die Eingaben der Eingabespezifikation genügt haben

Steuerungsverlauf (control flow) des Algorithmus

= Die Anordnung der Anweisungen eines Algorithmus, die bestimmt, in welcher Reihenfolge Anweisungen geschehen

• wird auch Kontrollfluss (flow of control) genannt

• Manchmal wird auch der Programmablauf oder Kontrollfaden (thread of control), also die tatsächlich abgespulten Schritte und Anweisungen so bezeichnet

Flussdiagramme (flow chart) = graphische Dargestellung eines Steuerungsverlaufs.

• Die Sprachelemente werden durch Symbole dargestellt:

• Verbunden werden diese mit Pfeilen und die Ausführung solcher Ablaufpläne folgt den Pfeilen zwischen den Kästchen

Struktogramme, Blockdiagramme oder auch Nassi-Schneidermann-Diagramme

Um den Steuerungsverlauf auch bei komplexen Algorithmen übersichtlich zu halten, schränkt man die Sprünge ein:

• Schleifen der Flussdiagramme sind höchstens ineinander

geschachtelt

• Schleifen überkreuzen sich nicht!

• Wir sprechen in diesem Fall von strukturierten Sprüngen im Gegensatz zu freien Sprüngen, die prinzipiell beliebige Ziele haben können

Idee einer virtuellen Maschine (als gedachter einheitlicher Computer) als Bindeglied zwischen Programmiersprache und Maschinensprache.

• Diese virtuelle Maschine sollte auf jeder Hardware emuliert werden (sollte verstanden werden)

-> Notwendig wäre dazu eine „Einigung“ auf einen allgemeingültigen Standard einer Schnittstelle.

• Befürchtung der Bevorzugung einer speziellen Sprache oder eines speziellen Maschinentyps

• Geschwindigkeitsverlust

• Spezielle Fähigkeiten eines Rechners (z.B. Vektoraddition) können nicht genutzt werden

Vorteil: Objektorientiert (Klassen als Abstraktionsprinzip), einfach, robust

Compiler: „Umgangssprachliche“ Anweisungen müssen in eine Folge von Maschinenbefehlen übersetzt werden (z.B. Daten in/aus dem Speicher lesen/schreiben, elementare arithmetische Operationen durchführen, Berechnungen an ganz spezieller Stelle fortsetzen)

=> Quellcode -> compilieren -> Byte-Code -> ausführen

Aufbau:

Ausführung:

1. Quelltext in Datei Hello.java speichern (Dateiname entspricht Klassennamen + Klasse muss bei Applications eine Methode main als Startpunkt der Ausführung besitzen)

2. Quelltext übersetzen = kompilieren -> Quelltext in Bytecode übersetzen = „javac Hello.java“ eingeben

3. Java-Programm ausführen (-> „java Hello“ eingeben, Interpretieren/starten des Bytecodes)

Rechner arbeiten mit binären Informationen, die in Bits (binary digit) codiert sind.

• ein Bit kann genau einen aus zwei Zuständen abbilden, z.B. {aus, an}, {wahr, falsch}, {0, 1}.

• 8 Bits sind 1 Byte = Menge von Bits, die notwendig ist, um ein „Zeichen“ zu speichern

• Allgemein gilt für n Zustände und b Bits: n = 2^b bzw. b = log2n

1. n = 2^16 = 65 536

2. b = log2 256 = 8

3. b = log2 26 ≈ 4,70…also 5 Bits (+6 Buchstaben Reserve!)

• 1 A4-Seite Text * 2.000 Zeichen * 1 Byte/Zeichen

= 2.000 Byte

= 2 kB

• 1 h CD-Audio = Abtastfrequenz 44,1 kHz bei 16 Bit/Sample pro Kanal

—> 2 Kanäle * 44,1 kHz * 16 Bit/Kanal * (60*60) s

= 635.040.000 Byte

= ca. 635 MB

• 1 h HD-Video (1.920 x 1.080) Pixel * 25 Hz * 24 Bit/Pixel * (60*60) s

= 559.872.000.000 Byte

= ca. 560 GB

Idee: Zeichen werden im Rechner intern als Zahlen gespeichert und bei Ausgabe wieder in Zeichen zurückgewandelt.

• Die Zuordnung von einem Zeichen zu einer Zahl ist Definitionssache.

Im Laufe der Zeit haben sich mehre Kodierungen (encodings) etabliert:

• US-ASCII: 7 Bit/Zeichen, also max. 128 Zeichen. Ab 1963.

• ISO-8859: 8 Bit/Zeichen, also max. 256 Zeichen. Ab 1987.

• Unicode/ISO-10646: z. Zt. 21 Bit pro Zeichen genutzt. Ab 1991. Verschiedene Realisierungen, z.B. UTF-16 (16 Bit/Zeichen), UTF-8 (variabel 8-32

Texte werden auf eine Tabellenstelle im Alphabet abgebildet

-> üblich sind ASCII (älteste), …utf-8, utf-16 und utf-32… (UTF = Unicode Transformation Format)

-> UTF ist eine Methode, unicode-Zeichen in eine Bytefolge abzubilden

Die Stelle an der ein Buchstabe in der Tabelle steht nennt man „code point“:

=> Ein Code point ist ein Codewert (hexa,dezimal, binär), der mit einem Zeichen in einem Kodierungsschema verbunden ist.

Lexikalik: Gültige Zeichen

• Wie spät ist es? / Wie — i¤t Ω↑?

Syntax: Grammatikalischer Aufbau

• Wie spät ist es? / Spät ist wie es?

—> maschinell prüfbar für formale Sprachen

Semantik: Bedeutung

• Wie spät ist es? / Wie spät ist grün?

Pragmatik: Intention im Kontext, z.B. Ironie

• Antwort "11:30" / Antwort "Es ist nie zu spät!"

—> maschinell nur teilweise prüfbar, aber Rechner kann Vorschläge machen (KI)

• Kommentare

• Bezeichner

• Literale (Datentypen)

• Block

-> in Unicode Zeichensatz = Buchstaben, Ziffern, Zeilenende, Leerzeichen, Trennzeichen, Operatoren

Einzeilige Kommentare beginnen immer mit einem doppelten Schrägstrich // und endet mit dem Zeilenende:

// Dies ist ein Kommentar

Für mehrzeilige Kommentare verwendet man die Zeichen /* und */ um Anfang und Ende eines Kommentars zu markieren:

/* Eine Standalone-Anwendung

muss eine main-Methode

besitzen */

Ein Bezeichner ist ein beliebiger symbolischer Name aus Java- Unicode Zeichen zusammengesetzt, aus

• Buchstaben, Ziffern und Unterstrichen

• Ein solcher Name muss mit einem Buchstaben beginnen (nicht mit einer Zahl oder Unterstrich)

-> Bsp. i, j, k, x, y, z, Schalter, Mein_Bezeichner, l_halbe, ...

• Java unterscheidet zwischen Groß- und Kleinbuchstaben!

• Es gibt reservierte konstante Werte (null, true, false) und bereits vergebene, Bezeichner vordefinierter Klassen (Object, String, System)

In Java müssen alle gespeicherten Daten typisiert werden, d.h. die Art und damit der mögliche Wertebereich muss angegeben werden -> definiert Speicherbedarf, erlaubte Operationen auf Daten und welche Umwandlungen verlustfrei möglich sind

Java Datentypen:

1. Datentyp für logische Wahrheitswerte:

• boolean 1 bit true oder false

2. Ganzzahlige Datentypen:

• byte 8 bit -128 … +127

• short 16 bit -32768 … +32767

• int 32 bit - 2147483648 … +2.147.483.647

• long 64 bit - 9223372036854775808 … +2^63 – 1

3. Gleitkomma-Datentypen:

• float 32 bit +/- 1,4 * 10^-45… 3,4 * 10^38

(Mantisse ca. 7 Dezimalziffern)

• double 64 bit +/- 4,9 * 10^-324 … 1,7 * 10^308

(Mantisse ca. 16 Dezimalziffern)