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 ' ., 2 3 0 0 4 / 2 0 4 - ) 5 $ # ' 0 + / 6 7 - 8 $ . 8
- - ! 6 7 9 # : ) , 8 # / 0 0 ; 9. - # +
# ' , $ # " / 0 ' - ! % . $ 8 3 0 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
: ( . , ; %< # * - . 0 " ) / % # 1 - %
0 # -" %< ) . ' # 5 1 + %
/ % ' . ' # - (= % . > 8 , " 3? .4 ) (= 0 #
6 * , . " . . * # 1 . > 2.
+ 9@AB
½
! " # $ % # & # % '( $ # $ ) * $ $ + # , $ $ )- % ' . ¾ . " $ ' / / ! & $ * '( 0 % 1 $ )) ' 1 1 & # '( * . 1 % 2 1 3 . % ' 4 5 6 ! 7 8 $ * 9 .
: );;)
4 # ! $ !% $
¾
! " # $ " %! & ' ( ) ( ) * + $ , ' - .# # / 0 " # ' 1 # ' 2 " * + * + ( )) * + ( ))) * + $ 3 4 . / 5 ( .5 6/ ! $ ' ( )% * + - ' .# 5 !7/ ( .# 5 !7 8 ' 1 / ! 9 - ' " ' 1 8 ( : ! # ' $ ' ( )% ( " *$ ;;+ ' $< 7 * $ ;=+ ' >
' 6 $ ' ( ? ! ( % * + " ' 8 6 . ) / $ ;@
$ $ ' & $ ;, ." / $ ;3 .A' "</ ) % # 8 - " < ) $ " " ' "< B % ' ! C (B
D " < 5 B 5#8 ' ! # < $"8 # $
!" # $% ! & " $ % ' ( ) * $ + , - . / - 0 - + ( / 1 - # $+ 0 2 2 3 " ! + - ! 1 " - $ ! # +
" $ 4 + 5 6 7
% '
* ,
8 89+ " 9 : ; : /+ 9 ) ; , " 3 " &
- < < " -
* 3 = (
>??@
+
9
;
X
c
;
<
>
X
O
@
;
X
;
>
D
H
c
D
G
D
9
X
^
<
J
D
[
@
X
O
@
@
;
O
D
D
>
<
{
>
^
;
J
;
>
Y
a
@
J
c
O
U
>
>
;
;
c
E
O
O
a
J
>
[
>
a
5
7
/
5
;
O
<
;
O
E
J
J
@
@
V
D
E
<
>
@
X
O
@
;
O
;
D
O
;
@
c
D
>
U
@
<
V
k
;
X
E
D
@
>
;
Y
<
X
;
;
>
@
<
;
m
@
O
c
o
;
O
[
[
M
U
D
E
E
H
_
E
m
\
<
E
X
>
O
;
@
>
O
@
;
U
@
>
;
n
^
^
<
_
`
J
D
a
o
O
;
;
E
E
a
;
;
O
V
E
;
>
£
;
<
;
D
D
V
;
O
@
O
@
X
;
}
;
<
D
_
z
<
m
O
J
U
O
V
<
J
^
z
O
O
E
<
M
X
a
;
}
O
c
o
;
<
;
J
a
O
E
J
O
;
X
;
;
E
;
@
{
O
V
;
;
D
<
>
D
<
o
X
X
>
}
@
O
D
;
O
m
J
<
<
;
;
@
<
D
M
>
;
J
E
<
E
<
;
o
;
O
>
;
c
U
r
;
H
U
E
E
;
c
O
j
U
a
O
c
O
U
;
E
E
U
@
H
E
E
O
X
X
;
@
X
a
O
<
J
@
@
;
O
D
@
h
J
U
H
U
;
a
>
^
O
c
a
O
;
c
D
M
E
>
¡
^
@
O
;
>
E
E
E
O
X
a
X
;
J
H
E
`
V
a
O
U
<
;
;
<
V
E
9
E
;
j
@
>
;
@
G
>
E
D
O
j
m
;
;
X
<
M
¡
U
^
<
a
_
X
U
E
O
^
>
£
@
D
E
X
<
D
@
E
;
V
<
;
;
^
m
U
[
@
O
_
h
M
c
<
X
`
M
h
z
U
h
^
^
G
[
¤
H
c
E
D
`
D
k
<
M
9
E
x
<
E
E
;
U
a
O
^
X
O
D
E
<
E
¡
>
o
c
;
J
;
;
M
o
<
@
V
r
X
c
>
<
E
@
E
o
E
;
_
;
G
r
E
s
;
o
;
;
D
E
@
;
O
;
c
<
M
D
M
J
@
X
;
O
X
;
D
J
E
>
J
;
c
X
@
J
H
;
E
¡
<
O
E
E
}
;
;
O
;
a
w
}
U
<
E
D
E
O
V
E
<
O
o
[
D
O
@
;
;
@
E
<
D
J
<
;
;
<
X
E
D
J
J
>
;
>
>
a
;
X
M
@
V
a
\
^
;
;
O
z
E
O
r
z
>
@
c
H
>
J
H
>
@
u
E
E
E
>
X
a
;
O
U
M
U
;
E
;
V
z
E
@
X
[
@
@
@
@
M
;
O
O
X
<
E
@
G
O
E
>
J
E
@
a
D
k
O
\
@
E
J
U
m
;
;
;
;
@
o
;
`
D
U
m
<
>
^
<
H
M
E
o
_
<
<
D
>
r
c
;
;
@
c
D
E
O
<
;
<
;
<
H
;
@
>
;
^
@
X
E
;
^
@
;
>
o
U
@
J
E
;
O
U
;
j
r
;
X
h
D
a
J
>
@
ª
^
_
@
;
c
<
;
;
E
<
E
<
m
;
<
@
E
;
>
o
;
X
>
;
c
;
O
V
>
^
c
a
H
J
<
U
[
>
D
;
>
E
>
;
O
E
J
>
E
<
H
;
j
H
E
E
O
M
;
D
o
;
o
;
E
^
@
>
;
@
O
>
@
r
<
^
;
;
E
O
<
V
@
;
c
;
J
O
<
E
E
;
>
;
@
E
;
U
¨
¡
}
O
J
^
;
_
;
D
<
J
>
H
E
;
O
D
@
c
D
;
E
E
M
>
E
;
X
>
c
X
o
>
@
>
M
D
@
U
k
^
<
D
r
r
E
¡
m
;
`
_
E
>
;
>
X
@
;
o
J
;
E
`
V
;
;
a
U
X
H
<
U
<
<
V
>
E
E
;
c
H
>
O
c
D
@
D
E
M
;
G
J
U
>
D
G
D
D
;
J
X
X
c
O
`
D
;
;
;
X
r
<
^
H
;
O
D
h
o
<
n
D
O
;
;
c
X
§
X
U
U
;
>
V
h
J
j
<
<
;
E
E
J
;
@
;
E
O
m
X
H
>
r
_
E
U
<
;
z
;
>
;
h
X
D
_
^
[
V
<
X
;
O
;
;
E
<
O
@
J
X
;
X
U
H
a
o
<
@
m
o
>
;
@
;
m
@
>
U
V
E
E
D
>
c
^
;
J
D
z
\
^
^
D
a
E
>
z
D
<
E
n
O
U
X
X
D
;
c
u
J
>
U
E
r
;
a
M
G
;
O
D
O
O
O
>
E
M
E
9
;
O
<
;
;
>
;
>
;
c
E
;
>
Y
X
D
<
>
M
X
O
^
D
>
D
G
@
X
<
E
>
M
V
;
;
<
D
<
_
D
<
m
U
H
;
H
_
G
@
z
^
[
c
>
E
D
«
c
D
O
;
X
9
D
J
G
}
a
E
J
J
H
O
D
©
V
-
Q
>
<
G
U
O
;
E
J
<
X
O
<
U
E
O
E
a
D
^
}
<
;
;
;
;
E
[
D
<
E
E
X
D
U
E
X
^
{
H
c
@
>
9
E
3
r
;
O
X
E
z
>
;
;
O
V
j
E
<
E
<
;
U
D
O
;
E
c
E
<
<
o
;
;
O
<
s
>
@
E
;
<
;
M
k
X
;
O
;
@
<
H
;
O
h
o
<
H
;
M
E
G
D
M
;
U
E
D
E
E
X
o
}
;
D
c
D
;
^
J
;
J
;
<
E
X
>
@
c
;
X
U
>
J
9
E
D
a
a
o
@
E
D
;
E
1
D
H
;
h
;
;
;
;
@
M
@
D
X
@
>
M
D
9
a
@
E
U
O
<
U
<
}
E
H
O
>
E
V
X
;
M
_
;
;
;
M
D
;
c
M
;
j
J
O
j
X
;
a
O
@
H
G
>
;
^
@
E
J
;
@
O
@
@
@
O
@
G
E
c
;
O
;
a
;
U
o
<
c
O
c
;
X
D
;
^
<
/
*
9
@
E
9
;
(
;
<
O
'
>
h
<
>
D
M
@
;
%
>
s
;
>
;
D
#
<
E
;
"
;
E
X
!
<
;
O
-
X
D
@
;
z
r
E
V
<
^
E
6
7
P
Q
/
+
k
`
A
%
%
,
6
%
r
t
*
H
%
s
k
(
C
(
%
H
,
l
%
k
t
(
#
k
K
-
#
!
(
(
%
(
C
!
%
%
R
*
(
C
i
(
#
%
(
%
/
P
k
%
*
k
u
/
M
/
%
`
k
r
/
!
+
H
"
s
!
+
!
"
Q
*
*
*
h
r
A
!
/
+
(
/
P
%
/
%
%
%
$
+
*
!
i
%
!
+
6
%
*
%
*
o
P
%
!
*
*
M
%
H
/
K
5
M
+
+
i
*
%
K
3
,
6
>
+
U
E
H
*
%
-
(
*
+
/
/
%
#
*
C
5
(
!
Q
g
/
+
*
*
(
>
H
#
%
%
#
-
/
!
,
5
(
5
*
+
(
+
,
l
*
%
*
W
,
%
*
E
(
(
k
%
+
%
+
>
i
/
*
*
C
(
+
+
#
+
!
*
%
U
R
%
%
C
*
,
E
#
A
5
*
+
/
C
#
l
!
+
%
+
/
R
%
*
+
h
#
*
*
/
p
!
!
>
f
H
H
h
`
*
P
!
+
l
%
#
/
%
g
+
M
M
(
,
e
!
%
5
d
*
C
*
P
c
*
,
+
m
(
a
+
W
(
,
/
+
R
g
k
*
5
l
#
6
,
H U
k
5
(
$
,
*
/
!
!
,
-
>
$
K
l
.
5
5
0
2
-
(
!
A
!
3
H
5
-
H
*
i
-
.
f
(
P
!
$
H
R
%
"
/
%
*
+
!
/
!
Q
!
!
5
!
+
C
/
A
+
%
%
R
%
/
+
w
%
g
%
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
!
º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
" !
º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º
#
$
%
º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º
º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
!"
!
"
º º º º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
" #$
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º
º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º
#
%
! "
# !
$ ! " % " &
'
( ) #
*
" ! +
# #
! ' , "
- ) . "
" ! / "
0 "
" !$ * " .
, 1 , $ ! "
"
2
" ) * 3 4
" 3 4 5 )
" ' -
# ¼ ½
%
( )
$ ' " " 6
klappe dieses Bit um
falls dieses Bit 1 ist, klappe jenes Bit um
setze dieses Bit Null 01011
klappe dieses Bit um
01011
01011 falls dieses Bit 1 ist, klappe jenes Bit um
setze dieses Bit Null 01001
01001
01011
01101
01001
11011
Umklappen
Nullsetzen
Testen
! " #
$ % & '
%
$ % & ( %% $ ) )* +
, - . +/ ( $% * !
+ . $ $ 0 1 + $ /$ % "/ $ 2 % $
3 $ $
+ - + 3 3 % $ " " # 4+ ! ' "/ $% 5 $ $ 6 $ ! $ 7 8 9 / % (% $ & * :0 ! %$ $ 1 4 8 9 7 $
7 % ; 2 7% / $ $ % # < # $ % ; $
% < 4 - $
$ 2 % %
Zutaten
(Software)
(Hardware)
Rezept
Backofen Utensilien Mensch
Kuchen
! " # !$ " ! !$ % % ! !! !$ %
& ! " ! " '
( ) * " " % + , - $ '. ! ( * " / $
0 & 1 !$ 2 ! ( * " " 2 0 3 - " " !$ % ! " .
(" " % !$ / " 04 !$ .
!
" # $ $ %
" $ & !'
( $) * # ! ' + , -
'
! $ $ $ . /
0 * 1 ' # 1 $ 2 $ 3 # % $ * 2 - '
3 * $ 4 %
* 0 ' 5 1 6 0 & 7 1
"
. 8
8 '
* / ,'
8
$ /
* $ % *# ' - 8 9+ :,
8 ; ,
(' ' * ' 0
;<½ 0 '
* ) * 9 ' % ) 1 # =
8
- !5 /
1 '
9 ! $ = 1 >
$ 1 ( $ # '
$ 8 ' " > " = , % *
! " ½
! " #$ % $ #& % ' ( ) ( * #$ + % * #, % #- % #' ! % ' . / , ) . . (0 - $ " / & + / ' 1 2 $ " 3 * 1 / & - 4
* & ( $ + , ' " ! 0 ) 1 566 766 1 8 & ( *
8 . 9.: 1 ! 8 . Ü Ý 8 1 Ü Ý * 8 +
. ! " * ' ) ! ' ; & &+
+< = > ? + ( 3 & ! ! , + ; # % @ ( +< = > <
3 A ( & - BC6B " +& D ' !
! "! # $ % & ' ! ( )*++ , "- # & , " . # & - / . % / 0 !, . &/ 1 2 $ / 3/ ! , ( 4 5 5 $ 6 7 ! $ . 0 / & , 6 ' & ! 8 5 0 0 !. & 9 0 0 ! % 6 % & - & % 1 0 / ' 0 / $ 4 4 , 0 !/ / 0 : : 1 )*;<
8 );=< 1 !/ 0% . , / ( : / ! 5 0 & , ( /$ $ 6 /9 % $ 7 4 1 . 1 % $ 4 & / , 1 0 ( 6 / );+< 1
5 6 , - / & 0 / $
! " # $ % & '( ) $ *+ $ " # $ # $
, & % -./0 -.10 2 3 & # % # 4 & 5 ' 6 # ) # # % 7 # 8#
, ) , 5 % 5 6 3 & # "( # $8 3 7 ) % % 5 # ) # $ 6 $ "
% # , ! 9 (6 ! " (6 $" % 9 -.:0 -.;0
2 3 <"= 5 <" => " $ " 8 ? " # 3
[email protected] A A , # " % B 4 5 # # # % # " -.10 2 # 2 -.1@ $" 6 C # ' C 7 % 6 A D # # 3 # " # # # -.10 2 E $ $
-.F0 2 3 '
3 5 # > 5 G C A( %
& %# C
!
" ! # $ % &
% ' ( ) * % !
( + , (
-!
- . % / 0((
1
2 & % " ( % 34 ! % 5 % ! 2 ' # - (
+ " 5 6 7 6 6 ( 2
! % 2 (( 8 $ % $ ) 5 ! -
9 $ ((
( 2 ( 2 1 # % "
% ( & 1 ) - %
9 1 : 1; 1 < ) . (( / = > $ ( ( ! ) 2 = > ( $
( & ( 5 ! ( & . (( / % 5
# % ( 9 ' 1 5(( ( & (! "( & # # ' !(
! ! ! " !
# !
$ % ! & ' ! " ($" ! ) * +' " ( " !
" # , " ! - "
" ' ! , .
/ ! ' 0 # 123( 4
" 5 6 " ! /(" 3( ,
7 / " # ! " 8
$ " 7' 9# ( : ! " # !" & !
" ; 7 4 # & !( !"
< ' =! " # 3 12 7 < ' " # " $ $ 7 # -
3 ( 8 ! ! =' = 4 ' /
( " 9 . (
7 " !
# & !
123( . " = ! " % !
# - !( ( ( " ! & # - !
( 4 1> " " ! '
. % #
% ' 7 7 ! " 8- ," 1?@A # @B9# = C % C 2>D " 2 ) -
) " E % !# . !
! " " # " " "$ % & ' ( "
) "$ ! * + # " ! "$ , " ( "
!# " ! - . !
/ 0 " ( #"
1 2
!" #$ %
" " # % &
%
% ' ( )% % *% + % , "
! " " " - " " # . /
% ! 0
% $ " % % #1 2 " / " , % ! % + 0 - " #1 2 % " . " % 3 " * ! #1 " " " /% " ! 0
% "
. "* % " " ! % " " " /% " !
1 4 &
0 ) " !
# 4 56
" / "
% "
"* % "
# . " 5
7 % 0 "
!
" # $
% & & ' ( ) * +
, , ! !
+
! , !
+
" -
, . # / . ! *
/ . /0 , -
1 #
. + / - 0 2 , 0 ,
# * * ,
" 3
4 , * ' -
*-
* ! 5
& 6 &
7
8 1 # , 9 & & * + + + -
6 5
# % 6 6 & # . !: /
$
!" #
$ # % & # ' ( # ) " # # $ # # # $ # * *# + &# # , - # . $ (/ # # # # # 0 # #
1 " # !" - 2" - 23 . $ &" $ # # # # $## . $ ) "# 0 4 # # ) " ! # % 0 ! # 5 ! # 6 5 . # # - ) " +## 0 ' # & !" " . 0 6 # *- 5# & 4 !" # % 5 # $# !" 783 !" "# 0 # ' # 1 *## # #" $ # $ & '" 4 9 5 # ) " " $ " $# 9 # ## 4 3 # 1 $ , 5 "# ( # ) ## 6## $ 6## "#- # #
! " # $ % & " ' & " '( ) * + $ , * - + * # . + /" + 0+"12 + + % +" .* , & ) + ' 3 ' + 4 + & +
+ 3
* + * & + + ) 5 6 7 3
8 & ' 3 9 3 % , * *
'
! ¼
! "
+ *
, 0 1 - + & . ¼ % ) /:2 - * % - .
Start
Name
Gehalt
John Brown
$21 000
Jack White
$34 400
Mike Green
$18 000
Joan Silver
$26 000
0
Wert der gemerkten Zahl
21 000 55 400 73 400 547 200 Ende
!"
#
! # $ %" # & # '
# " ( ) ' *) + ) % # ) % ! , - ! # .% / # 0 % +
$ *) ( $ ) '0 % ' # $
# + ! " # , * + 1 ( " ( 2 ' 3 # %" & # %# ¼ # # & '# % - # )# ) 2 ) 4 ' # ) ) $
jede zulässige Eingabe Spezifizierung aller zulässigen Eingaben
und
Algorithmus A
Spezifizierung der gesuchten Ausgaben als Funktion der Eingaben
gesuchte Ausgabe
algorithmisches Problem
algorithmische Lösung
!
"#
! $ % &
! '
(
) % * ! % % + '
% , - . /
'
! $ 0 1 ($ 0 1 2 ! 3 &
. /
0
2 3 !
4 5
! 6 $ &
! ! )$ 1 $
+$
(
$ 1 % !
&! $ ! 4
$ ! -
% ,
(
7 $
! ! * ! ' 8 $ & ) ! + ! ) ! 9 +* !
!
! " # $% & ' $ ( ) # * + ,- $ ' $ ) $ ' % . ) / ( 0 ) $ 1 234 ) ' , $ * 5/ + 6 ( , 0 $ % ) 5 ' ( +0 - # ( 5 ) ) 5
$ ) $ ) , !
¼
' 5 % ! 0 ¼ ) 1 7 4 % $ #$ ' ) 8 % 8 . $ 95 5 ) ' ) 5 $ ) $ % . $ 9 5 ) 5 " . $ ' 5 5 ) , $ / ( $ ' ) $ 5 : ) $
! " # $ ! $ % &
# ' ( ) *+ ! &
, ! % ( . " / $0
/ 1 ½ 2 0 ¾ 2
. % 3 2 $0 /
# ! 0 / % 45 6 & !2 0 / 0
( # , 0 ! 7 .
!
" # # " $ % " & ! ' " (# ) &! # * ) + # # & # , - ) & , ) & . & - / . # * , ) . + # * & - / 0 ! . . # 0 & ! " ! / & 0 1 & 1 0 . 1 " 2 ! 1 " +* 3 ) ! / # ! # 2 * /
" 2 ) 2 4 " ! &
3 ! # 1 ! . 0 & " . 0 3 ) ! )
5 !
2 ( ! " # # & ! & ! $1
! "
# $ % & '
( ) " *
+ ¼ ,
) - +
.
. " "
% *
/ ! &' ! 0 &( '
% " * "
! " ! " #$ % & "' ( )
! * + ,(- ! ". ( !
" ( ! " ( #/ (
0
" $ 1
".
, % 2
3 )( ( ' 4 0 ( 4 5 ( & '
, 0 , ' 3 )( & 6 ( ' % 7
! ( 2
! & ( 0 ! 7
1 ' 8 , 90- ( ( ' 9 ( '
) : (
!
" (
(
"
! " ( #, 6 ,
".
' ( 2 ; ' 9 ( ( ( : '
! 1 5 %( 9 '
" - ( , 5 " 8 ( / ( ! ' ! 6
5 & , 5 9 (
, & '
! ¼
! ! "# $ ! ! % &
" # $ % & '()
* '(+) '(() " , % - ., $, & , '(+) '(() # # / , 0 # , ' ) * , '+) # % - " 1 - " 0 '() 2 % $ % - & , # # 3 4 " , - 5 , 6 % " # 4 3 , 5 "
- , , #7 0 , , - / - # # ! $% & / , % $8 & - 4 #
! " # $
% %
& & ' & (&
&)
* + &
" + , -
* & &
+ . -
%
)
*
%
- % (& % / % 0 % 123 4 -
/ (& ! - )
& .# 4
#
.
&% 1 &) 2 - 4 (& . (& )
* - & 1 5 2
! ( )
* / "
1 2 -
%
& -
(& ! . 0- 67 &
- 3
5
$ - !
%
8 &
! )
+
. % ! +
% 5 9 - : . & & 4
%
+ )
. % 5 . % 8# & +
,
; :
0 8#
$ 3
. % ! . & #
%)
8
! & ( & & ! & % + ! &
½
½ ! ! " ½
dog
dog
dog
body
body
typical
typical
typical
body
typical
typical
typical
typical
dog
dog
dog
sun
body
body
sun
dog
dogma
sun
sun
sun
sun
body
body
sun
dogma
dogma
dogma
dogma
dogma
dogma
Ende
Start
Start erster Durchlauf (a)
Ende zweiter Durchlauf
(b)
!
! " # $ ! " % & $& ! ! ' " ! ! " ! (! ) * + " , + % ! - ". ' & /0* , % ! ! ! ! ! ' *% ' ! 1 % & % -! " , 2!! + % ! - $ " 3 4 (! & /0* , " 5 % ! ' 6 " % ! " + ' & /0*, % ! ! & * 7, %! $ ! ' % 6 8 9 &
& ' 8 ! 9 - " & ! ! " % ! " " ! " - ' " : " ; + ' ; & " % ! ! !)" &
24
78
78
78
78
78
12
24
69
69
69
69
78
12
24
46
46
46
14
69
12
24
26
26
26
14
46
12
24
24
8
26
14
26
12
14
69
8
26
14
14
12
46
46
8
8
8
8
Start
Ende
! " # $%
! "
#
& ' & () * + ,-. + - + ,-/. " -/ # 0 & & 1 2 // & " # # ,-/. 1 ' 3 2 & 2 , . 4 1 2 ) " 2 3 1 ' , . 5 2 ( * # ( *
! " # $%&' ( ) $%&' ! *+ * , - . / + ** ! 0 . 1 . . + ! . 1 !1 2 / ! * 0 3 1 - 1 ! " ! 4 * *+ 5 , *+ $%&%' $%%' $%&' ! *+ $%&%' $%&6' *+ *+ 5 ! 7 . $%&%'8 $%&6' * 5 , . ! 4 - * . ! 9** - : * ;1 " * *+ . ! . +!* 1 9: . * <+
- , 4" = + / * . > * *" 4 . * ( *+ , 9: < &6 *+ 1 / &? * - - . )@ . > ( * . )@ . )@
Start
notiere 0; zeige auf das erste Gehalt
addiere das aktuelle Gehalt zur gemerkten Zahl
Ausgabe der gemerkten Zahl
JA
am Ende der Liste?
NEIN
Schleife
zeige auf das nächste Gehalt
Stopp
!
" ! " # $ % ! & ' ! ( ! ! ) & *!! $ % ! " !!&
+ & ! ! , , & ( - # "! . ! % % ! ! ! $ ) ! ! ! "( & # " ! ! *# / # 0 ! 1 ! !& # ) " ! !2 ! #3 4 +! ! ! # ) " 5
Start
notiere 0; zeige mit P auf den ersten Angestellten
JA
addiere Ps Gehalt zur gem. Zahl
Ist Ps Gehalt höher als Qs?
Ist Q unm. Vorgesetzter von P? NEIN Ist Q NEIN setze Q auf den am Ende der n. Angestellten Liste?
NEIN
äußere Schleife
JA
innere Schleife
zeige mit Q auf den ersten Angestellten
JA
JA
Ist P am Ende der Liste? NEIN
Ausgabe d. gemerkten Zahl
setze P auf den n. Angestellten
Stopp
! " # !
! " ! # $ % &' ( )
½ * '
+' ! , ' ¼ - . % . ' ' &' /
' ! 0 1 - 2 ( ' ' ! &' 3 ' ' * 1
'' 45 , 0 ' % ' ' 6 1 2 7' ! ' + !) 3 '
2 0 ( ' + &' 2 . ' 0 '
+ 8 !2 * , 8 " 8 &' 0 9 + ' 2 2 ": . + / ( 9 2
' 0 9 !) -
; !" #$ % & ' $ ( )*
0 + 8 9 ! 0 1 < = < = > '' 45 '' 4? > 9 0 "
' ' 2: 9 ' 2 ' ! " 9 ' 9 ' ! " '
Start
initialisiere Zähler und Zeiger
überprüfe die nächsten Symbole
Suche nach dem ,,Geld“
,,Geld“ gefunden?
IM TEXT
NEIN
setze den Zeiger vor (überprüfe auf Ende des Textes)
JA TEXTENDE gib den Zähler aus Stopp
überprüfe die nächsten Symbole
Suche nach dem Ende des Satzes
,,. “ gefunden?
IM TEXT
NEIN
setze den Zeiger vor (überprüfe auf Ende des Textes)
JA
TEXTENDE gib den Zähler aus
Stopp erhöhe den Zähler
Start
Unterroutine search-for X
IM TEXT
überprüfe die nächsten Symbole
X NEIN gefunden?
setze den Zeiger vor (überprüfe auf Ende des Textes) TEXTENDE
JA
initialisiere Zähler und Zeiger
Aufruf von search-for ,,Geld“
Aufruf von search-for ,,. “
gib den Zähler aus
kehre zurück
Stopp
Unterroutine
erhöhe Zähler
Hauptalgorithmus
! "# $ %
& ' ' ( # !) !(
* ) + * # ( , !
- . ) # )( ! / # ! ) ! - ) ! -( )
! 0 # " $(# # 1 2
! " #$ % & $ ' ()% * &+ , $ ) !( - # . & / " & , " $( 0 1& & % 2$ , ,& & 3& ! %. & " 4 2$ 0 ' 5 6 $$ " ,& . 1 & &7 ,& 4 $ . 5 1& 2$ & " $ 7 ( % ! , ! 8$ 1& % , 9" . & & ) % % %
, : %( & 2$
$% & - & & / " & ; ; & , 4 5 7$ & " % $ , :$( ( & && !$0 % ($( & &" ( # & & & ,& & <( & $0
! " # $ % & ' % ( ) * * $ + $ ,- . !
/ - - 0 - % $ 1) 0 ! 234 22 ) % - 5 # & 0# '- 0 ) % ) - $ ) 6 # 1# #
/ * ) $ - ) ) - # # $ 7 - - 7 6' 7 # - - # 6' - - - 7 '8 0 * 9' 7 1 / - # - 6' / ) * - . + ) $ , ) : ; 7 <) ' - # 7 = ) $ 0 7 - : ) > / ) 7 5 : 0; * - : - - !# - * ! % - # +
A
B
C
!" ! # $ % $ ! & $ $ !% '
( $ $ " # $" % ! $ ! ) * ! $ + + ! , - . / ! $ 0 ! " / ! $ !! 1
* . $ !
$ ! 2 $ ! ! ! ! ! ! ! ! #!! ! 3" ! 4 ! 5 & * # " 6 , -7 ! $ ! " ! 6 ! ! ! $" 0 6 $ $"8 $ ! % $ & ! 5 7
! ! $" 0 5 /
!
! " # ! $
% ! &
# ' () *
+
' $ & ! +
( *
! ," -
.
! . # / . $ & "
½ ½ ! " !
! 0 %
# + .
() " *
, .
1 1 2
. , , /
( * 3 . " 45
Stopp
Start move 3 from A to B using C
move 2 from A to C using B
move 1 from A to B using C
A
B
A
B 1
C
A
C
A 2
move 1 from B to C using A
B
C
B
C 3
move 2 from C to B using A
B
A
move 1 from C to A using B
B
A 4
C
A
C
A 5
B
C
move 1 from A to B using C
B
C 6
!
" # $ #
# ! %& $ $ " #
' ( # ! # # # # #
$
# ! # ) * + ,
-
. / 0
1! 2 # 3 "
2$ 4
A
B
A
B 7
! " # $ ! % " & ' (" & ' ) & * ' ) " " + , , " * " ( , - . ) /) 0 *, " ( , 1 2 , ) , " ( . 1 " ! & + ' - ! " ) " 1 ) - 3 4) . , - 5 , , - " ¾
-" #"
#" " , . * 6 / . 3$ 7 7 . " $ ! 7 5 ) ! 3, ) 2 6 " " " " 1 ! " #! $! % &''(! ¾
¿
!
! " ! # $
% & !
'
! ! % ( ) *" + % *" % ¼ % , # # - ! ).% % / ' 0
- ).% % 1 0% # ' 2 3 *" % 4 5
0- % "' 1 % 1 % " ! 0% 2 ! % % *" ' 0% 6% 7 )
$
% '1 % 8 9 .% ! 0% ) ( * % ! * 6 :
! 0% ' " : 1
* * 6 ( ) ) ; - :
"4 6% < ¸
¸
¸ººº¸
0- ( ;
% 2
'
¿
! " # $ % ¼ & %! ' & ! ( ' % )& * ' + ' , ! ' -
% & $ %& " " % &
' ' ' , . !
/ 0 1 - - , $ ' ! ' ' "
' $ # 2 3 3 2 4 $ 3 , % & 3 - % &
3 5 5 ' ' $ " 3 6 $ ' , ' ' ! 7 8 , % & 6 $ 8 + $ ' ! ' ' - $ 3 % '& ! , . % & % &/ $ . / ' . % &/ ' ! $ - %& ! , 3 $ 3 9 0 1
! "
# $ % & '
$ ! " # # $ ( &
$ ! " ! " ! " $ ) ) * + $ *
)
! ", # + # + $ % - !+ ". ) & / ( ) + ) ) 0 / $ / 1( % % / ( 2 , $ $ / (
% $ -'
3. ) ' '
2
) $
$ - .
! " & ! " 4
! " # $ ! % " & $ '( )
* + " * , +
" - ) ". /0 " 1 +
% )
$ (" ! 0
2 3 +
" ' ( 4
½ ½¼¼
4
½¼¼
#
% ! ( #
( "
* #
$ " 0 % " " ( 5 0
% 1 % % %#
) % 0 6 7 $ $ % #
( 8 7 8 $% ! # ,( 0 " ! # * " ' ! 0
Variable
Vektor
Feld A[1, 1] item item
item
item
Datenstruktur item
item item
item
X
V[1] V[2]
V[N]
item item
item A[M, N]
Etage 12
Hotelanalogon
318
301
302
348
Etage 2 Etage 1
Hotelzimmer
Hotelgang
gesamtes Hotel
entsprechende Kontrollstruktur Anweisung
Schleife
verkettete Schleifen
! " # $% & '( $# & #
' )
*
# + ,+ " # + ,+ - . /01 ) ) + " 2 #
( 3 # + ,
# ( + # +
# ( + 2 ) ! " 2 # 4 #
5 #
" - 3 ! .
+1 6 7 ++ # ++
. )
item
item
item
Zeiger
item
item
item
item
item
Zeiger
item
item item
item
Zeiger
item item
item
Feld
item
Vektor von Vektoren
! " # " ! # &
$%
# !
' # " # &
%
' (# ) # * & +
& #
! # ,- ,."- ! & #
*
/ ' 0 # * ,."- $ #* 2# *&*# *1
* 3 4 " * 3
* 2 *&*# *1
4 "
5 4 "
*
2 3 6 # 7% 8 $ 4 " " * $ ! "
Eingang Eingang
Ausgang
Ausgang
Ende
Kopf
Warteschlange
Stapel
! " # $ " # % & ' $ $ $ ( ) % $ " * + ! ," $ ( - $ +
. / # $
0 1 # 0" 1
# 2& & ," !
! 3 ( # $
0 1 -
$ , # )
" . # 0 . 1 - $ $ * & " * $ 4 ' 5 ! & 4 " ' " 6 " 6 " % $
! $ %7 $ ' 5 .
! " !
#
$
%
&
#
# '
!
Ebene 1
,,blink“
173
,,door“
54.2
$20
Ebene 2
Ebene 3
,,what“
,,why“
Ebene 4
! " # $ % %& '
(
$ ) ) & # ( "* + $ ' , # % , - # - # . $ * $ # /0 #1 / ! 1 / " , # 1 /" 2 $ # ( 1 0 0 ! # / " # 0 1 3 43 #
5 6 ) , $ $ 0 & , " # 7 8 " $ " # # * # 9* : . 0
0
(
% # % : &
;
#
! !
"
# $ %
# & $ % ! ' ( $) ! & ( * ( ( % #
' ! ( ! +% , % % ' ! % % ' - ! * - ) . - / $ 0 % ! %
% % ( ( % ! * ! 1% 0 % % % ! % ! (
, 0 " % ( % ! ! ! * & % & % .#
/
! # + % #
( ! ( & % % # * & ! ! % & % ! & % & % #
% 2 Ì Ì
!
" # ½ $ !
&
%$
$
"
"$
!#"
&
&
Erster
!'$
!#
Letzter &
%$
"$
&
"
$
&
!#"
!'$
!#
! " # ! $ % %& ' ( ) * # + # ) ,$ + -./ ! %0 1 2 ! % $ & 2 + $ 3 0% ! ! %0 ! , '! ( 2 $ 4 ! ! 5 # % + %% 2 6 7 # * # , 8 % 1
-./ 4 $ % 1 . ,
Start
Ende &
%$
"$
&
"
$
!#"
&
!'$
!#
! " # $ % & $ ' (
) ) ) ( ' * ) "+ ( +$ ( ( +$ ) , - ./ 0 ) , - .1 2 3 4 * ) " 5 6
AH & %$ "$
AH !AH &
& !# !# !#
& "$ "$ %$ $ $
$ %$ & " !#" !#" !'$ !'$ !'$ !#" "
& & & "
&
! "
# $ %
& ' " ( ) * + ! , -. / / $ " # $ 0 , -12 / )* ! ( 3 4 & )
! 5 6 / ! 7 / * 8
! " " / & !
# ! ! ! ! " 3 * ! ! 0 ! 2 8 # 0 # ! 2 " ! !
! " # $ $ $ % $ $ " & $ ' $ ( )! *+ , # ." & $ / $ / , $ 0"1
/ 2 / $ " 0"1 # / '3 .+ ' ! $ " & % 4 # + $ /' ( + " 5 / ' 6 $ / $ ' ! & ! $ /' # $ " ' $ /' $ " 5 7+ $ 8' 8 # " 5 / # " 5# 5 % ' # + 5 " 9 / $ /' + / 5# - *+ $ $' 5: # 4 ;! $# $ < " 5 + = $ $ $ = # 6 % ' / < "
/ > $ " 5 # , # *+ : : " 7 3 5 # 7 ' " / , ( / -
! "
$ % & ' (! )% (
#
! *
) +$ , ' - $ )%
! . $ /
! * (
" ' ! ! % 0 ' 1 ! ' ½¾¿
2 ' 1$ ½¾¿ ! 1 2
/ $
1 ! 1$ '
3$ 4
2 ' " 1 (# (1 ( ' 1 ! 3
5' ! & (# (
3 ! * *'
6 ! 7 8 9 (
+ 5' 9 '
3% ! ' 6
1 ! & )%
+
/' :
(
2 $ +
! & ; 3% . (
!
<
' *
9
3 ' ! ! % ; & $ (
! !
!
! " ! !
# $
% &
&
' ( % ) ! #*
+ ( * ! , -
! % % !
$ & . / 0 1 , *
! 2 + 3
4 1
4 5
( " ! " 3
1 1
* % / 6 ! .
( ( ( 2*
1, * 7 ( % 1, . 0 4 ' $ 8
2
( 2 ! ( 1 # 4 ( 7
! 5
%
4
5 8 9 / 8 , . ) 1
! 4 )
. ( . 1
/ . :' ( 1
3 ; : # 4
3 $ 4 ; :4
< ! ' ( ! ;
!
" # $ % & ' " & (& & ) * +
, % $ # - + * . /0 &
! "# ! " # $ $ %& '() )* " %& + )* ' ," - . . " $ / 0 1 Ä Æ Ë 1 2 ( È 1 %& + )( 3 %& + 4 5 6 7 ( 8 4 5 ,
" (9 $ + 3 " %& ' 4 5 4 5 %& ' 4 5 4 5 4 5 %& ' 4 5 4 5 4 5 % & ' 4 5 4, 5 4 5 : . " 19 2 " ; " < Æ 2 (
, ( Æ . (
!" " !" # $ " %" &'& ( " ) * " * + * ½ ¾ , * * " " ) * ¿
- " )
./ + ) ½ ! 0 & " + "( ! 0 1 1( )
.. + "(
)
* ) ½ " ( 2 " + & 3 ( 4 5
5 0 + ! 5 6 ! 5 0 ! ( 5 7 ! 8 4 "
) " " 4
( + 3 3 (1 + ) 9 " " " + !" ( 9 " 4
5 : + 9
! " #
$ $ % #
&'& # " # !($
% # " # !(
" &'* #
!(
# )
+%+ % % "
# ! , - - % ,
%
% +%+ % #
&'. /% # - 0 1% &'&%
% " # $ ! % 2 # 0 " ! 2 # 0 " # ! &'3 #
% &'*
-
# " % # ! &'4 2 # 56 % % 5$ #
% 7
% # % % +
% 5 8
!
9
! )
! %
½
! " # $ $ % ! " &
' $ % " $ $ ! ( ) # % ( * + ,
$ - . / 0 1 $ )!)2! ( % $
3 .
+ # 4#
# $
(
3 / 4 % + 5 ( - 4 6 7 ' / + ! " 4 $ # ( ! ,
!
" # $ % & ' $ ' $ %
' ( ) * + , - - ( $ . ( * /
% $ " & ( * /
0 1 /
2 /
( 3) /
(4 0" - & /
/
5 1 - ( $ 6 7
-" & /
( 2 5 ( * /
8 - "
* 6 28 2 " ! ( 9 . 28 :
;
/
- *
- < * $ ( ) + " != $" * $
) $- " ( ) " - <
" ( *
- " - ! >?- ( * & ! ( 9 ) 2 - & " 3 4 " 2 * )
! " #$ % & ' $ ( ) % *& ( + & , - , , % , ( % ( . , + ( / ( *% ( % ( & " , 0 1 & 2 ½ , 0 " "3 4 5
¼
½
6 ¼ (% 7 # , ( ¼ &( , ( * ¼ * (0 8 9 ! "3 ,% ' 0 ( % ,(% & : ) , * ( % & % % & ( ½ !' 0 , ) (% -;) * - $; $) % , 1' ,& 4 5
, <=> * < > - , 6 $ 0 5 ½
" #$ %
!
& ' &( $ )
*
$$ +
! !
for-Anweisung Anweisung Zuweisungsanw.
for-Anweisung
for
for-Header
do
end
Anweisung
for-Header Variable
from
Wert
to
Wert
by
Wert
Variable Wert Ziffer
Variable
Ziffer Zeichen Buchst.
!" # ! $ %& ' ( ) %& * $ + %& # , $ -,.
, " / 0 ½
! " #$ % ¸ ¸ º º º ¸ & ' ( ) ¸ ¸ º º º ¸ * " " + # " ,- ! . / ( " " . % . 0 " ! # . . % 1 2 " . 0 % " " "
"$ " 3 + 4. , . , . " . & " ! ( " 0 5 + 6 " ! 4
7 1 . " 7 " " 0 " + # . 3 ! + # "
! . + # . * " 3 / 8 & + " 8 + # 1 0 3
½
+ 3 34 " 5" " 6 !
" 0 . "9 " 3 " 54 7 . 1 " " :%;2 <=44 > * !? 32/(2>> 2 327<?@ A6
! "# !$ % %& ' ( % ) * + ! , % $ ! (! %&
- % %
½
! . / % % $ ! ' ) $ . $ ! ) ! 0' $% 1 $, ! " 2 34 ' " ! 2 ( # ! " $ % 5 6 # % % " $ ' 7 * , ' 8 ' 9 : $ ' 34 ( + " % !' , " 1 ! 5 ' '. !' 76 8 ; 4$ 8 " ! 9 3 34 / ! % * ! ' " 4 % # < 5 % = (' ! 3 $
½ ¾
½ ¾
! " # $ ! % ! " # & " ' " # $ ( ) ' " ' $ * + #
, "
- ) . / )0 1 / 2 0 - # ' 0 - ! - # - È
Î - # % È % 3
) È - É ) Î % % É È % È . Î ) - Ê % Ê
È # $ ' - È ) Î # 4 ! # ) " Î - - ! 5
! " # ½ ! ¼ $ ½ " % & % ' %
È È ! " # ¼ $% # " & ' È $% # ' ¼ " Î Î (# È È ) ½ $% # ¼ $% #" ½ $% # " $ * $ " È È ½ $% # + ' È
¼ ½ $% # ' $ , % % $ -$ , . - # , / 0 ! . + - $ ' - . $ " " # - - $
! " # ! " $ % " # & ' &! !
( ) % &" * " + % , ! % # " #& ( * ! - # & " & . / 0 * % " * $ 1 2 3 % /& 0 ! 4 ( " ! $
algorithmischer Einfall A Algorithmus
Programmierer (menschlich)
AP
Compiler (Software)
Programmierung
Programm in einer höheren Sprache
Compilierung
AS
Programm in Assemblersprache
AM
Maschinencode
Ausführung auf dem Computer
! " # $ % & ' & ( ) * % + )
Å !
" ! # $% &' & ( '
)
#
* +' ,
- .
/ +'
0' * !
( È & ( ' ( Ë 0' *
' ) , -
*
# #- 1 2 2 0 & 1 +' 3 4 5 1 3 & 1 2 2 & + 2 2 6' & 0 7
½
&
' *
- & ( 7 ¼
½
¼ ! " # $ $ %$ & ½ " $
'
( "
" # $ $ %$ &' " ( $$
' # 06 0'' * ,
! ! " # $% & ! ' " ! ( ! "
) " * + , " - * " " . "
( /
0 ! , 1 ( ' 0 + + ( 2 3 4 " * !5 6 # ' , 7 8 . 2 ) 4 1 ) ' " * " " * . 1 " ' /
!
! "#$% & ' ( ) * ) + , !- . /
0 - 1 2
3 / ) + 4 ! 2 * 2 2 02 5 6 ! )
! ) / 3 7 . / / ) 8 3 1 ' / 3 1 ) 3 ,
9 4 : ;
3 7 < 3
/ 3
) , ) 7 "% = . > = , ? / . = / 8 , @ ! ) 1 * @ A 0
) ,./
A B ) ) * + / ) & / 7
C- )
, / 3 * 7 1 !
! ! "#
$ % & ' () " * ! $ ! ! + ! , + $ - . # ! "/ + / 0 # 0" " 1 0 / 0 2 3 ! " ! 4! 0 4! * ! ! % // ! ) ! 4!
0 0" 5 0 4! ! " 6 + # 7 ¿ " / * 7 " ! ! 0 ¿ ! . /8 +! 7 7 ! 9 // : ! 0 " * /" ;! / 0 5 4! 5 + / <8 /8 2 " ! ! 8 ! &$ ( ! 2 = ! / 9 ! ! " * + # ! 2 #! + 7 ! " 4! 8! + 0 " / ! ! 9 /8 "# ! 4
2 8! + > # 7 !/ 8 8 8!
! "#!
$ % & # ' "! ( ) * &
+ ! , # - $ . + ! % & ' , ! - * - & / & . 0!# + ! ! , . 1 # , # ) - 2 ! 3 & ! $ ' 4 * 3 5#6 3 $ 3 ! 3 7 & - + ! ! ) # # ! 3 ! 8 97
# %9! # & 97 : 97 9! # 4 ; ! 97 3 $ ! ! : # 3 ) - & ! .) ! 4 3 7 3 ! % # - " . !)
9! - ) - 5 - & 9! -# " 4 " & " . # #
¸
¸ººº
! "
! # $!% &' $ && ()& * % ! # & ()& ! ()& + ! % , ! +!-& ' .'# / )&
+! + & # 0 !
! % & # / % +! ! 1&
! &
# & $! % / +! !
+ & # +! / ) #
+ ! 23 * &
'
! ! # ! 4567 8 % & &' # 9 # + ! /& $ : + % &' ; # & & $ & ! + /& 0 & # !& & "
! 1& < &# 9 +! *& !
&
'
! ) = % # 45>> / +! >> + !& * ?# & % & &# ,
! "
# $ % & ' ( (( )( (
* + , - . , ( / " $
/
( 0 ! 1 ! ) ( !
"
2( ! 3
0 4 5 . 6
7 8 ( ( !
' ,(
! ( -& ( -
* +
"
( 5 9 : 9 /
( #
(
5 : ;<=> 5"4 * !
+ 5 3 7 #/ 5 3 - "? ( @ 0
(
8 '
1 1 5 ( ! 3
#/ A ( 5"4 3/
*, 5
A
(
3/ ;<=B ;
ÈÄ»Á ¾
½ ½ ! " # $ % & ' ($ ) % ( * ( + ( (! ($ , -% % .% / ' % 0 ! ,1 ÈÄ»Á & ( 2 3 % 3 ! 3
$ ÈÄ»Á (
ÈÄ»Á ¾
4 " # * * 3 5 # ( 5$ %! 3 0 # 6 7 !
UNIVERSITY_FILE
STUDENT
DEPARTMENT 100
STUDENT_NAME
ÈÄ»Á
COURSE 30
(15)A COURSE_CODE AAAA999
20
STUDENT_ID
DEPT_NAME
99999
(10)A
SCORE 99
COURSE_CODE AAAA999
COURSE 80 TEACHER (10)A
½ ½
! " ! # $ % &' ! $ '( ) * + * , -- $, . ! !/ 0,1 '( .$ 2 0 1 '( 2 '' . 0,1 '(' " 0,,,, 1 " ' 2 '' ½
$ % $ ' "#
$ & !
( ) * +% , % $
/
* 0
(*
1#
+ $
- ## .!
+ $
% '
+
!"#
% *
% 2 !
2
+ '
#
(
$ , 1# '
% 1 %
5
'3 "% !
1 $
4 %%!
$ .#
%
% '
% #!
6+
7 ) 8
!
1 9*
1 (
% %
!" # $ % & !" ' # # $( # # % # ) * + , % )
# - . #$ , + #$ /
# /
, "
/
0 $ 1% /
( % " 2 (- # /
- $ $# & % % 0 /# # 3 ( # 0 #$ $ (
0 # # /
0 4 1 + 0 1 ) #% 4 ) #$ - % # % # 0 , ) 3 ( , # #
$ " / , /# # / % ) / ## , '
, 5 # 3 (5 % % # 5 ) #$ . , $ 26 ( ' 2 5 - # 3(+ ) 3 6 $ 3 - ' % ( 2 , 5 % 1 + ) ' - 2 # 3 6 7& 26 $ %4 & $ 8 - , #$ 5 ,
9" # :(: , (; , 5% 5 ) < , #4 - #$ 26 %4 % # # = , / 2 # <
! " # $ % #& '
( ) * ' '
+ ,
- . )
)/
* )
0 #
1 2 $ ,
3 4567 ' + 8
0
$
9 $ -) !
9 ) :
) 8
+
(
; ; 8 - 0 < = ¼ ½ 0
1 ; 2
9 ) ' ( < 46 ) ' * 9 ; ; >
; ! / - ? 0 0 0 <
! "
# $ % $ & ' $ ( ) *
( ' + , (-
. & / 0# ("
! " ## & $
$
( ! '
( ! ( % ! # ! (
& $ ( & $
' .
#
&1
# "
' $ &
. .' 3 #
¼
(
( 2 . $
4 &1 5 6 7
% ! 3
2 .
(
' ( 1 ,
# 7 5 % 2 (
-"
( $ " # " $ # " + 5 5 &
!
2 #
& $ & ( 5
* $ ( 5 & '
"
! "
# $ % & "
%
' & & ( ) ) * + , # ) - . /& 0 1)
- , .
& 2 $ ¼ ½ *
2
3 2 , "
' 4 #
5 #
4 , ' # 5
! ! " # $
!
% & % ' ( ) ! * + ,+-. / " 0 ' $ ' 1 2 3 4 $ 2 % 5 ! $ $ ! 6 $ 3 3 ! 4
&3 $ 7 ! ,+8. /
9 % : %& ; ' 3 ) : ; < :(= 2; > ! 2 ' ! " $0 % ? $ $ % * $ 3 @ * A B $ A 9 ! = %
4 !$ 2 !
' ! )! *5 #
!! " !# $ # % # ! & ' () !
* + & , ) -./0
1 2
3
! 1
# 4$ 5
5 1 ! 6 ' 1 5 # & 7
' -8 ) 5 1 4 5
&
4 ' ! )9
" 9
! :
! ; 4
$ 1 ! 1 4 1 !
! 4 !
$ & 9 :
! $ #
" ! #
%
% # & '# # ( # ) *
+ , # - # #
. 0 ¿
* + # / # 1
#
2 .
0 # + 1 *
1 * 1 # 0
+ 1
* #
+ 1 1
+ 0
* 1 3 "
1 #
# # +
# $ *
* #
# # 2 !
$ 0 + # + 1 * # +
0 1 4 $ 1 0 ! # +
#
3 0 5
1 0 1 ! 1
. #
0 1 %
4 0 + 1
#
1 # * . ! 1
! 6
$ 3 ) 7 *
# 51
$ 01
+ $ 1# #
¿
! "
"
#
! " # $ ! %
& % ! " # $ '
! ' ! ( " # $ " $
) * + ! ! & º
, ( $ - . $ ! $ $ , $ ( !
( /
0 $ ! $
$ ! ! 1 2 3! " / ! ) 0 1 3 #
4 0 1
3
3 , * $
! 5 $ &
, !$ 2
( & 6 7 8$ "!! 7 3 (/ !
$ $ 6 7 ( # . $ ! $ " $ $ 9 " . $
! "
# !$ !
# % &! ' () * + !! %
(
), -
+ )! $
! " ! . ) / 0
º
# /) 1
! 2 ' )
" ' + !! ! ! !! 2 "
)
#
% ' /
" 1 $ 3 4 ! 1 !! . / ) 5675 & 8 '9 ' + & - ) + & + ! 8 ! 9) 2 ! ' / ) ) #) + ! ! !! % + & ! ! . + )
'
) /
:)& + !! / 56;< 3 ! )' ! + !! # ( + !! ! ( !$' #! ! - ( ! !
+ !
+ ) 1
! % ' ! ! 2 ! ) =
! "
#
$ % % & & '
( $ )* ! *
+ *, $ ! $ !
- & &! & , *
. ½¼ &! /! - * !
"0 $ !
1
& - & # (
1
!
* $
* - $
!
! -
1 0
! - * !
( -
, & &! 0 $ ! & - & &! " * &! # 1 "$ #2
- %
$3
! 1 $ !
4 " ! 5 * !
# ( %
6 !
" &! # "
!#
* (
5
- ( ! ( - 6
!3
%
" *7
1 !8
# 2 9 - !
0 ! ( 6 !
!
2 % 5
$* : !
! " # $ % &' ( % )
! " $ * % * % +
, "( - . *" " / ) +
, ( *" 0 %
- /
. 1 2 . "( 2 ( . % ( 3 # 4 ! (' . & - 5 . 67 ! & 3 %+ 8" ' ( 9 : "( ! & +; 9 : ! # + "( 8 . # & % ' # * * 8 . +
& - . ( % ' & 8 . - % & #+. . ' ! # ! " "( !
" . <= 3 . <>?@ 4 % # 3 %. " %. 3
# 5 3 . . 7 " " A' 3 ! %. ; # . %. " 5 ( 7 ! " & 5 98" : # "( 8 . 7
!" " # ! $
% #
& Ü ' % # % ( & ) ! " % * " % % & ( + ! , ! % )
- ( . " ' # . . " . . (
!
" # $ % & & ' # (# # ) $ * & * $ ! * & * !# + , $ -
* . . ) " . % / . # 01 ' * # , + 2 % 3) ' !# * , !# % ) ' 4 ! " 5 " #3 . 5 #
! "# "# " $ % &
' ! ! ( ) & ( ) & ! & ) & ! & * + , * - . * "# * / 0
½ ¾ ¿ $ & $ . 1 $ % $2 3 4 / * & 3 5 & * 3 4 & $ - # -
* 6 - ( -
LinkedQueue _front _back (a) LinkedQueue
Linkable
_front
_item
_back
_next
1
(b) LinkedQueue
Linkable
_front
_item
_back
_next
_next
LinkedQueue
Linkable
Linkable
_front
_item
_back
_next
Linkable 1
_item
2
(c)
1
_item
Linkable 2
_item
_next
3
_next
(d) LinkedQueue
Linkable
_front
_item
_back
_next
Linkable 2
_item
3
_next
(e)
!"
! #
$ # %" & ' # (
!
)
* + ,
! ( % !
! " # " $ % & " & ' ( ) * +
, -. / + ! % 01 02 " % 02 , 3 "
+ ! + - & 3 4 * & + # " / & " $ * ! 5 % 6 7 5 4 * ! ' ! ( 7
!
/ &
! / / ! ! 3
+ , & " , 8 ) ) * " 8 9 : + ; /
! " # $ ! % #& ' #& & ( ) *& + " #& & & % & ( ,$ % #& - & #&
. " / 0 % 1 & . 2 ' " . " *& 34 5 5 " 0. & - 62 ' # & ) #
& 7 & 8 #& & & #& 9
#& & : ; # % )&
% 9
& " . *& <
! " # $
% &# # ' # () %# " " # * ) # + * + # # & $ , *
#
- * # * . # / * ! , * " )
# ! )
*0 " * ) $ &1 & '" & " # # * ' ( *0
! " " # $ % & ' ($) * ) +%, & ($- ! %, . / 0 ! ( 12, & 3 4 " ( 15,
! " 6 ! 74 ' 6# ) ! " ! ( , ) / 4 6 " 8 " / 1 # ( 19, : -# " - ; #
6 ; ' / ! ! ' & ' 3 * ! : ! # - ) 4 3 : ! " * " 105 - - $ % " 8 " / " ; " ! # 6 6 ; " 8 " -# " ; ! - - ( 101,
! "! # ! $ !% " % " & ' " ! ( ) ! ( ) $ *! ! ) ! + ! ! , -* ! ! ' ! % . / $ *! 0 . & ! 1 2 3 4
0 ! "! . !* * & ! ( ! * ! . $ ! ! . ! ) & !
( , $ $ *!
5*! ! # " ! % 6 $ *! $ 5* $ ! ! (
- ! '! 5* ( + ! ! ! " )
+ ! $ !
# ! , ! &! % , " * $ (% & ! # , %% 7 8 ' * ! - ! ( " ! ! &% "! $2 , 9!½ " ! :; !!0
, 2 "
½ ½
5 4 6
um Maxim
3
4 5
3 Maximum 2
2 (a)
1
1 (b)
! "# " $%
& %'( % )* " % % %
% +# "" * , % - % $%% . $% " " + # "" , % $% */ ! % " +# "" +" 0% )* " " 0% ! !" 1 $% ! ! ! 1 0 , 1 % $ " % 2 )* " " 3 % "
2 1 "* 4 0% 5 % 0 % $%% 67&(' ! 0 % , 4 5 $ " 0 1 %* ! * 0 0% 3 % $ % 1 , % . $%% 67&%( % " +# "" % ! +# "" $ " 0% 0% % ! % )* " $%% 68 1 9 1 % 0 4 5 1 0%
$ ! #
$
$
"
$
$
$
! #
" e
"
c
d
#
"
b
#
!
! #
a
"
!
! # f
"
! " # ½ $ % " & '(
) '( # $ $ *+,- . # $ $ / 0 1% $/ # , # - # 2 & $ 3 4 " 2 / '( , $ *+,- " -5 + $ " , $ *+,- " - . " 6 $ 3 " / . , $ *+,- . " & " - 7 # " $ # ' "
! ! " #$ % &
!" # $ $ % & ' & " (
# " # " )
" * + !" , # # - . -. $ &
/
$ " 0 , ) 1 " # 2 # 2 2 " # " ) + + +&
) + ! ,
"* $ 3 " !
&
&4 5 ( $ 5 ( 5 $
& "*
&4 ) + ++ & , ' 6 1
! " #$
"
"% $
&
"' $
&
"
! " !# $% &' ' ( ! )
# *
+*
!
! , -!
. /
- ) * 0) & ! +
" * -)!%
1' !
0 -! +
2 , # )! + .
' ) !
" ) 3 34 )! + ¾
!# , 5 %
$ 6 (
!
*
+*
7
) )
) ! " #$ " (
)
"% (
) "'
¾
+
+ ,
)
( - )
"
15
5
64
8
12
11
4
35
12
11
teile
15
5
64
8
teile
15
5
64
8
12
15
8
64
11
verschmelze
5
8
11
4
35
12
4
35
verschmelze 35
64
5
35
teile
5
15
4
12 11
8
4 15
64
4
11
35
64
12
35
verschmelze
64 35 rekursiver Aufruf Mergesort
15
12 11 8 5
4
4
5
8
11
12
15
! "# $%&' ! "
$% ( %) " * )+ + $% ! % " %
!
"
!
#
$
$ % $ & ' ( ) % $ % * *
&
! + & % +!, % -,
% .! &
' ) & / & 0
% 1 % 2 %
*&% 1 % !3& 4
' &
' % &$
( '!
$ & &
&
% !! (
% 5 &! & 5 % ' ( +&
,
1 ! ' ' % ' 6 7 &$ ' &$ & .3& , ' 1 ! $ ! ' ! & ), '
1 ! 6 ! 7 *
/ 8
'0 5
& ' / 8
,
( '0 &
$ ( & $ / & .3& & 0 ) & & & &$ .3&
' %
8 # $
!9
'
& ! ,
& '
26 3
17
12
3
14
13
13 10
15
7
8
9 6
10
11
11 6
16
4
4
(nicht maßtabsgerecht) !
9
7
Gesamtkosten: 63 !
!
!
"
a
b
%
c !
!
"
$
e
'
% $
"
! '
% "
$
g
$
d
!
f
"
! '
%
"
$
h
!
" #$ %
& '
& % ' ( ) * & %
& + ,- .
/
% & (
" #$01 " #$0!1 2 % ' 3 2 % ' 4 ,- ' ( ! 5
! *
*(
! 6 * " ! '-" 7 ! 6 8 + 9 ! /
! " #
$ % #
&
' "# ( " $ ) * "
+ , - +
$ ) $
#
. " / " / ' 0 #
! 0 # 0 ' ' #
" # 1 " $ #
0 ( # # 2 #3 /
4 % " 0 # " 5 "
# " 0 "
" 67 ( # " " # % " " % $
" 0
" - ' 4 $ '
28 - 4
%
- & " - 8 4
0 9 ' :%
C
7
E 5
D 6
A
7
7
3
E
E D
5
B
B
6 6
6
F
3
A D
B
C
5
F
F
3
A 3 11 14
2
C
5
G
G
G der Graph
Greedy-Lösung Gesamtkosten:15
Lösung mithilfe der dynamischen Planung, Gesamtkosten:13 (optimal)
! " #
$ %
% & '( ! " ) * '( + ( , "
* % +( % '( - . / 0 1( % * % % 0 '( % ! * 2 3 4 5 '
% !
*
% 2 0
6
' % !
+ % ! %( ) 7 6
1 7
0 4 5 1 + % !
8 % ! 0 * % %
* '( % '( 8% !
# ! 7
1 7
0 % 9
+ ,
! " #$ ! $ %& !' ! ! ( ' ) " ! ( ' ! ! ( ' !
" * $ + " ,' ! ' $ ' - $ + #. /// + 0 $ ! 12 2 # $ / 32 2 ! + ! ($ 2 $. ) ) / ( 4 5 ! 6$ 7
) ' , # $! 8 !
9 $ 6$ : / ' ( ' ! # $ ! # 2 # 8 # ; $ 4< / $5 4 /( !/' 5 9 # ' 3 ! $ =$ $ 9 > 9 $ 6 6$ * - 2 , 6$ ($ ? <
6$ '
¿ !" # # $ % # % !"&% " ' "( ") % !"* % # # !"
% % # # # % +, -
% " # # . / # !"
/ / 0 # /
# & % !"* / # %) 1 " !" 2 # !" 3 ½ 2 %
3 " 3 ¾ ¾ ½ 1 % % % 2 +, - 4 . # # 3 2 & ) % + - # !" 2 !"* 5" # 1" 6%%
" 2% / % " 7 # / #
4 # 8 # % $%4 % *
"/ . % /% % # ,# # % 4 * "/ ¿
a
b
&
c d
!
! " " # # " # " ! !# !# ! " ! " ! $ ! " ! % !# & ! $ ' $ ! # $ ( " $ ' )*( " + ! " , !! ' - ( ! !
" % !# . $ & / 0 , ! $ . ! " 1# $ $ # . , " . ! + ! 2 . + " 3 4 " 2 + 5! " & ! + 3 4 "
vorn
hinten
(a)
1 2
4 3
(b)
1 2
5 4 3
(c)
2
5 4 3
(d)
3 4 5
! " # ! " $ %& ' % ' ( ) * + # # % ' # % ! ' #
' # # , #
' % ' # ' # - , ' # # % % ! - . ' # /# * 0 1 # ( ' ( 0 $ % % # # ! 2 . 0 # 3 4 # ' $ , % 5 ( . , 6 ! / , ' $ ' # 7 8 % # 2 9 #
! " # $ % & ! " ' $ ( )* + ! $ , - !
% . $ / 0 / 1 & 02 3 & 4 5 6 , 0 02 . 0 & 4 % )* 0 + *( 7 $ ** 8 * 7 5 02 7 # 6 0 7 9 : * $ 02 " 4 : % & 0 $ ** 02
! " #$
%
&' ( ) ! *) + ( %%
!
% ,
% - . / 0
, + %1 , )
( . . 2 3 % 2 % 4 5 . " ,
% 67 66 "
). $ 8 )
Î Æ Æ ½ Æ
!
"
# $ ! " ! & '
%
¼
%
Î Æ % Æ ½ Î ( )* !+
% , Á + ! * - . %
* / . ! ! * 0 !
!
" ½ #
! $ %& '( ! $
)
*
+
'( ! $ * ,
-
. & ! /
+ &
, +
+
,0
+
+ 1 '(
2 + '(
) + 2 '(
, 2
3
# , % .%
/
) 4 % , !
$
$ ! +
5 6
'( + )
6 + 2 + 2 , '( 2 7
+ * 87
$ . )
% , 4 9: , 4 9: 9: 9:
9;: .
, , &
$ ) < , . . / 9: , +
/ 2
. ,
!! ! " "# $ $ "# !!! % & & ' $ " ! $ !! ( & ) *+ ' $ " ! ! !! " ( , - * + ' " . ! ' ! ! / ( ! $ ! !! , ! ! 0 ! , ! ! $ ! ! , ! 1 , '
$ 0 $ !
& 2 ' $ " ! $ ! !! & 3 ' $ " ! $ ! !! *4 5 6 " $ + & 7 " 8
! 9 9 #!
' 9 #! , & : " " 9 ! ! ! 8 #! '$! & ;< ' $ " ! ' '( $! ' ! ,8 9 ( #! !! & ;; " " ! 8 ' !! ! 1 * " +
! " #
$%% ## # & #% '# #( # ) ## #
# !#& # * ( + )# , -
. ! # & #% $%%/
# 0
.
!
#& #/ 1% / 1%
. ( *# !#&
"
. ( !( 2 !#
" .
*/
. ( !( . ) $%% (
1%
"
% !#
)#( # # 0 + , . $%% !#&. !#(
* . *.
. !#&
" #. $%% ##
!#( $%% ( + # 1% (
( + 1 # # $%% . % !#& ( + 3 . (
# # 1 !# 2
$%% % %'. *# # * # + 1% !( #( !( # )# #(
# 0 . (# ( # 0 4 )( # 5'# # # $%% " ,# 6 # 7 # # )#-
.
( # 8 $%% !#(9 )( ! " # * $%% 6 # 7 # # 4 ## )#. ( !#( $%%9
! " # $ % &' ' & & ( ) & # * " $ & + " $ ,)& -(
'( . ) /
& & 0 + 1 2 & '( 0 ()
0 '(
½
! " " # $% & ' ( )# # " * $ ($ + + ( !(% & , ! - ($% & + ! '. '/ 0$ 1 + 2 3 $ ,#% 4$! $ ! ! ! + % 5 #+ + 6$
# 1 7 $ 7 & + , 6 % 5 $ " 8 9 $ ! - $ !% - ! $ % $( % : ,# $ !( ! )# # ! - ! + 7 $ !( !+
Start
notiere 0; zeige mit P auf den ersten Angestellten
JA
Ist Ps Gehalt höher als Qs?
addiere Ps Gehalt zur gem. Zahl
Ist Q unmittelbarer Vorgesetzter von P?
innere Schleife
JA
NEIN Ist Q am Ende der Liste?
NEIN
NEIN
setze Q auf den n. Angestellten
äußere Schleife
zeige mit Q auf den ersten Angestellten
JA
JA
Ist P am Ende der Liste? NEIN
Fehler
gib die gemerkte Zahl aus
setze P auf den n. Angestellten
Stopp
! "
# $
%& # ' ( ! ) ) * ½ ½
! " # $ % &' ( ) % # ) *+ (
, " % , - . . (/0 ( , .
( %
, 1 % (/0. 2.. 3 - . . 4 - 5 . , (/0. . 6 . , - ) - 5 (/0. 7 # 6 8 9: 5 - . ; . . 6 . % / < 4 . 3 . 3/ " .. 2 . ) ) . , ) 50 " . . = . 1 . ) ( = - 5
!
" # $ $ % &
" "
$ '
(
! ) *+, - . / ! 0 ) * '"
) * 1 2 / - $ 2 3 - ) *
' # ,
) * ! 4 !
. 5
. 67 0
! $ ) * - ) * 4 ' 7 8 # 1 ! 2 $ + 1 '
1 9
+ 2
: 3 ' 2 3
2 , # 1
2 ;
$ $ "
<
¿ º¾
' &
) * $ / /
= º /
" > 1
¾
! "# $ % ! "& "& ' # () #
# ' ' & !
* +
, ¾
-* . ! / , & # . & 0 1 23 & 4 *
/
0' & " * 1 5 6 +
5 ' & ½ ½ 3 5
' * 7 * ' 8 * 5* 8 9 &
8 ' + . '* # + ! "& & ' !
9 + 9 ' 8 :; 8 <=
8 , !
2 8
+ , , 2
8 8 >* ' - - !+ ?
!" # $ !" % ! " & & '" & ( !" ) * " + & &
& *, $ &
- ( . &
- / -( - * ' + * " ! 0 * ' * 1 ! $ . , $ 0
' $ * , ' $ $ &
&
' 2 ) 3 0" ' & 4 &
0 & 0 " 0 & 5 ' 6 ' - , & 78 3 " & "
6 9
4 5 : 9# ;: / # 0 , 3 &
& <= &
6 . " >
$ < " ' ? & <= +
!
" # $% & ' $ "
(
' ( )
'
*+ "
&
,$ - . / $ , "
, $ 0 1 ,
(
' 2#$ 3 ' 4 ' ( ' '
$ ( 5 5 1 6 7 ! ! + $ ( ,$ $
8
! ( " $ $ $ *
! ( + 7 ( 8 $ 9
*8 $ & 7 "
,
& !
$% " /$ ! 4 1 & & ' "
# 8 - ( 7 $ ,
6 7 , , 4 " + ( ! $ $% , $ : 6 ; 4 !< + & !" = $ ,
! $ 7 $ " 8 0 $ = $ 8 ( 7
*+
*
! $
% $% " ( 4 & 7
; $% ! "
! ! " # $ % # & % ' '
( " % ) ! * # # + , - ' ) . &
! / & # . ! ! - 0
# . ! % ' ! 1 2 ! 3 4 56 7 8 !
& $ 9 # ' # # 3& ' 6 , & & # $ : #
X = 17,6 an dieser Stelle
JA
Ist X = 100?
NEIN
Stopp X←X+1
!
"" # $ % & #
& " " ' $# # ( # ) *#+"
# $ ,
# #
" ! # $ -
&% . # # / "% - &% 0 & / ' #+# # $
!
1 $# " # / % & # # " $ 2 # %
' $ 3
jede zulässige Ausgabe
jede zulässige Eingabe
Algorithmus A
Algorithmus A falls dieser Punkt erreicht wird
tatsächlich wird dieser Punkt erreicht
dann ist dies die gewünschte Ausgabe
und dies ist die gewünschte Ausgabe
Ausgabe
Ausgabe
partielle Korrektheit
totale Korrektheit
! " # $ $
% & " ' ( & ) % * + %
, -
$ " ) * * $ . . / ( ( ! ! % 0 1 " '" . 2 3 . . ' "
( . 0 ! / 4 . 5 2
! * 5 " 6 # 7
! " ! # $ %
& ! !' !' (
% & ) $ * ( ' +!' , -
! . / . 0 1 (
2 3 $
/ 0 4 $
& 5 (
& + * ' '
6 7 8 *
' 9
* + % : % # 2. % : ; * <
& "'
' 2 ( 7 8 / = >0 ; % ?
* &
2
( # @ ' %' : A ' ! : ; @ 6
& 2. ! ,
%
algorithmisches Problem P; Algorithmus A
algorithmischer Prüfer
,,JA: Algorithmus A ist in Bezug auf P korrekt.“
,,NEIN: Algorithmus A ist in Bezug auf P nicht korrekt. (die Fehler sind: ...)“
¿
! " # $
# " # % &
#
&
& # # "
% # " % " # ' # ( &
)
'
' *" + ! % & , *" -
! " # ¿
Eingabe ist zulässig
Start Zusicherung
Zusicherung Zusicherung Zusicherung Algorithmus
Zusicherung
Zusicherung
Ausgabe erfüllt die gewünschte Beziehung
Zusicherung Stopp
!
" # $ %
& ' (
( ( )
* + ( ,
+ ( !
(
-
( # ( - (
( -
, +
. +
/ /0
+ ( !
(
# &
' (
*
# ( + *
, #&
* ( -
# (
( (
&
! " # $ % & ' ! ( ! ) # * + ! ,- ' " ! ! . / 0$* ' 0$* ' ! ' 1 ( 2 ( 2 ! 2 ! ! 3 % ' / ¼ " ¼ ' & !
' 4 " 25 ! )6( " 7 25 8 ! 9
+: //; <=, :< ;// = >? 4 $ " 25 ' + ( := , / " / 25 " 25 9
+: //; <=, : =
Start
X ← S; Y←Λ
NEIN
X = Λ?
Y ← head(X) . Y
JA
Stopp
X ← tail(X)
!" # $ $
% " & ' " () !" ) !" ) # " " ' *
+ ' ", () !" # !" ) # - , ' " # - " % ' " . ' ) # / (' + ' ' .
# 0#1
Zusicherung 1 Start
S ist symb. Zeichenk.
(1) X ← S; Y←Λ
Zusicherung 2 S = reverse (Y) . X
(2)
NEIN
JA
X = Λ?
Zusicherung 3 Y = reverse (S)
(3)
Y ← head(X) . Y
Stopp
X ← tail(X)
!
"
" #$
&
'
¿ (
%
½
)
*
" #$
¾
+ +
" &
¾
%
¾
, -
) .
/ / "
% )
+ (
&
)
)
0 +
'
" 0 ( 1+
)2 %
3
Start (1)
(2) NEIN
JA (3) Stopp
1 Start
2
2
2
2
3 Stopp
½! ¾! ¾! ¿! ¾! ¾!
" #$! % & ' ( )
*
' " *
'
+! , -
"
" - . / 0 1 / 2 ,
( 2 3
3 0 - , 4 2 " / + % - "
1 ( 3 4.
" #5! / /
¿ ! " # $ % " & & ' $ ( $ ) * + , - . - / 0 1 2 " ' 3 ½
¾
¿
¾
¾
¾
!"
4 ' ' " & " *¾, & % *¾, & 50 6 * # 6 , ' " *¾, # 6 0 ( ' & + 7 & ( ¼ ( ¼ * , & ' " $ # ' " % ' & ' $ ' ) ' !
! " # $ % & ' ' ( ) ' ( * *+ , # - , . * & ' # * & . / 0 / 0 , , #
& . & 1 2 ¾
¾
. # & ( - 3 , 1
* ( ' 4 & & ( 5 ( , . - . 6 , # % ( . ! " * ( / 0 , , 7 8 , 9 7
! "# $ ! %
& % ' (
) %
*
* ) % + , !
* -! . / 0
1
) "
! * ( ) / ! ) * ( ! '
2 + , 23 ) % *
* % * 4 * *
' !
+ *
, 5 3 6 7 ( # 3 8 % 6
! 3 & # * * * !
* * 9 % 2 ) -
% * &
/ * % ( ! : ; % * ( 2 /! < 46 =>
½ ½ ! " ! !
"
# ! ! $"% &' ! ! ½ ½ ( ) " * ½ ! ! " + " * ! ! " , # - (./ 0 ) ! 1 20 . . ! " !
3 4
!
½ ½ " 0 " * 4
-5 0 , - ' " * . ! 6 . - 7 /. 4
¼ 0 " -
. 8 9 ! /
" ! . : , ! " + 4/
; - ! 0 3 , & 4 " 4 -
!
" # ! $ % & # & '& ( & ) * + "
!
" # $ % & " ' ( ) " ' $ ( ) * ( " + $ ( $ " # "
! ! ! " #!# ! ! !! ! $ % ! "! ! " ! &' ( " &'
' % ! ! & # " ) *+, % % ! "! '- .+ ' / # -
"!
! #!#
' ! ! ! " !
" !
*+, "
N
X Y Z (a) Anfangskonfiguration: X enthält (mindestens) N kleinste Ringe; die übrigen sind schraffiert.
N−1
X Y Z (b) Induktionsannahme: Die N − 1 obersten Ringe werden korrekt von X nach Z bewegt.
N−1
X Y (c) Unmittelbarer Zug: Ein Ring wird von X unmittelbar nach Y bewegt.
Z
N
X Y Z (d) Induktionsannahme: Die N − 1 obersten Ringe werden von Z korrekt nach Y bewegt.
!" $
%
&
#
$
'
( ) $
*
! "!!# $ % ! & ' $ ! "!! % $
' ! "!! % $ ( ! " # !
! " # # $ % # !
## # & #
' (
) (
$
* *+ * , )
(* #
- # . / (* 0 1 )# ( * $ )+# % ! , ))# % $ - . )+# ! / % !!
2
( .3 !0 4
* - # (*
- # (*
, - ## # - # ( #
- /
5 - # & * ( 4
!
" ! # $ % & $ ' ( ) (& %
* +
, ( ! - * $ . $ ($ ( %( " $ * / * 0 ( * ( ) 1
)23 & ., 4& + ! 567,. + ((
* / 0 - 8 # $ * / ( + * % 4$ 9 : %
( ( 6 , ! 4 ( (
* ( ;< ;= 0 , $ ' / -
! " # $% & $' ( ) " * ' + " , ( ' $ % " ' $ # * % % + + " # -# . -/% . ( * /% " # 0 + # 1 ) ! " * ' 2'3 '% /% " + ( 1 0 " $ ( * ) $ ( + )% " % ' # ( + ! 4 % ' + " * ( $% ' 4 ' 1 * ( 5 $ ( / ( " $ # % # " 4 ! # ( + ( # ( )% " 4 % $ /% + ! ( 1 ) # " 6 /% # " ' 2'3 ( /% ( +' % ' /% " +%
/ # "
! " # $ % # & ' ( %) % ( * ( ) + " ,
- . % & ' # " / !
0 . # + ) 1 . + ! , # " , - % & # & . # 2 , 3 4 3 - . " ) , 5 , # % + ) * / - + 6 7 899: 0 - ) - - - ;+ ! , 8< =
5 " - 2 / >
! " # # " $ % & !
' !
$ ! ( ! $ " )
*
* + + + " (( ( $) # , ( - ! ( ( " " . / 0 /() 1 2 ( ! " !
1 )
( 1 + ( / ! ( " % ( 2 ' ) 3 / % * ' &4 " - / " ! & ) 4 / ! - (
(
+
" 5 3
$ 5 & 4
" !
/
! &4 (
! " # $ !%$
& ' ( ) * +" ' , - * * #% * & . & ' - ' . + . $ !
/& * - '
, $ *
' # ) /& 0 / 1 ' ( # - .) 2 &
+ ' . ) $ ' & + 3 4 ) $ 3, - + ' 1 4 2 /$ & # * /& 2 $ ) ' 0 5 . 1 ) * 1 ) ' / 5 )/& ) 5 $ )& 6 $ ' . 1 ) , 7 * ' , *) * - // % * ' . * % 5 0") 5 / , 8 '
! ! " # " $ % &' $ ( ( &' % $ )
* +
( , ( - . + %
/ 01 + ( - - ( + " ' $ 2
- 3 % - $ 4 , +
% " & $
(
" +
5 + & , . /0 / 0 12
½ ¾ ½ ¿
¾ ¿
+
2 , .½1 ½ ¾ .¾1 ¾ ¿ 6 .¿1 ½ * .
% 1 ¿ +
7 ( + - % ¾ - 8 +
! " # $ ! % &'( ) " $% * ! + # &' " ,' ) - # - + . / ) 0 - + 12 &' - ' ,3( + 14 # ) ( %% $ + 15 16 0 7 ,3 - % + # 8 ( ) 9 ( - ) - " ,' " 8 &' " ,3 : ; : ! " < % # ! ,3 = ! ) >
" % 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 $ ! *!*
; :
< 8
= 1 > *!* ? * % * ) 9 ; ! 6 = 1 &@'A $ !
; " !* > *
. !! " + / . 9 ! $ ! 9* 8 7
½
½¾
!
" # $ %&
! %" ' ! ! &
( ) %& *+ %& '
* , !- )
!" # $ % & ' ( ) * ! + '% * ,
. %/ * % %0' * 1(#% !
2 * ) % 345 ( %/ * )
% ! 4/ % ) %0' )
&' ! '/ ''! $ 6 '
%/%
&
!7 & ) %)
!8 ) 9 )
"!: ! !:
. 0% "!: ) ;
$%
% / )
% < ; $%
! 2
!
# &'
%0' ! $%) 9 < $% !
"!: %0'(
'' ) 6 = ;(
!
> %) ; ( ! < ? % ? '<
= '<
&' > ) &' ! / &' ) * ' = >
! @ < 9 ) 0% '
) 9 ' % 0% '
) '
! ) 9 $0' %
! "#$ % ! & ' ( ) & * # ' + ! * ( & ! ! ) ' ) , '! + ) ! * ( % ) ' + ) ( ) & * ( % & , ' + ) ) * ( % ! & ./ ! 0 + ) 1
2 ! & '2 3 * ! # "#4 * ! & ./ ) )# * 5! "#67"#89 & :( & 1 !3
! ;! 1 < 3 ! 1 ;! < 3 & ;! ! & ;! #
3
* ( ' = ' = ' ! ' ! & # > % ) !
#
"#6 % ? 1 ! . & 1 :( '% ) # * % # "#@ % !( & ! 1 # ( & !# ./ , :( ! )# ' ! 0 ! ! 1 :( ) # * % # "#8A B 1 ) , , ! ! # * & !( & ! 1 # C ! ! 1 -
!
"
# $ % & ())
'
*
%
+$* ,- % & . - % / ,- 0 % & ' ()1 +
2 * 3
! 3
4 3 - 2 % ()5 6 3 ! 3
2 3 - 2 %
()7 8" & - % & ! 0
9 0
! " #$$
$ $ ) $
Å
!
# ' -
Ò
Ñ
¾
Æ
Ñ
Ñ
Ñ
¾¾¾
¿
Ò
% & '
$
$
½
$
1
$
Ò
ÈÏ
Ñ
Ò
(
*+ ' , ¼ !
¾
Ñ Ñ Ñ
! . $
/ * '
!
Ñ
0
$
!
$ * '
* '
2
3 (4 2
! -
* '
2
*
, 5 # 2 5
2
3
!
- 2 * 3 3
$!
2 3 3 3 !
- 2
!
- 2 3 3
!
- 2 3
* '
* '
2
*
, 5 # 2
! " " " #
$ $ " $" % " &" '$ ( )
$ ! " *
&"+ '$ (
, ! " '$ -.
/ ! " " " 0 "# " "
#
'$ -
1 2 " 3 45 $ $ 6 # 6 " % $ 2 $ ! $ " 75 8 75 & "" 9 +
4 : $ "; $ 2 #
! $ " + 75 $ $; <
3 0 "" #
! ; *$ 8 75 & "" 9 $ # ! + #9 $;
! " ! #$ %
& % % ' (
' % % % ) *
( + %
' % (
(
% " ) % ( % ( % ,
" - ' . / / 0 1 2 ) ( % ) 3 ) " % 4"5 ) ) , ( % * % * % $% 6 % " * " . )
! " #
$ %#
% &" ' % ( ) *" + "
,# " ' - &" * & " . *" ! #" / #
" 0 &" %
#
! 1 # 2) % # 3" 2 #
3"
# ! " 4 2 % # ' " % *"
#% % & 5 " ¾¼¼6 ' # 3"
#7 # # 3" ! 2 8 # 5 16 ! ¿¼¼ & #
& # # % % % 3" % 1 *" 9 ! 3" :# & 0
) ' # # ,
# ! 3" # ; # ! 3" # :# ' "
% &) : # # 4
" & %
< = / %# *" > , # ( 2
*" ?+
! " # $ % &'
( )" * "+ ! ( " ,
+ % # ! - " # ½¼¼ " , , + "+ .
½¼¼
$/ # "
0 ) ' 1 *" ½ "+ 2 # *" , 0 # ( 3 0 0 "+ .
½ ½¼¼
, 4 " (" 0 # 2 5 ½¼¼ / 1 " 5 # $6' * ½¼¼» 0
½¼¼ $7' $8' # 0
.
½¼¼ ½
! " # $ $
$ % $ & ' ( " ) * + ' " & ' , ( - . / $ ( 0
$ " / 1 . 2 . 3 12 4& 56 1 4# / " 56 0 $ 7 $ 8 7 & 9 * 0 / ( " ' + / " # $ " $
" " # 7 ( +
/ " , ' " " 7 / " : / $ 1; 7 ( $ " 2
! " # $ $% & ' % ( ) ) * ( ( ( ) + # ( % , ) & - & ( . %. ) . & ) / .0 # . % & + #1 2 3 / 4 # " . 2 ! 3 5( $ & # 4 ! 3 ( # 3 . %# # 6 4 ' 5 .* 4 ' * 4 4 4 % 4 # 3 + # 3 7 8 4 # / " 6 ) # & . %. + 4 $ %%
! "
#
$
% "
&
" '
(
)
(
" ' *
+, -
( . /
(
½ ¼¼¼ ¼¼¼
% " 0
(
( 1
(
( 2 3
% 4 /5 6
¾
½
' )
' 6
½
" ' 2
¾
2 5
$ ' 2
0 % 2 6
½
1 3
¾
1 3 7
% /5 2 " 8
'" 9
"
# $
9
9 / 1 :; :<3
Start
betrachte die ganze Eingabeliste L
Y nicht gefunden
vergleiche Y mit dem mittleren Element der betrachteten Liste
durchsuche die erste oder die zweite Hälfte der betrachteten Liste, abhängig vom Ergebnis des Vergleichs
Y gefunden
Ausgabe ,,gefunden“
Stopp NEIN
Ist betrachtete Liste leer?
JA
Ausgabe ,,nicht gefunden“
Stopp
! " # $ % ! & & !' & && ( ) * ! " & * $ + * " & $ , - ! . ! / * & * $ 0 . 1 * * " & & * $ ! ! !! 1 & ! & ! * & - & " $ 2 ! !! 1 #- '0 - " 1* & 0% & 3 ! ¾¼ '&
(1) Allen (2) Baley (3) Boyer (4) Casy (5) Davis
Casy > Boyer Heureka !! Casy < Davis
(6) Davison
Casy < Davison
(7) Glen (8) Greer (9) Haley (10) Hanson Casy < Harrison
(11) Harrison (12) Lister (13) Mendel
Start
(14) Morgenstern (15) Patton (16) Perkins
Länge = 20 Anzahl der Vergleiche = 5
(17) Quinn (18) Reed (19) Schmidt (20) Woolf
¿¼
! " # $ %
&' $ ! ' (' ) * ¾ ¼ + , !' ' - ! * ¾ ¾ ' ¾ (' "
½ ' ' ¼ " (' . ½ ¾ ¾ ( # ) "
( ) ½
½ ¾
½
¾
!
½
¾
½
" # $ % & # ' ( ) * + , # , $
% - .(/ $ 0/1 , $ #& - 0 -$ ( 2- 34 $ - / # " 5 ( ¾
% / * 6 *&5& 7 # $ " 8 9
: ; $ - " 9
2 - 2-& 2
< = < 3 2 -
Start (1) K1 K2
(2) K4
(4) Stopp
(3) K3
Stopp
!
"
# $% & ' (
) " * " + " ,
- ! " . " " / 0 ) % 1 + 2 + 3 $ % (
" + )
! ! "¾#
$
"% & ' ( ) # * + $ ( " ,# ! "¾# ( % & " - #
½
.
% ! /
(3) (1)
(2)
(2) K2
K1
(2) K2
(2) K2
K2
K3 K4 (4)
log2N Segmente führen höchstens zu K2 × log2N Anweisungen
¾ ¾ ¾! ¾ ¾ " # $ ! ¾ ¾! $ % ! & ' ( '( ' )*(+ , % $ - ./ 0 0
1 % ! ! 2$ 3 4 , " 5
! " # $ % & ' ( ) *
0 5
$ $ ( ) ½ (
! " # $ % ! %& %& % ' " ( ) )* + , % ! - * *) ) " * . * " & * # & + / % ' '0 0 ! % . " & 1 ' ** ) ,* 2 3 4 * $ ) *
5 3 $ $ 0& &! & % # ) # * ' & 6
7 89 ( & 1 $ 0& & 3) 4 , , , 3) * ¾ 3 * 5 * $ 0& & .* * ¾ : $ 0& & *) % % % 4 & * * * * ; $ ! $ !
1 . 1 * & # 1 *) # $ 1 * ) ** ' * & ¾
½
!
" #
#
¾
" #
$
# %
%
% # # # ## & $ # '( ) #
$# * " #
) # #
" #
# '( + ,
- . $ * " #
($
# ( / # 0 0
0 '($
$"
# . 1 - ) ' # + '($
$
2 # # * " # ( 3 + 0 - '($
$ *
# 0 ## " # 2 # 41 - 5 '($ " #
$" 3
# 0
# '($
$
2 6
# % (# ( #1 6 / $ # # -# # / 5 # 0 '($
$" . $
# # - # 1 . 0 0
" 4 #1 " # #
$
7 # % . #1 6 " $ # 7 1 - .
$" # 7 1 8 &
ººº
ººº
! " #$ % ¾ & ' ¾ ( % (% % ( ¾ ) * % # + " ¾ % , " % ( - ( -% - . ! /
¾ - , ¾ % 0 % ' ¾ ' ¾½ 1 , 2 !% , # + 3 % !#4 567 % ! , % , ! ! ' 4 587% 4 97 ! )# * % , : 4 5; 5<7% % (% ! % !
% (= 3 % 3 > ? $%
! " = . > 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 % 2 31 (
"
) "
+ ( "
$' 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 . , , %052
! " # $ # % & # " ' ( )
" # * ) # +" , - - . # / % " # -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 '<
. - % %, 5 ) = 34 %, 0 ) - (
> 9 /
?# % " 6 @ - ) % 1 '( 0 = 39 4 6 ? '( 0 6 #
! " !
# $ ¾ % & ' ( ) * + ,- . / ( ) $ 0*1
* ) $ ) 2 3 45 46 ,, . 1 7$/ ( ) 1 3 48 ! ! 9 2 "
' 1 ( ) 0 !
7 12
3 4
: $ ' ; ' ) < ) ,6 . 1 7$/ ( ) . 7 $ # $$ =/ /
3 4,5 ,5 / *
¾
! / ( )
,4 ") =* $ / ! / ( ) ! / ( ) .1 $ # =/ /
3 4,4 ,> = 7 7 )
3 >,- // # $ 7 ? 3 >,- 3 >,4 @
/ . AB A B
$ < $) 9 7) / . / ( ) ! / / ! 7 * )& 9 " $ / ! / / #) ! % / " */ ! .
, " // # $ 3 ,> $
' ( ) 1 *
/ 7 7
# $ ! % &
*
+ !
) , (
-./ "
" + !
+ !
*
$ ! % (
)
*
! "
'(
0
) !
) !
"
! (
1 2 3 " " )
%
½
4
% 6, %
!
¼
"
¼
) 0
4
<
= " $ " > % + "
0#
7 -.89-:; "
5
<
=
0 1 = % % " <
> " % 5
% ?
-.8 "
½ " > % <
½
@ ½
+ !
1 ! %
! % <
¾ ½ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ )
)
¼ ½¾ ¾ ¾ ¿½ ½ ¾ ) + , -.A ! ! " ¾ < ½ ½ ½ ! % ½ ½ # % ¾ ½ ¾ 5 " >< % < -:; 6 %
+ "
+ ! "
1
½ ¾
¾
!
¿
! " # ! ! $ %! & #' (
¿
! # # '
!
¾ ½ *
¾
! )
¾
! " # $ % &
# ' (
¾¼ " &
'
) % &
# ' &
" &
)
*
+ ! # ) , ' ) ) ' - . / &
" 0 1 ) ' ) 2 3 ) ' ) & * ' & *
$ 4 ' 5 # ' * ) ). &
# ' 4 ) ( .
6 *
* 4 * 7
! " # $ ! % ! & ' (
) ( & * + , ' - )
) (
. )
/ ! + 01 ( 2
%
' 3 45 6 )
! ' ) !
) 7
# %" ( 8
45 & ! ' 45 5
½
( 9 : 9 7 ;
) 7
& < 8 ) (
%
! )
(
= # & *
)
# > 7
% 5 - , ( ' ?
' @ 5 7 ' & ! .
5 A & !7 ½
¿¿
!" # $ % & '
( ( ) * + , - $ , ./& 0 1 * 2' 3 , # 4 ¿''¿' 1
5% #
4 -
0 $- & # 1
¾ 0 '' ', #
4 5% 6
# # ,
789 '+
'' ', :
%
)0
# 0
* 4 ;0 ''
!
" " #
$ %"& % & ' ( $ )
' * + * , $
- " . / 0 (
. *1 2$
( 3 ) # 4 ( ! ,
. ' 3 .
5 -
$ !6
2 4$ 0 -
0 , 0 , . 2 - 0
* 78 # +
. 7
3
4 # 9:;
$
- < . 7 . '
' $ '
7 = ' ( $ <
= > , 5
? @ ! ? @ !
' ! '
Anordnung existiert immer (a)
Anordnung exisitiert nie (b)
! " # $ ! % & '" ( " ) '" *
'" + + + # * + ++ ) ) & , '"
- " . '" " / )% %
0 1 ) , ) 2 '" ))* )% ! * * 3 '" " )% % 2 ! ) ) 4
5 - ) * "
- 2"6 " !* ,
N
20
60
100
300
1000
100
300
500
1500
5000
Funktion
exponentiell
polynomial
5N N × log2N
86
354
665
2469
9966
N2
400
3600
10,000
90,000
1 Million (7 Stellen)
N3
8000
216,000
1 Million (7 Stellen)
27 Millionen (8 Stellen)
1 Milliarde (10 Stellen)
2N
1 048 576
eine 19-stellige Zahl
eine 31-stellige Zahl
eine 91-stellige Zahl
eine 302-stellige Zahl
N!
eine 19-stellige Zahl
eine 82-stellige Zahl
eine 161-stellige eine 623-stellige Zahl Zahl
unvorstellbar groß
NN
eine 27-stellige Zahl
eine 107-stellige Zahl
eine 201-stellige eine 744-stellige Zahl Zahl
unvorstellbar groß
½¼¼¼ ! " # " ! $ !
% &' '
( ' ) * ' +
, , ( ! ! ¾ " $ ! , $ ! -
' . ( $ /0 /1 !
2 . !
3 ! $ $ /4 !
3 ! 5 $ $ !! '- ' $ 6 , $ 7
$ 8 " ,
!
1040 NN
2N
1.2N
1035 N10 1030 Anzahl der Nanosekunden seit dem Urknall
1025
1020 N5 1015 eine Billion eine Miliarde
Anzahl der Nanosekunden an einem Tag
N3
eine Million 5N
1000 100 10 2
4
8
16
32
64
128 256
512 1024 2048
! " # $ % & ' " # ( " % ! ' ) * + , %
-. /" 0 ) ) * " ) 1 ) * 2) " 3 ¾ ) ) * 2) ) 2) 2 $
N 20
40
N2
1/2500 Millisekunden
1/625 Millisekunden
N5
1/300 Sekunden
1/10 Sekunden
78/100 Sekunden
2N
1/1000 Sekunden
18.3 Minuten
36.5 Jahre
NN
3.3 Milliarden Jahre
eine 46-stellige Anzahl von Jahrhunderten
exponentielle
polynomiale
Funktion
60 1/278 Millisekunden
eine 89-stellige Anzahl von Jahhunderten
100 1/100 Millisekunden 10 Sekunden
300 1/11 Millisekunden 40.5 Minuten
400 Milliarden Jahrhunderte
eine 72-stellige Anzahl von Jahrhunderten
eine 182-stellige Anzahl von Jahrhunderten
eine 725-stellige Anzahl von Jahrhunderten
! !"# $ % & '! ( ) * #
!" #$ % ! &
"
" #
& ' ' (# (# ' % ' (# (# ) ) ! * +,-+. / 0 " ' $ ! % ' #$ !! & !# 1 ! 1 " & %
½¼¼¼ 2 )3 ½¼¼¼ ' 4
#$
) & ! # ½¼¼¼
! ) 5 ! / 6 %
unhandhabbare Probleme handhabbare Probleme
Probleme, die keine angemessenen Algorithmen zulassen
Probleme, die angemessene Algorithmen (Polynomialzeit) zulassen
! " #
! $%&&' ! ¾ ( $ & ! ) *
( + ,- . # / ! +
(
!
01'&2! - 3 . ! " ! ! ( 2 ! , 3- 4 5 ! 6 7 8 # 9 #!
-&
# ( º : -
, 0
: 2 - 8
2 " ! 8
¾
!" !
#
$ $ % & !' ( !
$ )!
* (
+! , !"
Funktion
º
º
º
Maximal in einer Stunde lösbare Kartenzahl: mit heutigen 100-mal schnel- 1000-mal schnelComputern lere Computer lere Computer
N
A
100 × A
1000 × A
N2
B
10 × B
31.6 × B
2N
C
C + 6.64
C + 9.97
! " # $ " $ ! % & $ ' " ( $ ' ! ) " * ! + (
, ( , " - . % ( /0 1 1 2 $ * 3 " ) ( %( * $ ) ( . + . 4
' - 5 $ /0 6 ( * + * + 4 4 * $ $ , * $ $ ( * " ' 3 $ 4
!"# $ # %
& !' & #
( )' * + ! , - . / 0 ) 1 ! !' ¾¼ 2 3 0 ! ! 4
' ! 0 5 ! 5 ! +
! ( ) 6 $ 78 ! - ! 0 # 0 ! !'
#
* + 9
* + 2! 6 : ! % !
! 6 ) 0 9 ! # !
0 * + # ## $!! ## $ 9
!' ## 4 !
! "!# $ %& ' ( ) ) * ) + , , - , ) , ( ! . / 0 ! % ! ' + % ' 1 ( # 2 ) 3 ! 4
1 ) . & / 0 ! % / +
) 5 - 6& ! ! ) . .&
) , ( + ! +! ! ) ( 1 ! +! % 7 "!# 8 6 %% +! !
, )
8 7 9 ! ' + . 7 ., % ' .
& 5 ' & !% ) ., + $ ! ., 7 7 % ., 1) 7 9 ) 4
! 5 ! % , 0 . " + ) & ! &
6
6
3 9 4
8
4
3
4
10 3
7
5
7
3 7
5
(nicht maßstabgerecht)
Gesamtkosten: 28
ÌÓÙÖ ! " !
# $ %&' ( ) ! * + , # - $ "- " ./0 . 0 # " $ 1 2
" 1 - 1 ( 3 " 3 # " 1 3 !
1 3 4 " $ () - # 5 6 3 7) 8 * 9 ) # ! ./0 " 3 # . 0 " # " + 6 : 6 , ; " - " ! - 2 3 3 ) ! * " "! " # 1 2 '1< " 1 " " " 18 ) 1 , 3 6 " " " " ! 3 " 4 1 ) " 1 8 1 9 !
ohne die zusätzliche Kante gibt es keinen Hamilton-Pfad (a)
ein Hamilton-Pfad (b)
ohne die zusätzliche Kante gibt es keinen Euler-Pfad (a)
ein Euler-Pfad (b)
! " # $% & $ ' ( ) * + ! , - . / 01 2 + " 0 $ . #
) 3 % .1 ) , - 1 ! 4 5 $ ¾ 6 7 / 8 . 0 ) / 9: $ 01 2 . $ 01 ) ) !; ½ % - $
¾
! ! " # $ # % &
&
' () *
( +
,
+
-& +
, . + " , + / ! , , + " () . 0 () , " ,* &
+ / "
+ & ! 1 0
* 2 3
. () * $ 3 "
4 +5 - % - " ' 6 78
7 8 7 8 7 8 9 3
:
* $
½ 3 * ¾
*
! "
# # $ % ! ! ! &½' ! % &¾' ! ( ! ¿ # $ ! ) * $! +
! , % % ! .$ /! ! !% $ %
" $ ! ¾ & 0' # ! 1 " 2 * +! .$ " ( % !% $ %% ! 3 4 .$ " % * % $! % %
5 6$ 7 ) - -8 1 /% ! !+ % /+ !+ & 799' ! /% % : # 1 /% ! 1 ! /% % !+ % % + *+ & 0' ! + $! ¿
!" #
$ # $ %& '
( ) %&* ' & ( ) ( ( * + , % - # (. / ( %& ( 0 %& 1 %& ( / 2 %& + %& 34!25 0# 6 !"
# $ 72 34!25 ) 8* + # -
!"2 !
& & 9 2 + # 6# + ) *: + &2 # + # # , + $& -
!"2 2 & ;/< ;< ;/< 0# / +
!"
# $ %
&
' # # (
) #
# ( * +! # !
, # -
#
( . / $
## 01 023& #(
+
) # . #
4#
'
) +
# - # (" - /%
(
' 5 # 6 ' 5
7
(
( !#
) #( -
$8 # * & (" - 9 * % # !# !: ) #
9 ! # # # # ; # / # # ! # < ; ) =
; # $ # (
' !
-
"# &
; ' ' # < ; > / # ) # ; 9 ; ;
/ ,
/ ,
# $8 # ; / ,
/
# / ; - & = # ; #
;+
!
; 6 ) 8 +
, /#
!#
# (# ;
/# !# !: 5#
? < !# !: # +
! " #$ "
$ $ % #$ & ! $'
" "
#$
( ) *+ * , " *+- * *. "
* *
/ " + 0
!
" 1
*+ * #$
2
2
" " ' 3 % , ! 3 *+ *
! 4 ! "
" 3
* *+ * ! "
" #
%
! )
*. * ! "
,
* 5 "
*. !
- ) , ( %
! " *
*
*. $
* *. $ 6 78 - 3 % * ! " * % % % " 9 - % * *
" 6
! " : ; ! <
1
2 1
1 1
1
2
2
1
2 G
T
der Hamilton-Pfad ist hervorgehoben
Tour des Handelsreisenden der Länge 6 ist hervorgehoben
½¼¼¼ ! " # $
% & ' ( &
) $ * + ,* - ,- ( ( + + ( + ( + % + . . % ( # / . 0 % " # # % # * # # # ½ / ¾ %( 1%23 4 %+ 0 / 5. 6 ½ 7 * 8 9 . % $ $ / +:. + 5 % " 5 . 6 ;0 ½ ( #
G:
,
Anzahl der Knoten N
transformiere G in ein neues T
1
2 11 2
1 1
T:
, 1
2 2
Polynomialzeit p1(N)
Anzahl der Knoten N
Weist T eine Tour des Handelsreisenden mit einer Länge ≤ N + 1 auf? JA
JA, G weist einen Hamilton-Pfad auf.
NEIN
(hypothetische) Polynomialzeit p2(N) Insgesamt (hypothetische) Polynomialzeit p1(N) + p2(N)
NEIN, G weist keinen Hamilton-Pfad auf.
! " # $ % " & ' ( ) ' *) ) ' + ,- * ./0 1 ( 2 ) ' * ) 3 4 2 ) ' ' ) ( 5)* # ) 6 7 5)*# ) ( ) * 8 ' (
Ê Ê !
Ê "
" "
Ê
É
#$ % Ë
& '
Ê
É Ë ( ) É Ë " Ê "
( " " * $
"
+ " , "! - , Ê "
$ " .
Ê -' "
. Ê
/
$ .
) ' " Ê
! "! ." 0 1 , 2342 "! ' . ! / " . ' "! 5 (
*'
- / 5 ! " * ' *' 3
(
6 ! '
/
' ."" '
( )
" *
$
! "! # ! ! $ "! % &!! $ ! ! !! # $! $ ! ! $' $ ( $ ( ! $ ) ( )' $ # # ! $ # ½ $ !! ! ! %)' (* ! ) $ ( !
¿ !" # $ " %" & $! & " ' ( $! & )
%" & ! *% $ % + &
, " )
' $ $ "
! " # $ % " " & " '! ( !) * +, - " " ' * +, .! ' ' / ! ! " " * +, 0 ! ' " ! % !
¾
! " # $" % & # ' ( )*+ , - ## . /01/ 2 3 4 # 2 2 #3 5 3 # 6 4 # ' " " ! 4 ' , 7 8 # " 9 # " 6 .
½ !"# $ ½ % &
' $ ( ( ) ) * + ¿¼ , ' ) % ( -& ) $ . / ) % 0 ( 1 2 3 4 56) $ 5 77 78 $ 9
: )( ' 4 ,; ): ( ) $ < = ) ' + ,; ): < + & > ' > )( ' 6 3 ' & = % & ( % $ ( '
! " " # $ % & ' ( ) " ! * +
" , - $ $ $ " - ½ #$" ( + . ) " $ " ! -"" ! # " ! %" ! " # $ ( * / 0+ !$" 1 * (2
" ! 3 4+ 5- ! $ " $ " 3 3 . $ $ " 6 - 6 "# "" 7 ! " ! 2 # "" ! " & ' $ - 3 8 " $ # ! 9 7- . $ 7 " ) -" : ! 1! !# & 9 : $ 9 ) 6# ! 9 - 5&# - & " 4 * ! $ " ! ! $ 3 ! ; 4 5 "!#
7 . 2 "$ ' $$ $ 5&# - & $ ! ! ! $ #7 . ' $$ " - " ! 3 ! < "! -# = 8 " ' $$ " "
"" 5" " $ > 5&# - & # (" + " " " - ? . 7 $ & #
!"# ! $ !"# ! % $ ! ! $ ! ! $ !" # ! $ ! $ & " $ '# ( ! !"# $ ) " $ * + ' $ , - $ " ' + $ & ½¼. ¾¼. $ '# (
' $ ! - $ !* " ! & $ !* " &# $ & & '# ( " / ' '# ( $ $ ! !
0 1# $ , !"#" ! 2 $ $ " % $ $ !"# ! 2 !* - 3 $ 1" ! 4 !"# 5 # 4 0 65 ' ( ' ! $ 72 )8 ( ) 7 $ # 7 - ) $ 2 ) 3 $ !
! ½ " # # " # $ %
! & ' ( )) ) * ' ! ! ' % ) ' # ) + , #
* * * - . / # " # ) / 0 + # ( ! # ) ( ! # ) / ! / % # 0%
# ! , # ! . $/ ) ) & / % 1 2 1 2 ) , # 3 % % $ & # # ! # . % % ) ( # 1 2* % " /
' # ! % % % ( $ & ( 456 % 7 )* ) $8& " 7 )*' % # ) " * ) $ ! ½& , 9 ' % % *
0% ) -
: ) ) - ) # (* 7 )*# ; ) ) % % 9
B gewinnt A A gewinnt
A
B
B gewinnt
B A gewinnt
! " # $
% #
& # # ' ( # ) * ( + ,
# +
( ( ( # - . /
& 0 1 2 3 ´
¸ µº
) ( + ( $ ( #
( $
( # +
$ ) ( # ( ' 4 2 5 # # 4 6
!" " #" # "
$% " & '
' ( )*" " "
+
,
)
" " +
" + -
"
"
# . $
) /+ +
"
0# 1 +
1
/+ )* " 0# 1 +
) /+ +
1 "
/ 1
) /+ )*
$
/
0 2 3"
+ / " )* + # 4 #5 * ) $ " 2$ " )" 6 )*3
/ "
$ 7 8 " / #
) + " "
/ " / 9
) " /+ - (
"
! " # ½ $ ! % & " $ ' % % " % ( ) (
* + ," % - .( & ( ) $
& ( / % 0" / ' # , 0" , ' . ) , ) ' ) ) & # ) ( 1' ) '# ( ) ( ) * ( ) . 0" ) % % ( ) "" 0 " ( " ' ( + ( " " ' ( !" 23 2 3 (# !" 4 . , " ' " ( ( 5 6 ¾
¾
¾¾
¾¾
# "" 0" ' # ) - 7" '8 ( "
½ ¾ ¼
¼
¾
¼ ¾
½ !" # $ %& # ' ( ) * # ½ # % # ( * # + ¾ , ¾ - ' " " ""
" * !" .
/ " " 0 0 !" ) * + " " 1, 2 34 "" !" % " 0 # ( !" 0 # % " ( 0 ) 2 34 0 " * # 1, % ( " * 5 1, .
! " # $ " % & &'" " ( ' " ) * + " * ," +& " - ." ' / % &'" 0 1 &23 & $ . $ " " " " & 4 5" " ' " 6"
7" 8 4 " " # 9 " " 9 " " :&. " '" ; /& 0 8 " ( (
9" 0&7 0 " < +. 0 7 ,5= " 5 " / " " - ! ) " % &'" & . 0&7 0 8 +. 0 (& "" " " '= +" '" / 7 " # " "" ." * % & '" " " 0 9" " ,5= ' ' # / " / '" * '" +" : 1 - / "= "/ .
Presburger Arithmetik
EXPSPACE Roadblock (siehe Abbildung 7.14) EXPTIME
PSPACE Affenpuzzle (sieheAbbildung 7.1)
NPC co-NPTIME
NPTIME
PTIME LOG SPACE
Gehaltssummierung (trivial) und Primzahltest (nichttrivial)
LOG TIME
Telefonbuchsuche (siehe Abbildungen 6.1 und 6.2)
¾ ! "#$ % & ' ( "#$ % ) *+ ) ( , -( , -( . " , / " &0 1 * 2 3456 "#$ ) *+ "#$ ) *+
"#$ ) *+ ¾ "#$
7 , 8 / 0 , 9 , 8 "#$ % 8 , % , & 7 ' : , - % 8 , "#$ ) *+ # & 7 , . ; - ) " ) *+ "#$ < 7 , , , , " *
º
$
# #
$
%&'
! "
( ) % ) ( )
( # * +
) ,-. # ,. # / ( (
#
1
0 #
# - 2 " (
#
( )' # # 3# 0( ) 0' ( 0' ) ) 0 # ' # )
4" #(
)
3 3
%&'
0 # *
4" # # #
( "
%#)#
* # 3# ( 3)
%% &
4"
# ) # !
# ' 5
%% &
# # (
(
$% # 0
'#6 '
( 63 " ) #
-
) ( ) ) 3# ( ,'#6. # ,'.
3# 3( ) " " ! ) 5
(
'
) # %% &
%#)#
(
# 0' 3# #
#
# 7# ( ) ) $% 88 # 89 # )
!" # $ % &
$
% '
!" $ ( ) # % # # * +
( # , "-
. % & #
( # , "- '
/ 0 % # #
1
2 * # & 0 # &
# 2
2 2 & & 2 1
3 # & " 4 # # 2 &
½ ! " # $ % &%' ( " )$ * $+, + $ + * - $ $
¾
¾
½¼
¾
&%. / 0 0 &%& $ *% 1 " 1%
(
¾
$ 2 $+
!$ 2 $+
!$ 2 $+
¾
" " " 0! ( % 3 " $ 2 $+ " % &%4 1 " $ 0, 5 6 $ ! $ 0 * $+, % 1 " $ 0, 5 - (
1!6 * $+, ¾ % 7 " 1! $ $ " *! $+,%
&%8 7 $$ " 1 - - $ -
! "
#$
! ¾ % & ' ( ) !* & % +$ ,, - . / * / 0% &
,1 0 2 - 3! 4 3% ! 4 5 - ) & * - 0 *
½ ½
! " #
! "
½$
% " ! & "
# ' ! " $
#
! ' ! " $
#
( ) * $ + & , - $ % &. & ! +- /
0
# + 1 +$ &. & # /$ & &- ( 23 ' - $ 4. ! . -. $ & ! , & 5$ & ' - . 6789 ' $ . / !
-
-
( 22 * : * 0 ;
< ; =: - & -$ ; .
. 8&
" $
; -
.$ < ' < ! &$ / % < '. 5 ' < ! &$ % < < < ! ' < > ? &$ & < < ! * . / . . ! & " $ < / / @ < & $ / . . ! & " = $ @ < - . $ . . ! & " & $ > ? ! $ < -
<
A 0 ! ' / .
! " # ! $ # %& # ' ( ' ! $ # ) # * ( ' * + ' ! $ # ) , ' -
. * / ) *
' " * 0 * ! ', ) * * 1 2 * 3 / * * ' * 1 1 ½ ¾ !0 * 1 ) * 4
5 2 * 3
* * $ * ' ' "
6 6 - * ! 6 * ½ *
7 ! " # ( 6 # * ( %& ' * #
8 ! ! " # 6 , ' -
* 1 ¼ * *
' ! 4 9 : #& ' ! -
# ' , ' -
* / ' ; < # ( 6:
' =- + ' #
!" # 6 6 > ! $ # * 6 .
' '
: ?
6@)/ 6@)/ 6@)/ 6@)/ #%/ #%/ #%/ #%/
!
! "
#"$% & ' & ( & ( ) '*+ , "
-.
"
-. /0
"
"
/0"
1" ! 1"
-. /0"
! /0
/0" 2 "
3 & ' &
1 ' 3
1 ' ' ( " #"$# 4 1 & ( & ** +*
3 4 5 & & / '
+*
( ' & 6
! " # $
! " ! ! % & ' ( ) * + , - + . / !0 1 " 2 # 3 4 5 , 6 - * " , 0 7 8 09 7 & $ 7 1 5 3 7 , ,# : " : 6 0 , !0 1 , 0 5 , 6 8, ; * & 7 16 # 5 8, <
!" # $ % &
' # # ( " ! % " " ) * + , !
&" - $ . / &
. # ! 0 1 % 2 2 / # - # 3 & " 4
! 5 )"
4 ! 2 2 # ( " '
# / & % ! 2 & + # # " # . + 2 &
.
+ -" " ½ ¾ % 6 7
8
½
½
¾
¿
!
"
#
$ % & $
' (
%&
& )
& * +
, -+
. ! ! )
,+
+
+ / * ( ,0 0 1
) ,+ - 2 * + & 1 & -+
3
+ &4 %
& + ,+
5 +
6 2 6 & . 7
$
* +
+ + -+
8 * 2 6 4 -
- & - - & -
9 - & ½ " : ;# ( -
< "1 %
& , =# / Ì -
% 6
6 2
-
Ì % - /
-
7
!
Ì ! " # $% % & '## " () #
* % # %# $ # # # %#%
+ % , -. + #
%
% % + (
/ # 0 , % + %
" #
'##
( 1¾2 1¿2 , -3 ! % 0
, % #
%#
% # , -. , % 456 , -3 , % 46 7 + , % #
4 % # 6 8 %
0
& / 7
# , % # + 9(
%# :" 5#, % # ( ## # Ì 1
%
!
! " "
# ½ ¾
Ì
$ % & ' (
" " ) " (
* + ,½
&"' ( + ( - " . -
$ " $
/
+ " !
) 0 0!1 !
!
0 " ) 2 , 23
" 45 % - " 6 " % ( Ì 0 0!1
- $ 7 86 ,
unentscheidbare (oder unberechenbare) Probleme unhandhabbare Probleme
handhabbare Probleme
Probleme, die überhaupt keine Algorithmen zulassen
Probleme, die keine angemessenen Algorithmen zulassen
Probleme, die angemessene Algorithmen (in Polynomialzeit) zulassen
! " # $
Ì % Ì & ' & ( ) * + , ' + + + -+
-
. * & / 0 + 1 + - $ & ' &
& ' -
/ 2 + * 3 04++ ' -+ .& +- / + + 1 " 5 Ì ++ + 6 -+ 7 &8 & 6
9 -+ .& % 0" & +- " 1' + +-
W
Î Ï
V
! "! # !
" $% &' (! ) * + , + - % . + /
,
Ì ! Î Ï " # ' , Î Ï 20 3 0 " $+ 1
$ 4 ) 567 # 8
Î
8 +/ !
+
Ï )
# 8 , " " 0 ! ) " + ) ,% . ) ! ' 8 9 ' 0 *
)
$ 8 % ' 4 )! " 7 )
4
7
: 0 $ 2 + 3
!
" # " ! $ % & ' " " ( # (
) # # ! * + # ,
Ì -
#
. '
-
- #
"
# !
. ! " %
# +// 0 "/ 1
2 +// 0/!
" 345 6 . / +// !0!
2 " "
$ ! ¾
!0 # " 3456 # " 345 6 #! . % 0 " 2 - / / # "
# " 345 6 " 3456 1 " " ! ' 2 0 /0! 0 # # 0 "
7 " 0 ! !
1
2
3
4
5
X
abb
a
bab
baba
aba
Y
bbab
aa
ab
aa
a
(a) Lässt eine Wortensprechung zu: 2, 1, 1, 4, 1, 5.
1
2
3
4
5
X
bb
a
bab
baba
aba
Y
bab
aa
ab
aa
a
(b) Lässt keine Wortensprechung zu.
! " ¿ ¾ ¾ #
" ½ ¾
$! %! & ' "( ) ( * $ ! ! ! * + !, % * ! +- . * ! ' +- ! ! ! " /0 ' . . ! 1 . 2 %3 $4 . % ! 3 + ! 5 . * % * 6 . 7 . 7 ! ( 8 ! + ! 9( ! 6 . ! % ! 1 + ! 2 1 ! . 6 7 3 ! 1 2 ! 1 : ! ;( ! !
& 1 ! ! * ! 6 - ! ! 6 1 . +- ! < ! :
! 3
& ! = ! ! ! ! # 4 ! 9 ( ! # ! 6 ! ! $ > ! ! * & !
Ì !"# !
$ Ì % &
! ¼ $
$ ' ($ ¼
)
' ($ *& + *+
! Ì " Ì
# ! "
$ % Ì & " ' ( Æ ) ¾* % ! ' +& +& " ' Æ , " - . Æ ½ /+
" ' /
$ , Æ ) 01 $, * ,
,
- $ . /(
" $ 0 -1 , $
0 $
2
" $ 0 " $ $ *& + 0 & ( 3
0
$ (/( $ *+ $ 0 $ 0 $3 4
0
20
! "
" #
$ $ %
& ' $ $
%
' ( ) ) %
) ' * + ,
) '
( - ' ))
") . ' )
/))
) %
0 ) )
%
0% % " ' ) 1
# ) " ) # " % 23444 ) 5 ( - 678 % 93(,
)
$ ' 93(: '
0% + " ' %
0% 93( ' ; ) ) # ") )
)
' # %
)
1 )
%< , = ' )
* " ) >
¾
! "
#
$
%
$
½
»¾
¿ ½
& '
" $
( # ) * & " + ' ) , , - # . # ,
, " / )
0 1 * / 2 , 3 # 4 5 , " * 3 ) & 3 6 &+ + 7 / # + %, ' / & / $
/ 8 3 % (
½
½
Ê
" # # % &' -% .
!
# $ #
()* + $ '
,
Programm oder potentielle Algorithmus Eingabe R
X
Hält R auf X an? falls R(X)↓ ,,ja“
falls R(X)↑ ,,nein“
!" # $ % & ' ' (" % ) ) * # " + ,-. / & " , . " / 0 * ) $ 1 & # " %
2 3 %* * ) ) & + % ) 3 4 # " "
# 3 5 #
) & 6 1 7 # & ) % ½ ) % # ) ¾ )
!
" #
$ %$& '
(# # ) #
* + , + # *
+ +
*
*
# + - + * .
+ " + / 0 1
, 1 , 2 + ! # # #
+ 1 3 4 0 5# 5 ' 65 + + . 65 + ) # 7 *
6 5 + 5 6 + # + 6 )+ # 5 + 8 + - '5 +
9:05 #
+ , ; * +
- 5 * + )+ " * < + * # =
! " # " $ % ! & '
'
! ( ( ' % ( ) )
' )
( ) * & +, -
+, - . / $ $ , / ! " # $ % ! &
" ' () * + $ , # - % $ # . ' $ . / * * ! & 0 " + 1
!
" # !
$ ! ! $ % & ' $ ! ( $ ) *
+ $" , - &
)
+ ) " ) * & * '
' & .
/
)
$
) * & ) )
& ) ) 0 " !
& $ $ 1 ! ' .
/ ! ! ) &
$ 1 2 3 &
% Ë % É *
2 & $" )
" ) ¾ $ 45 6 7 8 78 !
Ï Ï ¾
! ! " ! !
EingabeProgramm W
W
W (hypothetisches) Programm Q für das Halteproblem
Q
,,ja“
,,nein“
neues (hypothetisches) Programm S
Ë
Ë É É Ë É Ë !
" # $
ÇÍÌ
ÍÌ % É & ! ! Ë ' ( # Ä % É )
Ë '
Ë ! !
* ! +
S
S
S
Hält S auf S an? Widerspruch
S(S)↓ ,,ja“
S(S)↑ Widerspruch
,,nein“
also S(S)↑
Ë Ë
also S(S)↓
Ë Ë ! " É # $
Ï Ë Ë Ë Ë Ë Ë ! " Ë # $$% # % & É '( É ! É Ë Ë ) Ë ) Ë É * +,-
Ë Ë É ! Ë Ë " # Ë Ë $ ! % &$ ! Ë Ë & ! '' ( )
% Ë Ë * ) É Ë Ë + $ Ë , Ë & )
Ë ! , "
Ë - Ë !
( ! !
É
.
/ ! Ë %
É ,$
01 . !
! " # $ % & ! " " " " ' ( ! $$ ) # $ ! $ ! $ # $ *$ + ( , $ ½ - . / '
" 0 1 # $
2 ' 0 " 3+ "
8
nein nein
ja
nein
ja
ja
ja
nein
ja
7
ja
ja
ja
nein
nein
ja
ja
6
nein
ja
ja
nein nein nein
ja
nein
5
nein nein
ja
nein nein
ja
ja
nein
4 alle Programme 3
ja nein
ja
nein
ja
nein
ja
ja
ja
ja
nein
nein
ja
ja
nein ja
2
ja nein nein nein nein
1
ja
ja nein
ja nein nein nein
ja
1
2
4
3
ja
5
Diagonalprogramm
vollständige Beschreibung der Halteinformation des 5-ten Programms
nein nein
6
7
8
ja
nein
ja
alle Eingaben nein ,,Negativ“ S des Diagonalprogramms
ja nein
ja
ja
falls S das 5-te Programm war, müsste dies ,,nein“ sein
! " # $ % & & $ & & & ' # ( & ) # * + ' , & ( ' - . ", /0 1 " # * + ( 2 ' & ' ' & ' Á
Â
Á
Â
Á
Á
Ä
Ë
Ë
Ë
Ë
Â
Â
Â
Â
Â
É Ä Ë ! Ä " # Â $ Ë % Ä Â & Â É $ $ Ë $ ' % É ! ( ))*" É + , - +., / ! - Ë 0 1 $ . - / 2 Ë Ä $ % )3 % Ä . " / % 4 ! 1 + , Ë / 5 - $ Ë 0 6 / 1 Ë %
!"#
$ % & '( ( ( )(
* + ( , -
.( (
!"# + ' . ( . / )( "( ( 0 ( 1 ) ( &( % )( $ % +2 $ ( )(
+
+ (
.( (
(
( ( )( 3 " - ( (
!"# ( 2
! " # % #
$
&
' " ( )
% *
%
+ ,$
%
! "
( - *
) # * %
,
" ! . " $ # , " /(0 1 ) " 2 & #
/0
3
4
"
" , ! #
) "
/0
% "
" 5 " ! & ,
2
) " *
.
2 -
) " 1 "
)
1 - ( ) ! 6 - /(0$ /0$
, # !$ 6 " 5 )
4
# /(0 /0 # ! $
) & , ( +
!
( "
# % " ! - 3 . "
Eingabe X
alle möglichen ,,ja“-Nachweise C weist X nicht nach erzeuge und überprüfe einen neuen Nachweis C alle möglichen ,,nein“-Nachweise C weist für X ,,ja“ nach
,,ja“
C weist für X ,,nein“nach
,,nein“
! " "#$ $ % $ &
' % # ! $ ' ! " # $ ' ( ! "#$ ) ' " $ ' ( "#$ ) ' * + # , $ - $ + . / ! " "
* 0 # $ '
! " # "$ % & $ ' ( ) * &
$ ( # " + ! " ' ) ,! # '
% - $ & $ $ " ' ! . -/ & $ - 0 + - , + & $ $ 0 " $
$ ' $ 1/ # $ ' ( $
' ! ( - ) , $ * ') .! $ 2 $ !' ' % $ ') ( 3 & $ $ $ & - , $ 0 " " ¿
, & $ 4 , $ *$ , $ 5
,, $ & - , $ ! & - , $ $ $ ' 5 6 , - -/ * " '# '
- 7 - ' " $ ' +
$ 7
- ') 8 -/ &
$$
' ( ! -/ ( $ 5 $ , - - $ $ -/ , , ! $-
! " # $ % ¿
! " !
# "$ % & '
(
"
) (
" *+ , - . ( / "$ ) ( + % % % " 0 *+ ( ' ( ) ( 1 2 3 - ' ( ( , $ ($" 4 "$ "
0 " 5 4 "$ 6 , 4 ( % ( 7 ( "$! 5 64 "$ "
0 ! 4"$ "
0 $($" 8 "
$ '$ 4 $($" 9 ) " 4( " ' ( & 2:3 2;3 , ( < (( =(
&
. ( ( 2 3 "$ $ >
(
*+ ( ' ( ) ( ( ( ,
( 8
! " # ! $ % & # ' ( ( ) " * + " * ** $ % , * - .
- . ( / 0 1 %
& , / + #* (
0 * + ( 2 & 3"45 $ 6 3 5 /
*
" "4 & * 1* * * !* 0 * $ % & 7 8 * ( ( 9 " 4 * * * / " * + 0 " Ì 3% *
!" " ! #
" $ ! % & '() * " ! % & ') +
* + * $ , -. * # / ! " $ ! .
% - ( ! 0 . 1 " 2# # %3 4 #5 * 3 6 $ % " $ !$
7 ". 2% " , # . " . . .8 " % * " 6 "
* " !
/ # 7 . # % . # 2( " " % # * / , 4 & . . * 2# 6 6" ½ *+ ! " # $ ( 9 .& 6 : $ 0
. " 2 $ & 7 2 7 . # .
z.B. Wiederkehr-Domino hochgradig unentscheidbare Probleme z.B. unbeschränktes Domino unentscheidbare Probleme
unhandhabbare Probleme
z.B. beschränktes Domino (vermutlich)
z.B. beschränktes Domino fester Breite
handhabbare Probleme
! " # $ % ! % & # ' (
% &% & # $ % % & $ ' ! ( )
& % % *#!$ % + , - . %
/ % % % & !
. $ 0 $ & / % % % ! 1 ' . % % , - 1 $
!
" # $$ "% & " % " '
( ) % *
* + ( , "% - % ( . / *
& % " 0 1 /
* % 2
/ * % "
3 / * ) " ( " * ) 0 & " 4 ( 5
4 " ( 6 " " 3 " 4 0 ( & , ) . ) - * / 7 * & 0 8 0
)½ " 0
" % 0 "
" 9
% 0 "
) "
" ) " & : ; < "
: ; = " 3 > , " 1
) >
. / ) "
: ; ," 1 ) >
. ) >
( 5 ?
½
!
"
! " # $ % #
& ' () " " * + * $ , % % -./0 1 2 3 4 )
5 6 $ " 7 8 9 2 , $ 2 ) ' 6 " * $
$ "
)
: ;< 2 7 9 6 9 = =
& 7 ' = >
hochgradig unentscheidbar unentscheidbar (nichtberechenbar) unhandhabbar handhabbar
Berechenbarkeit im Prinzip
Berechenbarkeit in der Praxis
!
"# $
# % &
#" ' ( $)
Ì # *# # ! * % + & , #
' %
- . /' % )
$# % '
/' # *
01 % ' / * $
) $ $
$ Æ ))Æ )2
# ' % 3 - $
4 . 56 '
7 8 * # 8 ) 9 #
! %* #
7 * # 9& 7 8 # 8 * 9& 7 # * 9& :
# / 3 + Ì %
! " # ! " $ %& ' $ ( ) $ * + %, ($$ ) " $ $ -
.
/
0
1
2
%3 ( ' + $ * $ ) " $ ( 4 ' $ ( $ ) $ $ * %% ! $ 5 $ $ * . 6# . 7 $ - ) 6# %8 9 . #: $ +
Ì ¼ ! Ì Ì " # ! $ " % & ' ()* + )* ' ()*
,-. + /0 1 + 2 + " )* $ 2 3 1 ! 4 # ,-- 52 1 / 0 / 0 ! + & ! $ 6 + & ! $ 2 + 7 #
,-8 7 9 5 : ; ,-< ! 2 + ! = 51 6 ! 1 2 $ 5 + + ! $ $ 5 + ! ,-> # ( " 2 2 ! ( ! " 2 ( ! & " 1 2 ,-? * " 5 /@ 0 + 1 " ! " @ / 0 ; + 5
½
!
" # $ % & '()
* & . &
-
¾
+,- &
,- /
"
'(0
.
12 3
.
12 3
1 3
.
1 3 # * 4
"
, $ 1
3 .
3 1
+,-
"
* 1
3 1,
3 . "
'(' # $ , & 5 * , 5 * 6 . 7 '(8 $ 9 . 7 !
: ; * , 5 <* .* : , & , , , . . 5 5 *
'=> 4 & 5 * & ! "
:
$ !
/& <* .*"
'=( # $ & & 7 *
5
! " # $ %# & " ' ' ! ( )! * "
+ # , - .+ / $ ( 0 1 2 # 3$ ! # # 3$ 2 % 1 1 *
)
1 " # * * # 4 2
$
( + 2 "
, " ( 5 (
, ( (
( 2 (
( /
15
−4
6
104
6.5
0
−61
3
586
1
7
102
15*−4*6*104**6,5*0*−61*3**586*1*7*102
! " #$
# %# & % ' ( #
) * + , -
%
% ). /
/ 0 + 1 + # 0
" % / + #* . 2 ½¼ 1 30 % ¼ ½ 4 + %
#* /
/ . 0 #
/ +
. #
0 -
+ # *
# 5 $
6 / 7 + 0 7 . $ 56 +
#*
. 56 + 56 + 3
894½ + %
$ + 7
#*
# +
½
T
V
Q
G
R
M
S
N
W
L
P
T**V*G**Q*R*S*W*L**M*N*P
! " # $ $ % & ' () *+ *+, ! ! - ' .
/ 0 $ '
1 #
2 ´ µ´ ¸ µ´¸ ¸ µ´ ¸ µ´ µ´ ¸ µ´ µ´ µ´ µ º
( $ $ ! # $ 3 ! # ' 4 5 $ 6 $ 7 " " 8 () ' ' - 8 . ' ' 5 !' 9 # () (' ) 0 5 ' 5 :$ " ' ( ' ! $ ( ' $ 5 - 5 ! 8 ' ; / 0' ' $< ' "
! " # $ % & '% (% # % )
* ) '% + , ) ) %$ (% ) '% & - . $ / ' 0 1 ! ( + # , 2 ( , *3 & - % + ( 4 % 5 &
, 6 ,
' )
7 8 + , 5
% ) +) 1 0 5 ' * $ , 5 9 *3 + $ % 4 , - % : 9$
d
c
c
a
a
b
a
*
d
a
b
b
*
b
c
* c
a
b *
a b *
c
! " # " $ % & ' ( ) $ (
&
'
* "
+ " " , " ( - $
- (
. %
, $ ( '/ 0 1 2 0 1 ( 3 2 & - $ '/ 4
'/ 0 1 ) 56*
!" # $ $
% $ & " $ $ # ' $ ( )
* $ " # "+ + % * , * # " $ -'
$
'
. # "
/ + + -' " " 0 * & 1 ' 0 " " ' 0 ' & ' ' + / " "+ / "+ $+ ' & " 1 '2
$ # '
"$ "+ ' ' #
3" ' 2 2 0 4 5678
, 0 2 0 2
( )2 ( ) ' # * #
a/a, R b/b, R move a
#/#, L
test a a/#, L
a/#, R b/b, L
#/#, L #/#, L
mark
JA
NEIN #/#, L
a/a, L b/b, L
return
a /a, L
b/#, R
b/#, L move b
#/#, L
test b
a/a, R b/b, R
#/#, R
! " #
$ % & ' ! ( ) ' * $ & ( +,* ! $ &
- ) » » . / $ 0
" 1
& 2 3 4$ / 4
0 5 6 5'6 1 » " & ) ( ) » *7
! " ! #" ! " $ %
8
& ( 9 *
&
!
" "
#
$" "
%
$
& "
$
' ( $" ) ( * +
& , -
$"
+ " $" * + * $" *
)
* (
)
+ " . " , ." / 0
* $" $ 1
2 "
1 3* &"
( - +
)
4 *
* ") "
+ #
( $
"
+ " 5$ /
0 (
*2 " *2 " "
"
+
*2 " %) ( 1
2 "
( "
) 1
2 "
4 *2 " ) " ( +
*2 " "
- ) $"
*2 " 6 .+ ( *2 " ) $"
*2 "
) + +
5
7
) "
% +
)
) 1
2 " + + )
. $" ( &
*2 "
* *2 "
+ )
$" %
*2 " $" *2 "
$
89
:
$
" ) ( %
*
*2 " *2 " -
... # # a b b a # # ...
... # # # b b a # # ...
1
... # # # b b a # # ...
2
... # # # b b a # # ...
4
... # # # b b # # # ...
5
... # # # b b # # # ...
7
... # # # b b # # # ...
8
... # # # # b # # # ...
10
... # # # # b # # # ...
11
... # # # # # # # # ...
13
14
... # # # # # # # # ... 16 JA!
... # # # b b a # # ... 3
... # # # b b a # # ... 6
... # # # b b # # # ... 9
... # # # # b # # # ... 12
... # # # # # # # # ... 15
!" # $ % & ' ( # ) * # # + + # , % $ # - . - . / 0 % 1 % , #
2 1 $ % 0 # $ 3( 4 $ 1 #
" , 1 5 % # 6 # 7 8 # # 1 9: ' !% ) " , 7 # , , 9: ' 9 9; 4 # 6 5 $ 4 9 ' % 1 # % 9; " # ; %, " # 6 # $ % % % , % # 4 <
*$$ ="=$ " !" %&' % ' ( ! " #
% 2 # # " < 1 9, $ 4 % ¾
! " # $ % # & ' () ! *
!
" ¾
# $ % & ' $ $ (
) * $ ) ) " + % " $ ) % " $
! +, - . ! ) / $ 0
" 1 $ " " +, ( ! !*$ # $ &2' 3 &2' # (4 " ! $ &252' &22' , "
# $ , "3 6 0
*
% + , * '% ! ( - ) % " .
/0
1 2 ( " ¾
1 3 44
½ ! " # " " $% " "" " " & & ' % " ( & ) ! ) * + % ! , "" " # " """ & $ " ' % - &
" % ( . & " & / 0 # " $ " ' " )
1 " & ! + " & "
2 2& 3" 4 5
66666666678998:;<66
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 +
6 6 6 6 9 9
6 6 6 > > >
6 6 = = = =
6 : : : : :
: : : : : :
+ + + + + +
7 7 6 6 6 6
8 6 6 6 6 6
6 6 6 6 6 6
9 9 9 9 6 6
8 8 8 6 6 6
: : 6 6 6 6
; 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
? @ " A " # "& ) " % &
! "
#
$ % ! " " &!
! $ " " " ' " ' ( ) )" " ! ! * " +
! " # $ % & ! ' ! ( ! )* ! + ! % & , -./0 $ ( ! , & % 1 % 2 1 % 3 34 4 5 6 ) % , 7 ! &! 7 ! 8 , 2 9 ! &! 2 8 9 , 2 8 , : 9 % ! * & % 5 # , ! ; , ( 5 ! , 5 , < , 53 2 * 1( 5 , 8' & 9 = > )* 7 ! < 4 ? 5 ! '
@ ! 5 8 9 ! ) : ! :
! ) % 6 < ! + 7 A ! + , ' + 7 ! , ' & & < 2
!
"
# $ "
$ % & ' # ()*+ ,
- % % . ! /
$ 0 $ 1 % &% ! 2 . " - . & & 3 4 * 5 6 %7! 8 9 6
8
4 9
! 3 & 4 : %
0 1 $ $ !7 - 2; 6 0 1 !
- - ! - %
. % <= 2 / 4 >
! ? ! 9 4
&
! / " $ -
' 4
; 6 ! >
% - ! / "
- - 4 $ @
$ " $ 0 1 $ ! /
4 % %= /9
! " #
$
" " %
&
'(
) " ) * + " , - ) $ * + "
)
,
) " !
. / " $ , - $ ($ " (
$
( " 0 ) ) ) $ 0 1 " , 2 , - $
3
* -4 -55 -56+ $ /(
3 7 0 $ ) $ 8
$ /
7
'
0 9
0 9 ,
) " 9 ) $
* " 0 1 $+ : ; ) $
< = 9 ) 0 0 ( $ , : $ ; ' ) " ) $ > $
! " # $ # % & ' ( ) * + &# " ,-$ + " . # $/ #" ,-$ + 0 1 $/ " & " 2 " ,-$ + ) 1 3 " &# " & ) ! "
)
4 ) 5 % 4 . # ) 6 ' . ) 6 1 *" + " + 7 3 8 9 * * " ' : " ' 1 " + ) $ 4 " ; " <1 % " ; " + " 8 (8 % ) ( * & + "
" ) .
, ) $
5 & ! " # )
* # " < 2 " #3 8 ) $ #= ) $ & >44 ) * ?= @ * # 5 4 " ! @ 6 1 & " " 4/+ 4/+ ) * " /+ )
1
...
b
*
a
5
b
7
!
7
a
c
a
c
#
...
a
#
...
b
!
a
..
.
b
*
a
5
2
3
4
7
7
b
a
!
b
5
!
5
a
a
a
c
*
*
# ...
a
c
a
b
b
...
#
! " # $% & ' ( ) *
! " # $ # % ! & ' ( ' ! " ) ! # $ # ! * ) % * + , * - . $ % + ) / . 0 +
1 ' $ % 0$%$ . $ % + 2 3 %4 0 %0 $ , $ # % 0 / 4 5 " * 6 # 1 ) ' # . 6 ! 4 / %
"% # $ % 7 " # " 6 * % 8 6 + 9 :;
6 " 8 % 1 + " ! "%
¼
! " # $ % & $
' ( ! # %
! ! ) #
# # * ! + ' ) , '
¼ ¼ ¼ ) - % ' ! . ) & ' ! -
# % - /
+ 0 1 ) ' # ) !(
% & # - ! ! 2 3
' 2 ) ! /
! 4
! " " # $ % $ "
" # & ' ( ) *& + , $ " " " . $ / & , 0 12 " . 3. " / " 4 $ " . ) 0 " $ ½ 12 "# " . 12 " . ! % 0 1 $ ! % &/
" " # ) $ " 4
" . " ¿ 5 6 "
7 . 0 12 # $ " 5 " " " ( $ " 8 ! 9 % : 8 2 0 (
8 ;1 " " " 1 8 ;1 5
1 $ 8 ;1
" ( 8 ;1 ( $ <= 9 $
12 $ & 1
.
# "
¼»½ ! ¿
Position des Lese/Schreib-Kopfes
...
#
#
a
b
*
e
b
!
#
a
g
a
3427 und 393014
ausgehend von der Korrespondenz:
#-0 !-1 *-2 a-3 b-4
#
# ...
c-5 d-6 e-7 f-8 g-9
! " # $ % & ' (%) % * *%+ , ) - )&. ,%- / % % 0
,.- % )1 0 / % / 2 + . 0 % ) / * 0 %!& %)3 % / + 4 / %1 & 5 ) % 6 1% ) *%+ , )- % ,% - 7 ) 6 % % & 8 + " % 9 1 *%+ % 0 % %() / ! 1 / ) &
½
!
" #
$ % % " # & ' () * + % , % $ - , . &
'
# /
% # %
' * * " # % ! * & " # 0 / 1 2 3 % 4 / +
' & & /
& &
5
1 * 2 63
# 7 * . 2 8 # . + + 9 . 5 * $
+
* # * . * ! : 2 6 & ;"" 5 . $
5
9 . " # 1½3
9
Ï
6 <
" # 1=3 > + " # 1
Ë
2 3 & .
! " # $ % &
$ $ ½ ' ( ( ¾ $) *& $ ½ ¾ + # ) , ( ½ ¾ $) $ , * $-+ & ) $ , . $ ( ' ( / 0 $ . ) $ ! 1
. ( & 2 & & ( 0 3) $ ! 0 ( &
& 4 0
) & ) $ ) $ ) & 0 0 ) $ ) $) # & ) ( () ( 0 $ " $ ) . " * 5+ ( 0 % # ' & ) ' & 6 0 7 (8 9) ( 0 # $ ! . " & ( 0 $ $ ( 0 & ( # . 4 ' )2 ( 9 ( 0
$ ½ $ ( ' & ! ' (
Algorithmus A
P implementiert A; ist in der Sprache L2 geschrieben
Programm P
Eingabe X
universelles Programm U, in der Sprache L1 geschrieben; simuliert die Arbeit des Programms in L2 auf einer Eingabe
Lasse P auf X laufen!
½
¾
Ausgabe (falls existent)
¾ !½"
# !¾" $ % # & % # ¾ ! " $ ! % '(" ½ ¾
) % * + $
, + - #. * / 0 $ 1$ - #. * &
+ 1 % » » 2 1 # 3 * 4 % '56
»
»
»
! "# $ %$ & ' $ ' $ ()$ $
# *+ ( ' , ' $ - - . # / . $ $ & . 0 ! $ &
# * 1 # % &'
2 '- ' 3 $$ % # 4 4$ . $
5.# 6 $ -
5 #
5. $$
# 5. $$ - &
5. $$ '
$# / $ 5.
$$ 0 5. $$ $ 5.
$$ # / & 5. 5. ' - 7 & $ # $ 8 $ ( '. % -. # $ & $ . ' $ 39 .' 0 . & 0 $4 6 $ $ - 5 $
% :'- #
/ $ '- :. $ * 5. $$ ; 6 '- $ . & ' ' # / < 0 5 $$ 5. $ 0 $# & ' 5 $- . 0 ' $ $
5 . 5 # = $ $ 5 $ 5 5'' 5 $ # 4
!
½
"
# $
% &
# ! $ &
"
% $ ' ' ( ) * ' "
+ &, "
& & $ - .
+ $ $ /& $ 0 &
-
& 1 0 &, 2 ,
'
* - &
& - "
3
, + " ! * + 3
24/ 1
&
"&
% $ 3 5
& &,
% % . ' - & 0 " $ " , - & + 6 7 ( 3 8 % , 1 9
1
6
: % 1 ; , :
! ½¼ »½¼ "
# $
%
# & ! ' (
! # $ ' ) '! * ( ! !
+
, & ( !
# ( ½¼ »½¼ " # $ -
# $ '
!
) ' * ! ) ' ' # ( * + .! ! / ( * # $ . ' 0 ' 0 # /
( !
) ' ! * ( 0 ! * (
( ! * # ! " ! # " $ ¾ " % ! &' ! ( ) "
1 '
, 2 -
% . ! * )( + ) )( + , "
! "# $ % &'( )
' * + , ! - , !! . . / 0 $ 1
2
3 4 5 6 5 "" 5 "78 9 !:, ; 0< <=> < 2
3 "?8 0 + ! @ !: . / , ) 9 !A . %! , . 0- @ . ) 9 9 . ' . ), 2@ > / 9 B8 C - 9 "D6# E ,/ !: 0 ! "D4# E , E ! $ ) , % ; 2<
5 "" 5 "7 0 , ! A ) * F . %! , ! 8
;9 , ! 3 < > ) ; . % % )G ;
! " # " $ % & % # % ' ("" ) * "+ ' $ " "+ # ! "+ , % '+ - % "+ " . ) / ' 0
% 1 2 "" 3 + 4# % / + 5 6 7 # " )8 # 8 ) " ' . 4 ( )7 + " ) 5 6 '+ 0 /"" " % " 9 + 9 /"" 9 ) " " ) "+
9 "+ - : / "+ : " 8 "+ ' " " # / " - " & ; $
5 0 / % "+ - 0 !+ )
! " # $ % & $ ! ' (
) " ! ) ) # $ ! * +
# * ! , * $ - $ .! # /
0 1 ! # / 2 0
0 Ì
' 0 + ! * *
2 ) , ' .!
' 3 4
) &
! 5 ! + ) & ! 4 0 0
2
+ , 6!6.! 4 )
7! $
! 7 ! 0 2 ' ) ! ( 0 7 # '
! " 5 8$ 0 # ! , " $
'
!. 4 ( " 0 9 , $ . ) !
Turingmaschine M
aab*bba
Eingabe X
Transformiere die Turingmaschine und die Eingabe in Kachelarten!
spezielle Kachelart t
endliche Menge T von Kachelarten
Löse das Parkettierungsproblem in der Halbebene mit der speziellen Kachel auf der Grundlinie. JA
(hypothetische) Lösung des Parkettierungsproblems in der Halbebene
NEIN
Nein: Mit T kann die obere Halbebene nicht so parkettiert werden, dass t auf der Grundlinie erscheint. Ja: Es gibt eine Lösung.
Endresultat: die (hypothetische) Lösung zum Halteproblem bei Turingmaschinen
NEIN
M hält nicht auf X an.
JA
M hält auf X an.
!" # ! #
$
Ì ! " # $ Å " % &' " # $ Å ' ! ! ! Å ( ) ! ! ) * Å $ + Ø ,
# die Parkettierung kann hier nicht aufwärts fortgesetzt werden, weil nichts an diese Stelle passt!
#
#
# #
# #
#
#
#
#
#
#
#
# #
#
#
# #
# #
#
#
#
#
#
#
#
#
mk, # # mk, # # mk+ mk+
# #
# #
#
#
tsa,a # ts+a ts+a
#
JA, # JA+ JA+
16 # #
# #
# #
# #
#
#
#
#
15
#
#
#
b
# #
# #
# #
b b
# #
# #
# #
# #
# #
# #
# #
# #
mva, b # mva, b # mva mva
# #
# #
#
rt, #
b
6
mva, # a mva, # a mva mva mva, a # b b mva, a b b # mva mva a b mva, b # a b mva, b # mva mva
5
4
3
2
1
#
0
0 0
mk, a mk, a 0 0
b b 1 1
# #
b b
2 2
# # # #
b b
a a
# #
# #
b b
a a
# #
# #
3 3
4 4
4 4 #
4 #
! "# $% %&
! "# $ % & # '#() $ % * $ '#+ , - . /# % '#0 # 1 2 " 3 4 5 # 6 7 '#+ % 8 9 #! " '#0 #: $3 3# ; / $ % % < # 3 $ / < 3 2
'#' # ; 2 =! $ #
, 3 , !6 3 4 > % / $ 3 # ? , 3 , # 4 / 4# # " ,@ / & 3# 3 $ A : # , 7 & 3# % $ 8 " # $ $B, % 8
! " # $% &'" $ ( ) * " $ + , % ! - . - " $ , + , ! / " $ , , ! - + , * " 0 ! / - , $ ! / $ , ! # $ $ &" , ! 1 $ $ 2 $$ $ ! / $% $ 3 45 4 5 $ . " $ ! / 6 ! 7 - ! 8 " - 9 63 $% - - : 2 " " $% ! 1 9% - 8 ; - " - 6 6 " " $ " 6 " ! # - - " ! / " . ! 2 4 5 $ 3 - - ( 45 4 5! # $% < $ + , ! . $% , $ + 3 < 6 $ % !
# $% = >!?? - 6
a
JA
a b
b
a
a b
b
b
b
a
JA a
! " # ! # $ % $
! & # & "' # ( ) (! ! ! * # ! ) * + , #
"
* + - ! . # # / 0 .
!
!" # $ % ½ # ½ &
!" # $ ' ( &! ! &! ' ) #
im Zustand s im Zustand s
Originalfolge X:
a a a a a a a a a a b b b b b b b b b b
JA!
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
entferne diese
im Zustand s neue Folge
JA! a a a a a a b b b b b b b b b b (sollte NEIN sein!) 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 der Automat verhält sich hier genauso wie auf der ursprünglichen Folge X
½ ! " ! # $ ! " % & ! '()* ! + % , -
+ # . ,
, / " 0 # +
, , + + ! + 1+ + ! 2 3 1+ 2 3 ! + ! 2 3 ,
0 ! 1 4
zeige Datum
d gedrückt c gedrückt
stelle Uhr
zeige Zeit an
d gedrückt
c gedrückt a gedrückt
a gedrückt a gedrückt
zeige Weckzeit c gedrückt
c gedrückt b gedrückt
Stoppuhr stelle Stunde
c gedrückt
b gedrückt b gedrückt stelle 10 Min.
stelle Min. c gedrückt
! " #$ % &
'( & ) (
* +
+ , - * '(
. ' #$
& ' + , / * 0! !1
1 0! . , + ! 2
3 4 *
! " # $ % $& ' ! ( ' & ) (
! * '
# $ ! + ' ' ( , ,- . ( / 0 . ! 1 2
0 3 - , 1 , ! . 4 0 # ( # $ (3 4 5 67 0 ( . 0 8 ! $ 8 9: # $ 4 . 8 ; , ( " 9: & 9: / ' % . 4 ( # , * < 4 & ( . 9: ! * /
!""# $ % & ' ( ) $ # * + " ,# + & - " , & " , , $ . ,
/ . * 0 * 1 2 $ 3 % $ , & $ " $ * " & " 45 - - & 6 789: ; 1 1 1 *
! "
# !
!
$"
% "
& '
#
& (
$ "
&
&
$
"
) " !
*
$
+
,
&
-
!
$
&
. "
$"
# /
!
! " # $ % " $
& $ '% $ () * & +% ' & $ " $ , & - ! ! $ .
" ! * . $ . , /, ! 0 " ! , . 1 . , * ! &
& , , - ! , 2 ! & - 3, & $ , 4 . . ! 4 % $ , " . . ! 4 % & ! 4 % $ , * . . ! 4 % . ! 4 % ! . " ! . . . ! 4 % ! . ! # . ! " (5 . + '! 6 *
. # 6 7 7 , + ' *
# &6 . # 6 7 7 , + ' *
# & " * ! $ & + ' 6 *
(8 & " + '! * (9 : 7 (9 - (; & " * + '! *:
! " # $ % & '
( )* ) & + , -. / &# & & 0 &
1 2 3 &
# ) %# 0 % ( % "
$ 0 & 0 ) %# (# -1 " 0 4 ) 5 6& 7 -1 " 0 7% ) 0 8 3 &
# ' 0 ( % 9 # ' &
$
0 % 0 (# -1 " 0 4 &: ) -1 " 0 # )% $ ) $ 5 6& 7 - 4%1 -1 " 0 )% # )% # " % ; < ) ; < # " 5 6& 7 $ ) -1 " 0 ) - 1
) # ) & - 1 0 7 7 % ) & & # $ #% " => & & 3% ( / -1 " -1 " # 3 -1 " ? - ?1 3 -3 ) ? ' $ 1
== & & @ 3% " 3 -) $ 1 =A & & ' 0
! " # $$ %&' ( # )*+ # ,
-./! 0 & ' 1 $2 3 450 6 # $$ # # 6 7 4 + # , $ ) 8 9
2 . 9 0 : 6 . 9 ; $ 4 #
( 6 . )! <&' . 9 8 ) $
. )! $
=
# 8 1 & ' . 9 !
# 1 &' > = > 3 $ 8 4 ? $ 4$ ) $2 @ &' ( $
& ' ( $ 8
&' ½ ? A $2 6 6 ½ ¼ ½ $2
6 $2
½ & ' ? ## ¿ BC D
4 &4# '
; 8 /
8
? E # 4 ) # #
@ &' 4 9 6 # # & ' 4 9 6 # # &' 4 9 6 # 8 # 6 6 # 6
½ ¾
½
! "# $ % & ' ( ! )
!
* " + , * "
! "# -% , !.%
% !.% %
, /
! 0 % 1 2% % ' 3 4 % %
-%
5 % 3 6# % %
% 5 7 * ! + ), % -1 " "# 0 % 8
! ! 9% : / % %
" % ; ) % & ' ! % % <
! % % ! " 1-
!
= ! 1 , !.%1 >' < 1 - * )
? @ A @ A @ A @A
* " B
3 0 < ) % 0 1- % * B )1 % -% % ! BC?)! 1 !.%
% %
0 %)
% 0 > 3. ! % 4% * 0% .% % " 9% < 0
! " ! # $% " & " '# ( )" * ( " + ' , - .& / * 0 1 # # ( 23 *# 4 2 % 2 - ! 5 0
- 0# - 6 2 7 ( & " ! ! # 0 % " - $ & ( ( 8 9 ! ' 0 6 # 0 1 6 # ' 0 # ( . -/# . 0(/# . %0/# . %% % /# . %0/ ( ! 6 ! # 1 2 # ( 3 0 ( " 6 8 ( $ % & 1 : ; $ < # 8 ' ( => 0 # ! ; 2% $
¾
! " #$ % % & ! ' $ $! (
) % ! )*
+ $ , - .! / % 0 . /$0 % % 1 2 .! + $ 3 %)! 4 5 % % $! 6 ' ( % ( ! 7 % & 8 4 ) % ! ) % 9 6 % ! : # $ 7 $ ) 5 5 %! % )!
¾¼¼
! "
#
" $ ! % & ' ( % " $ ) * ! +) +)
( $ $ , ) , !
) ) - . /! 01$ 2
$
. , ! 3 4 $ ' * 5 & ) 6 " $ 5 7 8 $ 9 :* ; ! ! " 8* $ &) & ) ! " . < & <
) $ ½
) " &) ( / & = % ! $ " : 9 ! $ >
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 ' 78 7 , $ 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#& ( - . 4 0 / = #
/ /
0 " ) . ) =
:
/
# . ) & / ' 1 4 :
= ) ! / ) / *+* .
7 %
! " # $ % " & ' " ( % ) * " * + $ $ # , , " " . , , / 0* " 1 0 2 * 2 0 $ 2 $ ! 3 4 , ' 2 / 0* 5 ' " ' * 0* # + " % 6 78 9 : ( ! ( ¼ ½ / " 0 # ) -6 ½ # ½ # ;#:6 ½ # ½ ) /<=-6 + #
¼ ½ !
" # $ %#
& '
#
X
Minimum von X und Y
Y
Maximum von X und Y
! " # $
!
"
#
$ % &' () * ! + ,- . »
/ # . # % &' 0 1 + 2 3 4 %
5
% &' 0 + 3 3 ! 2 + .5 % / 3 + 1 5
6 ¾ % $ %
) ¾ 6 % 7- 8 $ 3 % &' 9) + &:;(
6 , 27 % - 6
3
7 3 8 6
3
6
6
7
7
8
1
1
3
7
4
3 2
4
4
6
5
2 3
4 5
4
4 5
1 2
1
4
5
2
2
2 8
6 5
7 6
5
6 7 8
! "## $ % & '
## ( ½ ) * + ## & % , - & % , % . / 0 /
* ## 1 / 2 & & ! 1 & 2 2
%
$ / 0 0 3 -#
(Matrix ist bei der Bewegung nach unten konstant)
tM
sta
Te
74
t3
sta
Te t2
sta
Te t1
sta
Te
86 62
90
55
81
65
82
49
70
70
81
84
65
71
tN den Stu
t2 den Stu 1 nt de u t S
71
80
91
t4 den Stu t3 den Stu
72
94
0
0.1 Gewicht 1
0.23
0.125
Gewicht 2
Gewicht 3
0.3 Gewicht M
Liste mit den Endnoten
rechts ← links + (oben × unten)
! " # $ # !
% #
½
! "" #
$ % " & '() * % + , - $ % % . % /
% , % / % "
/ # # % % # & ½
# & ½ & ¾ # & ½ & ¾ & ¿ 0 % & " 1 /% % /" / % " /% % / # - 23 , " 1
, . 4 , " 5 "6 4 $ $ 7 / / ,% / % % % / "" '(8 " % "
/ & * % + / , %
, + % "+ , !
" 5 " - '(9. % % % #" ,
% # / / ! / , ! + # " " %+ + +: 7:
74 70
90
80
78
96
92
62
51
85
80
74
71
70
90
80
78
96
92
62
51
85
80 21.3
0
0 0.3
0.45
0.25
0.3
(a)
0.45
0.25
(b)
74 70
90
80
78
96
92
62
51
25.5
0
74
80
57.3
70
90
78
96
27.6
0
53.4 70.05
0.3
0.45
0.3
0.25
(c)
0.45
0.25
(d)
74 70 62.7
24
0 0.3
74
90
0.45
55.5
0 0.25
77.4 70.05
(e)
0.3
0.45
(f)
0
0.3
(g)
0.45
0.25
74.0 85.2 77.4 70.05
0.25
85.2 77.4 70.05
Gitternetz
Bienenstock
! " #
$ % & ! ' (
! ) * + , '- '- & ) .
/
0 !
1 ( 2 & 3&' 4 & 4 & 5 6 /& 3 '1 /& 7 $ + 1 '
2 . + 8 $ $ 1 4 8 ) & 1 ! & 9 ! 1 : 8 . ; 8 "/ # +& 8 & ' "%# "%#< 1 = 5' "%# " #
-
8 "%#'! 5 = &
8 "%#'! 4 = ! " #
! " # $
! % ! " $ & ' " ( ! ) ! " ! ! * + , - ! ! . / ) 0 ! " $ & 1 " ) & " ! 2 " % ! ! & ! % 3 " " 4
3 " ! " " ( " ! ! !"
5 $ ! ! " ! " & , " " ! ! 6 - 5 " 7 & & % 8 & & 9 ! &
$
+
! " " ! & * % ) 5 , % ! & $
! : ! & % ! 5 ; ! " +
! " "
+ ! < 5 ! " ! ! !
6 = ! " 2 33 $ " ! ) &
! " ! # ! ! $ %& ' & ! # ! ( % ' ) # ' " & # * '! ! + # , - ! * . ( ! / % 0 ! ' ! 1 ' ( ' ( / & ! # 2 " ' %% % ) . , %3' # 4! (' % ) % ! %& $ ! ! ' # 5 ! ! ' # - ( ' 6 ' 7 % ! ! 4 %& % ! $ % " ! # &8 9 ! *, $ % " ! % / 4 ! ! ( % : ! ! ! %3' ' $' " ( $ ! ! ( ! % ! . ( 0 ! " 4 ( ! . ; $ $! / % '! & $ 5! 9 7 - ! " % / ! ( 2 ! " % . . . ! - . " % - ½¼¼ (' " % ,
! " # $
%
& ! '
!
! " ! (
)
(%*+ º
, $ (
- . ) " , ( /
! $ $ " ,
# $ 0" 1( "
*
0
! $ 0
( 2 .
0 $ 3 " 4 & & &
/ ( $" 5 0 6
(
2
& 3" , (%*+ 7 & - 0
$ " 7
8 9 ,5
: ; < $ # 1) 2 3" 1) 8
9
$ ! 0 $ " 8
9
6 $ 0 ¾ " , 4 + +
1) 2 0 3" 1(0
1) 5 = " # $
! $ 6 $ 1) " ´
µ
´´
µ µ
! "
# #
$ "
% &'$( ) " "
* + ,
% (
- . / . # '
0 12 & 3 ,
% ( 4 " # 5
6 #7 8
& 2 0 " 1 +12 9" 1 + : " & "
$1 " 9 " # "
/
&'$
' # " &
.
# 0 &'$ 7 "" "1
2 &
% "( # 2 *
, # 1 "1
4 3 %: ; # ( 4 , 3 1 "1
, 3 1 3 1
"
, 3 1
: ; # 3 1 "
"
&
"
%
( "
." " /
! " #$ %$ & ' ( " ) " * + $ , # $ %
+ -( . +
+
* ! / 0" . ' . ¿ , (
! ! , !
1 23 '4 / #$ 56
7 $ / 7 ! . 0" $ ! , , #$ 58 56 - '$
! ( $ % '4
' '4 $ $ ,
9 $ !
1 $ 9 3
( &
: 1 $ 9 , 3 , &
1. & 9 3 + '
* ' "
"
¿
! " # $
% & ' ()
* + #
,
'- . / ,
0
' -" " 0
% 1 2 0
# , . 3
* 0
' $ $ 0
* 4 2 ) & 2 " % 0
,
( '
0 2 05 " 2 0
& 01 2 6 $ % "1 # ( , 7 7 8 1 9 9 ( 2 8 " 6 2 ( ( * 8
8 8
* : $ - $ " . "1 : ;6 < * % 8 "1 9 7 "1 * 6 % =( * 0
* # ' * "1 * " ' * # /
! " ! # $ % & ½ ' & " $ ( ( ) # &* + ," ' & * " ! $- - . /0 /1 2 3 ! 2 " 4 5 3 ! 6 $ 2 7 - ! 3 8 9 : % * ! % 7 ! ! " 7 - )" ! * 2 ) $ 5 $ ! : ! 7
: 9 " ) " + 7 " # ' 9 $-
% " ; $ ! $< ! & % 2 9 4 5 2 & #
! " # $! " % & ' () % ' * + ) ! "
,' - ' ! % .! / ' $0 ! & 1 2 ' 3 # & # 4 5 6 7 ( ' / $! 5 ' ½ ¾ . 5 ' 1 ½ ¾ ,
& 5 # 1 ½ ¾ ' ! , ,7 ! ! ' 8 ' 7 9 ½ 7 ½ ¾ 7 ¾ 6 7 1 1 ½ ¾ ' ' )
½
½
½
¾ ¾
!
½
"
¾ #
$ %
#
¾
¾
½ ½
!
¾
!! " # $ ! % ½ #! % # & ' ( ¾ & ) * ! + !, !! ! ' # - &. /' ! % % ! ! 0 1 ½
½
½
½
¾
¾
½
½
¾
¾
¾
¾
¾
½
¾
& '(
)*+
½ ¾ , - .
/ ( 0 - -
½
¾
" . .
2
+1
$
+$ 3
" .
½ ! ½ ¾ ! "! ! ¾ # $% ¾ ! "! ! # $& ½ ' ½ ! ' ! ¾ ! ½ ( ! ½ ( ¾ ½ ) ½ ! ¾ ' ¾ (* !
¾ ¾ ¾ ¾ ¾ ( ½ ! ( ) + ) (! ,
½ ) ¾ - ' . ! ' !! ( / !0 1 . . !!
! ) / !0 ! ! # $& 0 ½ ¾ ! !! !
2! ½ # $& ) ¾ , ¾ ( !0 # $$ ¾ ½
"0 ¾ 3 ! , ¾ ' 4) ¾ ½ ½ ½ * 0 $5 , ! ' . 60 ,
! " # $
% &' () &' *) + , - $ . $
½ / ¾ # ½
½ 0 $ / / " . ½
/
¾ & ¾ ) ¾ 1 # & ¾ ) $
,
! " # ½ ¾ ! $ % ½
& & ½ ½ & ½ ¾ & ¾ ¾ & ¾ ¾
½
' ! ¾ ½ ½ ¾ # ¾ # ( $ ! ¾ ) # * + ! * + !
# , -. / 0 # ! ! ! " # $ ! % & ! % ' ( ) &
$
! " # ! ! $ % & ' " ( ¾ " ( ) ! * %+& $ ,* %++& $ ( %+.& / $ * %+.+& %+..& %+.0& %+0& * %+1& $ 2 3 ) $ # / ' / / ,) 4 5 3 "
! " # $% & !' % ( ) # * ( " + %( ( ! ( # ( " ( *
! " " #$ #% ! &' ! ( &
)
* ( " + , " ) + *( !( -
) * ( ! ( + .
. & / + !( 0 0 - / 1 /
! 2 " 3 &" & + -+ !
. & ! 3 + . - ! 4 & 5 & ! ( 0 " - ( " " ! + &
! 2 6 5 + " & ! 4 ! 7 8 3 + !7 7 & 0 & )/ *! ( - -
! ( 5 0 &' !&
! "
#
$ % &'% ( ") "
* ' + " , -) #
*
. /% 0 " 1 2 3 -)
0 ' 2 - $ 4 5
2
' " 0 6
*
1 $ *
'% - 0 )
% 3 $ 3 % % $ 3 0 2
" 3 " "
- 3 " $ $ $ 1
%
7 " 1 / '%
8 $ 6 0 "# $ 7 *
$ '% " ) $
" #
!
# $ ! ! # % &
"
'"!( ) "*
+ " * " , ! # *
"*
- . / - " * % / / 0 ( ! /
) " (
)
/ / % 1 2
3
4
$ $ - +5
½ ½
½
¾
¾
½ ¾
- 5 % ( " * / ( " / " ( $ 3 4 -
$ !
!"
# $ % & ' ( ' ) *
+ , - %
.
"
, % ! %
! $
*
"
// . 0 % , , 0 ( #1 % *
/ , (
' 0 & 1
%2 1 3 )
, ) , % *
$ ! %2 0 ,
' " / 4 % 2 !+ 2 ' / *
*
2 / %
% "
' 0 5 */ 2 6 % 0
6
*
$
*
%2 / $
, . 5
2 !+ $ %2 '" % / /
!+ $ "
- ! " /
1
/ 2 " 7 , %
0 "
! , !+
2 1" 8 1
!
" #
"
# $ ! % & ' ( ) % *# +$ * & , - # -
+$ # # %
#
½ . /012 # #
½ # # # # - %
$
3 3' # *# /
*2 ,
*# 4 #( % & , *# *# ( # , *# 5 3 * ( # *#
¼ ¼ ½ ¼ ½ *# # %
*#
*# ( # " *
# -
#
$ # - # 6 3
# -
¼ ! " # $ %& " ! " # ' ! & $ %
( ! "
' " " " ( % " ) $" * + " , #
. " $ $ ' % , * + ( . " " / ( # $ 0 - 1 ( % ½¼ # % ! ! + % " & 2 * 34 " ' +
. ' 5 6 + * 0 ! !" & 0 " 7 " " ! 1 7 8 (
39:; # ! 7 8 "
" ; ! # "+ ! ( 8 5 5 " $ ! ; " " " " & " ( " " 8. 1 ! ! 7 , " ;
! " ! # $ % & ' " ( ! % ( # ) % ! *
) + , % - . /0 % " 1 2 3+ ! 0 " ' ! 3+ 0 . 0 & 0 . ! 0 1 3+ - 0 . 4 3 5
! " # $ % " ! %
&$ '
( # ) $ # ! "
" "
* " -
+ (
,"
'
(
" . $ # "
#
# ,.
*'
-
/ " $ $' . 0 # "
1 " " 2 # #
#
4
& $ $ 3
# !#
0 2 #
5
# # # ( 0 ' $ #
.# + "
! " # $ %
& ' # # ( ) *# + # ,
( - * # # # . / - * ½ ¾ - * . 0 # 1 $ * 2 &!3 3 - * + ½ ¾ 4 ( 2 4
% # 3 5 3 - # 4 # - )
/ - * - # 4
! " # $ % & ' ( )
! "
# $% & '( ( ) * % ( ) + ) ( , ( " -( . / '( $& % ) 0 ) 1( (
( ) ' % , " ( & (
* ( ) ( # (
2 ( 34 ) 4 #
# ) ( ( 5% 6 3 7 ) % / ( ) ( * 8
7 3 8 5 7
* 8 ' 6
3 # )
3 ( 5
(( 6 3 '
Ë ( 5 Ë ½ ( *
Ë
3
Ë
Ë
½
Ë
* +
Ë ! " Ë ! ! ! #
Ë
! $
Ë
! ! " Ë % & ! ! % Ë ' ( ( Ã ! " % & ! Ã )( ' *+ , ! Æ ! ! %& # , ' ' - . ' / & , % 0 / 1 Ë % ' " 2 - % 1 3& ! / ! " )2 + 4 ! % 5 , % ! % 2 40 ! $ %
& % " 6
!
" # $ % & ' " ( # ) * " # + , - ( . / ' , # & ( - 0 . 1 + 2 ! . (
3 & $ ( - 3
4 ' #5 6 ( # &7 78 8 " ( 4 1 ,1 9( $ 4 " " 8 . ( 3
8 " $ : # & !
- * " ( & ( 8 5 1 8 ( 3
! " # $ " %
# & ' ( ) * + ! , % + ' * ' ", $ .
/ $ ' 0 $ + 1 02 3 4 $ 5 + 4 4 6 6 ' ) # 3 3 / $ * ' , ! " + 7 $ & 8 ' 1 * 9 0 + : & & ;2 : < 2 1 0 ) 9 7 / : 7 ( 0 ) 9
$ # => = * > $ * 7 # ? ' $ ! 7 ", ' ,
! " # $ % & " ' ( ) * + ) * # ), * ¼ ½ - ¼ ½ . " / 0 1 0 2 3
( # 4 2 - 1 / $' % 4 4 2 - ' # ¼ ' ½ ½ ' $' % - ) 5 * 2 $% & 1 '
, ' - 2 # $ % 4 $ % 2 ' , , 6 ' 7 4 6 . / & / ¼ ½ - ¾ . ¾ ) ¼¼ ¼½ ½¼ ½½ * - 5
8 4 # +
1 & ( 9
! " # $%&! ¼ ¾ ¾ ½ %' " ( ) ¼ ½ ¼ ½ ¾ * ¼ ½ * ½ ¾ "
!""# $ " % & ' ("# $ $) * ! + " $# $ " # # , ,
" - * " $ .$ ' * , , * ($
/# , ! $ , # 0 !
1 1" "2 ( , " ( " # ' ! + ' , # ! , , 3 # , ,' # # , 4 / %5 & "#
3' ' 6 ." $ ) * ! 1 / ' 5 7 5# 5 , " # 6 +# 4' $, / 8 , 7 " , # , 7' # , , 8 7 #
0 4 ", , 79 $'/ $2 1 7 " '7 :%( # ) 7 :%(
7 7&7/3(
'7 :%(
+ # 6 9 # $ , ' & , 7# $, ' & " 1 #
$
$ . 4 ! &, ! # 6 ' (, " 8 ( " ;
! " # $ % & % & ' ( & ! ) *+ * + ,-. $ ' &/
0 & 1
/ 2 3 4 5!
6 7 ( % ( 8 6 7 !
9 8 0% : 8 7
; <
= > / = ?@ 0 6 <
/ 7 = > / &/ 7 & A 5 ( > & 8 & B <&/ & ! A 0 7 '
7 & 8 6
3
!2 6 !
! 7 :
' ¼ ;
8
! '
C> 6 ! & 8 & &
$ & 9 % 9 ! & 7 3 !
!" # $# % ! & ' ( ) $# * +
, !! $# *
, - ! + . ! . $#' . '!! / ( 0 1 !! . # . ! ! 2 3 ( # 4 + . ) . 5 ! -6 0! ( 7 ' ¿ . 0 +8 $ . 1 9 0 0 8 ½ : + 8 # 8 5 . . 8 . :
8 ;8 -8 + 7 " ' . 8 1 # 8 0 ! !
$8 < !
!
" # $ % & ' $ (
) *
+ , + )
-
!& % . / %
- / ( 0 1 . 2) 34456 *" 7$ 8
$ 2
0 ½ 6½¼ + ! , + *
$ *" " * , 9 $
! $ & !
$ 1 1: &
$ 2 6 +
- %
/ 1 ! ;
* $ *
$ & ' < - $
$ = # + / =
$ * % 1
< 1 *
( 1 $ . - *
% * - > '
1 . * :
1
1 ½¼
½ ! " # $ % & # ' ( )" # * + ,
(- # $ % ( % ( . / # 0 / *' + # (- % 1
% ' # 2 3 , 4 + 5 / " - ' (, " 6 7 ! - / , #" , ! 5 / # ! - & - ' ( - , , 8" 5 9 :;;< ! - " # * " & 0 /&( " = > , , + & 0 = , , " & ? & 3& ? , ) " , " =,( 3 / & # ( , - * " , $/ ) & , # ( ' ( * " @ / , A
$ , ' # ' ,( , " 5 / " 1 ) # ' ' ) ! " % "
! " # " " $% & ' "% () * & ' + " () , " , $ $ ' (
- $ " & . / () , / 0% ' * - " & +
1 2 ! " '!3 ! & ( % () , ) 2 ! ! 4 ' 5 !&
!
" #
$ %& ' " " ' ( ' ) * + , ' " ) - . / 0 + " " 1 ( ' 2 3 $& * ' " !/ " " 4 / 1 ) , 4 $"& ( / 4 ' , ' 5 ' ) $& !/ " " 67 8
)
9 $& 4 ' 4: '
" ' ¾
$"& 5/ 4 1 !/ 4 ' 4:
5 "
½
! ! ! " # $ % # & ' ( ! ) * + ( , $ ) ! $ - ) ) , $ ! + ! ) . , $ ( ! + $ ( ! / * . ( , $ $0 ! + $ 123 ( 4 5 126 ) ! - 7!"/ 8
$ 9 ! 8 $ : 12; ' < < % $ 8& / ( 9 $ , 3 8 ! = % & 9 (0 ! ( / ! # $0 0 ( 8: 4 $( / % & ' > !
/ 8 9
8 ( $ ! 0 $ 8 : ( ? $ @ ( ( 12A ( ( % # & -B
!" #$%" #$%"
& '!
(( # & (
)( ( & &
( (
* (( (
)(
( & &
(+ & ( ( ( (
( &
,+ -
( & (( $( (
, $( (
.
( ( /(
(+ &
, ( ( ( 1 /( &
& ,0
( (+ / ,
( 2 ,0 3 . ( ( ( ½
( (0
4 ( 5, ( & #)(( . ( ( , ( & 6 7( 7(( 6 . ( ( . ( ( ( 5 + & % / ()( , (/ 8(9 "
(/ ( (
/
& "( ( + & + - ( 2 ,
# &
(& 5, ( & ( ((
½
! " # $% &! " !
! '" ! ( ! ) * +" ! ! ! # ,
! $
! # - ! . ' $ ! "
" & !! !
! ) ! ! / $ / 0 1
$
'" !
2
3 ! 2 $ !! !! / ! $4 $ , ! # !
"
$ *!
" 2
# " / +
¾¼¼
! "# $ % & ' ! ( ) ! * + & !
, ! - #
. -# ) ! & / ) 0
.
- * ) 1 "
# & / 2 3
/ . 2 )
4 )
- -# 56 2 & 7 . 2 / #
-# 58 2 # # 2 /
& "9
. /
"
,
) ! 2 2&
# ) . ) "9 " / :
!
" # $ $
! " # ! $
%
& "
' ( " # " (
½
!"
# $ % # &" &
'(
#
!
# ) ' * ) ' + ,-./ )0
# ' ,-./ 1 # ) 2
3 ,-4/
2 ) ,-4-/ 2 # ,-./ 1 !
# 2 # 1 # & # ' &
% 5
' 0
6#
) ' # " # 7
# ) % # ' 8 '
9
6 6#
( # # '
) # 7 )( # ! % # 2 &
#
% )
1 # :
& # & #(
& #
½ ! "# ½ ! $ ! " % & ! ' ! "# ! ' ! % & % ½ ! ! ' " ' % ' ' ' ( %
& ' ! )' ! )' ' " "
& ' %& ! ! '# * !
! * ' ! + % ' ! , ! ! & " ! $ -, ! . ' &
½ ! " # $ ½
$ $ % % % & # ' $ $ ! ( ) $ *+% % + , ½ $+ - *+% . / $ * $ 0
½ % 1 $+ & 2 $ & 1 3 % 4+$ 1 $ / + 2 $ $ $ % 1 $+ & 1 $+ & 3 # % 0 % $ 5 6 $ # 7 3 % $+ , "&+ 5 ½ % *+% %
½
! " # $ % & ' (
) ! * + & * * & % , % # -! %
! * & ! * * % , % # -! & * . * / 0 + 1 2 ' 3 ) , * # -! % 2
* * # 4! * 3 + * % * + *
* + * & * %
/
. , * / * % % , % % 5 ) ,'
6 7 7*
% '
½
½
8 % 5
*
% % 6
"
!" # ! $ " % & ' " & ( ) $
" * #
+
# " " *
)"
½
!
"
½
" # $ $ % &! ' ( )
$ * +
, # -
.
"
½
!
- / $ $ 0 / + . 1
$ 1- ! -
# / $
+
- # #
$
2 ( 3 0 % 45 6 * *$ ( (
!
' $
, 1
1 2 $ $ 7 - 1 + # 8$
9
1 !
$$ ) :, !2 % -
! !!;
<
2 2= 1 $
2 0
2 $$ ,#! - # " 3 " $
$ 2 !
>
# + ? 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 :
; <
< = # # #
7 *
0
'# %
' # ; %$ #
#
! "" # ¾
! " # " $ % " # % $ " !& !
" ' ( ) * " + ,) - " & & * " ) * " . / / " " & % "
0 ! " - 1 + " / ! 2 # ) 345 !
* -1) ) " !#6 ! & 2 ) ! " ) -1) 5" ! 7 , ! " - # ) 8 0 ! " " % % ) 9 ) ! " - !#6 ! 6 )
3:8; ) !
) " 6 0 < " ! / ! " 2 =5 * * -
" < >) 6 ) " * ) ? @ ! " ! * <
! " # $ % & ' ( ) * ) ( )+ ! % ) , '$ $ # - # .# % ' # ! ) # %/ ½ 0 ) ) 1 #
& 2 1 .# & ' '$ ) . '$ ) - .# $ ' 3 1 ) ) ! # # 4 ) * & + 1
.# , # # # ! # # ) # 4 ) 1 ' 3 ) ) ,% # , # # .# ,% 4 ! # 5 # 1 ' 6 #
!# . * +
Eingabe N
Wähle eine Zufallszahl K zwischen 1 und N − 1.
Prüfe, ob K ein Zeuge dafür ist, dass N tatsächlich zusammengesetzt ist. K ist kein Zeuge. K ist ein Zeuge.
NEIN Wurden bereits 200 K getestet? JA
Diese Antwort stimmt immer.
NEIN, N ist nicht prim.
JA, N ist prim.
Diese Antwort ist mit einer Wahrscheinlichkeit von 1 zu 1/2 200 falsch.
! "
# $ % "
½ ¾¾¼¼
! " # $ % &" " ' ( " ( ) % * ' + # , *- % "
! " # $
! % " # $
! % ¾ ½ & $
' # % & $
() # $ )
"
&
! " " # $ ½ % & ' # ()*+ # & , " # ! ¾
¾
$-
% " !
¾
. # " " / 0 / !
!
! "
#
$ % & ' ( ) % $
* +, " /
$.
½ * ¾
"
0
$
& &
" 1 $. 2 '2( / "
½ ¿ ! ! " # $ $ % ! % & '( & ) ! #! *'(+ * + # " ! ' " ,
- .
Muster: h e r _ a _ g i v e Text:
(M = 10)
Suppose_we_wish_to_determine_ whether_a_give n_pattern_of_ sy mbols_occurs_in_a_leng thy_ t e x t. (N = 89)
Heureka!
! "# ¿ $
"# % &&'( ) *
+ , + - "#
,, - ,* . # %/ 0 * ,* 1( 2 * "# , + - * *, "# 3 * 4 ,* / .
5
$ $
$ . ½¼¼¼ -3 ,, 6 ,*
7 ! , 5 - , $, * 4 , , , 0 *
-3 ,* -3 + "# ! , , -3 / ! / + 3 . . ! $ 5 "# , +
-3 . . 4
! " !# $ %& '& ( ( ) * ( + ¿
! " #½$ ! %& #¾$ ! ' ( ! #½$ ' ( # ) * + , & $ - ! ! . ! & &
& & ! ' ( ' ¿¼ '& ½¼ -
½
!"
#$ % &' " ( $ )*( ( !" ) +" ! ( )*( , - . ( ! ( ! - ! /( ( + $,- , - ( ! - / ( - !" 0 $,- , - $,- , - + $ &'
) ( (! ) !(( ! $,- - ( 1( $,- ( , - ! ( ( . ((. 2 / & ! ( ( $ ( + ( $ ! - $ # ( +$ 3" ! ( ( 4 & $ !" )( ! ( ( ( &' 0 )*( (
! "
! " # $ % "& # & ' ( ) )) *+ , - & . / 0 # ( ! "& # 12 )3 4 ' ! # # ½ ! 5 & / 12 ! "&
1 12 ! )3 3 )3 ! 3 ) )3 +
% ) ( ) ) & - )- + 6 "& 3 # ) # 3 + 7 + ) 3 8 ) / ) / & )3 ) 4) . 3 7 / - + ) 3) .
$ / - . $ 3 )
.
) 6
NPC
co-NP
NP co-RP
RP
PTIME
! ! " # ! $ % & " ' $ # ( )! " (
* # +
# ,- ! . ½ ,-
, - ! . / ¾½ , - 0 " 1 2 % ! # ! ! 1 ( 1 $ ! % ! 1 ! $( % # % 1 ( * ! . ½ , - ! 3 # ! 0# . / ½¾ ,- $ % 0 3 !
* ! % & 4'! % 0 0 * &. 4' 5 %
! "
È
ÊÈ
ÆÈ
# $ % &' #( ' % ) %* +% % % ) # , -* . ,(# -* ) ,(# . / ' * 0 # % .1# ,( % 21" - # 3 ' - # - 4 4' 5 2 -* % % !. # 3 6 % (
-*
4 ( & # % # '
* % 7 8 '# 2 !# &' * % % '. $ * # #
9 % % % % :' $ ! 0 # .8 ' 5
% ( # 0 %
5 ! % % ¿¼ ;
.1# % 0 & 9 1 * # < = & ' 9 1 ' * -( # % -* ,( . %( & 2 ' &' * <
! " # $ % & ' (
# )* % & ' + ' !'
, - !' . / ½ ' # 0 / $ $ " #' #1& 2 + # ( (
+ 3 4 5 ! # 6 ! ' # / ! & " # #1&
! " #
$ " % & #' # (
#
" & #' ) $ ) #
!
* ) # " ) & #'
" ) + #
, -
- $ * .(/0 # )7 1
$ # # 8 $ #1& ,&
! " # $ % & '
! %
(
% ) $ * $ % (
!
+ $ ,
- ! .$ /, - - , 0
$ ' $ #
) !,
( (
1 2 ' 0 ! , ' , $ 0
3 $
0 -% 0 $ ' $
$ , -
, (
+ 4
$5 / -% % %
' ,
, $ $ '% 0 - $ !
$ ' % $- ,
'
$
$5 $
$ % % 4 -% ' !, -
,
0 , 6 % , ,
-% % 0 $ % ! $ , % , 5
,
, 6 $ ' !
$5 $ ( . $
6 $ %
% 0 -% ' / 5
$ ,
% # ) $ 7 % - $ # $5 6 $ /
, %
¼ ½ 4 8
- ¼ ,
# , 4$5 %
½
! 8 4
# . ( $ ' $ ) $ , , 6 $
% %
" %
! " # $ $ % & ' $$ ( ) * +# , ! $$ -# # ) .
$ # * /- $ % ! # $$ 0 $ # 12 $ & $$ $ $ ! $ # $ $ # $$ 0 $ # 3 # 1 # + ! $ ! # 0 , 0 # ( + # # 4
0 5 $ !$/ # 6 7 " / # # 7 $ $ $ ( $ # 6 # + ' / $ ! 6
8 # # / # ( ( # $ 0 + # $ 17!# ! $ 4 + 9: ; 4 % / $ # # $ 8 # 7 $ # $# ( ½»¾¾¼¼ ! $ / 6 4 ( 1 , # $4 ( $ 1 + / 3 $# +# 1 #
!
# # $#
"
%#
#
#
&# # ' # ( ' ' #
&#
#
&# )
*
+ # # & #
,
# '
¾¾¼¼
!
"
$
%& ' () * + !
#
$ , , "
# % -
-
'
. " -
/ / /
! ! !
& . $ ,
& !
0
# % ,
-
/ / / ' . " ' / ' / ' ". " / / / /
! " ! #
" # $# % &
' " ( )" % " + ,, -
*
%) ). " !
!)
) ) / )" ! # 0 )
" ) 1 / ) #
# 2 %
3
3
3
#"
,, 4 %) ). " * !
) 2 !
( 1 ) / 5) ( !* 2 * 1 6 ,, 7
0 #
,, 8 0 1
/
9 /*
0 " ( )" 0 '# !)
"
*
: /
"
%) 5 /*; *
*
*
%) 5 & *5 *
*
* ,, <
%) /*; *" ) ) )* = ) !) )" > ,, )
% # ! 2
¾
$
"
*
! " # $% & $ '
' ( % #
"%% ( ) *
& !
*
$
+ (
, & ( # $% , ' --. + ( / ' 0 $ (
% #
" $1 /
+ 2
! *
& ( # * / % ' % 3% " ( % 4 " & ( & ( --5 ' 0 " + 6 * 2 % # 7 $1
0 $ (
$
$
$ $
/ 4 % 0 "
( # % ' 0 $ ( 2
% "
/ ( 8 0 " + 6 2 & " & ( 9 ---: # ( & % 2 *; $
*
2 *; ---- + ( $ 2 ' / ' / ' /
/
' * /
*
%
! " # $! $ # # % # & " ' $ #( ') * ( + + $ ) * % # ! ' ) # ! , , - $! + . # $ # # %(
($# ( ! # ,$ ( $ /( + ') * % &! # + $#! & $( ! 0 ' + $ 1 # 2 3 4½5 & $( # 4¾5 ( # 4¿5 & $( &
! "# $ % & ' ( ) * $ + # $ % # , " $ -- " $ '
. / 01 2 $ % " ' 3 4
( %4 " # , , $ 3
5 3 $ ! ½ $ , ) ) , 6$ , ) ) , $ 5 7 # $ . # - 7 $1 ( * 2' $ 8 # 2 &' $ " # $ 3 $ 2 ' 2 ! $
) 3 # 6 - $ " $ 3 $ 3 # # $
! " " # $% % & ' $ ( " % ) !*$ + $ , - ' % & % $ .
$ $& ' ! / "
0 1234 5 # % .$ 6 % / % $$ / 7 ( . ( $ " * % %
% " / ( !% " , - & " , - " 8 %
6 / / &
) ! !$ + 5 " % & $ * & , $ *- $ ! * & , % - 9 . * 9 8 %
! "# # $ %
& ! & % &
(
'
)
! & & & ! %
*
" ! !
%
& + & , - # ,
&-! " .
& / &
& #! $
% !
% ( 0 1
& ( 0
2
& " !
3 )
4 " ! " +& 5
6
# "
" & % ! 50 0 ! ! & # !
%
# 7 % ! & 8
!
% . & %
" ! # " ' % # & ! % % $ " "
%
! &
! &!
% % !
% %
"
"!
Alice
Bob
,,Angriff im Morgengrauen“
Bobs ursprüngliche Botschaft M
Bob entschlüsselt mit DecrB
DecrB (,,Angriff im Morgengrauen“)
Bobs signierte Botschaft S
Bob verschlüsselt mit EncrA EncrA (DecrB (,,Angriff im Morgengrauen“))
Alice entschlüsselt mit DecrA Bobs signierte Botschaft S DecrB (,,Angriff im Morgengrauen“)
Bobs verschlüsselte und signierte Botschaft
grundlegendes kryptographisches Protokoll mit öffentlichem Schlüssel
Alice verschlüsselt mit EncrB Bobs ursprüngliche Botschaft M ,,Angriff im Morgengrauen“
! "
# ! $ # ! % & ! '(')
* + ! +!! ! Ë !
! " # $ % $ & % '( (
# ( ) * (
! + ( # ( $ , " " - * ( # ( . * ( ( ! # ( # ( ( ( ! , / $ . 0# (# / % ( / / ( $
( 12 . ( 2 ( 3 # 4 5 #
! + ( ' $ ) ( 12 . ( 2 3& ( 3 # 4 ! 6 / 5 ! ( + 7# ( ( "
$ 6#+ 0 68 68+ 7 + $ & $7 # 0# 7 #
! " # $ % & ' ( # ) ( " * ) ) #) &# + , %
$ " - & $
. ! - "/0"/ 0 0 $ &! & +*"0 1 , # ) ) 2 )
- "/0" / 0 0 # & - "/0"0
# # / 0 * !
/ # # ' ' " 3 ) / 0 ! 4 + " & # * ! 3 2
/ - "/0"/ 0 0 ) " -0# "* - ) 0 2 * & +*"0 # # - #
" * 2
4 -0# " * 5 # 4
"
¿¼¼ !
" #
$% & % ½ !
'
"
" " ( !
"
¾½
! " # $ %! &
% ' "! % %! '
(%% "! % % ) * '+ , ! - . (
% ! '! * (%% +
% ( ' ( %! / %! 0%%1 + &
%! - 2 % " $"+"3 - , 4 '% 0 - 1 2 % ! 2 4 %!
- %! "% 5 + 6 '% - ½
!
! " !!#
$ ! % & " !!# '
(
!
) %
* !!
+
, - ) %
'
'
./0 !
$ ! ' ! 1
!
!
'2 !
& ! ! ,/
3 ' 4
, $ + 1 0 ( ' ! ' ( &
! ,
5 ,
1
(
6 +
1 7 ,
! ( (
'
, 1 617 !
! " # $%& $%& ' ( # ) * *'+ ,- . & / #
! " #$ % & ' ! " ( ( &
( ! ( ) $ *
" + ,
- * ! .
* (( - )
/ / 0 * & )
, 1 # / 2 0 ! / ( /
3 ( ( 4 !
# 5 " 6 2 # )
/ / )
# ( . !
!
7 # + ! )
/ /
* 5 5 . ( &
! " # $ # % ! % ! & '
% % # % ( & $ )* + ,-,- . / 0 , 1 # 2
& # $ # $ # , ' $ 0 3 # 0 ,
# 4 5$,6 6 $ ! 7 4 , 3 5 ' % 5 , 3 & % 5 %
! $ % 6 / + ,-,- . , / %
' 8 $ # , 3 $ 9: : ' & 0 + 7 $ ' # # 6
$ ;
Alice
ursprünglicher Kartenstapel
Bob
Karte 1 Karte 2 Karte 3 Karte 4 Karte 5 Karte 6
Alice mischt und verschlüselt mit EncrA
Karte 2 Karte 5 Karte 1 EA
EA
EA
Karte 6 Karte 3 Karte 4 EA
EA
EA
Bob wählt vier und verschlüsselt zwei davon mit EncrB
Karte 5 Karte 3 Karte 1 Karte 6 E
Alice entschlüsselt alle vier mit DecrA
EA
EA
A
EB
E
EB
A
Karte 1 Karte 6 EB
Alice’ Blatt
Karte 5 Karte 3
EB
Bob entschlüsselt die beiden mit DecrB
Karte 1 Karte 6
Bobs Blatt
! " #
$ %
& ' (
)
½
! " # $ %
&
! #
' (
' )
# ( # * + '
' ( , " % - * ! # , . ( !
, ( ( / 0 ( 1 / / # ( ( 2 ,
3# 3 # 4 ! , ( ( " % , . ( !. 2 * - ( . , ! ( / 2 5 ! ( * " % . $ ( ( 6
/ , ( * , # 4
# ! + #
( - (
0 3
!
" # ! $ # "! % &
'( ! # % ) *+# , ! - ! . / 0 / % ! 1 ! 0 ) *+1 2 !
! # , 0 3 . / ! 3 4 0 5, 6 ! 4 7 $ / % 6 ! 8! , 0 . / , 0 3 # /
0 40 !0 ! 0 0 9 .
. / / ! 3 0
$ 1 # 1 4 : $ ) *+1 . % & / ! )*+1 . / 3 ! , 6: . % # / 8! 0 # , % . + ! 0 / / 8 , 3 ! ! 6 "! !
/ 4 ! ; % & . 0 0 / 6 % !+" . + / . . / ) *+1 ! +
0 $ ! 0
! " # $ %$
! & $ ' ! " '( ) *$
) ( ( $ + ' ' , ' ) ( ! - ( ! " . ( + ' % / 0 - ' / ' - % / ) ' ! " ( '
' 1 ! 2 $ 3 -( ! . # % 4 5 ( ) $ ) 5 4 + $ %$ ! - " %$ $ *$ *$ $ )! 6 & % 4 ! % 7 - $ $ *$ ! " 0 # - 1 %$ $'$-8 ! " . ( $ 9 % : . ( 9 $ ; $ $'$-8 * % 1 ( 9 3 ! - + " $ ( ( ( 3 -( 3 ( '( ) 3 ! "< # 4%$ ( ( ( 0 ! & )
!" #$ % & ' ( " ) )
!"
)* +,- %
) " . "
/ ( ' , % , ) (
0
) $ ) 1 / % + $ 2 ( + 3 +
$. . ! $ 4 $ 5 6 7 ( ( 3 / 8 / 3 , , + , $ /
, ) ( 7 ) / . 8 ( / 8 . . /
/
4
( 9) ( , $ . ( + . . " : $ $ / . , " : , ( / $ ) : $ . / : " 8 , " , ( + ( / , . * / , ( + $. ( / , ( $ 8
,
$ ; & ( 52 6%
( ,
! " # ! " $ % & '( ) * % + # ! ,- ! ,% ' . # - .&% /
0 1 ! ,% 2% # ' ! - 1 3 # 1 # 4 5%% - 6 1 , 1 7 5 ' - 8 , $% 6
,( 7 - , % - 5
5 % " 9 # - ! 1 5 * 2 3 %!
' . # : ! ! # %8 - # ! ¾
! " # ¾
10 ≈
10 ≈
10 ≈
Farben 10 ≈
10 ≈ 10 ≈ 10 ≈
10 ≈
10 ≈ 10 ≈
(a)
10 ≈
10 ≈ 10 ≈
10 10 ≈
10 ≈
10 ≈
10 ≈ (b)
! " # $ % " " & ' (
' ) *" &
+ ' , & ¿ -" . ' /
% ) ( " ' &
" ' 0 1 ) ' " )
! " ! #
¿
! !
" ! ! # # !$ $ % " % ! ! ! " ! & # % % # ' ( $ $ ) #'' * # ' # '' ( # $ ' ' % % + , ' ' % ! % # ( % ' #
# ' ' % ! - % ! . / % % 0 1' 2 % . ' 0 # (% ( $ # & 3 ) ' * ' ! 4 % ' ( $ # % + 5 % ½ ' !# % % 1
# % % %
$ # ! , # * % % ' $ ½ " 0 % * #'' $ ' , # * % # % % ( $ ¾ ,$ / '' , # % / 0 ' * # / % , #
!" # $ %& ' ( ) * ) + , * - - . ( * - / 0 ) 0
- ) * - ( 1 2 $ 3 ( - % ,%# ) / 4 2/0 /% / ( 5( ,
* * % 0 * 3 %
$ ) * * 6 % * * * 7 * 4 , 2 / ,% 89:/, 4 8;:/ 3( < * 1 4 . ,
* * =% /5 * * % 4 * ) 7 %/
!
" # $
% & '
'
" %
% (
)
!
! * ) + , ( - ' " ' ./
"
" "
( 0 1 ! . "
$ .
2
3
4 2 5
" 6 7
3 ' 648 '
"
- ) " 0 -6 5
' %
*
+'9# !-'
: - -!# # -
#( - #
-
. ' #;# 7 8 " # +# 5 " < .
! " # $ $ % % $ "
& " " ' ( " ) * "+
, " , - ! " ! .'/ $ "
0 .'/
( . )$ / " & 1 ) . " $ 2 )3$ # , 4 2
$ " 5 " , " / ,3 , ' - 6 " 0 " & " " #" %' 7 8 , %' 9 "
. 5 $ 3 2 & ! 2 ) !
$ $ ! ( . ! " , $$:
)$ ; ! 6 < $$: ( 9 2 6 ! $
! " # $ % &' ( ) # * + "
*
# *
, & # ) -. / "
½
*
# $ 0 1 $ $ ! /
½
4! 5 6 3
)
)
2 /
3. 5
1
) * 46 " & # 46
# 4
* 1 * & * #
6
46 * & * 1 #
*
. .
!
. $ #
* "
!
" #
$ $ " $ % $ &% ' $ ( $
! " # $ ! % &! ' ( ) * $ * ! ' + , + - . / 0 / ! + 1 , 1 , 2 3 * ! 0 ! # ' / 2 - 4
! 5 0 2 2 ! & * / !
! " # $ % & ' ( ) * * +
, * $ % - ) . / ! # $ *
, " * ! + " " ( 0 1 2 3445 6*!*$ % 7 !$ 7 $ 8 $ , " $ ) $ , 3444 $ ) 7
9: ! 3444 $ ) ( " 7 ½ $ , $ , !1/ ) 8 / / 6*!* ! ( + " ( 8 . / * $ , $ )( ; ! ( 8 ) , , !
, , 7< ! / ! ! ! ! !
! " # # $ % & '( ½ ) ! "
) * ) + , - . ! ( ) '( ) + , $ + ,
$ / 0
!
" # / # . 1# " . * # * !. , 2 3445 ! ! *" # & 1# $ 6 & ! $ % # %" & ( &
& $ 7
&
8 " $ &
# . 9 : & &
"
. 9 ; . ! . ! . & +
# & * . # # ;
$ / # < # )" ! % ; ! ) / $ " . # % # .
= & ;- )#1 $ ! > # "
! " # # # $ % & % ' ( ) * +$ # , - . % # % #% ¼ ) + # ) # - / #% ( 0 % 1(% " 2 - % ' # . 0 +$ . % # , - +$ 3 # - . + # ! # 3 #( + # - % 2 - #% - / & . # # ! # - 3 + ! ( # - 4 5 ' 3 + ' ! 6 7 # - ) * (# +$ +$ % % 4 +$ $ # " . % !( % % 8 &% 8 ! + !( 8 ) &% 3 # ! 1 % # 0 0 +$ ! + + % + % .# $ +$ +$ . % ) 9 % # ! . # ( 0 : 3 # # 0 : 2 ( ; # ) . % '
!"
½
#
$ # %# % # & #
' # ( ) & * + , - . + / 0 .1 2 / 3 45 6 0
#
7 . 8 9
5 # :3 8 #
8 . ; 2 # #
1 " .
%31 8 # 3 # #
#
8 " # *
. ; # - # 3
8 '
# %
2 ' *<===*8 # > . 2 <= ' ? # * #
' @
3 @ 4 6 ' ABC= D * 46 ' AB=A . E ? # # D % 8 # ABC= ? . # #
' <===
' <==A 3
# @ 46 ) F / . -.
8 ABBC <=== # & *
!" # $ $ ½
! " # $ % & ' ( ) % * ( ) +,, -. / , ( 01 , , ( ( 1 1 * , , 2 3 ( ! * 4 , 5 , 6 + (( , , , & 1 4 $, 2, 6 % +,, 7 8 & / 9 % 4 * 4 ( $ ( , /( : +% $ ), ( 6 4 ! ; ), <( ( ( =,, , % / 6( * % , ( ( * (( 4 4( ( ( * * 0 1 ( ( %
4 ) $ (, ( )
> ! ( ) < #, ,, > $ 5 ( ) , ( ) < ( = ) ( )
! " # $
$ "
% " $ $ " &
$ $ ' ( " & & )
* $ +
% *
, + - +
$
+ + *
*
*
" )$ # ,) " ( *
$ )$ ,) " *
( *
" " *
, . *
+
$ $ . ,
) +
$
' $ $ $ " ( , " *
# " / $ ,
" % $ ( % '
*$ , " ! 0 $ 1 , "
" 2 3 " , 2 3 (
,
,
4
) 2 3
4
! " " " # $ % % ! & ' ! % ( ' % $ # ) $ * ! ¾ + , - $ %+
' ' . % /% " % % 0 $ , '1% 1% ' "! ) % ) $ 2 # ) 3 ) 4 %
) *% 3 ' ! )! $ / & ! $ ! 5 ' -
) %+ * $ ! ' )! 6
! ( !-!& !' ) 7 % " 8 $ )
! " #
$
% % & ! ¾
! " #
$ $
%$ # $ $ &' ( "
) # & $ " " * +$ $ ,& -' &
.
/
%$ $
0 ( 1 + ( $ $
&" #+ 0
" $
" " ( $ " 2 %
$
%$
&( ! # & $ & 3 4 , "
, ( 5 .! - 0 $ 6$ $
$ / , -' & $ (
* & , " & " 6 $ &' 7 2 &" ( $ ( $ & 8& " ( 6 (
! "#$ % " & ' ( ) * ! + , - +. +. / - / 0 1 +. / ! ( ! ( / 2 ! $ " ) ! /$ 0 $ +. ! , ) ' $ (
3 ) & * " ! 0 ) +. + ! % ) ! % 4 & * +. & * 5 6 % 1 +. + ! ! $ ( +. + !
7 1 + ) ! ! 8 9
! + $ ( + ! ! ! 5 $
: 0 ) ! ! ) (
!"
# $ !
!" !" % & ' ( ) * + ¿ , - . / ' 0 1 % 2 * 3 4 + 5 $ , $) 6 7 8 + " 9 + 3 8 $ : ; +$ 6 * !" 3 + $ ! < * , # , !" $ ! 7 3 = = , = !" , ; $ !" + + ; $ + ! ; ! +$ 8 $ +> = 3 , * ! 8 $ % 3 ! $ ( 37 ,
! 37 ? ! # ) 5 3 @ 6 2 7 # !
! " # $ # % & #
# ' & # # # # " # ! # "( ) & * # " ( # # + , # # " -# + ./, "
0 1 " 0 2 # " 0 3 '! ' 0 # # ' # ) 2 4 5 6 78"79" ( + # ) ' " 5 ) # ! " 0 * - : # ;# # ; # ( ) # # # 6 ( 9 # ! "0 & " '# # ! # : # " ' 0 : " 0 # < = # : " # ' # , + ) + # ( # " 4 ) # 41 # # ,) ½¼¼" # ># # " ' ( '# ?'
! " #
$ % &
$ ' & (
" )
* + " , -
+ " . ' /01 2
! " # $ %# & ' ( ) *" +" $ * & ) , ! ( -% - % ' ( - , % . " ) ( ( */ ! 0(% 1 ( ( # % , ( ' % $ ( & % % - 2) * (% 2 ! % . *
'(% 3 4 ! ! % , 2) * ! %4 5 5 " , 6 ( 3 ) ' ( * 3 % ) ( ( ' 2 ( ' " 3 7 3 % , ) -8 "
! " # $ % & % ' & ( ") # % $ *" ( %
% # ( ") % % # %
% &
% &
( ") + ' %$ ( ") + % , ( ") ( ) % *) ) ( ") ( ) $ *) % ) ' -") & % $ % ( ") ( ) . &
( % % $ /) *)%0 * ( %
* ( ") % % ( $ 1
) 1%
*) &
# 23 4 ( % ( ") 5 6" . 7 ) *) $ 8 1 *)
Festlegung der Ziele, Alternativen, Zeitvorgaben
Bewertung der Alternativen, Analyse und Auflösung der Risiken Risikoanalyse Risikoanalyse Risikoanalyse
Prototyp 3
funktionsbereiter Prototyp
Prototyp 2 RisikoProtoanalyse BESPRECHUNG typ 1 Bedarfsplan, Simulationen, Modelle, Bewertungen Lebenszyklusplan Betriebskonzept Softwareanforderungen Produktdetaillierter entwurf Validierung der Entwurf EntwicklungForderungen Code plan
Plan der nächsten Interation
Integrationsund Testplan
Modultest Entwurf IntegrationsV&V test Akzeptanztest Entwicklung, Verifizierung Service des Nachfolgeprodukts
¿
! " #
$ % # & # % '
% ( # # # $ ) ) # *
!'
+ , *
- # ! (% % . " / 0 + 1 # (% / 2 ' 3 ! 3 '
¿
! " #$ # # %# & ' $ & ( ( # ) * # "## ! + " ( , $ % ! - #
. .# / # 0 1 ! )# % - * ) * " * & 2 ) * * , * % $ & " ) * + " # 0 * # # ,
( & * & & ) * 3 " # *4 )# # / 5 %6 , # 5 # * " # # 7 + %# 8 &0 ) # 9 $ # , : #
# * ( * ## 8 % $
! " #$ %$ $
& ' " ( &
) * ! $ $ $ ! $
+ ! ! $, ( ' ! -$ . / ! 0, -$ & & 1 2 -$ " 3 & * 4*5 6 $ 7 . 2 1 - $ ! 2
8 + 9 : & ! 2 * * 3 & ( ; * & 1 $ - ; $ ; &
