Grundlagen derInformatikSommersemester 2007

Prof. Dr. Peter Kneisel

Didaktik: Durchführung

Diese Vorlesung enthält Übungen Die Übungen werden je nach Bedarf durchgeführt. Zur Vorbereitung werden Übungsblätter, je nach Vorlesungsverlauf

zusammengestellt. Weitere Übungen sind im Foliensatz vorhanden und sollten selbständig und

vollständig bearbeitet werden.

Vorsicht ! Kommen Sie in alle Veranstaltungen - machen Sie die Übungen Überschätzen Sie sich nicht - auch wenn Sie PC-Crack sind

Didaktik: Folien

Der Vorlesungsstoff wird anhand von Folien dargelegt Die Folien bilden nur einen Rahmen für die Inhalte. Die Folien sollten daher mit Hilfe

eigener Vorlesungsskizzen ergänzt werden - am besten in Form einer Vorlesungsnachbereitung max. 3 Tage nach der Vorlesung

Zusätzlich zu den Folien werden Beispiele an der Tafel oder am Rechner gezeigt. Diese sollten Sie vollständig mitskizzieren.

Zur vollständigen Nachbereitung, z.B. als Klausurvorbereitung, sind die Folien einheitlich strukturiert

Es gibt genau drei Gliederungsebenen: Kapitel, Unterkapitel, Abschnitte Die Inhalte jedes Kapitels und jedes Unterkapitels werden jeweils motiviert und sind

verbal beschrieben. Zusätzlich gibt es jeweils ein stichwortartiges Inhaltsverzeichnis der Unterkapitel, bzw. Abschnitte

Die Vorlesung wird ständig überarbeitet, so dass sich die Foliensätze ändern können (und werden)

Laden Sie sich zur endgültigen vollständigen Klausurvorbereitung nochmals zusätzlich den kompletten Foliensatz herunter.

Literatur

Diese Veranstaltung ist anhand (wirklich) vieler Bücher und einer Menge eigener Erfahrungen erstellt worden. Jedes Buch hat dabei Schwerpunkte in speziellen Bereichen und ist daher sinnvoll. Eine Auflistung aller dieser Bücher ist nicht sinnvoll.Stellvertretend für all diese Bücher sei hier ein Buch angeführt:

H.P.Gumm, M.Sommer: „Einführung in die Informatik“; Oldenbourg-Verlag 2004

Motivation ist alles !Hier ein paar Bücher, die das Interesse und den Spaß an der Wissenschaft im Allgemeinen und an der Informatik im besonderen wecken soll:

S.Singh: „Fermats letzter Satz“; DTV, 9.Auflage 2004 M. Spitzer: „Geist im Netz“; Spektrum, Akad. Verlag 2000 H. Lyre: „Informationstheorie“; UTB, 2002 A.Hodges: „Alan Turing, Enigma“; Springer-Verlag, 1983 D.R.Hofstadter: „Gödel, Escher, Bach“; Klett-Cotta, 2006 (Taschenbuch 1991)

Inhalt

Wie jede Wissenschaft befasst sich die Informatik mit ihren eigenen „Objekten“. Was diese „Objekte“ sind und was man mit diesen Objekten machen kann - und wie - wird in dieser Vorlesung auf eher abstraktem Niveau, aber immer mit Beispielen aus der Realität eines Informatikers (oder einer Informatikerin), erläutert.

Diese Vorlesung konzentriert sich auf den „Kern“ der Informatik. Vertieftere Einführungen in z.B die Bereiche der Programmierung, Rechnerarchitekturen, Betriebssysteme, etc. sollen daher bewusst den entsprechenden Veranstaltungen vorbehalten bleiben

Inhalt1. Informatik2. Information und Codes3. Zeichen und Zahlen4. Datenstrukturen5. Algorithmenentwurf

Überblick und Einordnung

TechnischeTheoretischePraktische

Informatik

Dyn

amik

(A

lgor

ithm

ik)

Elemente

Strukturierung

EP

OOP

1

5

AD

Sta

tik (

Str

uktu

r)Information

Codes

Zahlen

Zeichen

Daten-strukturen

3

2

4RA

AFSSWT RN

Kapitel 1 Informatik

1962 wurde der Begriff „Informatique“(als Kombination der Begriffe „Information“ und „automatique“) von Philippe Dreyfus, einem französischen Ingenieur eingeführt und als „Informatik“ ins Deutsche übernommen. Als junge Wissenschaft ist die Informatik mittlerweile in viele Bereiche der älteren Wissenschaften eingezogen und hat viele eigene Bereiche neu erschlossen. Die Informatik ist damit mittlerweile wesentlich mehr, als der anglo-amerikanische Begriff „Computer-Science“ vermuten lässt.Dieses Kapitel möchte einen (kurzen) Überblick über exemplarische Inhalte, Struktur und Geschichte der Informatik geben

Inhalt1. Motivation

2. Definition

3. Die Teilgebiete der Informatik

4. Die Geschichte der Informatik

5. Zusammenfassung des Kapitels

1.1 Motivation

Die Beherrschung eines Computers macht Spaßund gibt der informationssüchtigen Gesellschaft das Gefühl persönlicher Freiheit(so wie vor Jahren ein roter Sportwagen)

Die Beherrschung gibt Macht.Für das Funktionieren einer demokratischen Gesellschaft ist es wichtig, daß viele Menschen Computer verstehen und beherrschen.

Der Computer schafft und vernichtet Arbeitsplätze und ist eine Herausforderung für die Gesellschaft

Das Verstehen der Gesetzmäßigkeiten bei der Entwicklung von Computerprogrammen ist eine intellektuelle Herausforderung

Das Umsetzen dieses Verständnisses ist eine intellektuelle Genugtuung. Der Computer schafft neue Betätigungsfelder und Lebensinhalte Zunehmend viele Aufgabenstellungen der realen Welt sind ohne Einsatz von

Methoden und Werkzeugen der Informatik nicht mehr zu bewältigen Der professionelle Umgang mit Computer ist im Beruftsleben eine nackte

Notwendigkeit !

1.2 Was ist Informatik

Jedes Lehrbuch der Informatik gibt seine Definition der „Informatik“. Auch der Duden beschreibt die Informatik als „Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern“.Durch die Beschränkung auf den Aspekt der „Verarbeitung“ geht diese Definition meines Erachtens nicht weit genug. Ich werde daher in diesem Unterkapitel eine eigene Definition wagen. Die dabei verwendeten Aspekte werden exemplarisch verdeutlicht, wobei bewusst in Grenzbereiche der Informatik gegangen wird .

Was die Informatik wirklich ist, kann kein Lehrbuch erfassen.Sie werden - hoffentlich - am Ende Ihres Studiums eine sehr weitreichende Idee davon haben.

Inhalt1. Definition

2. Beispiele

1.2.1 Definition

Informatik

Die Wissenschaft, die sich mit dem(automatisierten)

von Information befasst

Erfassen

Transportieren

Speichern

Verarbeiten

Umsetzen

1.2.2 Wissenschaft

Informatik ist nicht die Wissenschaft vom Computer(sowenig, wie Astronomie die Wissenschaft vom Teleskop ist)

Informatik ist eine Wissenschaft… und keine Bastelecke für Software-Spieler

Aspekte der Informatik als „reine Lehre“ (verwandt mit der Mathematik) Naturwissenschaft: entdecken und beschreiben von „natürlichen“ Phänomenen Ingenieurwissenschaft - mit der typischen Vorgehensweise

Problemstellung Analyse Teillösungen Synthese Lösung

1.2.3 Information

Information ist die Bedeutung, die durch eine Nachricht übermittelt wird (nachrichtentechnische Definition)

Kapitel 2

Information ist eine elementare Kategorie Chemie: Stoffumwandlung Physik: Energieumwandlung Informatik: Informationsumwandlung

1.2.4 Erfassen Sensorik

Bildverarbeitung

300000

Datenmenge(Byte)

60000

(52,204,248) (33,75,125,190,251)

3000

100

1.2.5 Transportieren Telekommunikation

Telephonie

300 - 3400 Hz~5-25000 Hz

Abstrakte Datentypen (N. Wirth: Algorithmen und Datenstrukturen)

1.2.6 Speichern Datenrepräsentation

Einfache TypenAufzählungstypenIntegerRealBooleanChar...

{rot, gelb, grün}

[0,1,..,65535]

[3,4e-038,..3,4e038]

{TRUE, FALSE}

{ASC(0),..,ASC(255)}

Strukturierte TypenArrayRecordVarianten RecordMenge...

array [n..m] of Type

record Type 1: element 1 Type n: element nend

set of Type

Abstrakte TypenListenBinäre BäumeVielweg BäumeGraphen...

1.2.6 Speichern Datenrepräsentation

Objektrepräsentation

Assoziation

Vererbung

Aggregation

Verwendung

Instantiierung

Klassenname

AttributeOperationenEinschränkungen

(G. Booch: Objektorientierte Analyse und Design)

Teilprojekt

Projekt

Projektleiter

Mitarbeiter

n

Buchhaltung

Controlling

Personalwesen1

Class Teilprojekt: public Projekt { Projektleiter projektleiter; Mitarbeiter mitarbeiter[MAX_MITARBEITER];public: Teilprojekt (Projektleiter); ~Teilprojekt ();}

Teilprojekt::Teilprojekt(Projektleiter pl) { // some method-calls of Buchhaltung, Controlling, Personalwesen}

main { Teilprojekt1 = new Teilprojekt(Projektleiter1) // See Budget1 for buget details on Teilprojekt1 }

1.2.6 Speichern Datenrepräsentation

Objektrepräsentation (B.Stroustrup: The C++ Programming Language)

Teilprojekt

Projekt

Projektleiter

Mitarbeiter

n

Buchhaltung

Controlling

Personalwesen1

AssoziationVererbungAggregationVerwendungInstantiierung

n1

1.2.7 Verarbeiten Prozessmodelle

Petri-Netze (C.A.Petri: Kommunikation und Automaten))

1.2.7 Verarbeiten Prozessmodelle

Interaktionsdiagramme (G. Booch: Objektorientierte Analyse und Design)

R1 R2 R3 R4 R5

N2 N1

Axon

DendriteSynapsen

1.2.7 Verarbeiten KI-Ansätze

Neuronale Netze

ai=F(Wij*Oj ,ai)

a AktivierungszustandW VerbindungsgewichtungO AusgangswertF Aktivierungsfunktionf Ausgabefunktion

Oj

Oi=f(ai)Wij

1.2.8 Umsetzen Aktorik

Manipulatoren

Anzahl Freiheitsgrade

25 2 (1)9

1.2.9 Zusammenfassung

Modellierung der realen Welt Abbildung realer Objekte und deren Beziehungen (Strukturen) auf rechnerinterne

Objekte und Strukturen Reduktion von Redundanz Strukturierung von Information

Abbildung realer Aufgabenstellungen und Prozesse auf Rechnerprozesse

Umsetzung des Modells auf die reale Welt Abbildung von Rechnerprozessen auf reale Prozesse Abbildung von Datenstrukturen auf reale Strukturen

Erfassen Transportieren Speichern Verarbeiten Umsetzen

1.3 Die Teilgebiete der Informatik

Wie viele Wissenschaften, ist die Informatik kein homogenes Gebilde, sondern lässt sich anhand unterschiedlicher Kriterien in Teilgebiete strukturieren.Dieses Kapitel beschreibt die wohl geläufigste Einteilung der Informatik in drei, bzw. vier Teilbereiche.

Inhalte1. Technische Informatik

2. Praktische Informatik

3. Theoretische Informatik

4. ( Angewandte Informatik )

1.3.1 Technische Informatik

Konstruktion von Verarbeitungselementen Prozessoren, ...

Konstruktion von Speicherelementen Hauptspeicher, ...

Konstruktion von Kommunikationselementen Bussysteme Lokale Rechnernetze (LAN: Local Area Networks), Weitverkehrsnetze (WAN: Wide

Area Networks), ... Mobilfunknetze, Satellitenkommunikation, ...

Konstruktion von Peripherie Drucker, Scanner, .... Festplatten, Optische Platten, Diskettenlaufwerke, ...

...

1.3.2 Praktische Informatik

Umgang mit Programmiersprachen Programmierung Compilerbau ...

Entwicklung von Software Analysemethoden Designmethoden Realisierungsmethoden Testverfahren ...

Unterstützung der Softwareentwicklung Projektmanagement von DV-Projekten Qualitätsmanagement in DV-Projekten ...

...

1.3.3 Theoretische Informatik

Sprachen und Automaten Formale Sprachen Grammatiken Sprachdefinitionen

Berechenbarkeitstheorie Komplexitätstheorie ...

1.3.4 Angewandte Informatik

Anwendung in verwandten Wissenschaften Numerische oder stochastischer Verfahren in der Mathematik Simulationen in der Physik und der Chemie Bildverarbeitung in der Medizin Genanalyse in der Biologie Lehrprogramme für Natur-, Sozial- und Geisteswissenschaften ...

Anwendungen im täglichen Leben. Computerspiele, Multimediaanwendungen, Textverarbeitung, Tabellenkalkulation, Datenbanken, ... Steuerung von technischen Prozessen Web-Anwendungen ...

...

1.4 Die Geschichte der Informatik

Die Informatik ist eine junge Wissenschaft, hat aber, ähnlich wie andere Natur- und Ingenieurwissenschaften Wurzeln, die weit in die Menschheitsgeschichte hineinragen, Wie keine andere Wissenschaft wurde die Informatik jedoch von der Erfindung eines Gerätes, dem programmgesteuerten Rechner (später „Computer“) beeinflusst. Dieses Unterkapitel wird die Wurzel in der Menschheitsgeschichte und auch die Entwicklung des Rechners vorstellen.

Inhalt1. Information in der Geschichte

2. Automaten und Steuerungen

3. Erleichterung der Rechenarbeit

4. Pioniere der Informatik - Praktiker

5. Pioniere der Informatik - Theoretiker

6. Die Generationen

1.4.1 Information in der Geschichte

Erfassung durch Sinnesorgane Transport durch akustische, optische, chemische Signale Speicherung durch Gene oder neuronale Elemente Verarbeitung über neuronale Elemente Umsetzung direkt oder indirekt über Gliedmaße

Entwicklung von Wort,- Silben- und Buchstaben-schriften

1.4.2 Automaten und Steuerungen

ca. 100 v. Chr. Mechanismus von Antikytheraälteste erhaltene Zahnrad-Apparaturwahrscheinlich zur (analogen) Berechnung derBewegungen von Himmelskörpern

MittelalterMechanische Uhren mit Sonnen-, Mond- undPlanetenbewegungen und Figurenumläufe anKirchen und Rathäusern

17./18. Jhdt.Spieluhren, Schreib- und Schachspielautomaten

18./19. Jhdt.Fliehkraftregler für Dampfmaschinen, mechanischer Webstuhl mit Lochkartenbebändert (Jacquart, 1805)

1.4.3 Erleichterung der Rechenarbeit

Rechenbretter Seit dem Altertum China, Japan, Russland Addition/Subtraktion ähnlich schnell wie Taschenrechner

Lehre der Grundrechenarten Durch Zahlensystem schematisierbar Lehre an mittelalterlichen Universitäten Durch Rechenbücher weitere Verbreitung des Wissens

(z.B. Adam Riese 1492-1559) Rückführung der Multiplikation/Division auf

Addition/Subtraktion durch logarithmisches Rechnen mit Hilfe von Tabellen.

1.4.4 Mechanische Rechenmaschinen

Wilhelm Schickart (1592-1635) Maschine für die Grundrechenarten (1623)

Blaise Pascal (1623-1662) Gottfried Wilhelm von Leibniz (1646-1716)

Arithmetik des Dualsystems

Philipp Matthäus Hahn (1749-1790) Feinmechanische Rechenmaschinen

19./20. Jhdt: Sprossenradmaschine Hermann Hollerith

Lochkartenstanzer/Sortierer/Tabellierer

1.4.5 Pioniere der Informatik - Praktiker

Charles Babbage (1791-1871) Difference Engine (1812). Überprüfung von Logarithmentafeln.

Alle Merkmale eines programmierbaren Computers. Entwurf einer Analytical Engine (1836).

Wurde nie gebaut

Konrad Zuse (geb. 1910) Z1: mechanischer Rechner Z2 / Z3: Elektromechanischer Relaisrechner im Dualsystem mit

Lochkartensteuerung.Erster voll funktionstüchtiger Computer (1941)

Grundlegende Arbeiten zur Programmierung und algorithmischer Sprachen

Howard Eiken Mark I, II, III, IV (1944)

Dezimalrechnender Relaisrechner

1.4.6 Pioniere der Informatik - Theoretiker

Kurt Gödel Theoretische Aussagen zum Algorithmenbegriff:

Es gibt Aussagen die algorithmisch nicht entscheidbar sind (1931)

Alan M. Turing (1911-1954) Definition des Algorithmenbegriffes über eine hypothetische

Maschine(Turing-Maschine)

John von Neumann (1903-1957) Grundlegende Arbeiten über Computerarchitektur:

Speicherung der Daten und Programme auf dem gleichen Medium

Definition von Registern insb. Indexregister

1.4.7 Die Generationen

Generation Beispiel Technologie Speich./Geschw. Software

Vorgenerat. Z3 Elektro- 0,0002 MIPS Verdrahtet1941-1944 Mark1 mechanik

1.Generation ENIAC, Z22 Elektro- 0,02 MIPS Maschinen-1946 - 1958 UNIVAC, IBM650 röhren 1-2 KByte sprache

SIEMENS704

2. Generation IBM1400, AEG TR Transistoren 0,1 MIPS Assembler1959 - 1964 CDC6600 Kernspeicher 32 KByte FORTRAN

Siemens2002 Stapelbetrieb

3. Generation IBM370, PDP11 ICs 5 MIPS Hochsprachen1965 - 1980 Siemens7000, Halbleiter- 1-2 MBytes C, Pascal

Cray 1 speicher

4. Generation PC, Gray XMP Mikro- 50 MIPS Sprachen der 1981-1999Sperry1100, VAX prozessoren 8-32 MByte 4. GenerationIBM309x Optische Sp. Parallelisierung

Gegenwart Workstations Pentium, 100 MIPS NetzsoftwareHochleistungs- Power PC 1 GByte OO-Sprachen PCsNetze C++. JAVA

5. Generation supraleitende 1000 MIPSKeramiken viele GBytes

www.top500.org

1.5 Zusammenfassung des Kapitels

Die Informatik befasst sich mit der (automatisierten) Erfassung, dem Transport, der Speicherung, Verarbeitung und dem Umsetzen von Information

Die Informatik ist eine „naturwissenschaftliche Ingenieurswissenschaft“ Die Informatik gliedert sich in Technische, Praktische, Theoretische und

Angewandte Informatik Die Geschichte der Informatik beginnt im Altertum, besteht in Ihrer heutigen

Form aber erst seit ca. 1945. Zur Zeit befinden wir uns in der 4. Generation.