Algorithmik: Die Kunst des Rechnens 3540243429, 978-3-540-24342-7, 978-3-540-37437-4 [PDF]

Zitiervorschau

Algorithmik

David Harel Yishai Feldman

Algorithmik Die Kunst des Rechnens

Übersetzt von Micaela Krieger-Hauwede Mit 124 Abbildungen

123

David Harel Department of Applied Mathematics Weizmann Institute of Science 76100 Rehovot, Israel [email protected]

Yishai Feldman The Interdisciplinary Center P.O. Box 167 46150, Herzliya, Israel [email protected]

Übersetzerin Micaela Krieger-Hauwede [email protected]

MSC-Nummer: 68Q01 ISBN-10 3-540-24342-9 Springer Berlin Heidelberg New York ISBN-13 978-3-540-24342-7 Springer Berlin Heidelberg New York Bibliografische Information der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.ddb.de abrufbar. Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Springer ist ein Unternehmen von Springer Science+Business Media springer.de © Springer-Verlag Berlin Heidelberg 2006 Printed in Germany Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Text und Abbildungen wurden mit größter Sorgfalt erarbeitet. Verlag und Autor können jedoch für eventuell verbliebene fehlerhafte Angaben und deren Folgen weder eine juristische Verantwortung noch irgendeine Haftung übernehmen. Satz: Micaela Krieger-Hauwede, Leipzig Herstellung: LE-TEX, Jelonek, Schmidt & Vöckler GbR, Leipzig Umschlaggestaltung: KünkelLopka Werbeagentur, Heidelberg Gedruckt auf säurefreiem Papier 33/3100 YL – 5 4 3 2 1 0



 

 
 
    
  

 

 
    



  




 
  

 


  



 
   

 !" 

 #$% 


 &
" '


  

    
   


  

  
      

  
            

  



    


    
 


    
 
 
 
                     

  
 
   
  !   
   "
   !     
  
   
#
    
   
 $% 
&  

 $
   !'  
    (   
 )   % % !   
  % 
 
 %
 *   %
 +  
 +
 
  
  
 % 
 
 
 *
  ! 

 
 
  *  
 %    

 ,
 

 
  
  $   -
 ! ' 


     % 
   ! (  
 . ' 
 
  
 % % /  
  
 
 !   
    
 

 
 % % 
  
   -

 +   ! 
  
 % 
 
     ! 

 
   +   
  
  
 
 %'  
 $  
 

  !    
    
  
 
   0 
 
 
  
 +   ! 

     (  
 
   
 .  
   


  $%
  


 / 
 
   
'  
  



 

   +   *       
 
  



 
  )   $%   
  
 
 
 %
 
 +  1 
 2 
 
 
  
   


 
  $% 
   
  

  
+
  /     
  %  
  '  
           


 
 


 
,          

 
 







    


 

  

      
      

 
  
  

  
 
 


       
   
 
 
!  
   "     
   #


 $       
 % 
      
 
   %     &
 
  ' 
     
          
&   
   
 

(
   

       "   
 )  *
  

 " 
  +   ,     
     
   
  & 

 -  .    
  
  ' 
 

    
  

  ' 
 
/


  .  

  
   
   ' 

    0   /


 
    
  
  
  01
      

' 
., 
 2300
4   
 
/


    2   0
4 - 
 )
5 $
#



  
   ' 
 
  0  + 
 /

 

  
 6 
 7 - 8    $   
.
 
 8

 
 
 -  
 - 
 !    
   6 
7 
  
 9 #
 

:

   
   
 )  

  

   
 ,        

       8  
  #
     
  /



  0 0
   
 ;

   9
.   
 


   
 
 
    -


    
 #

     

  +      

     #
 ' 

,
 $  
 
     #


"
     
        
/ 0 
   
'   
-           
! %    
  
 
.
 $
 

 

     8 
 30    0
      .            
   )
   
 
    

 
 
   #   
 ' 
1
   %    .
 




    





   
           
     
 
                
      
   

       
        ! 
       
     "   #      $            
 % 

 & % %    $ 
 

 

          
         '(
  
)    
     *!  +,-.  /   +,-0 
   1          

     
    
   1 
     !  %      2

    3     & %     #!  4  !  1 

 
  

  5 %  
             6           2

    & % 4     !7 
 ( 
 4     1 4  
      !   

     !!    
      (8     9 ! 
  
!4  
    %   
         %!    ( !  2       
 %       ! 4   7        
     
       6     2    8 
8!       !  6   & %    
         

        
 $ 

             

 

  4  5 %
!   5 % 
   
   
   :7     
         
       %
               %   3             
    

       2    
   

    
  5 %
4  
 
     5 %
    %
              ; %
  <  =   
   3   $

   5 !        1<   
             ! 4  
     

      & %     %
   


   


  



            

  

 
        

     

      


   
  

 ! " 
          

 #

 
$           
 %"    
         & ' ( ') 

* 
½   +   ,   
    

"



- . /    
    0    
  
   %  # 1
 ,  


     .  .   02

  ,2 # 0 
"     *  
     

 



  3 4  

    . 5 # 6 


   
    .
 
 34 5    3  4 


  
   -   )      # 
   ,  

* 
   
  %  # 1
*  
 
7   #


  
 

8
,     .       8     
    # 1   
0 

  %  ( '
  
    "   
 )  . 
 # +   
 
 ,  9

 :
 ( . ,  ; %
 


'  
 

6



 
$
 ' 

 
 

(



 



   
 

?



!  (
 % *     +

 
 " 

 '  
 
8
6
 .    ) 

/   $
 ;@ 
 






 $
  


$
 '  & $
 ;, ." 

/  $
 ;3 .A
'
"

h




D

M

@

;

%

>

s

;

>

;

D



#




 "    
   
 
 
  % 
 8
 : 

 
    ! 


 
  
 ) 
  
 =   
 " 
    
   

 
 = 
  
 
    

 " 
(  
 = 
 % 
 '
    

 +
 ?

 $
       @
  + 
   
  ) 
 %  
  :

       @
  ,
  " 
(  
 #
 :

  
    
 "   


  % 
    
 -
            ;   7
 
  ,
  


  
 
 
 ,( 
     


  
   
   
 

   

 
    $

 
 
 @  %    
  , % + 

  -
 
  

 ,




    



 


    


 

 

    

   
   

 

  
 

        !  ½¾¼    

 


 !! "   
 #$

%! 
  & $ 
   '
$( 

    )   
  *
    

+
    &%  $ ,   

 
  !%      -  &  .    

 -   
 /
 
 

$      &%    !%    0'

      %

  .%   1
$2  3 

 &%      "$    
  .    4!5 /  . 
         !% 6 '!  
 1$
 

 
$7   $  $
    7    '  .  !  /  
  1
 

 -  




 .  
 
8+. +"  
%! 
   .   
  

$  
 

 .   !%  -      
  

$     
  !4! .  !   &!    
  &  
 "  
%!    ! !  
7 9
   
 
  )  #$  
  
      :1
; 4  

 .  
   7!! 

 - 
% 




 1

  .     
"   
      #$ 7
 3 
  



$
* 

  

 .  
% 
 /
 
 
 6 ,      
 1
  ! 
?
!  # $
  1

  
 


     




   


          
          
     
     
 

  
 

         
   
               ! 

    "       #  
 $ !
!

       " !  
     %     
      &'(( 
  )
    * + "    ,"
 
    .         

      . "  
 !     /  &'(( "    

 "     01    *  2 %
    
 3 4  
  5)   6      7 .            +  

 8         
  6          
 9 
  !       :
        0   $ ! *!*   
  
  

  ;      
 :        

              *!*    ?    *    %  *
        )         9     ;      !    6 =
  
   1        &@'A    
          $ !
 
      



    
     ;   " !*   >    *
   

    . !! "   +   / .   
       9   
!   $ !
  
          9* 
8       7



                  ½ 

½¾    

    


             



       

  !

    " #  $   
%& 

      !       %"  '   ! ! &   

   (  ) %& *+        %& '

  

          

     

         *  , !-      )




    


                 

       
        !" #
     $
 % & '   
 (     )    
 *    ! +  '%  *  ,

  

      
 .  %/ *  %     %0'  * 1(#%     !

2
   *    ) %     345  (        %/ *  ) 

  % !    4/ %    ) 
    %0'  ) 

     &'     !    '/     ''!     $
 
 6  '

 
  %/%
 

      
    &

 

        !7 &       )      %) 

 


     

!8   ) 9 
 
   )



 
       "!: 
 ! !:

 . 0%     "!: )   ;        

  $%   

%   /     ) 

 %  <    ;       $%

! 2

     


!

 #    &'    


 

 

%0' !
 $%) 9     
 8     
 
%   -    %
 0
 4
 
 !  - 7%    
  @.  
 3    







"
   @   >
 8% 
 
 = -
2
  
  

  
2


%  

-=   

! 
,
 

 A 


  
 B

 
 
 :
% 


 >
 8  ,   
 ,
 !
 /





 


    

 


             

             


         
         

           
            # $

  

!   

 "

   % "   &"    


   

'   # $

    



  "  % "   &"   (


 "   "


           
  
 "                 " 
    &"

)  

*  

' 



 

   

 
  
            
     

 
    
  !


 

 "# 

   
   


  
$ %

 
    
       &'"      (
    ) 

 
     ( *
+
   % "    
     ,
   
  - 
        . * 

        .   %
 

 

-     


 
      
 
    
  

 
    -        %
       
 
#   
 "   /  0 1

     -  
 
 2 $     

 "      
     
  3    


2

   *  

  

   % 0 4 2
  
    - 
 5 ,  

  4$     6 
 

   - 
  1
   !

  7 2
!'





 
 -     .   -   
    

    
  
   

  
  -   5 ,      78$

 79$ )

      
     


 
 $  !

 
      & 

 
    


 
 
     ,
   
 
 "  ) 

 

 0  
























    


  

    

      


        



        

   !"     #"  #" $ 

$  % #"   $   &$    '













   
 %      ) "    $      &  &*


 
+#"   , #"    
+#"     &$   *"     #"   


 #" "   #"
 "(

  

  "    +  +#"    #" - "      "   


 .  "     / 

 )  0   - " 
 #"    #".      *#"#"     1  $       - "  /  !  ! 2.    &  #"  #"      

     )*#"  





+#"

1 

 .

    1 #"
 $(   1   
   




+#"
  




$( 1

#"     ! 2  #"
 #" #""  




 1      !  


   , 




+#" 3  "    


+#"

3  4  5  6    %   "  #". 

        " #"     ).

 0       / '

   

  3  7  #" - "
 8     

 #"        1  "    #" 

* %#"* " $   - 9:   ; "  &    #" /        )   #" 



  /    1    7  #"
 #"

  $#" 

   
 %#"       

4  5  "    /      " 
 1    #" %#"    4  "   

    $(.

*( +    - " "   )  


  &  "  
 #"
 $<    #" "   #"    - "  




      +     1  .

 8$(     

  #"  + #"  #"   -

        #"   #"


    

&

&

"

!'$



!#

"$

!#"

%$

 &



$

Erster



Letzter

& & " !'$ !# "$ !#" %$  &  $ 



 


 
 
       
     


  
 
 





½


 


 






 


 


 



¾




 ¾



    

   

 


   
                      
    
     
 




    


    
 

  

      



 




  


  
     
   
   
 
 

 
   
    
  
   
     
  
   
  
 
 
  

!   
 "



  
 
    

   
 #
 $  
   

   

   
   
     
    
 
% & 

 
' (
)  &( &  ( * $ (  #

 
 
' (
 
  
     
 
 

     $ 
 
   + 
 
(
  +  
   (    

 
   &

!  
   


        ,
-   
   
   .
/ (  "
       
   
+  
  #

 
 )   .
 
 
  ( 
.
( 
 &

 
  
  
  (   
 
 #
 
   )
     
 

 
 
      +  


 
   & 
 $
 
 
 



    ,     
    & 
 #   &


 + ) 
  #
 


 & 
 %  




 

,

 
   .

  

 #

 $
  




  $   
  
 # 


(


- 

  0
   
 
  , 
 
 
  )   
  
 
  
#/  

    
 

    & 
 
#/  
   ,
   
 $ 
(
  
 
 (

    
 
)  #
  
  0
    &  (
 #  &  

     (        1 
   


#
  




    
 
  
  . -

   
 
  #
 

!)).
( 



 


   
  
    
  
  
 
 
     
 

   
  ,
% 
 
   ) 
   %       
 

 
  
 2 
  .
   
 

   
  #    

 
3   
   %        ,
  
  

 ¾    ¾

»¾

 


 ¾ ).
(


 

  

  
 

 4 
   !)

    



    




   

            
        
         

     

  

 
!



"     

      #  "  
    
   $     %  
  " 


    &   '            ( 

 $    )  % * +    ,  "     



    

 




 " 
  
  

  
  

 + #     
" 

 *"    

         -$  . /.
 

 ) " 

 / 
 % #  


(  .    0  ½






  / 


 *
 

"    
     "  .  

 $

 "  #       



   +           

  
    %  

     /
        

  
   

   "     %  "     '   ¾ 
         1  *  ,  




    2 )  '   "   


$

     % "     3    

 

  %    0"    4     


      +     "     %  
    /  
$      '    3    .

  %

  "     
 /  . "      "

     
  "     

   
 
¾

    '   '.

 )  






-0    
5 -
   
*
 (  $  3 .   3 


 







)   5 -


    
 
     '   " 


  

  )  "  
 


$   )   5


¾

   
¾ 
¾

6


   % " 

   %" 

  

   
   "       

 ,

  
 
 ¿

"      
    1
   
   2"  


         
 
 "      

    '0 7% 8 .    
     

"    
   0      '     9  




    

ein O(N3) Algorithmus für P

O(N N)3)

obere Schranken von P ein O(N2) Algorithmus für P

Ps inhärente Zeitkomplexität

O(N N)2)

algorithmisches Problem P

?

ein Beweis, dass P in O(N × logN) ist

O(N N) × logN)

ein Beweis, dass P in O(N) ist

N) O(N)

untere Schranken von P



  
             



 
 ¿  
     
  
  
 


 
 
 
 
  
     
   
      
 
      !  

  
 ¾  
       

  "
 #
 
 
   
 $   % "    
 &   '    ( )
 
  * *+  
 
   
 
    

  


    




   

    
     
 
 
       


 

  





 
 

 
 
           ! 
  "    
  


  



    !  "  
  " 
#


     

$#
       

         
!  "
     "  %  

&  
#   

#


$   

 '

   $#
 
 


  #
 "

 

  
%  

 &  '

 "    
(#            


 )


  "    

  
     

     "         
    
 
 ¾     


¿    *     )
 
 
   
       

"

 &   



  
 "  
   
  )
 
 
  "    

  
      
   


 "  
   +
 
!
" 
)
      
      
  )
  
   
      
 
      "
 

 "  
 !


 

 
       #


 
 
 " 
 
 
   
     
  



 

  
   
  
&   

,  -


 ../   

 

 
 



#  *  " 
"

"      
0 * #


" 

  
  
 
 

   
   '

 
      "
  



0   ! 


    
"
      " 
    
   

   
 1 
"
 



      
       " 
          
 
" 
  



   2  
  


&      
  3     
  
 
 
   
(
   
 
  
" 

   " 
 4 
 

 " 
          
 



&       "


 
 
" 

" 5



   

   


 
     

          " 
   " 
 

6  


 
  

  " 


    
     
 
  


     
                !"  #$
## %    &
   %  
     
         ¿




    

Vergleiche Folgen von vergleichsfreien Anweisungen

Y ist 6-ter in L

Y ist 4-ter in L endgültige Schlussfolgerungen Y ist 7-ter in L

Y ist 2-ter in L

Y ist 7-ter in L



 


 
      

  
 


Y ist 4-ter in L

Y ist 3-ter in L

Y ist 1-ter in L

Y ist 5-ter in L


   
 
 
  
 
 
    
  
  

  
 
  
 
     
 
   
 
 
    
   !"#
 
 
  

 

 

   

  

 

    


 

     
  $ %!
 !
 
 &
  
  '
 
 
     




 &
 
  
 
  
  &
 

 
 " 
!
 
  
 
    

  
 ( 
 %
 )


 *  !  
  % * '
 $ 
 &  $ 
 !  
)  )



  

     
 )   

) * 
  +




 )!" !

  
 )



 
 &
  !
 )
!  % 
 
 
  
 
#  !" *!  ,  !  
 
  '


 -  
  ,   
 
 +   
     
 
    
 ( 
  
     
   
 
    


 


*   ! +*  
! .

¾





¾

 


¾


    




        
            
         
      
                
            
 



¾  
    




    
  
 
      
  
    
  
  
    
  



  

    
  ½ ¾ ¿         
  
     
 



       !   
" #  
$  # %
$ 
  &


 #    $    '
 
 
           !        
 
    &


 (   

    
)  (     
    

 ! 
 

  
     (

  ( * 
+ 
  %  

          , (    (
         
 
          *

 ,   &

 
    ( 
+         

         !     
  
  
    
 
    
 


   ' *  (  -.)   /
     (           /           0   !   

1
    
  
 



       
  
  ½¾¿   2   1
      




    ! 
         1     !

    +   !  
* + 
   

 
   3    4  
  0 ½¾    5         4      
  1
 


    
  +  
 +     4       (
 '
    6   +  
)   7 
 
+


  
 
  4 
 
   1
    1   *  '! 
  
      0     
         +   6      
) 4   
   

  
 +    1  8+        

   " 







 



 

 



 
   



 
 



 




 ¾



 




 
  
  



  
  





   



 

 
 

 ¾



 



   
     
   6
    0   ¾    !  6
  1
  
 
   (+    
 (  
   ! 
   
    /           (+  
   '  (  -.) 4 
   6
  0   ¾
 1
   
   

 
    ! 
       (     ¾
   
+  










!      "  

   
¾     #    $ 
   
    
  

           




    


 
    
 
 
  
    
 
     


    

 

  
  
    
 
 

 

 
 
 ! 
 "

    


  
      #      ! 
    
 
  $  

  %
  
 
 

 
&
 
 
 $ 
 


 
   
 
  
 


 '

  
 
 
 " 
    
 

  
  
    
   



   
   !  ( "
 $  ! 
 
 
 &      

   
 
 
    
           )  %   
 $  
 
   *  
 
 
  +
  & ,    )
 
 
  

  - ! . 
 $  
  
 

 
   %   
       



 /    



 
   ' 0 
  1 
  
 
  $  
     
 *2 )  
 
 1
 ! ! 

  
   
 
   
    % %   
 




 
 
 
  

 
 

 $ 3 "       
 
 
  
 % 

  
 

 $ 3 "

 ! 
 !  
  
  4&  
  
 
  - 

 
  
  
  
 
  
      
   !  
 

  )  +

  
 
 ')

 
 
       


 
  

 ! 
 "
    
 
 
)    
   
 
  $   
.  
  "
   

  
        

 
     ')

    
   

    3 %
       
 
/
    20          5&
 6  
 
 7
   
   
  

  
 / $   

  & 0 

 8
 
       
 9


   
    $  

   
 /

  
 

 5
 
 
 
 

 50  
 
  
 

 
 ' 

  $  
 




    





 


      


  
   
      





  


  
  
    


    
!
 
   "  



 #
  


" 
       # 

   
$ 

% 

 &

   




 
  
 %
  '   
 


        ( 
 %    )



  
  # 


    '! 



 
 %


  
 

  

*


 
 ( 
 


 
 


    $


  
 
 

+
  
 %    


  

", 

 * 
 
 
 "-
&

     .
         "  
 
 / $
*, 

 &

   *   


   
 +
  0  



1 $
 0 % 
 231 ( 
     



  
 "

 

 
)   "
 
      

 


 
  
+

  
 ( " 


$'
4
 
#  
  


"  
 5& $
 ( /

 
 %
 6
  " 

 7  
 " 
  
8 

 

 

  
 8  
 
 %

,  $ &  %




 (

$ %   
 
   
 ( 



   "
 $
  
$'
4 6  
 
 

 
   

"
  
 ) $

0  $  
 )   
 $
8 
 

1 (  
 

 
 
 
%9    :


  ;  
 


 
    




"
 




    

&

 

#

$

'

" !

%

"





 

#

!


   
    
 





 
   
 
     
  
     
 
  
    
  
   
 
 

       
 
         

   ¾  


    
 
 
  
        


    
        ! 
 
 " 
 #  

 $ 
 
 
  %    
  
 &%

  
  !      
  
 
       " 
'
         



                            






 



   



  

        !



  
   #
 ¿   %#  &   ' $(
 %#  
     #  

"  

  $ %#

 %   
%     *  +  

   

    ,     -# )    

  % 

$(  %   # # )            





      

  (

 ( 
       " 
 
 
   
)
  
 "
  *+   *,- 

 

 
 "
 *+ !
 
 
    
 #.$
 /
   
 


 #0$     "
 *,- !
 
  1
!    


 

 #0$ 2 "
 *,-     
 
!    
 ( 
 
   
    
  
   
3 
  
 4

 !
 
  
  
 
   



  
 1

  
    
   
 5(   6
3 
 
 " 
  
 
 7
 
 
 
   



    

&

#





$

" !

' "



% 

!

#



  


   

 
   
     
  
 






 


 


 

 
   
     








 

  
    !" 







 
 
 #   
$

 
 
 
 Ý% 
"  
   


 
& '
  

 ("   







 


 
 
)




 

 *

 

 
   

  
     ("

+

  ÇÆ
 Æ  '
 


,
    -"

. 
  







    -" 

 /  

0
 
 1
  
  

 ,

    
 

 2  
2   

  #  # 
 )


 
   - ("  #

 
  

  
  

 # 
 



  '  
 # 
 
 

    
+
 2
 
 #

 



 

  - (" 



  &3
  Ç Æ "
 '  




 ,

  -"  
  


 
&
   -"  
  




'
+


  
4
 
  
  
 

      ½   



 











.  
  
 
 
  



 
0  


 )


 
5
 6
   .    
 

 
 ,



  
 
,
    
 
%0
52 





    


   
 



        
       
          
   
  

   
 
  !
 
  
"  #   
 $ 
  
   
  

      #  %

   
   & #  
  "   '               ( 
   )
   

   "    #  
 *
 
        )#   +" 
     ,   -  - .  #     
 /
 

  % 
"     #  -0 0  '  "  #  ) " 
 1
 
 "  
   
  )  $   
    )#   1  21
 
3
 
 4 % 
 
     5

 +  "    #
     #  
" 
  *
   
   $

 #
    

 " 
 #  6 
       '" 
       
   " #   
   1
     
 1 # #"      
     
 +  #  
   
   ( #         &"    1
  


     1   
   
    "   *
  
     " #     '  

 #
   7 "  


  #
    
        %   8
    

  
    
 
      
  



 





    


 

9     
    

 +# 

: %     
+
"   -"     ;
 
" # 

    #" 


    




      
  
 

      
   
 
 
    

    


  
 

         





   
 !

      !"

 

   
 
 

 # 
   
 $
        
           
   
 
   $
  

 %  
 



  
     &  
 ' 
  


    !  
 
  

   !    ( $
 
  (  

 
   !      ) *    
)
   

 
 


    !  


 $ + ,  
  

 
 

   - *  
 
   
 


   
  

   



  
 .

   
 %    *   ' 
 )

    !  &  
 .    $
   
 
  
   


     
 
 

  
 

 

 *  
 % 
  )
 

 
  

 
 
*    

/  

     

$
     
   "
 
      %   *       %
        !    !"
* "    ) 

       0    
   
)
(
   ".
(

 
 $
  *  

  
  !   
 
     

    

  
*     ".
( 
 *  %
 
 

   
 
 
 
 
"
 
 
    !       
   
 
  
*  
"
 
 
 -  
   !   
 
     


 
 %.
 
 
  
 

 
 !  
  % 


   
   


      
 
 
     
 
  
 
 
        *    
   
  
 1  ( ) 
 $
    


    
    
 
 
   
  
 ' 
     
  
    
*   #  
   
 
 0
   
       !      !  2 
3 
 
 0
  
  /"
 
 
 
  
 
  %
 (    #  
    !"
    #  

 
  

 

 
 

 


  





 
 

 
!


 È 

 
" ˾ Ì

Ç
Æ ¿ 

 Æ ¾  




    


 


      

 
   
         

 

   

    
 

  
 



 
 
  
 






 
   
  
 
   

 
 
  
  
   
    
   
 

  
     
  
 



  
  
       !
    " 
 
   
     # 
½
 

   $      $  % !$  %    % !$       %        &  '  %       
 " 

   #  


  

   ($             
 
    
 
     $ 
    "     #    
       ($    
 )   &   
 
  !
  %  '
   %   
 




   
 




 
*
 


 




 
*
  *
  * %  '
   %   
 




   

 
 

 *
 



 
 

  +
, 
    -  ' . $  '      
  
  /             0
 
  1&2


 

   0
  .         $    
      .         3& 4 $
)
 +,   %   
  
   '     % 
    
    
   + 

 !$          ,5   %    0  .     




   5 6        & 4 $&

   0          
 
   %    0   
  0    





 

 


 ¾














 













   


  





¾


    




                
    !   
   "    






#                 
   $  %      "    &    &    
'(       &    )  *        + %,
'(   ) -      +       . 

 '(             &          /  )  % 0 % !*     
&  0 % !*    - %      -  1    

  +     2  +     2  +     2

         






      3+    4 - 5 
0 6       *  !          
'(        7         +  

 * )  6  8

 0 % !*            
&  ) -      9:! !;       

    





        %   .  1 




   ) %, +   1



 2



%, +   ! 1






  

2

 


2 '
9            /
      

       ?
#   %  "   6

@  -   )  %                 1 '( 0            = 39  4  6   ?
'( 0                 6   #





    


     

  

           
        !   "       !


    

  # $     

        

¾    
 %  &    '( ) * 

      +
,- .      /( )         $ 0*1

 * )  $     )    2       3 4
5  4
6   

,, .      1    7$/( )        1          3 4
8      !!         
9   2 "

    '1 ( )          0    ! 

 7      12  

   3 4
   

:  $     '  ; '        )
$  

  '( )     1   *
 



     /  7    7  



    




   
  

     
   

  
  
   # $  ! %   & 
  

 
    *

+ !

 )
  ,
 
    
 (

 -./ "  

   " + !






 

+ !


 
  *








     $  ! %  (

    )


 *


 ! "

 '( 
  
 





0 



 



 



 )
  
  !   



  )
  
  !

    "





 




 ! (   
 
 


 1
 2  
 
 
   3 "          " )





 

 
 %


    





  ½

 
   4

%
   6,    
 %



 ! 

¼

"

¼














 )       0  
  


 


 4

      

< 

=
  "   $
      "
>  % +  "




   


 
 
  0#

      

 7  -.89-:;     "  


 
  


  5


 
    

 




 

 

    



   %


. /    )         "      


   : ; 
   
    ,"        1  
 ) > 

.    ) >   
           

 (  5    ?




     


  

   
        

 
         
    
           
  
 
     
 

  



 


 

   

    


   
  
 

½

      
    

    

     

  !
   
 

  "          
 




     !      " 

    #   $          
   %   #  

 

   &
    '           
           () "  
       "      

  *
  + 
       
    *
   $    ,    %   %  -./0 1      2   3
 
 
 4 ) 

 5 6 
           
  $      "    7 
    8   9     

  2      ,   $  
  
  2  ) '    
      
6     "   *
    $    

     $       
  "         

   )     

 :  ;  4
 
 
&  5 * 
&  !   
  " 


 
:  


  


  $ 
 !  

  

 

 /& 

       
 /
 
   9 
B8 C 
 
  - 

9
   

  "D6# E  
   ,/ 
 
  !:
 
    
   0      
  ! "D4# E ,   

 E !  $ )
,
 
 %     ;      2'    
  
  

 
   
     7         
  $ )"    
       
?(
  
     
 #" 
       
    
       7 ) $ 

  (   (   
  ( 
    $              "  )




    )  #  /       $ (@   
   %
 
    /    
    &
)  AB   AC    $ ½



 
 

  
  


  

 
 

  
   



   
 



  


  

 

  

 




   


         

 



 


 
       
     
     
  
     
  
      
 
      
   

 
 
     
!
 
 "  ! 
 





 # $  
  %
   


 

     
 &   

 
   
 
  ' 

  ()   
 ! 
 











  #  
      
 

 
 

 !   

    
   
#         * 
 " #     
 ! 
    
      "
 $  

  

     + 
   
 ! 
   

    
      


     
 "   
 ! 
  & 
       % 
  * 
 
 ,   
    
           
   
       
  

  
    
 
 !  

        $   .  



   
    
  - --    
  

  
 
   
  "   

       
         
 


 
   

   
      .  
      !        ¾ 

!
  

 

   
 
  .$   / 
 
)  
 

 



  
 

 0
 
  $      1 
  
 
 

$      
 


      
    2
 3 !    1
 
   
  
 
 !  
 

4
        
    
   
  !
 
 
 &
  5  
 
   !
      


 %
 # 6 #
 
 
 0    
 
 2
 7 
   0           
  .
 
  !   
                
   # 
  
 

   










 

 
 

 
 

 
 



    
 



    
 
  ¾






   

erster Schritt (N/2 Prozessoren)

zweiter Schritt (N/4 Prozessoren)

log2N-ter Schritt (1 Prozessor)

$21 000 +

$55 400

$34 400 + $138 600 $18 000 +

$83 200

$65 200 +

+

$547 200

$97 650

$42 550 +

$68 550

$26 000



  

     


    
    » 


            

     
 
           
 
      

  
   

          
      

   


          
 



 !      
    

 

     
 "#" 


     $ %  & ' (  
     
¾  ) 
         *    

        


 & ' (     &' %         
    +  '  
)   ,  -

    ,    +   
 



  

 

  .            
   
           ,
 ,


         

 


      
                     
   
   

         
  
      
!   "
 
  
   #
  $   %     

    &
  $  '
  
   (   
     
     
    ) 
      $


      *    +    ,
  
  $   &
      &
     $  &   )
   
  
!     #  
     #
 
   - 
 
    
             
  $  .! &       
         /0!!1
  2
   
 3 *      
 ((     &   
  !
   &
     #      
&
   &       0 0  .        - 
  &
   
  
  $  
   
  
   
  
    
  # !   ( 
        #   2(4  
0   

 &   ,
0
               
    $   &   - 
  0   
      
 5   - 
 0
 *    /
  
      
   ,   / 
        
 ,   $ & 
     


     #   *        5
     $  . 
&           $
 (

  %

     6   '

    787        ,  
 $

    9
       
 -      5
 
    
     5    0 0  . 
  
 
  
 

  

 
    &  
  $    
!  :     #
         ,
 
  /          
   #   
&  
   $  !  ' (   
 
   ,   /    $   #    2    
&  
    ; 1
    # (
     #       0       #   &
  $    
   
 ,  &     
0 
& 
       







  
            ' ( 
    -          6      
 &   .  




   


 


   

 

 
     

   
  

   
  
 
 

 
 ! 


   
  


  

 "#$
 

 

 

 

 
 %


  
 


#  

 

 



 

 "#$
 
 
!   


 

  
 
  

  

 


 
     
$

&
'




   
  
 
  

    

   
      
 

½ 
 ¾   
½    
¾  ! "#  # 


 
  ( 
 ) 
  
 
!  
*
 
+ # 

     
     ,  
 
- 
 #

 

 "#$
 *

..  *

.      $$
    

 ! 
 
  $ / 


  


 


 
 0
 

  
$1 

 -
 




 
 - 


 

 "#$
 

 


    !    
 

  
   ! 1
 %

 


! 
      
  
 
 2&33,  ! 


 
#
  4 0
 
 


 - 
 #
 $  5
 


 
  $1
!   $ $

     $1 '

 



 
   
  
 
  

    

   
      
 

½ 
 ¾    # 
½ 
 
¾    "#  # 


 
  2
 

! 



     
 # 

  
3


-          676 ,
  
 



 5
 




 # 
 »¾ 


  
 
! 
 /

  
  
 5

$

 
  
&
 
3
 

  /

 
 


  

 8 
   
 


 

!  

 
  

 8 
   
 




 8 
    


  


-     
*


 %
 
!
 

- 
  


 %
 


9!
 
 



! 


 

$1$
  4
 
 $
 



         

 

Name

Aufwand (Prozessoren)

Zeit Produkt (schlimmster Fall) (Zeit × Aufwand)

Bubblesort

1

O(N2)

O(N2)

Mergesort

1

O(N × logN)

O(N × logN) (optimal)

parallelisiertes Mergesort

O(N)

O(N)

O(N2)

odd-evenSortiernetzwerk

O(N × (logN) 2)

O((logN) 2)

O(N × (logN) 4)

O(logN)

O(N × logN) (optimal)

sequentiell

parallel

,,optimales“ Sortiernetzwerk

O(N)




    
 




    
 





  


  

 

 

 

 
  
 


 



    
               
      
  


          

    
  
     

   


 !
  
    

  

    
 " 
 
 


  
 
  

   #
$ 


 
    
   %& 




    
  
  
 

 %  
  

  
 
 

 !
 &
  
" ' ( 
 
)   
       $

 
  


"   *
   
 
 




  " ' 
  
       

    +    &
   
    ,%  
 

  ,&    
  -           
   
.
%  
  

 /  %
 
         0
  




   


     

       

 
      

 
        

 
                      
 ! "#
    $
    



           % 

   "& '


    "

          (  
)   *+,- . 
       
     
         !           &   

     
     /      0 

 
1    

  
 2 





    0 
  

 .                       
     3  
)  
         



    3  
)      (4

   
   


"  )
  0 
    #

     5
  
   3  
)     6      /      7  
    5
   
   - .    /
  # 8       4  
     /       2       





     9             
)  



 :

  
 ;         




/ 
   #

   
        »
   )    # #

     0 
  7  
   


   
 &  
 8  
&  B 

  
   





 #
 
  
 + ?   
0  $
 7


      

 
  
  
 

       
      
 

      
  
    
     


 
   
 
 !      "  # 

 
 ½


     




         
 
 
   
     
 
   


  
 
  !  !     "  # $   % !
 &'%  %% %
      %  "   ''%
  %   

    (
   
  
  
 $ ¾¼¼ " 
 
  
   
   )    *   & "    *%%
 +      %
  )
 
 
  % ,    ' * -
  
 
   !    % .  . %

/    
  -
  
 %
 % 01  
2
 % (  . % 
        
  -
  
         %  3

  % -%'

 %    % %'%  4
  &  
  %  ,%     % 5
  (    
 ''%
      ,%6 

     
 


 ,%  *   %   '
  
     *
    %

  
 
   %   7
  
 '
  +       %  %%   
   
  
 
 '   /%   "  8
 +   9 %       
 (     
% "

 % '         $'   %  '
  " 

 ,%
 
 %
   
   


 


 


  : ;
' <
  
    ) ,%
   '
 +
    
 5
  +
     . 6    +
   *
 +
 
    =   ,   ,%
 *  ,%
    
   
      )    ,%
      
% $  '


 +
  %
2  * 
  ,%
  
    +
      >  
   )  '  ,%
  
   

    
     
  ,%
  
  
  9
    +
        '%  
   +
   
    * ,%
    
 +
 
  
 %
       % 
%  %
  '  
 .





    


   
  
  


 
   
 

 
   
 
  

  
   

  

 

 
      


 !" 
 



 # 
      

 
 

$



 $%  
    



    
  
 & # 




 
 
  


 '



   

   & #   

   $      # 

 





 

  
 #   

½
(

  



    & )
*
 





 

 

 



  


)
   


(




  
) 

+

   
 
   *  )
 



 


(

  
,


   ) 
  
   
-
  



     

 
 #  
    
 


    
     
   , 


.-






  
 
 


)



+

  
  /

      
  +

 0
 +

   (    


  
 #  

  


 


 
   & )



     ) 
  
  #   + 

 & # 
         


  
    #   1 2  
 
 )



 

 
 $


          

 
 

    )



 
      


 3   

     






 4

5 


   
 

          




3 
 
   


 465  








 # 

  $        

  



+ 
  
  *     




 7  *  


 &   $
  ) 

)
     

/


% 







8



  )  

  9  


%  

 

% 


)
 

        



   
0    
  ,  




 
$    
  

¾


 
  


  
 
)

      


 7- '  


 )


      
 

   :  

    

9 
 * 0   
  
  
 
: 

  



;
   #   
  #




    



 

 
  


  

  
  
  

  
   


    

   

  
      
 
   !      "   "   

  #   ! " 

 
   
      
  $"    

      %   " 
  &' 

  (

   
 ) 

   



    

 
  
     *! 
  
  
   
 
     
 # +    $"    '  



 
  
 %   

 # ,     
 -   



 "   
+   
     $"    
 $&
  

  
    .+   /  0   



 ( "    +    "

 +  %
      ' 
  $&

' 0    "      $ 

  1

   
  

      $"    
 2 + 
    
'   
   +  $     #    '"

  '  1"
 
!

   3% 4


 " 5

 " "  " 6     41"
!       
 1      " 6     
 /7 " 3'"  " 
 #   $&
 ! 
'     
  
 "  5

 "       "  * 
   " 
    $'    , 1
' 
        (  5

 "    %
      $+      "   "  
     
'+ 
    

        
'  $

   '"

    
 2 +   ""+  

  8""   
   ' 
  $&
    

      
 
    # % 
 
  
 ""   
 
    /7  "    
 



  

 1" 

  %
       

   
   

     
  .   ,0   $ 3'"      1"
 
  0     

 ,0 

  
  "
 9 #  3' 

 "


    





        
      
        
    
  
       
  
  
     
     !    ! "      #
"
   $     %

         
  &

  

 "


 
 #  ' ()*+ ,
 "
      -    #
    

     ' 
  % 
 

       

    .
 
½   "
 
  
          %/
   

    0  -
   "  -
 
  
 %
      
    12
      
3 2 %    
 
   
 14 
 
        5 
6   #   "  
"  7    3 .
 
   %  
 " #  # 
      '  %
   8   
  "     
    !"   
""  "           
 
   9   
     8  :
  '

     ; #  7  "   
    !  :
 '    $     #$ 
 $  " &  



 
 
 

  



       
     


       

 
       


      

!  ¿




    

leer Batterie eingesetzt

Batterie entfernt

Batterie schwach

Hauptkomponente Licht

Uhr und Wecker Uhr einstellen c 10 Min. Min. c

d

c Sek.

c

Stunde

c c

c Monat

Tag

zeige Datum

Licht aus

d zeige Zeit

Licht an

a

b a

b freigegeben

b

zeige Wecker

a Stoppuhr (in aus)

d

c

Null

b Anzeige Betriebsmodus aus

regulär d (in d an) Runde

b

b

b

c

Piepmodus

Wecker einstellen stelle Stunde c

stelle Min. stelle 10 Min.

c

Weckzeit erreicht piept

an

b oder c

still

30 Sekunden vergangen



  





    

 
      


    



         
  
   
    
     !

  " 
   
 


   
 #    
 
 

$


  %
!&      

 
 
 

 " 


 



 '  
 
 

 
      
 

  (
  
   !     
 )    *
 !   

   

 !    '

+
  
, 


 
 

   -

  !
 
  
 
   $

 .
&  


 !



/
 
 0


 
   

 
  
   

 



 


 
  



 
 
  

 
 

 



  

 

 
 
   
 

 
  


 


  


 
 
!


 







    





  





       
   

  
   
          
 

     
    


             
 ! "   
 !
" 

    #


 $  %$$
 &'& 



 $   (     

      


   
 


 
    ) (  $
*  $   +,    
   ,


 
   $  -       
 
*       
 $  

  ½
*          
 
*     $ 
 


   $  

 


 
*  $ .# 
     $

*  $ /0  1
  ,2   $     *  3 $  4   %
$*  
$*     3   
*   , 


   

   ,

    
 ( 5$      6  


   )

 $  ,


 



 $ 
              
 

   


  
 7      5    
 -  


    


    



 .8   

 
 
 


 
 

  


    0 8
$  

 $ (         
   
3 9  
   $            : 
*  

 9      #   $   
    
 
 



      $  
* +    $  +,  
    $*

  +,      1 $* 
 
    



  ;   #  
 (   



    
   <      
       = $$  ,

 
      >
  

 %      ;   
       

  =     
 

$     %
    +   $
   
  ;$ 
         %  $   6

           ;         ; 
  $(   
 
   #   6

  * 
 



     5    

 )   
  < 
 $ =
               

 
 
 




      


 
 




   

 


   

 


 
 


 
 


 


 


 


  
 

 

 
  
    

  
 

 
 



 

  

!
 
 
 "


 

 

 
 #

 

 
   
$% 







 
 & 
 '

 (&
 
 

 
 #
)

 
 "%


 (
  
*



+


 




 
"

 ,
 
  !
  -

  ( 
!
%

 

 
 (
 (&
. (
/
 


 0 
 


 


 ! %
 
 -

 ,
 
  !
  *    1



 !
%

 

 




  

  %-    

 #



  ,
 

 
  (&

 
 2
  2

%


 

 
 3  

 ( 
   
(

 $   
  (
-
 !
 



    
 

 
 
   

4




 
 
 ,

 ,



 


 (
 




%
 ( 
  
*


 



 !
%
0


 

  
/    

   
 5

 
 

 (
 


 
  

3


  $
 (
 
 
   
 &  
  
 # 

  
 
 (
 
 /

  
 #



  
 0 
  2 
%

 

  
!
%

 
 
  


 

   
6 


 
 2%
 
 7
 %
 

   


  
 


  


 "

  
 
 8 
  
9  


 ,
 1

(
 

 ,

 
(&



  

 
 



  "
0 
%
  "

 
 

  

  (&

  



 

 ( 

 "
  


 

 
0   
   
!
%

 ( 


  



 4


 $


 :


 
  


 2   


 

 
   ,


 *   0  ;
 
B -
 
 
    
  
 
 
 
 .  -


 
  
 * 
 #

5 /

    
  
 
 $   
  
  

 
 


5 %  
 !  
    5 3!
 
 
%
     
 #
 




 
?


5 
   %
 

 @
 

 
  #
!  





  5 $ 
 
 
 !
%

 


5

 5

" %


 $8%+&      )   

>    

 !


  6 


!
 3
#
   $8%+&    
 
    
 

 $  


 
 


     




      
    

   


       
 

   
 
      
 
  
 
   

 
    
  
  
       


  
  


       


   !
 
   "      
 #! 
$        % &  
    #"  &  
  ' 
  !()
 




$ 

%   

 
 
    

        

   *
  
  %  + 
  , 



'  
      $     
  

$  
-  $  +
  
 


   !() )
 
    ,   
 
 
  
,   
 
  
. #)

 $    

 /  
" &   #)

  '    & 



      
   ,  
 
 . #! 
$      )  % & $ 

    %  
  


  
   
 
 0  !()  
1 
  

    
 +  !()  
     2    
  ' 

  
       
 
 
    
  




 
"        
   



 


  )
 
   
 
  

*
   *
    
  
)
 
    " 
  
 

 
 
 3 

   

/


 
 


  

!()         
 

  
-        
  %   

 
  
 

/

".

 .   
  4  . )   




 .     
3 
  
  
   !   



(      5


        
%
3  
  

 

3 


     
   

 

   
  $ 

   
(    

  

/   
  


6





 .  7

 . 5 
$       4  . 0 
  
6 

 .   4  . !      5
  !
 
  5




 

 

   %

%  
 
 6


 ! 
6   


½¼ 


      

   $    
  
   
   
+
 
    
   5       
  

                  

(  
 $  




    


                     
             

                  

  

 !"         #
 $  %    

 &




  " '    "    ( 

#  )    $ *   )     %  
  $   " 



    +      

  $  (     ) &        ,      (

 


  "  '   

    - "       

  ! 

." /  " #        0  1


        2     !"  "       ' 3' 3   
&   "            .           %   3 4"     5



    $  

  "      4"  
  &       +  6   .      %    !  "   %   (    

 "
 3

  2    !"   )    *
   

2         

 

     3

     / 
         " "        % 72  3'    8 " 9 23    : 8( )    -     
3

   5 


    5  


      ) 

 
    5          
    -  91 2  .           23    6     .  $   "   %   

 !   .      -   )    

   5      2 &      !  # 3      )       - "

 .       2         2   "      .          "   !"  "    3      2    )   ' 3'                   !  -   2  $              2       #    !  -                               "   .  ;


     




 
       
  

 
 
      
     
   
   
 
 
    
 
 
   
   
 !" 
   

 



     
  # 
  
    
   $
$   
   
 
#  
 
 
 

       

 
 

     
        

      %
 
 

 & '  
   
 

 (  

 )      *   
 + %

 



    

 
  
  " 
  

  
    ,
 &


 $
$  
 
  (   

  
     
 

 
-     
 " 
        

 
 !"
   
  .
     
 
  $
$  (   
 
 

     

  
 
 
 " 
      '  $
$   (      -  

   
      
 
    
 )

 
 
 
 
 ) / 0    1 
  

  
  
 
 2  *   


  3 
 )4   
 
    ( 


  #
  
   
 
    *        
 
    )
 )

  5
  
 
)    
 *
  
 
   
   
  
    )     
 " 
   
 
 6 

%6   
  
  6       " 
     7 8
  
 '         
 *              
    
  9 
 )

  - 
 )  
  : 
 *
   

  
 
   ) 
  
 6 
  ;

    
 
      3  4    
 


 
    (   
 


  


   
 " 
    
  
    
  
   ?    


(    "  ) 
  '    "  


 5

 ?99?

   ,:  > 4 D  
 



   
 

6
 8 ( E * * 7$ > D   F>$ 




   G 
!!" 

H  6
6
5     
   

 
      9#$$ 
 4 ' <
! =   *0    (    &2$$     

** 2,  D    3 
4,      I /$ : J  )

4
#*  !"# $ #   $ 
 %
  ½
8C $ 9 5 ""
  '. 6K 0 ,$    (2 . # <
! =     * B   $    +  2,  8$   $ ?$    ,   1 
(

 <
 G"=    ,   1  +  2,       

   $$  ,   ,   * 0$   ,1 D  02 ' *2
  (

 $ 

   , 0   


$, $    '  <
G=      1?  . $  8$9       $$   *2    > $ >*$   +2   ,   ,    
 . $$   , '    '     8  ,$   +1,1
      + 2,           $$  ,  $
8   *$  > $ 1$ 7 $ 0    ( 

7 $  8
('$      &'


 
 
(     L$
8 I
. 6

  #
 $ .   7-(   "
!" 





   

    


                     
!  ! " #   $! %  $
! &
!  !' ( ) "

 
      "  *$+" *!!
,
-" .// )  0 " 
      
 
       
   " , &    1 (" 232 4 
 $!   5" 

       "
 *$+" *!!
 ,
-" .//.  6 "     
    " ( #$    7 

" 238 *  
" &  9  $!  $!
"      !
 "
 *$+" 6 : %& " 222   ! *  % ! 
 !   

    ! %  $ !  ;$