Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Gliederung 1 1. Wissenschaft Informatik 2. Modularisierung 3. Grundstrukturen 6. Kommunikation in

Grundkurs Informatik 11Kurshalbjahr 11/II

18.06.2013 1

Gliederung

Gliederung

1. Wissenschaft Informatik

2. Modularisierung

3. Grundstrukturen

6. Kommunikation in Netzen

4. Datenstrukturen

5. Algorithmen

Kurshalbjahr 11/I

Datei klasse11I.pptx muss sich im selben

Ordner befinden.


18.06.2013 2

Gliederung

5. Algorithmen5.1. Sortieralgorithmen5.2. Iteration und Rekursion

5.3. Aufwandsbetrachtungen

5.4. Berechenbarkeit

6. Kommunikation in Netzen6.1. Kommunikationsebenen6.2. Strukturen vernetzter Systeme (Topologie)

6.4. Datenübertragung in lokalen Netzen

6.5. Datenübertragung in Weitverkehrsnetzen

6.3. Adressierungen

6.6. Schichtenmodell (Referenzmodell)


18.06.2013 3

Algorithmen | Gliederung

5.2. Iteration und Rekursion

1 3 5 7 10 2512 23

12 3 25 10 7 1 5 23Sortiere(1,8)

5 3 1Sortiere(1,3)

10 25 12 23Sortiere(5,8)

1 5 10 25 23Sortiere(7,8)

Der Sortieralgorithmus Quick-Sort arbeitet nach dem Prinzip der Rückführung eines Problems auf ein vergleichbares Problem geringerer Größenordnung.

So wird im Beispiel die Sortierung einer Liste der Länge 8 auf die Sortierung zweier Listen der Länge 3 bzw. 4 zurückgeführt.

rekursiv arbeitendeAlgorithmen

Aufwände


18.06.2013 4

"Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich selbst zu definieren (rekursive Definition)."1

Rekursion am Beispiel der Potenzberechnung

entsprechendesStruktogramm

potenz ( b , e )

e = 0 ?

Rückgabe : 1 Rückgabe : b * potenz ( b , e-1 )

Abbruch Rekursiver Aufruf


5.2. Iteration und Rekursion


18.06.2013 5

p ( b , e )

e = 0 ?

1 b * p (b , e-1)


Potenzf ( n )

n = 0 oder n=1?

1 f (n-1) + f (n-2)

Fibonaccizahl

p(2,4)

2*p(2,3)

2*p(2,2)

2*p(2,1)

2*p(2,0)

16

8

4

2

1

f(4)

3 + 2

f(3)

2 + 1

f(1)

1

f(2)

1 + 1

f(1)

1

f(0)

1

f(2)

1 + 1

f(1)

1

f(0)

1

Lineare Rekursion Baumrekursion5.2. Iteration und Rekursion


18.06.2013 6

Zusammenfassung Algorithmen | Gliederung

Iteration 2 • Methode, sich der exakten Lösung eines Rechenproblems schrittweise anzunähern

• wiederholte Anwendung desselben Rechenverfahrens• Ergebnisse eines Iterationsschrittes werden als

Ausgangswerte des jeweils nächsten Schrittes genommen

• Umsetzung i.Allg. durch Schleifen

Rekursion 1 • Zurückführen einer Aufgabe auf eine einfachere Aufgabe der selben Klasse

• Rekursiver Aufruf (Definition einer Funktion durch sich selbst)

• Rekursionsabbruch (Abbruchbedingung)• Umsetzung i.Allg. durch ineinander geschachtelte

Funktionsaufrufe5.2. Iteration und Rekursion


18.06.2013

5.3 Aufwandsbetrachtungen Algorithmen | Gliederung

Komplexität

Zeitkomplexität Speicherplatzkomplexität

wird im Allgemeinen in Abhängigkeit von der Problemgröße n angegeben

• Turm von Hanoi: Anzahl n der Scheiben• Sortierungen: Anzahl n der Elemente• Berechnungen: Eingabegrößen n!, bn,• Rundreiseproblem: Anzahl n zu verbindender Städte

k

n

7


18.06.2013 8


Aufwands- bzw. Komplexitätsklassen

…O(nb) …O(bn)

linear (potenziell) exponentiell (permutativ)

O(n)

FakultätPotenz

O(n²)

Bubble-Sort

O(2n)

Turm von HanoiFibonacci(rekursiv)

O(n!)

Rundreise-problem

polynomialer Aufwand

überpolynomialer Aufwand

Testen 2


http://www.gf-webdesign.de/sortieralgorithmen/index.htm


18.06.2013 9




18.06.2013 10


Aufwandsklassen:• logarithmisch• linear• polynomial• überpolynomial

Bubble-Sort:• Aufwand A(n²)

Quick-Sort:• Aufwand A(n*log2n)



18.06.2013 11


5.4. BerechenbarkeitFrage, welche Probleme mit Hilfe einer Maschine (Computer) lösbar sind

• Statische Finitheit• Ausführbarkeit• Terminiertheit• Dynamische Finitheit• Determinismus• Determiniertheit• Allgemeingültigkeit

Voraussetzung: Algorithmus

"Intuitiv versteht man unter 'Berechenbarkeit' alles, was sich algorithmisch lösen lässt." 4

(endliche Beschreibung des Verfahrens )(bezüglich jedes Verfahrensschrittes)(Verfahren darf nur endlich viele Schritte benötigen )(Verfahren benötigt endlich viel Speicherplatz)(jeder Schritt eindeutig festgelegt)

(gleiche Eingaben liefern gleiche Ergebnisse) 34

(bezüglich vergleichbarer Probleme)


18.06.2013 12


Algorithmus bekannt?

vertretbare Abarbeitungszeit?

Problempraktisch

berechenbar

Problemtheoretisch

berechenbar

nachweisbar keinAlgorithmus vorhanden?

Problemnicht

berechenbar

Problemderzeitig nichtentscheidbar

JA

JA JA

NEIN

NEIN NEIN

Ackermannfunktion Halteproblem Satz von Fermatbis 1995 !

5.4. Berechenbarkeit


18.06.2013 13

Kommunikation (in Netzen) Kommunikation in Netzen | Algorithmen | Gliederung


18.06.2013 14

Kommunikation in Netzen | Algorithmen | Gliederung

6.1. KommunikationsebenenMensch Mensch

Nachricht

Daten Daten

Maschine Maschine

Repräsentation Interpretation

Sprache

verbal(Inhalt)

nonverbal(Interpretation)

face-to-face Kommunikation

Information Information

Mensch Mensch

computervermittelte Kommunikation CVK


18.06.2013 15 6.1. Kommunikationsebenen


computervermittelte Kommunikation (CVK)

• weitestgehendes Fehlen nonverbaler Kommunikation

• angenommene Anonymität

• asynchrone CVK• synchrone CVK

positive Effekte negative Effekte


18.06.2013 16

6.2. Strukturen vernetzter Systeme Kommunikation in Netzen | Algorithmen | Gliederung

Abbildungen aus WIKIPEDIA, Die freie Enzyklopädie: Topologie (Rechnernetz), 2010.URL: http://de.wikipedia.org/wiki/Topologie_(Rechnernetz) [Stand: 17.05.2010]

lineare Busstruktur

Ringstruktur

Baumstruktur

Sternstruktur

vermaschte Struktur


18.06.2013 17 6.2. Strukturen vernetzter Systeme


Ein Graph besteht aus einer Menge von Elementen (Knoten), die mittels Verbindungen (Kanten) miteinander verbunden sind. Ein geschlossener Zug aus Kanten und Knoten heißt Masche.

Mathematisches Modell Graph 5


18.06.2013 18

6.3. Adressierungen Kommunikation in Netzen | Algorithmen | Gliederung

a) MAC-Adressen6 (Media-Access-Control-Adresse)• 48 Bit lange Hardwareadresse (physische Adresse), • Bestandteil jeder Netzwerkkarte - wird in einem PROM

gespeichert und kann nicht verändert werden• Eindeutige Adressierung jeder Netzwerkkarte• Herstellerkennung (24 Bit) und Adapterkennung (24 Bit)• hexadezimale Schreibweise mit 6 Blöcken à 8 Bit• Beispiel: 08-00-20-AE-FD-7E

00001000.00000000 … 01111110• Verwendung in drahtgebundenen Netzen, in denen im

klassischen Ethernet gleichberechtigte Datenstationen angeschlossen werden7

• 248 = 2,81*1014 mögliche MAC-Adressen


18.06.2013 19 6.3. Adressierungen


b) IPv4-Adressen8 (Internet-Protocol-Adresse)• 32 Bit lange Adresse in Computernetzen, die auf dem

Internetprotokoll (IP) basieren (logische Adresse) • Trennung in Netzwerk- und Geräteteil („Hostteil“) durch

SubnetzmaskeAufbau von IP-Adressen (IPv4)

IP-Adresse 192.168.002. 100Netzkennung Hostkennung

Subnetzmaske 255.255.255. 000

• 232 = 4,3*109 mögliche IPv4-Adressen

c) IPv6-Adressen• 128 Bit lange Adresse (64 Bit Netzsegmentpräfix, 64 Bit

Interface Identifier)• 2128 = 3,4*1038 mögliche IPv6-Adressen


18.06.2013 20

6.4. Datenübertragung in lokalen Netzen Kommunikation in Netzen | Algorithmen | Gliederung

Größe in Byte

Beschreibung

6

Ziel-adresse

6

Quell-adresse

2

Typ-information

bis 1500

Nutz-daten

4

Prüf-summe

maximal 1566 Byte

ETHERNET-PROTOKOLL (Rahmen)

MAC-Adressen (Media-Access-Control-Adresse)

IEEE 802.3 für drahtgebundene lokale Netze (LAN)


18.06.2013 21 6.3. Adressierungen

6.5. Datenübertragung in Weitverkehrsnetzen Kommunikation in Netzen | Algorithmen | Gliederung

IP-PROTOKOLL (Paket)

internet protocol / zielorientiert

maximal 65535 Byte (theoretisch)

4

Quell-adresse

8

Headerlänge

Paketlänge

…

1

Time to life

bis 65515

Nutz-

daten

3

Folgeprot.

Prüfsumme

(Header)

4

Ziel-adresse

Größe in Byte

Beschreibung

bei Version IPv4 (32-Bit-Adressen)

IP-Adressen


18.06.2013 22 6.5. Datenübertragung in Weitverkehrsnetzen


4 Byte Prüfsumme

bis 1500 ByteNutzdaten

ETHERNET 14 Byte Header

TCP-PROTOKOLL (Segment)

transmission control protocol / verbindungsorientiert

4

Quitt.-nummer

2

Quellport

2

Zielport

bis 66540

Nutzdaten

4

Sequenz-

nummer

8

Headerlänge

Flags

Prüfsumme

(komplett)

Größe in Byte

Beschreibung

maximal 65560 Byte (theoretisch)

i.Allg. 1460 Byte

Adresskomponenten zur Zuordnung der entsprechenden Dienste

Beispiele: 20 FTP-Data

80 http

443 https

Nutzdaten maximal 1460 Byte

TCP 20 Byte Header

IP 20 Byte Header

Zusammenspiel der Protokolle




Aufbau von Routing-Tabellen

Netz ARouter BA

192.168.2.1

192.168.3.2

Netzkennung: 192.168.2.0

Netz B

Netzkennung: 192.168.3.0

Router B?

192.168.3.1

138.62.3.15 Zieladresse

Nächster Netzknoten (Router)

"Ausgang"

Netz- bzw. IP-Adresse

Netzmaske

138.62.3.25 255.255.255.0 192.168.3.1

192.168.2.110 255.255.255.0 192.168.2.1 192.168.2.1 1

Schnittstelle Hops

192.168.3.2 2

192.168.3.20 255.255.255.0 192.168.3.2 192.168.3.2 1

217.79.215.140 255.255.0.0 192.168.3.1 192.168.3.2 ???

Gateway bzw. Router



6.6. Schichtenmodell (Referenzmodell) Kommunikation in Netzen | Algorithmen | Gliederung

Modell zur Realisierung der offenen Kommunikation zwischen heterogenen Netzen

Prinzip: verschiedene Aufgaben werden in verschiedenen Schichten angeordnet

DoD: "Das Department of Defense (DoD) hatte 1980 mangels standardisierter Protokolle eine Protokollfamilie … ins Leben gerufen, die DoD-Protokolle. Das Architekturmodell der DoD-Protokolle … kennt nur vier Kommunikationsschichten."9

OSI: "Open Systems Interconnection (OSI) beschreibt international vereinbarte Standards, mit denen offene Systeme arbeiten, und definiert die Regeln für die Implementierung dieser Normen." Offene Kommunikationssysteme sollten den freizügigen Informationsaustausch auf der Basis gemeinsamer Protokollvereinbarungen und Schnittstellen erlauben.10


18.06.2013 25 6.6. Schichtenmodell (Referenzmodell)


packen(Package Assembling)

entpacken(Parsen)

übertragen

(1) Netzzugang

(2) Internet

(3) Transport

(4) Anwendung

DoD-Modell

(1) Bitübertragung

(2) Sicherung

(3) Vermittlung

(4) Transport

(5) Sitzung

(6) Darstellung

(7) AnwendungOSI-ModellEinheiten

Daten

Segmente

Pakete

Rahmen

Bits

Protokolle

TCP

IP

Ethernet

HTTPFTPPOP3SMTP


18.06.2013 26

Quellen1 Nach: WIKIPEDIA, Die freie Enzyklopädie: Rekursion,2011.

URL: http://de.wikipedia.org/wiki/Rekursion [Stand: 10.03.2011]

2 Nach: WIKIPEDIA, Die freie Enzyklopädie: Iteration,2011.URL: http://de.wikipedia.org/wiki/Iteration [Stand: 10.03.2011]

4 Prof.Dr.J.Rothe, H.Heine-Universität Düsseldorf.URL: http://ccc.cs.uni-duesseldorf.de/~rothe/INFO4/folien-kapitel-6.pdf [Stand: 04.04.2011]

Quellen | Kommunikation in Netzen | Algorithmen | Gliederung

3 Nach: WIKIPEDIA, Die freie Enzyklopädie: Algorithmus,2011.URL: http://de.wikipedia.org/wiki/Algorithmus [Stand: 31.03.2011]

5 Nach: WIKIPEDIA, Die freie Enzyklopädie: Netzwerk,2013.URL: http://de.wikipedia.org/wiki/Netzwerkstruktur [Stand: 29.05.2013]

6 Nach: ITWissen, Das große Online-Lexikon für Informationstechnologie: MAC-Adresse.URL: http://www.itwissen.info/definition/lexikon/MAC-Adresse-MAC-address.html [Stand: 29.05.2013]

7 Nach: ITWissen, Das große Online-Lexikon für Informationstechnologie: Ethernet. URL: http://www.itwissen.info/definition/lexikon/Ethernet-Ethernet.html [Stand 29.05.2013]

8 Nach: WIKIPEDIA, Die freie Enzyklopädie: IP-Adresse,2013.URL: http://de.wikipedia.org/wiki/IP-Adresse [Stand: 29.05.2013]

9 ITWissen, Das große Online-Lexikon für Informationstechnologie: DoD-Protokoll.URL: http://www.itwissen.info/definition/lexikon/DoD-Protokoll-DoD-protocol.html [Stand 17.06.2013]

10 Nach: ITWissen, Das große Online-Lexikon für Informationstechnologie: OSI (open systems interconnection)URL: http://www.itwissen.info/definition/lexikon/open-systems-interconnection-OSI-Offene-Kommunikation.html [Stand 12.06.2011]

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

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

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

http://ccc.cs.uni-duesseldorf.de/~rothe/INFO4/folien-kapitel-6.pdf



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

http://ccc.cs.uni-duesseldorf.de/~rothe/INFO4/folien-kapitel-6.pdf

http://www.itwissen.info/definition/lexikon/MAC-Adresse-MAC-address.html

http://www.itwissen.info/definition/lexikon/MAC-Adresse-MAC-address.html

http://www.itwissen.info/definition/lexikon/Ethernet-Ethernet.html

http://www.itwissen.info/definition/lexikon/DoD-Protokoll-DoD-protocol.html

http://www.itwissen.info/definition/lexikon/open-systems-interconnection-OSI-Offene-Kommunikation.html


18.06.2013 27 Jahrgangsstufe 12

Quellen | Kommunikation in Netzen | Algorithmen | Gliederung

7. Sicherheit von Informationen

8. Datenbanken

9. Computergrafik

Kurshalbjahr 12/I.

Kurshalbjahr 12/II

Documents

Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Gliederung 1 1. Wissenschaft Informatik 2. Modularisierung 3. Grundstrukturen 6. Kommunikation in