Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Dienstag, 21. Februar 2017 10:46 
40 Artikel (8 Seiten, 5 Artikel pro Seite)

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


Primitive Rekursion (Informatik)
mehr... (40 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 8937 mal gelesen
Der Begriff der Berechenbarkeit spielt neben dem der Komplexität in der klassischen theoretischen Informatik eine zentrale Rolle. Zunächst sollte man sich fragen, was das Adjektiv „berechenbar“ überhaupt bedeutet und worauf sich dieser Begriff bezieht. Intuitiv werden viele darunter wohl verstehen, dass etwas „sich errechnen lässt“ bzw. „vorhersehbar“ ist. Um jedoch etwas berechnen zu können benötigt man sicherlich ein Kochrezept, also einen Algorithmus bzw. eine Funktionsvorschrift. Schließlich müssen wir auch noch klären, was man alles berechnen kann, es wird sich nämlich zeigen, dass nicht alle Funktionen berechnenbar sind.

Sowohl Turing- als auch Registermaschinen sind Modelle von Maschinen. Sie nähern sich der Frage nach der Berechenbarkeit von der Seite der berechenbaren Automaten. Die jeweiligen Programme, welche auf diesen Maschinen laufen, müssen spezielle für das jeweilige Modell und die jeweilige Problemstellung zugeschnitten sein.

Einen hiervon differeten (aber äquivalenten) Zugang zur Frage der Berechenbarkeit besiert auf speziellen Funktionenklassen und darauf abgeschlossenen Operationen (Verknüpfungen). Mit den so genannte rekursiven Funktionen werden wir Lösungen von Problemen beschreiben und nicht, wie es bei den Maschinenmodellen üblich ist, die einzelnen Schritte des Rechenweges. Das Modell der rekursiven Funktionen versucht also nicht eine Maschine bzw. einen Automaten nachzubilden, sondern packt das Problem der Berechnbarkeit sozusagen bei der Wurzel, d.h. es nähert sich der Frage nach der Berechenbarkeit von Seite der Algorithmen.

Im Einzelnen werden behandelt:

  • Definition "intuitiv berechenbar"; Heranführung an den Begriff "Berechenbarkeit"; Grundlegende Definitionen
  • Nicht berechenbare Funktionen und deren Existenz; Beispiele und Beweis; Kardinalitätsargument;
  • Primitiv rekursive Funktionen; Induktionsprinzip; Basis-Funktionen; Grund-Funktionen; Konstante Funktionen; Nachfolgerfunktion (suc); Projektion auf den i-ten Eintrag; Substitution, Komposition, primitive Rekursion; primitiv rekursive Funktionen abgeschlossen gegenüber den Operationen; Beweis; Algorithmen; berechenbar;
  • Arithmetische Funktionen primitiv rekursiv dargestellt: Addition, Multiplikation, Potenzierung, modifizierte Subtraktion, Fakultät, Signum-Funktion, Maximum, Minimum, Identität; Abgeschlossen gegenüber Umordnung und Weglassen von Variablen; Fallunterscheidung;
  • Primitiv rekursive Relationen: Prädikate, Und, Oder, Nicht, Kleinergleich, Größergleich, Gleichheit; Charakteristische Funktion
  • Der unbeschränkte mue-Operator; echte Erweiterung der primitiv rekursiven Funktionen; alle berechenbaren Funktionen; Minimalisierung; beschränkte mue-Operator; Beispiele;
  • Ackermannfunktion; wichtigsten Charakterisierungen; Eigenschaften; Beweise; streng monoton in beiden Argumenten; wächst stärker als jede primitiv rekursive Funktion.
Geschrieben von Alexander am Mittwoch, 17. Januar 2007 mehr...

Probabilistische Primzahltests (Mathematik)
mehr... (58 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 7749 mal gelesen
Primzahltests sind wichtige Beispiele so genannter probabilistischer Algorithmen. Der Solovay-Strassen-Test war sogar einer der ersten seiner Art und wird am Ende dieses Dokuments behandelt.

Die in diesem Dokument behandelten Primzahltests, der Fermat-Test bzw. Miller-Rabin-Test, sind eng miteinander verknüpft. Der Miller-Rabin-Test kann als Fort- bzw. Weiterentwicklung des Fermat-Tests angsehen werden. Beide Algorithmen basieren auf dem wichtigen und einfach zu beweisenden (kleinen) Satz von Fermat. Allerdings treten beim Fermat-Test Anomalien in Form von Carmichael-Zahlen auf, welche der Miller-Rabin-Test erfolgreich versucht zu umgehen.

Auch der Solovay-Strassen-Test ist eng mit den beiden anderen untersuchten Primzahltests verwandt. Dies äußert sich auch im Zusammenhang zwischen den einzelnen Pseudoprimzahlarten.



Im Einzelnen werden behandelt:
  • Grundsätzliches Vorgehen bei einem probabilistischen Primzahltest, Vorgehen bei einem negativen Testausgang um eine große Primzahl zu finden.
  • Brute-Force-Mathode um eine Zahl zu testen, Zusammenhang mit der Komplexitätstheorie, AKS-Test, deterministischer polynomieller Primzahltest.
  • Definition Zusammengesetzte Zahl, Primzahl, Primfaktorzerlegung, Primfaktoren, Hauptsatz der Zahlentheorie, es existieren unendlich viele Primzahlen, Primzahlsatz und Primzahlverteilung.
  • Anforderungen an ein Kryptosystem; Komplexität; deterministisch; stochastisch unabhängige Wahl der Basis, Zeugen (witness), nicht Zeugen (liar), randomisierten bzw. probabilistischer Algorithmus.
  • Der Fermat-Test, Lemma von Bézout, modulare Inverse, "kleiner" Satz von Fermat, Satz von Euler; a Einheit im Ring Zn genau dann, wenn ggT(n,a)=1; Pseudoprimzahl, Beispiele, Einheitengruppe, Restklassenring, erzeugende Elemente, Eulersche phi-Funktion, Menge aller Basen bilden eine Untergruppe von (Z/nZ)*, zusammengesetzte Zahl, Pseudoprimzahl für mind. die Hälfte aller Basen oder aber für alle Basen.
  • Carmichael-Zahl, Satz von Korselt, Verteilung der Carmichael-Zahlen, "wahrscheinlich prim", Charakterisierung von Carmichael-Zahlen, mindestens Produkt drei verschiedener Primzahlen.
  • Rabin-Miller-Test, Polynom T2-1 hat in einem endlichen Körper der Ordnung p die einzigen Nullstellen +1 und -1, Beweis bzw. Herleitung, triviale Wurzeln bzw. nicht triviale Wurzeln, Beispiele, starke Pseudoprimzahl, höchstens für die Hälfte aller Basen b kann eine zusammengesetzte Zahl eine starke Pseudoprimzahl sein, Laufzeituntersuchungen, O-Notation.
  • Quadratische Reste, quadratische Nichtreste, Anzahl der Quadratwurzeln, Legendre-Symbol, Jacobi-Symbol und quadratische Reste, Zusammenhang beider Symbole, Satz von Euler, Rechenrelgen des Jacobi- bzw. Legendre-Symbols, Eulersche Pseudoprimzahl, der Algorithmus.
Geschrieben von Alexander am Freitag, 12. Januar 2007 mehr...

Primzerlegung in Z (Mathematik)
mehr... (18 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 6382 mal gelesen
Die Zahlentheorie ist zusammen mit der Algebra das wohl älteste Gebiet der Mathematik. Das unvergängliche Problem der Zahlentheorie ist das der Teilbarkeit:

Ist eine Zahl durch eine andere teilbar oder nicht?

Fast alle Themen der elementaren Zahlentheorie sind Variationen dieses Themas oder wurden zumindest durch diese Fragestellung motiviert.
Untersucht man das Teilbarkeitsproblem näher so stößt man unweigerlich auf die Bausteine der natürlichen bzw. ganzen Zahlen, den Primzahlen. Zum Einen können Primzahlen als Spezialfall von Seiten der Algebra (Primelemente) betrachtet werden, zum Anderen kann man diese elementar über den zahlentheoretischen Zugang studieren. In diesem Dokument werden wir den letzteren Weg wählen.

In alt bewährter Manier werden viele Beispiele zur Veranschulichung aufgeführt; ferner werden Beweise sehr ausführlich behandelt.

Im Einzelnen werden behandelt:

  • Das Teilbarkeitsproblem, Voraussetzungen und Überblick.
  • Prinzip vom kleinsten Element, Prinzip der vollständigen Induktion, Beweis der logischen Äquivalenz bzw. Zusammenhang beider Prinzipien.
  • Teilbarkeit und der Ring Z der ganzen Zahlen, Verknüpfungen Addition, (Subtraktion), Multiplikation, (Division), ganzzahlige Division, a teilt b, Beispiele, Integritätsring, aufgehende Zahl, Vielfaches, Lösen linearer Gleichungen ax-b=0 über Z, Rechenregeln für die ganzzahlige Division und Beweise, triviale Teiler, echte Teiler, absolute Betrag, Abschätzungen für Zahlen a|b.
  • Division mit Rest, Beweis der Existenz und Eindeutigkeit, Quotienten, Rest bei der Division, modulo, Modul, Rest, a kongruent b, Kongruenz, Modulus, Äquivalenzrelation für Restklassenringe bzw. Restklassen.
  • Primzahlen, Definition, zusammengesetzte Zahlen, Charakterisierung der Primzahlen, Unzerlegbarkeitseigenschaft, Primeigenschaft, Einheiten 1 und 0 der Addition und Multiplikation, Existenzsatz des kleinsten Teilers einer natürlichen Zahl der eine Primzahl ist, Unendlichkeit der Primzahlen, Satz von Euklid, Euklidscher Beweis, Konstruktionsverfahren von Euklid am Beispiel, Abschätzungen für Primzahlen, Fundamentallemma, p|ab dann folgt p teilt einen der beiden Faktoren.
  • Hauptsatz der elementaren Zahlentheorie, Primfaktoren, Primfaktorzerlegung, Primzerlegung, Eindeutigkeit der Primzerlegung, Existenz der Primzerlegung, jede natürliche Zahl ungleich 0 besitzt genau eine Primzerlegung, Hauptsatz für Z und N.
Geschrieben von Alexander am Freitag, 12. Januar 2007 mehr...

Software Engineering: Die Aktivität Analyse (Informatik)
mehr... (29 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 5031 mal gelesen
Erfahrungswerte zeigen, dass die Anforderungsermittlung, bzw. dessen Ergebnis die Anforderungsspezifikation, bei sehr großen zu entwickelnden Softwaresystemen nicht ausreicht um direkt zur Realisierung überzugehen.

In diesen Fällen bildet die Aktivität Analyse einen Brückenschlag zwischen der Anforderungsermittlung und der Realisierung. D.h. zum einen wird die Anforderungsermittlung von Realisierungsdetails entlastet und zum anderen liefert die Analyse ergänzende, präzisierende und weiter strukturierende Informationen. Nicht zuletzt ist es von Bedeutung, dass abschließend eine Analyse-Verifikation durchgeführt wird.

Im Einzelnen werden behandelt:

  • Zusammenfassung der Tätigkeiten und Ergebnisse aus der Anforderungsermittlung.
  • Ergebnis-Dokument Analysespezifikation (Analyse-Klassenmodell, Interaktionsdiagrammen, Zustandsdiagrammen, Ergebnis der Verifikationsaktivitäten)
  • Tätigkeiten der Analyse: Anwendungsfälle in Klassen überführen (Schnittstellenklassen, Kontrollklassen und Entitätsklassen), Analyse-Klassenmodell mit Operationen auskleiden, Verfeinerung bzw. Neuerstellung von Interaktionsdiagrammen und Zustandsdiagrammen, Aufdeckung von neuen (Nicht-Standard-)Operationen.
  • Heuristiken für die Klassenmodellierung: 1:1 Assoziationen und Klassenaufteilung, Generalisierung
  • Klassenmodellierung: gewisse Nähe der Analyse zur Realisierung, Aspekte für die Nähe zur Abstraktion.
  • Vorgehensweise in der Verhaltenmodellierung: Erstellung eines partiellen Objektmodells, Einbindung des Anwendungsfalls, Mechanismus, Kollaborationsdiagramm, Aufdeckung von (Nicht-Standard-)Operationen.
  • Schnittstellenklassen: Akteuer-Anwendungsfall-Schnittstellenklasse (kurz: AAS), Akteuer-Schnittstellenklasse (kurz: AS), Zusammenspiel.
  • use-Beziehung und (Nicht-)Standard-Operationen, Zusammenhang zwischen Verhaltenmodellierung und Vervollständigung des Analyse-Klassenmodells.
  • Verifikation: Inter-Modell-Verifikation (Analyseklassenmodell vs. Interaktionsdiagramme, vs. Zustandsdiagramme, vs. Anwendungsfall-Modell; Intra-Modell-Verifaiktion, Vollständigkeit, Eindeutigkeit und Konsistenz.
Geschrieben von Alexander am Samstag, 25. November 2006 mehr...

Software Engineering: Anforderungsermittlung (Informatik)
mehr... (49 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 3992 mal gelesen

Beachten Sie, dass dieser Atrikel aus einer Reihe über "Software Engineering" stammt:

Nachdem wir die Grundlagen der Softwareentwicklung in den ersten drei Dokumenten dieser Reihe konstatiert haben, werden wir uns sodann daran machen die erste und auch grundlegende Aktivität "Anforderungsermittlung" genauer zu studieren. Auf dem Ergebnis dieser Aktivität fußt das ganze spätere Projekt, entsprechend sorgfältig sollte diese Phase des Entwicklungsprozesses durchlaufen werden. Es werden die grundlegenden Chancen aber auch die Gefahren der Anforderungsermittlung sowie ein übliches Vorgehen in dieser Aktivität aufgezeigt.

Im Einzelnen werden behandelt:

  • Ziele der Anforderungsermittlung, Gliederung der Anforderungsermittlung (in Extrahieren, Verhandeln, Validieren und Verifizieren, Spezifizieren), Anforderungsspezifiaktion (Dokument bestehend aus Anwendugnsfallmodell, dem Domänenklassenmodell und dem Verhaltensmodellen), objektorientierte Anforderungsermittlung.
  • Motto "Nicht zuviel auf einmal und alles zu seiner Zeit", Problemadäquatheit, natürliche Modellierung, Problemwelt, typisches Vorgehensmuster, Gefahr der zu frühen Detaillierung.
  • Jeder Anwendungsfall behandelt eine klar abgegrenzte Aufgabe und liefert ein relevantes Ergebnis, Zerlegung von Anwendungsfällen, grundsätzliche Regeln zur Erstellung von Anwendungsfällen.
  • Glossar, Verbindung, Akteur und Pakete, Richtlinien.
  • Domänen-Klassenmodell: Ermittlung der Objekt bzw. Klassen, praktische Vorgehensweise, Assoziationen, Attribute, Studium der Szenarien, Fehlen jeglicher Operation, problemadäquat, Strukturen aus der Problemwelt.
  • Modellbereinigung: Jede Domänenklasse sollte mehr als ein Attribut besitzen, ableitbare Attribute und Assoziationen einer Klasse sollten als abgeleitet markiert werden, zu jeder Domänenklasse sollte im Normalfall mehr als ein Objekt in der Problemwelt existieren.
  • Verhaltensmodellierung: Rolle innerhalb der Anforderungsspezifikation, oftmals zu detailliert, externen Interaktionen, zustandsorientierte Verhaltensmodelle, Definition Zustand.
  • Validierung und Verifikation: Was ist eine Validierung, was ist eine Verifikation, Vorgehen, Walk-Throughs, Reviews.
Geschrieben von Alexander am Sonntag, 05. November 2006 mehr...


40 Artikel (8 Seiten, 5 Artikel pro Seite)

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


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: 658
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.0851 Sekunden, mit 51 Datenbank-Abfragen