Zuletzt angesehen:

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
lesson:first [2023/08/12 15:54] – [Was ist Informatik eigentlich?] mccab99lesson:first [2023/08/27 13:44] (aktuell) – Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
-===== Was ist Informatik eigentlich? =====+===== Über Algorithmen =====
  
 <WRAP center round info 95%> <WRAP center round info 95%>
Zeile 28: Zeile 28:
 Bestimmt ist dir beim Tippen in dem Textfeld schon aufgefallen, dass einiges anders ist. Aber: Herzlichen Glückwunsch! Du hast soeben ein informatisches System ([[https://etherpad.org/|Etherpad]]) in Form eines kollaborativen Dokuments benutzt. Bestimmt ist dir beim Tippen in dem Textfeld schon aufgefallen, dass einiges anders ist. Aber: Herzlichen Glückwunsch! Du hast soeben ein informatisches System ([[https://etherpad.org/|Etherpad]]) in Form eines kollaborativen Dokuments benutzt.
  
 +++++Mehr zu Etherpad |
 <WRAP center round tip 95%> <WRAP center round tip 95%>
 === Tipp 1: Mehr über Etherpad erfahren === === Tipp 1: Mehr über Etherpad erfahren ===
Zeile 33: Zeile 34:
 {{youtube>rqhbathigpc?}} {{youtube>rqhbathigpc?}}
 </WRAP> </WRAP>
 +++++
 ==== Informatik löst Probleme ==== ==== Informatik löst Probleme ====
 <WRAP center round todo 95%> <WRAP center round todo 95%>
Zeile 80: Zeile 81:
  
 Algorithmen werden in der Informatik mit Programmiersprachen umgesetzt. Das sind Sprachen, mit denen sich Lösungsstrategien sehr gut und eindeutig formulieren lassen. Diese Sprachen unterscheiden sich voneinander in ihrer Syntax und ihren Möglichkeiten. Wie du noch sehen wirst, muss so eine Sprache noch nicht einmal Text enthalten - einfache Symbole oder gar Farben erfüllen auch diesen Zweck.  Algorithmen werden in der Informatik mit Programmiersprachen umgesetzt. Das sind Sprachen, mit denen sich Lösungsstrategien sehr gut und eindeutig formulieren lassen. Diese Sprachen unterscheiden sich voneinander in ihrer Syntax und ihren Möglichkeiten. Wie du noch sehen wirst, muss so eine Sprache noch nicht einmal Text enthalten - einfache Symbole oder gar Farben erfüllen auch diesen Zweck. 
 +
 +++++Bubblesort in der Programmiersprache Python |
 +Du kannst dir hier die Umsetzung von Bubblesort in Python ansehen - einer momentan sehr weit verbreiteten Programmiersprache.
 +
 +<file python bubblesort.py>
 +def bubbleSort(arr):
 +    # Anzahl der Zahlen ermitteln
 +    n = len(arr)
 +    # Erstmal nehmen wir an, dass keine Vertauschungen notwendig waren
 +    swapped = False
 +    # Jetzt nehmen wir uns jede Zahl vor und vergleichen sie mit ihrer Nachbarzahl
 +    for i in range(n-1):
 +        # "for" ist eine Schleife, die (n-1)-mal läuft
 +        # i ist ein Zähler und erhöht sich bei jedem Durchlauf um 1
 +        # die letzte Zahl lassen wir beim Vergleich aus
 +        # wir gehen nur bis zur vorletzten (n-1)
 +        # das sind praktisch die "Durchläufe"
 +        for j in range(0, n-i-1):
 + 
 +            # bei jedem Durchlauf müssen wir Schritt für Schritt durch die
 +            # noch nicht geprüften Zahlen gehen
 +            # Durchlauf 1 - Schritt 1, Durchlauf 1 - Schritt 2 usw.
 +            if arr[j] > arr[j + 1]:
 +                swapped = True
 +                arr[j], arr[j + 1] = arr[j + 1], arr[j]
 +         
 +        if not swapped:
 +            # wenn wir nichts tauschen mussten, sind wir fertig
 +            return
 + 
 + 
 +# Zahlen, die zu sortieren sind
 +arr = [64, 34, 25, 12, 22, 11, 90]
 + 
 +bubbleSort(arr)
 + 
 +print("Ausgabe der sortierten Zahlen:")
 +for i in range(len(arr)):
 +    print("% d" % arr[i], end=" ")
 +</file>
 +++++
  
 <WRAP center round todo 95%> <WRAP center round todo 95%>
Zeile 157: Zeile 199:
   - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf.   - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf.
   - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn.   - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn.
 +  - [[loesung:bubblesort|Lösung]]
 </WRAP> </WRAP>
  
Zeile 168: Zeile 211:
   * Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort?   * Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort?
  
 +++++Auflösung |
 +
 +Das Aufwändige für einen Rechner sind Vergleiche. Im Prinzip muss man für einen Vergleich eine Subtraktion durchführen und dann zwei Fälle unterscheiden:
 +  - Ist das Ergebnis 0, dann sind die Zahlen gleich
 +  - Ist das Ergebnis von 0 verschieden, dann sind die Zahlen nicht gleich
 +
 +Ein Tausch von Zahlen ist dagegen vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung:bubblesort|Bei Bubblesort hast du gesehen]], dass für die gegebene Zahlenreihe 40 Vergleiche notwendig sind, um den Algorithmus abzuschließen. 
 +
 +Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, aber wir schauen mal.
 +  * das aktuelle Pivotelement ist **fett** formatiert.
 +  * eine unterstrichene Zahl ist ein Zahl, die mit dem Pivot-Element verglichen wurde
 +  * die Anzahl der unterstrichenen Zahlen ist also die Gesamtzahl der Vergleiche im aktuellen Durchgang
 +
 +**Durchgang 1 - 6 ist Pivotelement:**\\
 +__3__ __7__ 1 8 2 5 9 __4__ **6**\\
 +3 //4// 1 8 2 5 9 //7// **6** ( 4 und 7 wurden getauscht)\\
 +3 4 __1__ __8__ 2 __5__ __9__ 7 **6**\\
 +3 4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\
 +[ 3 4 1 5 2 ] //6// [ 9 7 //8// ] ( 6 und 8 wurden getauscht, Vergleich war unnötig, die 6 muss die kleinste Zahl sein)\\
 +
 +Wir haben in diesem ersten Durchgang insgesamt 7x Zahlen miteinander verglichen. Die 6 liegt jetzt schon auf ihrer Endposition. 
 +
 +Wir werden weiterhin ...
 +  * für das Pivot-Element **2** 3x vergleichen müssen
 +  * für das Pivot-Element **4** 2x vergleichen müssen
 +  * für das Pivot-Element **8** 1x vergleichen müssen
 +
 +Wir kommen also mit 13 Vergleichen aus. Quicksort ist um Größenordnungen effizienter als Bubblesort. Bei einer bereits sortierten Liste (Best-Case) bringt Quicksort keinen Nachteil gegenüber Bubblesort.  
 +++++
 ===== Ja, und was ist jetzt mit Informatik? ===== ===== Ja, und was ist jetzt mit Informatik? =====
 Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines //Teilbereichs der Informatik// (algorithmisches Problemlösen) kennen gelernt: Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines //Teilbereichs der Informatik// (algorithmisches Problemlösen) kennen gelernt:
Nach oben