e-dokumen.com

1 Einführung Strukturen, Eigenschaften und Beschreibungsmöglichkeiten von Information undInformationsverarbeitungsprogrammen Möglichkeiten der Strukturierung, Formalisierung und Mathematisierung vonAnwendungsgebieten Modellbildung und Simulation.Ist die Informatik eine Wissenschaft?Wesentliches Moment der Definition einer Wissenschaft ist das Verfügen über einetheoretische Basis, aus der neue Erkenntnisse abgeleitet werden. Dies ist in der Informatik vielfältig unter Beweis gestellt. Als Beispiel sei die Entwicklung von Programmiersprachen und Rechnerarchitekturen aus theoretischen Erkenntnissen über Prozesse und Systeme der Informationsverarbeitung genannt.Informatik ist eine StrukturwissenschaftCarl Friedrich von Weizsäcker gibt in seinem Buch “Die Einheit der Natur” eine Unterteilung der Wissenschaften in Naturwissenschaften (Physik, Biologie) Ingenieurwissenschaften (Nachrichtentechnik) Geisteswissenschaften (Philosophie) Sozialwissenschaften (Soziologie, Politologie) Strukturwissenschaften (Mathematik, Informatik)an und bezeichnet die Informatik als Strukturwissenschaft. Zitat:“. sie studiert Strukturen in abstracto, unabhängig davon, welche Dingediese Strukturen haben, ja ob es überhaupt solche Dinge gibt.”Wurzeln der Informatik: Mathematik, Physik Nachrichtentechnik (Kybernetik: Wissenschaft von den Beziehungen zwischen dem Verhalten vonSystemen, d.h. ihren Erscheinungsformen, und ihrer Struktur)2

1.1 Was ist InformatikEs hat sich eine Entwicklung der Informatik zu einer selbständigen Wissenschaft mitvier wesentlichen Elementen vollzogen:1. die formale Spezifikation von Systemen der Informationsverarbeitung2. die Darstellung von Systemen durch Datenstrukturen und Algorithmen3. die automatisierte Durchführung von Transformationen von Daten, um Information zu gewinnen4. die Synthese und Analyse von Hardware- und Softwareinstrumenten als Basisder Implementierung von AlgorithmenAmbivalenz der Informatik:1. Die Informatik erfordertdas analytische Herangehen der Naturwissenschaftenunddie formalisierenden Methoden der Mathematikzur Lösung eines Problems der Informationsverarbeitung. Zuordnung eines konkreten Problems zu einer Problemklasse Frage: Was ist Information, wie ist sie zu beschreiben und wie kann man sie ausDaten erhalten? Frage: Wie sind informationsverarbeitende Systeme zu entwerfen?Beispiel: Computer Vision Maschinensehen1. Wie ist die visuell wahrnehmbare Welt zu repräsentieren/strukturieren, um visuelle Wahrnehmung technisch zu realisieren?2. Wie sind Struktur und Dynamik von Systemen zu verstehen, umvisuelle Wahrnehmung realisieren zu können? Umwelt:(äußerer) ProzeßBeobachtung: DatenSystem:Bewertung, InterpretationAktion: Wirkung- Architektur- interner Prozeß3

1 Einführung Rechenprozeßdert:Programmerfor- Informatik beschäftigt sich mit– RechnerstrukturenDaten– Programmstrukturen– DatenstrukturenRechner (Maschine)2. Die Informatik lebt durch das konstruktive Element der Ingenieurwissenschaften:Ohne die Möglichkeit der Anwendung gäbe es die Informatik nicht! Tätigkeiten eines Ingenieures [nach ENCYCLOPAEDIA BRITANNICA]:Die schöpferische Anwendung wissenschaftlicher Prinzipien auf denEntwurf und die Entwicklung von Strukturen, Maschinen, [.] im Hinblick auf eine gewünschte Funktion, Wirtschaftlichkeit und Sicherheitvon Leben und Eigentum. Wie lassen sich abstrakte Beschreibungen von Systemen informationsverarbeitender Prozesse auf konkrete Realisierungen abbilden?- Hardware ”Rechner” Rechnerarchitekturen, Computer Engineering- Software ”Programme” Software EngineeringAuswahl aus unendlicher Zahl von Möglichkeiten unter Randbedingungen(Zwängen) enge Benachbarung/Überschneidung von Informatik und Elektrotechnik Gegenstand der Informatik ist vor allem anderen:– Analyse und (Re-)Organisation der Arbeit mit Hilfe informationstechnischer Mittel, ihre maschinelle Unterstützung oder ihre Ersetzung durchMaschinen und– die Entwicklung der Informationstechnik zu diesen Zwecken, insbesondere die Entwicklung des methodisch begründeten Entwurfes von Soft- undHardware und der Integration informationstechnischer Komponenten zuSystemen.Drei Paradigmen der Informatik:1. Paradigma: Theorie (verwurzelt in Mathematik)Ziel: Schaffung einer kohärenten und validen Theorie nach 4 Schritten4

1.1 Was ist Informatika) Definition: charakterisiere die zu untersuchenden Objekteb) Theorem: stelle Hypothese über mögliche Beziehungen unter diesen Objekten aufc) Beweis: untersuche, ob diese Beziehungen wahr sindd) Abstraktion: interpretiere die Ergebnisse2. Paradigma: Modellbildung (verwurzelt in experimentellen Naturwissenschaften)Ziel: Abstraktion abgeleitet aus der Beobachtung von Phänomenen nach 4 Schrittena) bilde eine Hypotheseb) konstruiere ein Modell und leite eine Vorhersage abc) entwerfe ein Experiment und gewinne Datend) analysiere die Ergebnisse3. Paradigma: Entwurf (verwurzelt in Ingenieurswissenschaften)Ziel: Konstruktion eines Systems (Gerätes) nach 4 Schrittena) benenne die Erfordernisseb) gebe eine Spezifikation anc) entwerfe und implementiere das Systemd) teste das SystemFolgerungen aus dem konstruktiven Element der Informatik: Die Informatik ist in bedeutendem Maße eine Ingenieurwissenschaft Die Informatik vermag durch ihre Ergebnisse die menschliche Gesellschaft enorm zubeeinflussen– Die technologische Entwicklung schreitet der gesellschaftlichen Entwicklungvoran– Gefahr starker gesellschaftlicher VerwerfungenMuß das Machbare auch zu jeder Zeit realisiert werden? Der technologische Fortschritt treibt die interne Entwicklung der Informatik starkvoran– Was gestern uninteressant war, weil technisch nicht realisierbar, muß heute entwickelt werden, weil morgen realisierbar5

1 Einführung– Softwarekrise: Die Entwicklung der Programmierkonzepte hinkt der Entwicklung der Hardware nach Die technische Realisierbarkeit bedeutet nicht die Durchsetzbarkeit auf dem MarktBeispiel: ParallelrechnerDiktat des Faktischen: preisgünstige Universalrechner werden immer billiger, schneller, weiter verbreitet, einfacher zu bedienen/programmieren.Die Programmierparadigmen der Parallelrechner sind noch nicht weit entwickelt: ihre Programmierung ist langwierig, teuer und kompliziert.Gebietsgliederung der Informatik:1. Technische Informatik stellt die erforderlichen Gerätschaften (Hardware) bereit beschäftigt sich mit der Konstruktion von Schaltwerken/Rechnern, Speicherchips, Prozessoren, Peripheriegeräten sehr eng mit der Elektrotechnik verbunden Hardware muß potentielle Anwendungen im Auge haben gekennzeichnet durch Nutzung hardwarenaher Programmierung und Simulation der Hardware2. Praktische Informatik stellt im weitesten Sinne die Programme (Software) bereit schlägt Brücke zwischen Hardware und Anwendungssoftware beschäftigt sich mit der strukturierten Erstellung von Softwaresystemen: Informations-/Kommunikationssysteme, Betriebssysteme, Übersetzer Künstliche Intelligenz: Wissensverarbeitung gekennzeichnet durch hardwareferne Programmierung3. Theoretische Informatik stellt im weitesten Sinne die abstrakten Strukturen bereit hat besonders enge Beziehung zur Algebra und Logik beschäftigt sich mit: Automatentheorie, formalen Sprachen, Komplexität vonAlgorithmen, Berechenbarkeit von Problemen6

1.1 Was ist Informatik4. Angewandte Informatik beschäftigt sich mit dem Einsatz von Rechnern in unterschiedlichsten Anwendungsgebieten (z.B. Textverarbeitungssysteme, Sprachverarbeitung,Bildverarbeitung, Handschriftenerkennung) “Bindestrich-Informatik”Medizinische Informatik, Wirtschaftsinformatik, Rechtsinformatik7

1 Einführung1.2Die Geschichte des maschinellen RechnensDie Geschichte des maschinellen Rechnens Die Informatik ist die Wissenschaft, die denMenschen bei der Ausführung geistiger und körperlicher Tätigkeiten unterstützt odervon ihnen befreit. Hierdurch ist ein inhärenter sozialer Sprengstoff im Wesen der Informatik begründet. Geistige Tätigkeiten:––––––Rechnen mit Zahlen und SymbolenBewerten von Daten und AussagenVerstehen von TextÜbersetzen von TextVerstehen von natürlicher Sprache, Erzeugen natürlicher SpracheVerstehen von Bildern, Maschinensehen Körperliche Tätigkeiten:– Regelung und Steuerung von Prozessen mittels Computer (“eingebettete Systeme”)– Roboter- Industrierobotor: blind, “dumm”, d.h. operieren nur unter vordefinierten Bedingungen- autonome Systeme: visuelle, sensorische Wahrnehmung, lernfähig, unter weniger eingeschränkten Bedingungen einsetzbarDie Informatik hat ihre Wurzeln im Bedürfnis, geistige Tätigkeiten zu mechanisieren.1.2.1 Das Rechnen mit ZiffernZiffern stellen Zahlzeichen eines Zahlwortes dar, z.B. “neun”: IX oder 9 Die römischenZahlen wurden nach einem Additionssystem gebildet,z.B. 1996 MDCCCCLXXXVI oder MCMXCVI.Die Zahlen wurden mit Zahlsteinchen, den “calculi” gelegt, hiervon stammt der Begriff“Kalkül” ab. Die Ziffern von Eins bis Neun sowie die Null als Zeichen für leere Stellenwurden durch die Inder (ca. 800 n.Chr.) eingeführt. Sie “erfanden” das Dezimalsystem,ein Stellenwertsystem zur Basis 10. Erst diese Einführung des Stellenwertsystemes derarabischen Ziffern erlaubte die Mechanisierung des Rechnens mit Ziffern.Eine Zahl im Dezimalsystem besitzt die Darstellungz10 n 1Xi 08αi 10i , αi {0, 1, . . . , 9}.

1.2 Die Geschichte des maschinellen RechnensZ.B. 199610 1 · 103 9 · 102 9 · 101 6 · 100 . Auch heute existieren im täglichen Lebennoch weitere Zahlensysteme, z.B:z12 Dutzend, z60 zur Zeiteinteilung (von den Babyloniern). Von Gottfried Wilhelm Leibniz (1679) stammte der Entwurf einer dual arbeitenden Rechenmaschine miteinem Stellenwertsystem zur Basis 2:z2 n 1Xαi 2i ,i 0αi {0, 1}.Erst in diesem Jahrhundert erlangt das Dualsystem seine Bedeutung zum Rechnen:Konrad Zuse entwarf 1933 eine durch Relais gesteuerte Rechenmaschine. TechnischeRealisierung des Dualsystems: 1/0-Codierung über Schalter, Relais, Röhren, Transistoren:1: Spannung/Strom0: keine Spannung/StromHierdurch ist der Aufbau komplexer Rechenwerke für arithmetische Grundoperationen ermöglicht, deren effiziente Ausführung durch logische Schaltkreise erfolgt.1.2.2 Das Rechnen mit SymbolenDas “Buchstabenrechnen” wurde von der indischen Mathematik im frühen Mittelalter eingeführt. Hieraus leitet sich die algorithmische Lösung arithmetischer Aufgabenab, z.B. die Division (Adam Ries, 1492-1559). Damit kann eine erste, noch unscharfeDefinition des Begriffes Algorithmus gegeben werden:Algorithmus: Umformung von gegebenen Größen auf Grund eines Systemsvon Regeln in andere Größen.Z.B.: (a b)(a b) a2 b2 (Anwendung der Regeln der Algebra) Das Rechnen mitZiffern und mit Symbolen ist auf einer allgemeineren Ebene als gleichwertig anzusehen:1. Das klassische Rechnen kann als Manipulation von Zeichenketten aufgefaßt werden.2. Jede Manipulation von Zeichenketten nennt man Rechnen (Begriffserweiterunggegenüber der Umgangssprache!)Damit versteht man unter Rechnen eine regelhafte (algorithmische) Abbildung einer Eingangszeichenkette auf eine Ausgangszeichenkette:9

1 EinführungInTTransformationOutUnter Umständen kann für diese Abbildung (Transformation) ein geschlossener arithmetischer Ausdruck angegeben werden, generell ist sie aber durch eine abstraktere mathematische Funktion beschreibbar. Beispiele für das Rechnen mit Symbolen: 1963 Programmsystem zur Formelmanipulation 1950 erster Textmanipulator: Editieren von Text1960 automatische Silbentrennung mechanische Sprachübersetzung (erste Ansätze 1933 Smirnov-Troyanski), machteEntwicklungen auf dem Gebiet der Linguistik erforderlich. Die Berücksichtigungdes Kontextes ist notwendig:“HUND” “DOG”aber“HUNDERT” “HUNDRED” Schachspiel (N.Wiener, 1948; Shannon, 1950: grundlegende Theorie) Mathematische Beweise.1.2.3 Logisches RechnenDie beim Rechnen mit Symbolen angegebene Transformation T kann auch die Zuordnung eines Wahrheitswertes Out {true, false} zu einer Zeichenkette In erzeugen,wenn In eine Aussage tDabei sind Aussagen sprachliche Gebilde (Sätze), die zur Beschreibung undMitteilung von Sachverhalten dienen, welche als wahr oder falsch bewertetwerden können.Es gilt das Prinzip der Zweiwertigkeit einer Aussage. Die Aussagenlogik beschäftigt sichmit der Bewertung komplexer Aussagen. Leibniz (1672-76): Ansätze für ein logisches Kalkül Boole (1847): Algebraisierung der Logik10

1.2 Die Geschichte des maschinellen Rechnens Shannon (1938): erkannte Parallelen in der Arbeitsweise von Relaisschaltungenund Aussagenkalkül Entwicklung einer Schalttheorie, z.B. systematisches Vereinfachen von Schaltfunktionen Abbot (1951): Bau einer digitalen Rechenanlage zur Durchführung logischer Verknüpfungen Frege (1879): Begründung der modernen LogikDie Prädikatenlogik stellt eine Verallgemeinerung der Aussagenlogik dar:Sie ermöglicht die Einführung einer symbolischen Sprache für die Beschreibung vonAlgorithmen und ihren Objekten. Die Geschichte der Algorithmen ist die Geschichtedes logischen Rechnens mit Symbolen! Heutiger Stand der Entwicklung:Die Interpretation/Übersetzung von Anwenderprogrammen erfolgt nach logischen Regeln, die ihre Entsprechung in der Funktion der Schaltkreise des Rechners haben. Esexistiert eine 1:1-Abbildung der Software auf die Hardware.1.2.4 Das Rechnen mit SignalenDie numerischen, symbolischen und logischen Berechnungsaufgaben sind äquivalentinsofern, als daß sie sich auf diskrete Zeichen (Zahlen, Buchstaben, Operationssymbole)beziehen. Symbole sind Objekte des menschlichen Geistes, sie sind Modellierungen vonPhänomenen der Natur (z.B. interpretierte Signale). Signale sind Phänomene der Natur.Sie haben unendlich viele Interpretationsmöglichkeiten. Welche hiervon gewählt wird,hängt von der Intention des Beobachters ab. Albert Einstein zur Crux der Modellbildung:“Insofern sich die Sätze der Mathematik auf die Wirklichkeit beziehen, sindsie nicht sicher, und insofern sie sicher sind, beziehen sie sich nicht auf dieWirklichkeit.”Für die Symbolverarbeitung kann man von folgenden Annahmen ausgehen:1. Symbole sind AbstraktionenSie sind “sauber”, d.h. nicht gestört. Sie geben die Wirklichkeit zwar nur näherungsweise wieder, enthalten aber das für die Aufgabe Wesentliche.2. Symbole sind endlich, sie erfordern einen endlichen (vielleicht sogar minimalen)Aufwand zu ihrer Repräsentation und Beschreibung.3. Typische Berechnungsaufgaben sind von begrenzter Komplexität, sie führen inendlicher Zeit zum gewünschten Ergebnis. Das trifft bei weitem nicht auf alleProbleme zu!11

1 Einführung4. Typische Berechnungsaufgaben sind deterministisch, in der Auswahl der Bearbeitungsschritte besteht keine Freiheit.Prinzipiell sollte man für die Signalverarbeitung von folgenden Annahmen ausgehen:1. Signale sind die Wirklichkeit, sie enthalten relevante und nicht relevante Komponenten. Sie enthalten Störungen, die mit dem relevanten Signalanteil untrennbarverbunden sind. Signale sind “schmutzig”.2. Signale sind kontinuierlich, sie erfordern im Prinzip einen unendlichen Aufwandzur Repräsentation oder Beschreibung. Die Repräsentierung von Signalen im Rechner erfolgt in der Form von digitalen, d.h. diskretisierten und quantisierten Signalen.3. Es gibt wesentliche Aufgabenklassen, die von sehr hoher Komplexität sind. Siekönnen mit deterministischen Algorithmen nur mit sehr hohem Aufwand (in sehrgroßer Zeit) oder überhaupt nicht exakt gelöst werden.4. Typische Berechnungsaufgaben sind stochastisch (nicht deterministisch), in derAuswahl der Bearbeitungsschritte werden Freiheiten zugelassen (z.B. Heuristiken, Zufallsprozesse zur Steuerung).Mit dem Rechnen mit Signalen beschäftigen sich folgende relativ junge Disziplinen: Signaltheorie (ca. 1945) Nachrichtentheorie (ca. 1945) Mustererkennung (ca. 1960) Neuroinformatik (ca. 1980)Zur Erfassung des Zusammenhangs zwischen einem gestörten Signal und einem Symbol werden die Theorie stochastischer Prozesse (entwickelt aus Wahrscheinlichkeitstheorie), die Informationstheorie und Entscheidungstheorie herangezogen. Das Problem, wie auf den symbolischen Gehalt von gestörten Signalen geschlossen werdenkann, ist nur teilweise gelöst.12

1.2 Die Geschichte des maschinellen RechnensBeispiel: numerischer Code des Buchstaben H: 010010002 (ASCII-Code) gedruckter Buchstabe H: nur Störungen der sätzlichzu grobabgetastet,um 30 abgetastet,keinegeneigtverrauschtStörungen handgeschriebener Buchstabe H: zusätzlich auch Individualität desSchreibersFrage: Wie kann aus dem Signalmuster das Symbol des Buchstaben H erkannt werden? Das Erkennen von maschinengeschriebener Schrift (OCR)wird beherrscht (Reduktion auf klassische Problemlösungen). Das Erkennen handgeschriebener Schrift jedoch nicht, wahrscheinlich ist eine Erweiterung klassischer Problemlösungen nötig.Beispiele für das Rechnen mit Signalen sind Mustererkennung (Pattern Recognition, ca. 1960)Als Muster wird eine durch eine Menge von Messungen oder Beobachtungen erzeugte Struktur sifzierungBedeutung(Symbol, Bezeichnung) Bildverarbeitung (Image Processing, ca. 1965)Unter einem Bild wird eine matrixförmige Anordnung von Helligkeitswerten chreibung(Satz von Symbolen,oder andere Formder Beschreibung)13

1 Einführung Maschinensehen (Computer Vision, ca. 1980)Eine Szene (durch Kamera beobachteter Weltausschnitt), gegeben durch ein Einzelbild oder eine Bildfolge, soll interpretiert werden, um Beschreibungen oderReaktionen abzuleiten.Bild(folge)((2 1)D-Signal)InterpretationVerstehenBeschreibung, Reaktion(z.B. eines Robotors)Die Interpretation oder das Verstehen einer Bildfolge ist nicht als lineare Folgevon Berechnungsprozessen realisierbar. Es stellt sich die Frage, ob sich die visuelle Wahrnehmung des Menschen technisch realisieren läßt. Das Symbolverarbeitungsparadigma der Kognitionswissenschaft führt nicht zur Lösung. Zu vielen Problemen der Wahrnehmung können keine Algorithmen explizit angegebenwerden.In der Neuroinformatik sind in Form von neuronalen Netzen Ansätze zu Berechnungsverfahren begründet, die auf explizite Formulierungen von Algorithmenverzichten.1.2.5 Die Entwicklungsgeschichte der RechenmaschineDie bis zu unseren heutigen Computern führende Entwicklung von Rechenmaschinenverlief in 3 Etappen:1. 17. Jahrhundert: Mechanisierung des Rechnens mittels mechanischer Rechenwerke einfache Ausführung der Grundrechenarten2. 19. Jahrhundert: Automatisierung des Rechnens mittels Daten- oder Programmspeicher und Steuerwerk komplexere Berechnungsabläufe3. ca. 1940/1950: Einführung der frei programmierbaren elektronischen Universalrechenmaschine Entwicklung bis zum heutigen Computer über 5 GenerationenIm folgenden werden einige Stationen der 3 Etappen skizziert: Leibniz(1673): 12-Dekaden-RechenmaschineSchnelle Multiplikation mit Hilfe von Zehnerpotenzen, stufenweise verschiebbareZahnradwalze (Staffelwalze), dieses Prinzip wurde von fast allen mechanischen Rechenmaschinen übernommen. Charles Babbage (1843): analytical engineBahnbrechendes Konzept eines universellen Rechners mit14

1.2 Die Geschichte des maschinellen Rechnens– Rechenwerk– Steuereinheit für Iteration und bedingte Verzweigung– Zahlenspeicher– E/A über Lochkarten-Band nach Jacquard (1805)zur Ber

Informatik I WS 2000/01 R. Koch Informatik II SS 2001 R. Koch Informatik I WS 2001/02 R. Koch Informatik II SS 2002 R. Koch Informatik I WS 2002/03 R. v. Hanxleden Informatik II SS 2003 G. Sommer Wie alle gedruckten Werke von gro ßerem Umfang war da