Computational Thinking Suchen und Sortieren [Ordnung muss sein…] Kurt Mehlhorn Konstantinos...

Computational Thinking

Suchen und Sortieren[Ordnung muss sein…]

Kurt MehlhornKonstantinos Panagiotou

Suchen

• Welche Telefonnummer hat Kurt Mehlhorn?• Wie schreibt man das Wort “Equivalenz”?• Welche Webseiten enthalten die Woerter “Uni

Saarland”? Welche ist die “wichtigste”?

Beispiele

Aha!

Noch eins

Aha!

„Freibad heißt ja nicht, dass es jedem freisteht, einfach irgendwo rumzuliegen“Ursus Wehrli, 2011

Konzepte

• Informatik = “Informationsverarbeitungstechnik”

• Ziel: Information ablegen und verarbeiten, hier: moeglichst schnell wiederfinden

• Was lernen wir aus den Beispielen?

Erste Überlegungen

• Daten können alles Mögliche sein:– Zeichenketten, Zahlen, Bilder, …

• Hier: (Name + Telefonnummer)• Annahme: Daten liegen ungeordnet vor

Problemgrösse und Aufwand

• Wir müssen schlimmstenfalls alle Elemente durchsuchen um sicher zu sein dass das gewünschte Element nicht da ist:

• Sei N die Anzahl Elemente• Dann beträgt der Gesamtaufwand

(schlimmstenfalls) N Vergleiche.

Ein Beispiel

• Das Internet hat mehrere Billionen Webseiten• 1 Billion = 1.000.000.000.000• Optimistisch:– Pro Sekunde koennen wir 1.000.000.000 Seiten

durchsuchen– Dann brauchen wir 1.000 Sekunden!

Ich finde Kurt’s Nummer nicht!

Wie machen wir das besser?

• Angenommen unsere Daten sind sortiert.– Hier: (Name + Nummer), nach Name

• Abstrakt:

Binärsuche

• Gegeben:– Liste mit N Elementen– Sortiert: der Nachfolger ist groesser als sein

Vorgaenger. • Frage: enthält die Liste ein Element x?• Algorithmus:

Konzept: Divide and Conquer

Der Algorithmus

• Sei L[i] das i-te Element der Liste L

Suche(L[1], …, L[N], x) falls N = 0 dann fertig Sei m das mittlere Element in L, also m = L[N/2] falls x = m dann fertig falls x < m dann Suche(L[1], …, L[N/2-1], x) falls x > m dann Suche(L[N/2+1], …, L[N], x)

Komplexität

• n = 1: Kosten = 1• n = 2: Kosten = 2• n = 3: Kosten = 2• n = 4: Kosten = 3

Komplexitaet

N

Anzahl Vergleiche schlimmstenfalls

1 2 3 4 5 6 7 8 9

Der Logarithmus

• Verbleibende Elemente im Allgemeinen:– N -> N /2 -> N /(2 * 2) etc

• Komplexität:– Die kleinste Zahl i so dass

N / (2 * 2 * … * 2) < 1 (i mal)

• Diese Funktion heisst diskreter binärer Logarithmus• N = 1000: Log(N) = 10• N = 1.000.000: Log(N) = 20• N = 1.000.000.000.000: Log(N) = 40• N = Atome im Universum: Log(N) = 240

Zusammenfassung

• Lineare Suche vs. Binärsuche• Funktioniert wenn man die gegebenen Daten

ordnen kann:– (Name, Telefonnummer)– Webseiten?

• N vs. Log(N)

Algorithmus ist nicht gleich

Logarithmus

Wie sortiert man?

Erste Überlegungen

• In der sortierten Reihenfolge befindet sich das kleinste Element zuerst.

• Algorithmus:– Bestimme das kleinste Element unter den

verbleibenden Elementen– Füge es an das Ende der bisher sortieren Elemente

hinzu.

Beispiel

Ein Detail

• Wie bestimmt man das kleinste Element in einer Liste?

• Algorithmus:– Gehe die Liste Element für Element durch– Merke das bisher kleinste gesehene Element

L[i]: das Element der Liste an i-ter StelleN: die Länge der Liste

Finde_min(L) Min = L[1] Für alle i zwischen 2 und N Min = das kleinere aus L[i] und Min

Komplexität der Sortieralgorithmus?

• Angenommen wir haben N Elemente• Im ersten Durchlauf:– N-1 Vergleiche um das kleinste zu bestimmen

• Im zweiten Durchlauf:– N-2 Vergleiche

• …. Im i-ten Durchlauf: N-i Vergleiche• Total:

Was heisst das?

N N(N-1)/2 Laufzeit in sec10 45100 49501.000 499.5001.000.000

Mischen

• Einfacheres Problem:– Gegeben zwei Listen A und B mit jeweils N

Elementen.– A und B sind bereits sortiert.– Wie erzeugt man eine neue Liste, die sortiert ist,

und alle Elemente aus A und B enthält?

Beispiel

Merge

• Sei A[i] das i-te Element von A, B[i] analog• Merge(A,B)

a = 1, b = 1, c = 1solange a <= N und b <= M

falls A[a] < B[b] dann C[c] = A[a], a = a+1, c=c+1sonst C[c] = B[b], b = b+1, c=c+1

Komplexität?

Ein Beispiel

7 3 2 8 9 1 4 6 N = 8

7 3 2 8 9 1 4 6

7 3 2 8 9 1 4 6

4 67 3 2 8 9 1

3 7 2 8 1 9 4 6

2 3 7 8 1 4 6 9

1 2 3 4 6 7 8 9

Sortieren durch Mischen

Unsortierte Liste

Teil 1 Teil 2

Teil 1, sortiert

Teil 2, sortiert

Sortierte Liste

merge

Falls die Liste nur ein Element hat,tue nichts.

Ansonsten:sortiere sortiere

Konzept: Divide and Conquer

Warum so kompliziert?

• Weil es extrem schnell ist!• Komplexität: wie viele Vergleiche sind

notwendig?

Alle Kosten…

Was heisst das?N N(N-1)/2 N Log(N) Sekunden10 45 33100 4950 6641.000 499.500 99651.000.000 19.931.568 < 1

Aber…

• Manchmal sind Vergleiche sehr teuer– DNA Sequenzen mit mehreren Tausend Einträgen

• Spezielle Sortierverfahren:– Bucketsort– Eingabe: Zeichenketten

• Idee: Telefonbuch

EimerAmélie – Julia – Lena – Laura – Anna – Lea – Lina – Sarah – Elena – Nina – Selina – Vanessa – Alina – Jana –Emma – Hannah – Lisa – Sophie – Sandra – Leonie – Luisa – Nele – Franziska – Samira

Idee: 26 Eimer, einen für jeden Buchstaben im Alphabet

Laut vornamen.de: die beliebtesten Mädchennamen

Der L-Eimer

LenaLaura Lina Lisa Leonie Luisa

Komplexität

• Jedes Zeichen wird genau einmal betrachtet.• Falls die Eingabe insgesamt N Zeichen hat, so

werden N Entscheidungen insgesamt getroffen.

• Der Algorithmus ist also linear.

Zusammenfassung

• Suchen:– Binärsuche vs. Lineare Suche

• Sortieren:– N^2 vs. N Log(N) Algorithmen– Lineare Algorithmen für spezielle Fälle

Orga

• Übungen amDienstag, 16-18 Uhr bei Cosmina

fallen ab sofort aus!

Bitte an alle Teilnehmer: weichen Sie auf andere Gruppen aus.