Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division
|
Dateibereiche
|
|
|
Metadaten
|
| Titel:
| Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division |
| URL für Lesezeichen:
| http://ubdok.uni-paderborn.de/servlets/DocumentServlet?id=8716 |
| URN (NBN): | urn:nbn:de:hbz:466-20090212010 |
| Kollektion:
| Dissertationen |
| Status: | Dokument veröffentlicht |
| Sprache:
| Deutsch |
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten»Dissertation |
| Medientyp: | Text |
| Autor: | Lürwer-Brüggemeier, Katharina [Autor]
|
| Beitragender: | Meyer auf der Heide, Friedhelm [Gutachter]
|
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke |
|
Beschreibung
(Deutsch):
| In dieser Arbeit werden Berechnungen mit dem Einheitskostenmaß über einer Operationsmenge, die die ganzzahlige Division DIV einschließt, betrachtet. Es werden die Sprachklassen CCn(S) der Sprachen LCZn,, die durch S-Berechnungsbäume mit S C{+,-,*,* c,DIV,DIVc} erkannt werden, charakterisiert, sie werden für S={+,-,DIVc} und S={+,-,*, DIVc} vollständig, für S={+,-,DIV} und S={+,-,*,DIV},n=1 vollständig und für S={+,-,DIV} und S={+,-,*,DIV},n>1 teilweise charakterisiert. Die Beziehungen zwischen den Sprachklassen CCn(S) werden vollständig bewiesen und es werden untere Schranken für solche S-Berechnungsbäume bewiesen. Die erste untere Schranke für ({+,-,*,DIV},_}-CTs führt zu einer doppellogarithmischen Lücke zwischen Polynomauswertung über {+,-,*} und {+,-,*,DIV}. Daher stellt sich die Frage, ob Polynome über {+,-,*,DIV} in o(d) berechenbar sind. Dies ist mit einem Algorithmus von N.Bshouty in konstant vielen Schritten für endliche Eingabemengen möglich oder für Eingaben aus Zn, wenn als weitere Operation die bitweise Konjunktion hinzugenommen wird. Diese Ergebnisse werden zur Beschleunigung der Matrixmultiplikation, der Determinantenberechnung über {+,-,*,DIV} und der Potenzierung von Matrizen über {+,-,*,DIV,ggT} benutzt. |
|
Beschreibung
(Englisch):
| In this thesis computations with an operation set including integer division DIV in the unit cost model are considered. CCn(S), the families of languages LCn that can be recognized by S-computation trees SCTs with SC{+,-,*,* c,DIV,DIVc}, are characterized. They are completely characterized for S={+,-,DIVc} and S={+,-,*, DIVc} and for S={+,-,DIV} and S={+,-,*,DIV} only in the case n=1 and partially in the case of n>1 for S={+,-,DIV} und S={+,-,*,DIV}. The relations among the classes CCn(S) are completely determined and lower bounds for such S-Cts are proven. The first nontrivial lower bound for ({+,-,*,DIV},_}-CTs leaves a doubly logarithmic gap between the lower bounds for polynomial evaluation over {+,-,*} and {+,-,*,DIV}. This leads to the question if a polynomial p can be evaluated in o(deg p) over {+,-,*,DIV}. This is possible with N. Bshouty’s algorithm in constant time restricted to a finite input set__or over all integers with bitwise conjunction as an additional operation. These results are used for acceleration of matrix multiplication, of determinant computation over {+,-,*,DIV} and of_matrix powering over {+,-,*,DIV,gcd}. |
| Fakultät / Einrichtung: | Fakultät für Elektrotechnik, Informatik und Mathematik»Institut für Informatik |
| Dokument erstellt am:
| 12.02.2009 |
| Dokument geändert am:
| 12.02.2009 |
| Datum der Promotion:
| 17.12.2008 |
|
