Title:

Eine Klasse von Problemen in O(n²)

Description:  Gibt es zu einer gegebenen Menge S von n ganzen Zahlen drei Elemente aus S, deren Summe 0 ist?
Author:Hoang Nguyen
deutsch
  
ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012 
 
|<< First     < Previous     Index     Next >     Last >>|
  Wir empfehlen:       
 

1 Eine Klasse von Problemen in O(n²) Hoang Nguyen März 2002 Einführung In  dieser  Seminarausarbeitung  beweisen  wir  für  einige  Probleme,  dass  sie  mindestens  so schwer  sind  wie  das  folgende  Basisproblem:  Gibt  es  zu  einer  gegebenen  Menge  S  von  n ganzen Zahlen drei Elemente aus S, deren Summe 0 ist? Wir nennen solche Probleme 3SUM- hart. Der beste bekannte Algorithmus für 3SUM benötigt    (n²) Zeit, was auch für die grosse Klasse der 3SUM-harten Probleme eine unüberwindbare Barriere zu sein scheint. Die Suche nach  o(n²)  Lösungen  für  diese  Probleme  ist  hoffnungslos,  solange  das  Basisproblem  nicht schneller gelöst werden kann. 1  Reduktion Wir  setzen  die  Komplexitäten  zweier  Probleme  in  Relation,  wenn  ein  Problem  das  andere löst. Dies geschieht durch Transformation der Instanzen. Definition 1.1  Seien A und B Probleme. Wir sagen, dass A f(n)-lösbar durch B ist, genau dann  wenn  jede  Instanz  von  A  der  Grösse  n  durch  eine  konstante  Anzahl  Instanzen  (der Grösse  O(n))  von  B  und  O(f(n))  zusätzlicher  Zeit  (Transformationskosten)  gelöst  werden kann.  Wir  beschränken  uns  im  Folgendem  darauf,  jede  Instanz  aus  A  zu  jeweils  nur  einer Instanz aus B zu transformieren und notieren A<<f(n)B. Für A<< f(n)B und B<<f(n)A nennen wir A und B f(n)-äquivalent und schreiben A==f(n)B. Ist A f(n)-lösbar durch B, so ist B in gewisser Weise mindestens so schwer wie A. Das aus der Definition folgende Lemma macht dies explizit. Lemma 1.1  Seien f und g zwei Polynome und A<<f(n)B. Sei )) ( (    n g O obere Schranke für B und )) ( ( ) ( n g O n f , dann ist )) ( (    n g O auch obere Schranke für A. Sei umgekehrt )) ( (    n g untere Schranke für A und )) ( ( ) ( n g o n f , dann ist )) ( (    n g auch untere Schranke für B. 2  Das Basisproblem Problem: 3SUM. Instanz: Eine Menge S von n ganzen Zahlen. Frage: Gibt es a,b,c     S mit a + b + c = 0 ? Der beste bekannte Algorithmus für 3SUM braucht    (n²) Zeit im Worst Case. 3SUM ist f(n)- lösbar  durch  viele  Probleme  (für  folgende  Reduktionen  genügen  Transformationsschranken f(n)=O(n log n) ). Diese sind mindestens so hart wie 3SUM.
  
Bürgerliches Gesetzbuch BGB: mit Allgemeinem Gleichbehandlungsgesetz, BeurkundungsG, BGB-Informationspflichten-Verordnung, Einführungsgesetz, ... Rechtsstand: 1. August 2012
Siehe auch:
Handelsgesetzbuch HGB: ohne Seehandelsrecht, mit …
Strafgesetzbuch StGB: mit Einführungsgesetz, …
Grundgesetz GG: Menschenrechtskonvention, …
Arbeitsgesetze
Basistexte Öffentliches Recht: Rechtsstand: 1. …
Aktiengesetz · GmbH-Gesetz: mit …
 
   
 
     
|<< First     < Previous     Index     Next >     Last >>| 

This web site is a part of the project StudyPaper.com.
We are grateful to Hoang Nguyen for contributing this article.

Back to the topic site:
StudyPaper.com/Startseite/Wissenschaft/Naturwissenschaften/Mathematik

External Links to this site are permitted without prior consent.
   
  deutsch  |  Set bookmark  |  Send a friend a link  |  Copyright ©  |  Impressum