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

  • View
    107

  • Download
    2

Embed Size (px)

Text of Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Gliederung 1 1. Wissenschaft Informatik 2....

  • Folie 1
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Gliederung 1 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.
  • Folie 2
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Gliederung 2 5. Algorithmen 5.1. Sortieralgorithmen 5.2. Iteration und Rekursion 5.3. Aufwandsbetrachtungen 5.4. Berechenbarkeit 6. Kommunikation in Netzen 6.1. Kommunikationsebenen 6.2. Strukturen vernetzter Systeme (Topologie) 6.4. Datenbertragung in lokalen Netzen 6.5. Datenbertragung in Weitverkehrsnetzen 6.3. Adressierungen 6.6. Schichtenmodell (Referenzmodell)
  • Folie 3
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 5.2. Iteration und Rekursion 3 135 710251223 123251071523 Sortiere(1,8) 531 Sortiere(1,3) 10251223 Sortiere(5,8) 15102523 Sortiere(7,8) Der Sortieralgorithmus Quick-Sort arbeitet nach dem Prinzip der Rckfhrung eines Problems auf ein vergleichbares Problem geringerer Grenordnung. So wird im Beispiel die Sortierung einer Liste der Lnge 8 auf die Sortierung zweier Listen der Lnge 3 bzw. 4 zurckgefhrt. rekursiv arbeitende Algorithmen Aufwnde
  • Folie 4
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 4 "Als Rekursion (lat. recurrere zurcklaufen) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich selbst zu definieren (rekursive Definition)." 1 1 Rekursion am Beispiel der Potenzberechnung entsprechendes Struktogramm potenz ( b, e ) e = 0 ? Rckgabe : 1Rckgabe : b * potenz ( b, e-1 ) AbbruchRekursiver Aufruf Algorithmen | GliederungAlgorithmen Gliederung 5.2. Iteration und Rekursion
  • Folie 5
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 5 p ( b, e ) e = 0 ? 1 b * p (b, e-1) Algorithmen | GliederungAlgorithmen Gliederung Potenz f ( 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 RekursionBaumrekursion 5.2. Iteration und Rekursion
  • Folie 6
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Zusammenfassung 6 Algorithmen | GliederungAlgorithmen Gliederung Iteration 2 2 Methode, sich der exakten Lsung eines Rechenproblems schrittweise anzunhern wiederholte Anwendung desselben Rechenverfahrens Ergebnisse eines Iterationsschrittes werden als Ausgangswerte des jeweils nchsten Schrittes genommen Umsetzung i.Allg. durch Schleifen Rekursion 1 1 Zurckfhren 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 Funktionsaufrufe 5.2. Iteration und Rekursion
  • Folie 7
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 5.3 Aufwandsbetrachtungen Algorithmen | GliederungAlgorithmen Gliederung Komplexitt ZeitkomplexittSpeicherplatzkomplexitt wird im Allgemeinen in Abhngigkeit von der Problemgre n angegeben Turm von Hanoi: Anzahl n der Scheiben Sortierungen: Anzahl n der Elemente Berechnungen: Eingabegren n!, b n, Rundreiseproblem: Anzahl n zu verbindender Stdte 7
  • Folie 8
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 8 Aufwands- bzw. Komplexittsklassen O(n b )O(b n ) linear (potenziell) exponentiell (permutativ) O(n) Fakultt Potenz O(n) Bubble-Sort O(2 n ) Turm von Hanoi Fibonacci (rekursiv) O(n!) Rundreise- problem polynomialer Aufwand berpolynomialer Aufwand Testen 2 5.3. Aufwandsbetrachtungen
  • Folie 9
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 9 5.3. Aufwandsbetrachtungen
  • Folie 10
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 10 Aufwandsklassen: logarithmisch linear polynomial berpolynomial Bubble-Sort: Aufwand A(n) Quick-Sort: Aufwand A(n*log 2 n) 5.3. Aufwandsbetrachtungen
  • Folie 11
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 5.4. Berechenbarkeit 11 Frage, welche Probleme mit Hilfe einer Maschine (Computer) lsbar sind Statische Finitheit Ausfhrbarkeit Terminiertheit Dynamische Finitheit Determinismus Determiniertheit Allgemeingltigkeit Voraussetzung: Algorithmus "Intuitiv versteht man unter 'Berechenbarkeit' alles, was sich algorithmisch lsen lsst." 4 4 (endliche Beschreibung des Verfahrens ) (bezglich jedes Verfahrensschrittes) (Verfahren darf nur endlich viele Schritte bentigen ) (Verfahren bentigt endlich viel Speicherplatz) (jeder Schritt eindeutig festgelegt) (gleiche Eingaben liefern gleiche Ergebnisse) 3 3 4 (bezglich vergleichbarer Probleme)
  • Folie 12
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Algorithmen | GliederungAlgorithmen Gliederung 12 Algorithmus bekannt? vertretbare Abarbeitungszeit? Problem praktisch berechenbar Problem theoretisch berechenbar nachweisbar kein Algorithmus vorhanden? Problem nicht berechenbar Problem derzeitig nicht entscheidbar JA NEIN AckermannfunktionHalteproblemSatz von Fermat bis 1995 ! 5.4. Berechenbarkeit
  • Folie 13
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 Kommunikation (in Netzen) 13 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung
  • Folie 14
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 14 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung 6.1. Kommunikationsebenen Mensch Nachricht Daten Maschine ReprsentationInterpretation Sprache verbal (Inhalt) nonverbal (Interpretation) face-to-face Kommunikation Information Mensch computervermittelte Kommunikation CVK
  • Folie 15
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.1. Kommunikationsebenen 15 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung computervermittelte Kommunikation (CVK) weitestgehendes Fehlen nonverbaler Kommunikation angenommene Anonymitt asynchrone CVK synchrone CVK positive Effekte negative Effekte
  • Folie 16
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.2. Strukturen vernetzter Systeme 16 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung Abbildungen aus WIKIPEDIA, Die freie Enzyklopdie: Topologie (Rechnernetz), 2010. URL: http://de.wikipedia.org/wiki/Topologie_(Rechnernetz) [Stand: 17.05.2010] lineare Busstruktur Ringstruktur Baumstruktur Sternstruktur vermaschte Struktur
  • Folie 17
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.2. Strukturen vernetzter Systeme 17 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung Ein Graph besteht aus einer Menge von Elementen (Knoten), die mittels Verbindungen (Kanten) miteinander verbunden sind. Ein geschlossener Zug aus Kanten und Knoten heit Masche. Mathematisches Modell Graph 5 5
  • Folie 18
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.3. Adressierungen 18 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung a) MAC-Adressen 6 (Media-Access-Control-Adresse) 6 48 Bit lange Hardwareadresse (physische Adresse), Bestandteil jeder Netzwerkkarte - wird in einem PROM gespeichert und kann nicht verndert werden Eindeutige Adressierung jeder Netzwerkkarte Herstellerkennung (24 Bit) und Adapterkennung (24 Bit) hexadezimale Schreibweise mit 6 Blcken 8 Bit Beispiel: 08-00-20-AE-FD-7E 00001000.00000000 01111110 Verwendung in drahtgebundenen Netzen, in denen im klassischen Ethernet gleichberechtigte Datenstationen angeschlossen werden 7 7 2 48 = 2,81*10 14 mgliche MAC-Adressen
  • Folie 19
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.3. Adressierungen 19 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung b) IPv4-Adressen 8 (Internet-Protocol-Adresse) 8 32 Bit lange Adresse in Computernetzen, die auf dem Internetprotokoll (IP) basieren (logische Adresse) Trennung in Netzwerk- und Gerteteil (Hostteil) durch Subnetzmaske Aufbau von IP-Adressen (IPv4) IP-Adresse 192.168.002. 100 NetzkennungHostkennung Subnetzmaske 255.255.255. 000 2 32 = 4,3*10 9 mgliche IPv4-Adressen c) IPv6-Adressen 128 Bit lange Adresse (64 Bit Netzsegmentprfix, 64 Bit Interface Identifier) 2 128 = 3,4*10 38 mgliche IPv6-Adressen
  • Folie 20
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.4. Datenbertragung in lokalen Netzen 20 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung Gre in Byte Beschreibung 6 Ziel- adresse 6 Quell- adresse 2 Typ- information bis 1500 Nutz- daten 4 Prf- summe maximal 1566 Byte ETHERNET-PROTOKOLL (Rahmen) MAC-Adressen (Media-Access-Control-Adresse) IEEE 802.3 fr drahtgebundene lokale Netze (LAN)
  • Folie 21
  • Grundkurs Informatik 11 Kurshalbjahr 11/II 18.06.2013 6.3. Adressierungen 6.5. Datenbertragung in Weitverkehrsnetzen 21 Kommunikation in Netzen | Algorithmen | GliederungKommunikation in NetzenAlgorithmenGliederung IP-PROTOKOLL (Paket) internet protocol / zielorientiert maximal 65535 Byte (theoretisch) 4 Quell- adresse 8 Headerlnge Paketlnge 1 Time to life bis 65515 Nutz - daten 3 Folgeprot. Prfsumme (Header) 4