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.
Grundkurs Informatik 11Kurshalbjahr 11/II
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)
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Algorithmen | Gliederung
5.2. Iteration und Rekursion
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 5
p ( b , e )
e = 0 ?
1 b * p (b , e-1)
Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 8
Algorithmen | Gliederung
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
5.3. Aufwandsbetrachtungen
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 9
Algorithmen | Gliederung
5.3. Aufwandsbetrachtungen
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 10
Algorithmen | Gliederung
Aufwandsklassen:• logarithmisch• linear• polynomial• überpolynomial
Bubble-Sort:• Aufwand A(n²)
Quick-Sort:• Aufwand A(n*log2n)
5.3. Aufwandsbetrachtungen
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 11
Algorithmen | Gliederung
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)
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 12
Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 13
Kommunikation (in Netzen) Kommunikation in Netzen | Algorithmen | Gliederung
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 15 6.1. Kommunikationsebenen
Kommunikation in Netzen | Algorithmen | Gliederung
computervermittelte Kommunikation (CVK)
• weitestgehendes Fehlen nonverbaler Kommunikation
• angenommene Anonymität
• asynchrone CVK• synchrone CVK
positive Effekte negative Effekte
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 17 6.2. Strukturen vernetzter Systeme
Kommunikation in Netzen | Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 19 6.3. Adressierungen
Kommunikation in Netzen | Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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)
Grundkurs Informatik 11Kurshalbjahr 11/II
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 22 6.5. Datenübertragung in Weitverkehrsnetzen
Kommunikation in Netzen | Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 23 6.5. Datenübertragung in Weitverkehrsnetzen
Kommunikation in Netzen | Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 24 6.5. Datenübertragung in Weitverkehrsnetzen
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
Grundkurs Informatik 11Kurshalbjahr 11/II
18.06.2013 25 6.6. Schichtenmodell (Referenzmodell)
Kommunikation in Netzen | Algorithmen | Gliederung
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
Grundkurs Informatik 11Kurshalbjahr 11/II
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]
Grundkurs Informatik 11Kurshalbjahr 11/II
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