Grundkurs Informatik 11 (D.Wolff) Kurshalbjahr 11/I 19.02.2013 Gliederung 1. Wissenschaft Informatik 2. Modularisierung 3. Grundstrukturen 6. Kommunikation

Grundkurs Informatik 11 (D.Wolff)Kurshalbjahr 11/I

19.02.2013 1

Gliederung

1. Wissenschaft Informatik

2. Modularisierung

3. Grundstrukturen

6. Kommunikation in Netzen

4. Datenstrukturen

Gliederung

5. iterative & rek. Algorithmen


19.02.2013 2

1. Wissenschaft Informatik1.1. Informatik, Information, Daten

1.2. Teilgebiete der Informatik

2. Modularisierung2.1. Grundprinzip

2.2. Parameterfreie Module

2.3. Module mit Parametern

2.4. Zusammenfassung

2.5. Funktionen

Gliederung


19.02.2013 3

Gliederung

3. Grundstrukturen

6. Kommunikation in Netzen

4. Datenstrukturen4.1. Grundlagen

4.2. Array (Feld)

4.3. Record (Verbund)


5. iterative & rek. Algorithmen

4.5. Höhere Datentypen


19.02.2013 4

1.1. Informatik – Information - Daten

Wissenschaft Informatik | Gliederung


"computer science

Informatik ist ein Kunstwort aus Information und Automatik. Es ist die wissenschaftliche Lehre von der Informationsverarbeitung mit Hilfe von Computern. …"1

1 ITWissen, Das große Online-Lexikon für Informationstechnologie: Informatik.URL: http://www.itwissen.info/definition/lexikon/Informatik-computer-science.html [Stand: 03.09.2012]

http://www.itwissen.info/definition/lexikon/definition/lexikon/Information-information.html

http://www.itwissen.info/definition/lexikon/definition/lexikon/Computer-computer.html

http://www.itwissen.info/definition/lexikon/Informatik-computer-science.html


19.02.2013 5


Automatische Informationsverarbeitung

InformationDatenInterpretation

Repräsentation

Analoge DatenDigitale Daten

im Allgemeinen alsbinär digitale Daten



19.02.2013 6

Positionssysteme


Allgemeine Darstellung zn*bn+…+z2*b2+z1*b1+z0*b0

Dezimalsystem: Basis b = 1010 Ziffern (0, 1, 2, … , 9)

Dualsystem: Basis b = 22 Ziffern (0, 1)

Hexadezimalsystem: Basis b = 1616 Ziffern (0, 1, 2, … , 9, A, B, C, D, E, F)

Beispiel:42dez = 101010dual = 2Ahex

4*101+2*100 1*25+0*24+1*23+0*22+1*21+0*20 2*161+10*160



19.02.2013 7

1.2. Teilgebiete der Informatik



1.2.1 Theoretische Informatik

Formale Methoden und mathematische Modelle fürFormulierung und Untersuchung von Algorithmen

Rechnerkonstruktion

Berechenbarkeit (Bsp: Halteproblem)Komplexität und Effizienz (Bsp: Potenzberechnung)

QUELLE: http://de.wikipedia.org/wiki/Bild:Architektur-der-informatik.png [20.09.2007]

http://de.wikipedia.org/wiki/Bild:Architektur-der-informatik.png

http://de.wikipedia.org/wiki/Bild:Architektur-der-informatik.png


19.02.2013 8 1. Wissenschaft Informatik


1.2.2. Technische Informatik

Funktioneller Aufbau von Computern und peripheren Geräten

Prozessor (Rechen- und Steuerwerk) Interner Speicher/Arbeitsspeicher (ROM)Ein- und Ausgabegeräte (Tastatur, Maus, Monitor,

Drucker, Laufwerke/externe Speicher)Bussysteme

Logischer Aufbau von Geräten und Schaltungen (Hardware)

Von-Neumann-RechnerLogische Grundschaltungen




Logischer Aufbau von Geräten und Schaltungen (Hardware)

Von-Neumann-RechnerLogische Grundschaltungen

E1 E2 Ergebnis Übertrag

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

Binäre AdditionDezimal Binär

128 64 32 16 8 4 2 1

S1 1 2 3 0 1 1 1 1 0 1 1

S2 8 9 0 1 0 1 1 0 0 1

Ü 1 1 1 1 1 1 1 1

Erg 2 1 2 1 1 0 1 0 1 0 0

Dezimal Binär128 64 32 16 8 4 2 1

S1 1 2 3 0 1 1 1 1 0 1 1

S2 8 9 0 1 0 1 1 0 0 1

Ü 1 1

Erg 2 1 2


19.02.2013 10

Logische Grundschaltungen



&E1

E2

A

E1 E2 A

0 0 10 1 11 0 11 1 04 Transistoren

NAND - Glied

&E1

E2

A

E1 E2 A

0 0 00 1 01 0 01 1 18(6) Transistoren

AND - Glied

³1E1

E2

A

E1 E2 A

0 0 00 1 11 0 11 1 18(6) Transistoren

OR - Glied

³1E1

E2

A

E1 E2 A

0 0 10 1 01 0 01 1 04 Transistoren

NOR - Glied

&E A

1E A

E A

0 11 02 Transistoren

NOT - Glied

E1 E2 Erg Ü

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1




&E1

E2

A

E1 E2 A

0 0 00 1 01 0 01 1 18(6) Transistoren

AND - GliedE1 E2 Erg Ü

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

E1 E2 AND NAND OR NOR … ???

0 0 0 1 0 1 … 0

0 1 0 1 1 0 … 1

1 0 0 1 1 0 … 1

1 1 1 0 1 0 … 0

Bei zwei Eingängen sind insgesamt 16 logische Schaltungen möglich!

Additions-ergebnis:

XOR


19.02.2013 12

Binäre Addition



E1 E2 Ergebnis Übertrag

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

=1E1

&E2

A2 (Übertrag)

AND

XOR

A1 (Ergebnis)

Umsetzung über logische Grundschaltungen(Halbadder)

VolladderAddition zwei einstelliger (…!) Binärzahlenmit einlaufendem Übertrag

WIKIPEDIA, Die freie Enzyklopädie: Volladdierer,2010.URL: http://de.wikipedia.org/wiki/Volladder [Stand: 09.09.2010]

Die Abbildung wurde an der angegebenen Stelle unter der Lizenz„Creative Commons Namensnennung-Weitergabe unter gleichen Bedingungen Deutschland“in Version 2.0 (abgekürzt „CC-by-sa 2.0/de“) veröffentlicht. (siehe Seite Lizenzbedingungen dieser Präsentation)

http://de.wikipedia.org/wiki/Volladder




1.2.3. Praktische Informatik

Lösung von konkreten Problemen der Informatik, wie Entwicklung von

BetriebssystemenTreibern für periphere GeräteProgrammiersprachen und entsprechenden CompilernSoftware inclusive der Implementierung (Programmierung)

1.2.4. Angewandte Informatik

beschäftigt sich mit Anwendungen von Methoden der Kerninformatik in anderen Wissenschafts- und Gesellschafts- bereichen wie Wirtschafts-, Bio-, Chemo-, Medien- oder Geoinformatik sowie Computerlinguistik


19.02.2013 14

2.1. Grundprinzip

2. Modularisierung

Modularisierung | Wissenschaft Informatik | Gliederung

"Modularisierung ist ein allgemeines Prinzip aus den Ingenieurwissenschaften und dient insbesondere der Erzeugung überschaubarer Systeme, deren Komponen-ten unter Umständen auch in anderen Systemen wieder verwendet werden können."1

1) Hartmut Härtl:SoftwareEngineering,2006.URL: http://oszhdl.be.schule.de/gymnasium/faecher/informatik/softwareprojekte/prinzipien.htm [Stand: 04.10.2007]

Problem / Aufgabenstellung

Teilproblem 1 Teilproblem 2 Teilproblem n…

http://oszhdl.be.schule.de/gymnasium/faecher/informatik/softwareprojekte/prinzipien.htm


19.02.2013 15 2. Modularisierung


"Auf die Softwareentwicklung angewandt fordert dieses Prinzip die Aufteilung des Systems in überschaubare Teile, mit klar definierten Schnittstellen."1

1) Hartmut Härtl:SoftwareEngineering,2006.URL: http://oszhdl.be.schule.de/gymnasium/faecher/informatik/softwareprojekte/prinzipien.htm [Stand: 04.10.2007]

Modul 1INTERFACE

IMPLEMEN-TATION

Modul 2INTERFACE

IMPLEMEN-TATION

Modul 3INTERFACE

IMPLEMEN-TATION

Schnittstelle Interface

http://oszhdl.be.schule.de/gymnasium/faecher/informatik/softwareprojekte/prinzipien.htm


19.02.2013 16

2.2. Parameterfreie Module

2. Modularisierung


procedure TFStart.Bu… begin

eingabe; …

ausgabeend.

procedure TFStart.eingabe;begin z1 := StrToInt ( EdZahl1.Text );

z2 := StrToInt ( EdZahl2.Text ) end.

…

procedure TFStart.ausgabebegin EdErgebnis.Text := IntToStr ( erg )end.

Implementationvar z1 , z2 , erg : integer; Globale Variable

(bezüglich dieser Unit!)

Aufruf der Module


19.02.2013 17

2.3. Module mit Parametern

2. Modularisierung


procedure TFStart.Bu… Var z1 , z2 : integer;begin

…eingabe(z1 , EDZahl1);eingabe(z2 , EDZahl2)

…end.

procedure eingabe ( var was:integer ; woher:TEdit )begin was := StrToInt ( woher.Text );end.

Aufruf der Module

Umsetzung der Module

Um eine Kommunikation der Moduleuntereinander zu ermöglichen, müssen diese Schnittstellen besitzen, damit sie Daten austauschen können.

Dies wird über Parameter realisiert!

Damit können die Module gleichzeitig vom Programm unabhängig werden.





19.02.2013 19


2. Modularisierung


Module bieten eine Kapselung (encapsulation) durch die Trennung von Schnittstelle (Interface) und Implementierung:

Die Schnittstelle eines Moduls definiert die Datenelemente, dieals Eingabe und Ergebnis der Verarbeitung durch das Modul benötigt werden. Die Implementierung enthält den tatsächlichen Programmcode.

ParameterlisteINTERFACE

IMPLEMEN-TIERUNG

lokale VariableProgrammcode (Quelltext) des Moduls

Variablen-parameter

Wert-parameter

http://de.wikipedia.org/wiki/Kapselung

http://de.wikipedia.org/wiki/Interface

http://de.wikipedia.org/wiki/Implementierung




Keine Wiederverwendbarkeit!

Wiederverwendbarkeit möglich!

Modularisierung

ohne Parameter mit Parameter

programmabhängigeModule

reine Programm-

strukturierung

programmunabhängigeModule

Programm-strukturierungund Kapselung


19.02.2013 21

2.5. Funktionen

2. Modularisierung


function name ( … ) : Ergebnistyp

……result := Ergebniswert

INTERFACE

IMPLEMENTATION

Umsetzung als Funktion

Häufig liefern Module genau einen Ergebniswert zurück und entsprechen somit dem aus der Mathematik bekannten Funktionsbegriff y = f ( a , b , … ). Derartige Module lassen sich in DELPHI als Prozedur mit einem Variablenparameter oder auch als Funktion mit reiner Wertparameterliste umsetzen.

Aufruf: ergebnisvariable := name ( … );




function eingabe (woher:TEdit) : integer;var wert : integer;begin wert := StrToInt ( woher.Text );

result := wertend.

function summe(wert1,wert2 : integer) : integer; var summe : integer;begin summe := wert1 + wert2;

result := summeend.

procedure ausgabe(wert:integer ; wohin:TEdit);begin wohin.Text := IntToStr ( wert )end.

Aufruf der Module:

Beispiel für den Einsatz von Funktionen

procedure TFStart.Bu… var z1,z2,erg : integer;begin

z1 := eingabe(EdZahl1);z2 := eingabe(EdZahl2);

erg := summe(z1,z2);ausgabe(erg,EdErgebnis)

end.


19.02.2013 23

3. Grundstrukturen

3. Grundstrukturen

Grundstrukturen | Modularisierung | Wissenschaft Informatik | Gliederung

SEQUENZ

ALTERNATIVE (BEDINGUNG)zweiseitige Alternativeeinseitige Alternativemehrseitige Alternative

ZYKLUS (SCHLEIFE)

WiederholzyklusSolangezyklus

Zählzyklus Genaueres in „Grundstrukturen.pptx“(Dateien müssen sich im selben Ordner befinden!)


19.02.2013 24

4.1. Grundlagen

4. Datenstrukturen

Datenstrukturen | Grundstrukturen | Modularisierung | Wissenschaft Informatik | Gliederung

Zur Umsetzung gefundener Algorithmen benötigt man neben der Algorithmenstruktur auch eine dem Problem entsprechende Datenstruktur (Von uns bisher als Variablentyp bezeichnet!).

"In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden."1

1) WIKIPEDIA,Die freie Enzyklopädie:Datenstruktur,2007.URL: http://de.wikipedia.org/wiki/Datenstruktur [Stand: 01.01.2008]

Dabei lassen sich viele Probleme mit den elementaren Datentypen (integer, real, char, boolean, …) nicht bzw. nicht effektiv lösen.

PROBLEMDATENSTRUKTUR

ALGORITHMENSTRUKTUR


19.02.2013 25

4.2. Array/ Feld

4. Datenstrukturen


In einem Array lassen sich mehrere Werte identischer Typen (Zahlen, Zeichen, logische Werte,…) speichern. Der Zugriff auf die einzelnen Werte wird über Indizes realisiert. Beispiel: mehrmaliges Würfeln, bei dem die Anzahlen der gewürfelten

Augenzahlen gezählt werden

über elementare Datentypen sechs Variablen eins .. sechs

über Array eine Variable feld

eins zwei drei vier fuenf sechs

feld

feld[3]feld[1] feld[2] feld[6]feld[4] feld[5]

TYPE TWuerfel = ARRAY [1..6] OF integer; VAR feld = TWuerfel;


19.02.2013 26 4. Datenstrukturen


Arrays lassen sich auch über mehrere Dimensionen vereinbaren.

"Im eindimensionalen Fall wird das Array häufig als Vektor und im zweidimensionalen Fall als Tabelle oder Matrix bezeichnet. Arrays sind aber keinesfalls nur auf zwei Dimensionen beschränkt, sondern werden beliebig mehrdimensional verwendet. "1

1) WIKIPEDIA,Die freie Enzyklopädie:Datenstruktur,2007.URL: http://de.wikipedia.org/wiki/Datenstruktur [Stand: 01.01.2008]

Beispiel: zweidimensionales Array für Texte

TYPE TTabelle = ARRAY [1..3,1..10] OF string; VAR feld = TTabelle;

feld feld[3,2]

… … …

feld[2,1]1

1

2

2

10

3


19.02.2013 27

Strukturierte Komponente StringGrid

4. Datenstrukturen


Um eine effektive Ausgabe der in strukturierten Variablen abgelegten Daten zu ermöglichen, bietet DELPHI die strukturierte Komponente StringGrid in der Komponentenpalette Zusätzlich an.

Ausgewählte Attribute:

ColCountSpaltenzahl (gesamt)

DefaultColWidthSpaltenbreite (Standard)

DefaultRowHeigthZeilenhöhe (Standard)

FixedColsAnzahl der "Kopfspalten"

FixedRowsAnzahl der "Kopfzeilen"

RowCountZeilenzahl (gesamt)


19.02.2013 28

4.3. Record (Verbund)

4. Datenstrukturen


In einem Record lassen sich im Unterschied zum Array mehrere Werte verschiedener Typen (Zahlen, Zeichen, logische Werte,…) speichern. Der Zugriff auf die einzelnen Werte wird über die Komponentennamen des Records realisiert.

Beispiel: Personendaten

Nachname Vorname Groesse verheiratet …Komponenten-name

Müller Max 1,78 nein …Inhalt(Beispiel)

string string real boolean …Komponenten-typ




Die Typ- und Variablenvereinbarung hätte im genannten Beispiel folgendes Aussehen:

TYPE TPerson = RECORDnachname : string;vorname : string;groesse : real;verheiratet : boolean;

END;

DELPHI (Personendaten):

VAR person : TPerson;

Der Zugriff auf die Komponenten erfolgt durch Punktnotation:

Beispiel: person.vorname := 'Max';


19.02.2013 30


4. Datenstrukturen


Datentypen

Dynamische Typen müssen nicht vor der Laufzeit festliegen

Statische Typen müssen vor der Laufzeit festliegen

Einfache Typen Strukturierte Typen

Kontinuier-liche Typen (REAL)

DiskreteTypen (BYTE, INTEGER,CHAR,BOOLEAN)

Feldtyp (ARRAY)IdentischeKomponenten-typen

Verbundtyp (RECORD)VerschiedeneKomponenten-typen

DIESE ÜBERSICHT IST NICHT VOLLSTÄNDIG!


19.02.2013 31

4.5. Höhere Datentypen

4. Datenstrukturen


Dynamische Typen Datenteil Adressteil

(Zeigerteil)

R E C O R DListen

Beispiel: Datenlisten, Aufbau ganzer Zahlen

Bäume

Beispiel: Stammbäume,Hierachien

Anker

NIL




Schlangen

enqueue

Prinzip: FiFo (first in - first out)

dequeue

Beispiel: Warteschlangen

Stapel push pop

Prinzip: LiFo (last in - first out)

Beispiel: Kellerspeicher (Stack)


19.02.2013 33 3. Grundstrukturen

Grundstrukturen | Modularisierung | Wissenschaft Informatik | Gliederung

ENDE


19.02.2013 34 ENDE


Lizenzbedingungen„Creative Commons Namensnennung-Weitergabe unter gleichen Bedingungen Deutschland“Den rechtsverbindlichen Lizenzvertrag finden Sie unterhttp://creativecommons.org/licenses/by-sa/2.0/de/legalcode

Zusammenfassung des Vertrags in allgemeinverständlicher Sprache ohne juristische Wirkung.Es ist gestattet: das Werk zu vervielfältigen, zu verbreiten und öffentlich zugänglich zu machen sowie Abwandlungen und Bearbeitungen des Werkes anzufertigen, Namensnennung: Sie müssen den Urheber bzw. den Rechteinhaber in der von ihm festgelegten Weise, die URI

(z. B. die Internetadresse dieser Seite) sowie den Titel des Werkes und bei einer Abwandlung einen Hinweis darauf angeben.

Weitergabe unter gleichen Bedingungen: Wenn Sie das lizenzierte Werk bearbeiten, abwandeln oder als Vorlage für ein neues Werk verwenden, dürfen Sie die neu entstandenen Werke nur unter dieser oder einer zu dieser kompatiblen Lizenz nutzen und weiterverbreiten.

Lizenzangabe: Sie müssen anderen alle Lizenzbedingungen mitteilen, die für dieses Werk gelten. Am einfachsten ist es, wenn Sie dazu einen Link auf den Lizenzvertrag (siehe oben) einbinden.1)

1) WIKIPEDIA, Die freie Enzyklopädie: Datei:Volladdierer Aufbau DIN40900.svg, 2009.URL: http://de.wikipedia.org/w/index.php?title=Datei:Volladdierer_Aufbau_DIN40900.svg&filetimestamp=20061107192017[Stand: 09.09.2010]

Zurück zum Volladder

http://creativecommons.org/licenses/by-sa/2.0/de/legalcode

http://de.wikipedia.org/w/index.php?title=Datei:Volladdierer_Aufbau_DIN40900.svg&filetimestamp=20061107192017

Documents

Grundkurs Informatik 11 (D.Wolff) Kurshalbjahr 11/I 19.02.2013 Gliederung 1. Wissenschaft Informatik 2. Modularisierung 3. Grundstrukturen 6. Kommunikation