www.AlgorithMan.de
Where theory comes alive
16 KiB
Bestimmt alle Primzahlen von 1 bis n mit dem Sieb des Eratosthenes
14 KiB
Eine Klasse, mit der man Elemente des Quotientenkörpers (englisch: Field of Fractions) eines Rings benutzen kann. damit kann man z.B. Brüche (= FieldOfFractions<int>) oder rationale Funktionen (= FieldOfFractions< polynomial<float> >) benutzen.
21 KiB
19 KiB
Ein Programm, das lineare Markov-Ketten löst.
3 KiB
Eine Klasse für Matrizen, mit Matrizen-Addition, Multiplikation, Transposition, Pivotisierung (die man z.B. für das Gauß'sche-Eliminationsverfahren oder den Simplex-Algorithmus zur Linearen Optimierung braucht) Tensorprodukt, etc.
17 KiB
Eine Klasse für Polynome, einschließlich Polynom-Multiplikation, -Division, Ableitung, Integral, etc.

Sehr interessant ist die Methode zur Bestimmung der Nullstellen. Damit berechnet das beiliegende Programm branchingnumber die Verzweigungszahl eines Verzweigungsvektors. Damit kann man also die Laufzeit von komplizierten, rekursiven Programmen berechnen.
Beispielsweise ist branchingnumber 1 2 = 1,618 (Goldener Schnitt), weil das die größte Nullstelle des charakteristischen Polynoms \(x^2-x-1\) ist (siehe auch hier). Entsprechend ist die Laufzeit der rekursiven Berechnung der n-ten Fibonacci Zahl gerade \(O(1,618^n)\).
1891 KiB
Die wichtigsten Dateien über das TVDS (Topdown Vorverarbeitendes Determinanten Schema), den Algorithmus, mit dem ich 2003 bei Jugend Forscht teilgenommen habe.
Der Algorithmus verwendet Memoisation um den Aufwand zur Bestimmung der Determinante einer Matrix nach dem Laplace-Verfahren von \(O(n!)\) auf \(O(2^n)\) zu reduzieren.