Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Mittwoch, 26. April 2017 00:18 
40 Artikel (8 Seiten, 5 Artikel pro Seite)

zu Seite: 4 1 2 3 4 5 6 7 8 zu Seite: 6


HeapSort - wie man mit einem "Haufen" sortieren kann! (Informatik)
mehr... (9 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 2700 mal gelesen
Der Heap-Sort ist ein grundlegender Algorithmus der in (fast) keiner Vorlesung "Datenstrukturen und Algorithmen" ausgelassen wird.

Dieses Sortierverfahren wird meist im Kontext binärer Bäume eingeführt; dies ist dadurch begründet, dass der natürliche Definitionsbereich der besonderen Datenstruktur "Heap" ein binärer Baum ist. Dennoch wendet man in der Praxis den Sortieralgorithmus Heapsort für gewöhnlich auf normalen Arrays an.

Die Methode des Sortierens durch direkte Auswahl beruht auf dem wiederholten Auslesen des kleinsten Schlüssels aus (den restlichen) n Elementen. Auf einem ähnlichen Prinzip basiert der Haepsort, doch die zu Grunde gelegte Datenstruktur Heap (zu deutsch Haufen) behält mehr Informationen und ist deshalb deutlich schneller als die 'normale' Variante des Sortierens durch direkte Auswahl.

Der Inhalt dieses Dokuments behandelt überwiegend die heuristische Vorgehensweise des Algorithmus. Es werden viele Beispiele durchexerziert und erklärt. Am Rande wird auf die Kosten und evtl. Beweis der Korrektheit eingegangen. Die notwendigen Algorithmen für eine mögliche Implementation werden ausführlich dargestellt und hinterleuchtet.

Im Einzelnen werden behandelt:

  • Vergleich mit naiven Sortierverfahren: Einfügen, Löschen, Suchen
  • Definition, Heap-Bedingung, Minimums-Heap und Maximums-Heap, Alternative Formulierung der Heap-Bedingung für binäre Bäume, Beispiele
  • Algorithmen: StelleHeapBedingungHer(), ShiftDown() ["versickern"], EntferneExtrema(), ErzeugeHeap() - konkrete Beispiele zu allen Algorithmen.
  • Analyse des Heap-Sorts
Geschrieben von Alexander am Donnerstag, 29. Juni 2006 mehr...

AVL-Bäume: Ausgeglichene binäre Suchbäume (Informatik)
mehr... (9 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 3031 mal gelesen

Das Suchen, Einfügen und Entfernen eines Schlüssels in einem zufällig erzeugten binären Suchbaum mit N Schlüsseln ist zwar im Mittel O(log(N)) Schritten ausführbar. Im schlechtesten Fall kann jedoch ein Aufwand von der Ordnung Theta(N) zur Ausführung dieser Operation erforderlich sein, weil der gegebene Baum mit N Schlüsseln zu einer Liste degeneriert ist. Es ist daher natürlich, durch zusätzliche Bedingungen an die Struktur der Bäume ein Degenerieren zu verhindern. Die Operationen zum Einfügen und Entfernen werden dann allerdings komplizierter als für natürliche Bäume.

Im Einzelnen werden behandelt:
  • Kosten für das Einfügen (insert), Löschen (delete) und Suchen (member) in AVL-Bäumen
  • Definitionen: AVL-Baum als spezieller binärer Suchbaum, Balancefaktor, bal(v), linker Teilbaum, rechter Teilbaum, Algorithmus isbalanced, Beispiele
  • Operationen auf AVL-Bäumen, 4 elementaren Operationen auf AVL-Bäumen, Doppelrotation, einfache Rotation, wann welche Operation?, Schema für die Doppelroation und die einfache Rotation, Doppelrotation = zwei einfache Rotationen
  • Löschoperationen
Geschrieben von Alexander am Samstag, 27. Mai 2006 mehr...

Hashing in der Informatik (Informatik)
mehr... (29 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 2728 mal gelesen
Hashing ist eine Methode zur dynamischen Verwaltung von Daten, die durch einen eindeutigen Schlüssel angesprochen (gesteuert) werden:
  • Suchen nach einem Datensatz,
  • Einfügen eines neuen Datensatzes,
  • Löschen eines Datensatzes.
Gehen wir davon aus, dass zu jedem Zeitpunkt nur eine (kleine) Teilmenge K aller möglichen Schlüssel U (und die zugehörigen m Datensätze) gespeichert sind, so kann versucht werden, die Datensätze in einem Array a der Länge m zu speichern, also a[0..m–-1]. Das Array a[0..m–-1] bezeichnen wir als Hashtabelle und die Größe der Hashtabelle wird durch m festgelegt.

Die grundsätzlich Idee ist nun den Speicherplatz eines jeweiligen Datensatzes mit Hilfe des eindeutigen Schlüsselwertes zu berechnen. Dazu benötigen wir natürlich eine Funktion, welche auf einer Teilmenge der natürlichen Zahlen definiert ist - die Hashfunktion. Diese muss um den praktischen Anforderungen zu genügen gewisse Eigenschaften aufweisen.

Im Einzelnen werden behandelt:
  • Grundlagen des Hashings, Behälter, Array, Datensätze, Datenstrukturen zur Verwaltung von Dictionaries, dynamische Datenmengen - Einfügen, Löschen, Verändern
  • Kosten, Platz, Zeit, O(n), Komplexität
  • Hashfunktion, Auswahl der Hashfunktionen, totale Abbildung, surjektiv, injektiv, effizient berechenbar, Kollision, Beispiele
  • Wahrscheinlichkeit einer Kollision, Beispiel
  • Klassifizierung der Hashverfahren, Verkettung der Überläufer, offener Adressierung, offenes Hashing, geschlossenes Hashing
  • Sondierfolge, Sondierungsarten, Lineares Sondieren, quadratisches Sondieren, Doppel-Hashing, Beispiel
  • Divisionsmethode, Multiplikationsmethode, Mittelquadratmethode
Geschrieben von Alexander am Freitag, 12. Mai 2006 mehr...

Der Faktorraum von V nach U resp. Quotientenraum V modulo U (Mathematik)
mehr... (11 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 4347 mal gelesen
Faktorräume von Vektorräumen werden überall in der Mathematik benötigt. Eingeführt werden sie dagegen oftmals in einer Vorlesung zur linearen Algebra, seltener im Rahmen einer Analysis-Vorlesung.

Ein Vektorraum und ein Unterraum wird zur Konstruktion eines Faktorraums benötigt.
Ob man damit elliptischen Funktionen definiert, einen Beweis über nilpotente Endomorphismen erbringt oder aber den Homomorphiesatz beweist - überall erweisen sich diese, zunächst scheinbar schwer zu begreifenden Räume, als überaus gewinnbringend.

Im folgenden Dokument werden Faktorräume prägnant dargestellt, dabei wurde insbesondere auf die Anschaulichkeit Wert gelegt, deshalb findet man auch viele Skizzen und Beispiele.

Im Einzelnen werden behandelt:

  • Nebenklassen und Repräsentanten, wohldefiniert
  • Unterraumkriterium, Untervektorraum, Beispiele
  • Kriterium für die Gleichheit von Nebenklassen, Äquivalenzrelation (Reflexivität, Transitivität, Symmetrie)
  • Basen von Faktorräumen, Faktorraum ist ein Vektorraum
Geschrieben von Alexander am Mittwoch, 19. April 2006 mehr...

Platon und die antike Metaphysik (Philosophie)
mehr... (7464 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 2894 mal gelesen

Der griechische Philosoph Platon (428 - 348 v.Chr.), bekanntester Schüler Sokrates, stammte aus einem wohlhabenden und angesehenen altadligem Geschlecht Athens. Aufgrund seiner (familären) Beziehungen hatte er die Möglichkeit in der Politik Karriere zu machen. Insbesondere die Hinrichtung seines Mentors Sokrates (399 v. Chr.) ließ in ihm die Überzeugung reifen, dass die Stadt Athen von den Sitten der Väter abgefallen sei und überhaupt alle Staaten schlecht verwaltet wären (siehe unten, Platon, Briefe VII).

Geschrieben von Alexander am Donnerstag, 16. März 2006 mehr...


40 Artikel (8 Seiten, 5 Artikel pro Seite)

zu Seite: 4 1 2 3 4 5 6 7 8 zu Seite: 6


Umfrage
Ganz klar, das schönste Ressort der Mathematik ist die

Zahlentheorie
(Lineare) Algebra
Topologie, Maßtheorie, Integrationstheorie
Statistik, Wahrscheinlichkeitstheorie, Stochastik
Analysis, Funktionalanalysis
Funktionentheorie
Kombinatorik, Graphentheorie
Diskrete Mathematik
Lineare Optimierung

Ergebnisse
Stimmen: 662
Kommentare: 0
Umfragen

Login
Benutzername:

Passwort:



Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0777 Sekunden, mit 51 Datenbank-Abfragen