Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

#yolo#swag#bitches

#yolo#swag#bitches
by

Florian Wiegner

on 27 January 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of #yolo#swag#bitches

Allheilmittel - PC?

Zeitkomplexität
• beschreibt Anzahl der Rechenschritte und die Länge der
Eingabe
• "asymptotische Laufzeit" -> Anlehnung an eine Asymptote
bezogen auf das Zeitverhalten einer unendlich großen
Eingabemenge
• Hauptproblem : "
wie stark stiegt der Zeitbedarf an, wenn
mehr Daten verarbeitet werden müssen
"
• Zeitkomplexität und Algorithmen
- Anzahl der Schritte, welche der A. für die Bearbeitung der
Eingaben benötigt
• Einteilung in worst case; avergae case und best case
Platzkomplexität
• Bedarf an Speicherplatz eine Algorithmus
zur Lösung eines Problems, abhängig von
der Eingabe
• zu untersuchen gilt der steigende
Spei -
cherplatzbedarf
bei ansteigender Daten -
menge
• Zeitkomplexität eines Algorithmus kann
niemals kleiner sein als dessen Platzkom -
plexität, da für das Schreiben jeweils
mehrere Rechenschritte benötigt werden
• Einteilung in Komplexitätsklassen nach

Zeit - & Raumkomplexität
Effektivität
• Effizienz bezieht sich auf die Sparsamkeit eines Algorithmus
und dessen benötigten:
Ressourcen, Rechenzeit & Speicherplatz
• umso effizienter der Algorithmus, desto schwerer ist dieser zu
verstehen
• umso effizienter ein Algorithmus, desto schneller ist dieser bei
der Lösung des entsprechenden Problems
• Effizienz wird außerdem durch
Implementation
in der je -
weiligen Programmiersprache,
Hardware
und durch
Einga -
bedaten
beeinflusst
Erfolg
Das 26-Dame-Problem
Gliederung
1. Einleitung
1.1 Einführung in das Thema
1.1.1 theoretische Informatik
1.1.2 zu behandelnde Probleme
2. Hauptteil
2.1 Komplexität
2.1.1 Zeitkomplexität
2.1.2 Platzkomplexität
2.4 Effektivität der Algorithmen
2.3 Probleme

3. Problemvorstellung
3.1 Sortierproblem - Bubblesort
3.2 Damenproblem - Backtracking

4. Schluss
4.1 Zusammenfassung - Erfolg
4.2 Quellen

theoretische Informatik
• Hauptziel: Lösung der Problemstellungen in der Informatik mit Hilfe von verschieden Algorithmen bzw. Maschinen
Berechenbarkeit
• (= Rekursionstheorie)
• Teilgebiet der theoretischen Informatik
• befasst sich mit der Frage, welche Probleme mit
einer Maschine
(speziell: mathematisches Modell
einer Maschine)
lösbar sind
• hohes Augenmerk liegt auf Terminiertheit* von
Algorithmen und Programmen

Problemfeld 1
"Sortiermaschine"
Bubblesort
Problemfeld 2
"Damenproblem"
Backtracking
Funktion FindeLösung (Stufe, Vektor)
1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:

a
) wähle einen
neuen Teil-Lösungsschritt
;

b
) falls
Wahl gültig
ist:
I) erweitere Vektor um Wahl;
II) falls
Vektor vollständig
ist, return true; //
Lösung gefunden
!
sonst:
falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
sonst mache
Wahl rückgängig
; // Sackgasse (
Backtracking
)!
2. Da es
keinen neuen Teil-Lösungsschritt
gibt: return false //
Keine Lösung
!
22.317.699.616.364.044 Lösungen
10 Monate Rechenzeit
void bubblesort(int *array, int length)

{

int i, j;

for (i = 0; i < length -1; ++i)

{



for (j = 0; j < length - i - 1; ++j)

{

if (array[j] > array[j + 1])

{

int tmp = array[j];

array[j] = array[j + 1];

array[j + 1] = tmp;

}

}

}

}
Zusammenfassung
• vereinfachte Strukturen der Algorithmen
• steigernde Effizienz durch komplexere Algorith -
mensysteme
• komplexere Problemfelder der Informatik schneller
und verständlicher analysierbar

mathematischer Erkenntnisgewinn durch Lösungen verschiedenster Probleme
Bestimmen des effizientesten Algorithmus
manche der gefundenen
Lösungen
lassen sich
praktisch implementieren
, um Menschen automatisierte
Vorteile
der Mathematik- und
Computer-Nutzung
zu verschaffen !
lösbar?
unlösbar?
Laufzeit eines Algorithmus auf Basis der benötigten Rechenschritte

Speicherbedarf durch Variablen

Effizienz bestimmt durch:
Worst-Case – das schlechtestmögliche Verhalten

Average-Case – das durchschnittliche Verhalten

Best-Case – das bestmögliche Verhalten
Effiziente Algorythmen meist die Angaben, welche polynomial zur Eingabe verlaufen
Bsp.
k
n
liniear verlaufende Algorythmen
Bsp.
c
x
n
Landau Notation:
für größere Eingaben verwendet
Laufzeitverhalten und Platzbedarf durch Vernachlässigung konstanten Variablen darstellbar

In Praxis, hauptsächlich mit kleinen Eingabegrößen gearbeitet
uneffizient, wenn Parameter zu groß definiert ist
k
uneffizient, wenn Parameter zu groß definiert ist
c
Halteproblem !

Funktionen, die von keinem Computer je berechnet werden können

Mengen (Sprachen,Probleme), die unentscheidbar sind
Mengen, die nicht einmal aufzählbär sind z.B. Eingabewert zu groß
meist nur geringfügig/ansatzweise lösbar bzw. Spaltung in einzelne Teilprobleme
Quellen:
http://de.wikipedia.org/wiki/Wikipedia:Hauptseite
18. August 2013 ca. 15 Uhr
http://www.info-wsf.de/index.php/Damenproblem
18. August ca. 15:30
http://www.proggen.org/doku.php?id=algo:bubblesort
18. August ca. 16 Uhr
Full transcript