%!PS-Adobe-2.0 %%Creator: dvips 5.526 Copyright 1986, 1994 Radical Eye Software %%Title: maxseg.dvi %%CreationDate: Thu Jan 16 09:08:04 1997 %%Pages: 4 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSCommandLine: /sw/tex/bin/Dvips maxseg.dvi %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1997.01.16:0837 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{ pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get} B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{cc 1 add D }B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail} B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{ 3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{ 3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 39158280 55380996 1000 300 300 (/tmp_mnt/home/math/schwicht/wwwpublic/papers/akad96/maxseg.dvi) @start /Fa 7 118 df76 D<01FF800007FFF0000F81F8001FC07E001FC07E001FC03F000F803F8007 003F8000003F8000003F8000003F80000FFF8000FFFF8007FC3F800FE03F803F803F803F 003F807F003F80FE003F80FE003F80FE003F80FE003F807E007F807F00DF803F839FFC0F FF0FFC01FC03FC1E1B7E9A21>97 D<003FE00001FFF80003F07E0007C01F000F801F801F 800F803F800FC07F000FC07F0007C07F0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF 000000FF000000FF0000007F0000007F0000007F0000003F8000E01F8000E00FC001C007 E0038003F81F0000FFFE00001FF0001B1B7E9A20>101 D<07000F801FC03FE03FE03FE0 1FC00F8007000000000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFE FFFE0F2B7DAA14>105 D114 D<00700000700000700000700000F00000F00000F00001F00003F00003F00007F0001FFF F0FFFFF0FFFFF007F00007F00007F00007F00007F00007F00007F00007F00007F00007F0 0007F00007F00007F00007F03807F03807F03807F03807F03807F03803F03803F87001F8 6000FFC0001F8015267FA51B>116 DI E /Fb 6 112 df77 D<007E080381980700780C00381C0018380018780008700008F00000F00000F000 00F00000F00000F007FFF000787000387800383800381C00380C00380700380380D8007F 0818177E961D>103 D105 D108 D110 D<00FE000383800E00E01C 00703C007838003878003C70001CF0001EF0001EF0001EF0001EF0001EF0001EF0001E70 001C78003C3800383C00781C00700E00E003838000FE0017177E961D>I E /Fc 10 128 df<07FFFFF8007C0078003C0038003C0018007800180078000800780008 00780008007800080078000800F0100000F0100000F0100000F0300000F0700000FFF000 01E0600001E0200001E0200001E0200001E0200001E0000003C0000003C0000003C00000 03C0000003C0000003C000000780000007C00000FFFE00001D1F7E9E1E>70 D<07F8000C0C001E06001E07001C070000070000070000070000FF0007C7001E07003C0E 00780E00F00E10F00E10F00E10F01E10F02E20784F401F878014147D9317>97 D<00F800070E000E07001C0700380380780380700380F00380F00380FFFF80F00000E000 00E00000E00000E00000F001007002003004001C180007E00011147D9314>101 D<00000E003E1100E1A301C1C20381E00780E00701E00F01E00F01E00F01E00703C00703 8007870004FC000800000800001800001C00000FFF000FFFC007FFE01800F03000306000 30C00030C00030C000306000603000C01C070007FC00181F809417>103 D<01C003E003E003C0018000000000000000000000000003801F80078003800380070007 0007000700070007000E000E000E000E000E000E001C001E00FF800B1F7F9E0C>105 D<00E007E001E000E000E001C001C001C001C001C001C003800380038003800380038007 00070007000700070007000E000E000E000E000E000E001C001E00FFC00B207F9F0C> 108 D<038E001FB38007C78003C780038300078000070000070000070000070000070000 0E00000E00000E00000E00000E00000E00001C00001E0000FFE00011147E9312>114 D<0080010001000100030007000F001E00FFF80E000E000E000E001C001C001C001C001C 001C00380038203820382038203840384018800F000D1C7C9B12>116 D<1C0380FC1F803C07801C03801C0380380700380700380700380700380700380700700E 00700E00700E00700E00701E00701E00703C00305E001F9FC012147B9319>I<30307878 F8F8F8F870700D05779E17>127 D E /Fd 1 4 df3 D E /Fe 32 128 df<00000200000006000000060000000E0000001E0000001E0000003F 0000002F0000004F0000004F0000008F0000010F0000010F0000020F0000020F0000040F 00000C0F0000080F0000100F0000100F0000200F80003FFF800040078000C00780008007 8001000780010007800200078002000780060007801E000F80FF807FF81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E003C003C003C003C003C003C003C003C00 3C0078007800780078007800F0007801E000F0078000FFFE0000F00F8000F003C001E001 C001E001E001E001E001E001E003C001E003C001E003C001E003C001C0078003C0078007 8007800F0007801E000F007800FFFFE0001E1F7D9E20>I<0000FE0200078186001C004C 0038003C0060003C00C0001C01C0001803800018070000180F0000181E0000101E000010 3C0000003C00000078000000780000007800000078000000F0000000F0000000F0000000 F0000000F00000807000008070000080700001003800010038000200180004000C001800 060020000381C00000FE00001F217A9F21>I<01FFFFFC001E0038001E0018001E000800 1E0008003C0008003C0008003C0008003C00080078001000780800007808000078080000 F0100000F0300000FFF00000F0300001E0200001E0200001E0200001E0200003C0000003 C0000003C0000003C00000078000000780000007800000078000000F800000FFF800001E 1F7D9E1E>70 D<01FFF800001F0000001E0000001E0000001E0000003C0000003C000000 3C0000003C00000078000000780000007800000078000000F0000000F0000000F0000000 F0000001E0000001E0000001E0000001E0008003C0010003C0010003C0030003C0020007 8006000780060007800C0007801C000F007800FFFFF800191F7D9E1D>76 D<01FE00007FC0001E0000FC00001E0000F80000170001780000170001780000270002F0 0000270004F00000270004F00000270008F00000470009E00000470011E00000470021E0 0000470021E00000870043C00000838043C00000838083C00000838083C0000103810780 000103820780000103820780000103840780000203840F00000203880F00000203900F00 000203900F00000401E01E00000401E01E00000401C01E00000C01801E00001C01803E00 00FF8103FFC0002A1F7D9E29>I<01FFFF80001E00E0001E0070001E0038001E003C003C 003C003C003C003C003C003C003C0078007800780078007800F0007800E000F003C000F0 0F0000FFFC0000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0 000003C00000078000000780000007800000078000000F800000FFF000001E1F7D9E1F> 80 D<0007E040001C18C0003005800060038000C0038001C00180018001000380010003 800100038001000380000003C0000003C0000003F8000001FF800001FFE000007FF00000 1FF0000001F8000000780000007800000038000000380020003800200038002000300060 007000600060006000E0007000C000E8038000C606000081F800001A217D9F1A>83 D<0FFFFFF01E0780E0180780201007802020078020200F0020600F0020400F0020400F00 20801E0040001E0000001E0000001E0000003C0000003C0000003C0000003C0000007800 0000780000007800000078000000F0000000F0000000F0000000F0000001E0000001E000 0001E0000001E0000003E00000FFFF00001C1F789E21>I86 D<00F1800389C00707800E03801C03803C03803807 00780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C 800F070013147C9317>97 D<007E0001C1000300800E07801E07801C07003C0200780000 780000780000F00000F00000F00000F00000F0000070010070020030040018380007C000 11147C9315>99 D<0000780003F80000700000700000700000700000E00000E00000E000 00E00001C00001C000F1C00389C00707800E03801C03803C038038070078070078070078 0700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F070015207C9F 17>I<007C01C207010E011C013C013802780C7BF07C00F000F000F000F0007000700170 023804183807C010147C9315>I<00007800019C00033C00033C00071800070000070000 0E00000E00000E00000E00000E0001FFE0001C00001C00001C00001C0000380000380000 380000380000380000700000700000700000700000700000700000E00000E00000E00000 E00000C00001C00001C0000180003180007B0000F300006600003C00001629829F0E>I< 003C6000E27001C1E00380E00700E00F00E00E01C01E01C01E01C01E01C03C03803C0380 3C03803C03803C07003C07001C0F001C17000C2E0003CE00000E00000E00001C00001C00 301C00783800F0700060E0003F8000141D7E9315>I<01E0000FE00001C00001C00001C0 0001C000038000038000038000038000070000070000071E000763000E81800F01C00E01 C00E01C01C03801C03801C03801C0380380700380700380700380E10700E20700C20701C 20700C40E00CC060070014207D9F17>I<00C001E001E001C00000000000000000000000 0000000E003300230043804300470087000E000E000E001C001C001C0038403880308070 80310033001C000B1F7C9E0E>I<01E0000FE00001C00001C00001C00001C00003800003 80000380000380000700000700000703C00704200E08E00E11E00E21E00E40C01C80001D 00001E00001FC00038E000387000387000383840707080707080707080703100E0310060 1E0013207D9F15>107 D<03C01FC0038003800380038007000700070007000E000E000E 000E001C001C001C001C0038003800380038007000700070007100E200E200E200E20064 0038000A207C9F0C>I<1C0F80F0002630C318004740640C004780680E004700700E0047 00700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C01 C038001C01C0708038038071003803806100380380E10038038062007007006600300300 380021147C9325>I<1C0F802630C04740604780604700704700708E00E00E00E00E00E0 0E00E01C01C01C01C01C01C01C03843803883803083807083803107003303001C016147C 931A>I<007C0001C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003 C0F003C0F003C0F00780F00700700F00700E0030180018700007C00013147C9317>I<01 C1E002621804741C04781C04701E04701E08E01E00E01E00E01E00E01E01C03C01C03C01 C03C01C0380380780380700380E003C1C0072380071E000700000700000E00000E00000E 00000E00001C00001C0000FFC000171D809317>I<1C1E00266100478380478780470780 4703008E00000E00000E00000E00001C00001C00001C00001C0000380000380000380000 38000070000030000011147C9313>114 D<00FC030206010C030C070C060C000F800FF0 07F803FC003E000E700EF00CF00CE008401020601F8010147D9313>I<018001C0038003 800380038007000700FFF007000E000E000E000E001C001C001C001C0038003800380038 20704070407080708031001E000C1C7C9B0F>I<0E00C03300E02301C04381C04301C047 01C08703800E03800E03800E03801C07001C07001C07001C07101C0E20180E20180E201C 1E200C264007C38014147C9318>I<0E00C1C03300E3C02301C3E04381C1E04301C0E047 01C060870380400E0380400E0380400E0380401C0700801C0700801C0700801C0701001C 0701001C0602001C0F02000C0F04000E13080003E1F0001B147C931E>119 D<0E00C03300E02301C04381C04301C04701C08703800E03800E03800E03801C07001C07 001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800F038 00F07000E06000C0C0004380003E0000131D7C9316>121 D<01C04003E08007F1800C1F 000802000004000008000010000020000040000080000100000200000401000802001002 003E0C0063FC0041F80080E00012147D9313>I<306078F0F9F0F1F060E00C05749E17> 127 D E /Ff 15 123 df<000FE000007FF80000F81C0001E07C0003E07C0007C07C0007 C07C0007C0380007C0000007C0000007C0000007C1FE00FFFFFE00FFFFFE0007C03E0007 C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007 C03E0007C03E0007C03E0007C03E0007C03E0007C03E003FF9FFC03FF9FFC01A20809F1D >12 D<387CFEFEFE7C3807077C860F>46 D69 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F80000 FC00007FC0007FFE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C00003C C0003CC0003CC0003CE00038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>83 D<07FC001FFF003F0F803F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E03C03 E07C03E0F803E0F803E0F803E0FC05E07E0DE03FF8FE0FE07E17147F9319>97 D<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC00 00FC00007C00007C00003E00181E00180F807007FFE000FF8015147F9318>101 D<1C003E007F007F007F003E001C00000000000000000000000000FF00FF001F001F001F 001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E >105 D107 D110 D<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC00 7EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II114 D<01800180018003800380038007800F803F80FFFCFF FC0F800F800F800F800F800F800F800F800F800F800F860F860F860F860F8607CC03F801 F00F1D7F9C14>116 D119 D<3FFFE03FFFE03C07C0380F80701F80603F00603E00607C0000 F80001F80003F00003E06007C0600F80601F80E03F00C03E01C07C03C0FFFFC0FFFFC013 147F9317>122 D E /Fg 2 49 df<0000300000F00001C0000700001E0000780001E000 0380000E00003C0000F00000F000003800000E000007800001E000007800001C00000700 0003C00000F00000300000000000000000000000000000000000007FFFE0FFFFF0141E7D 951B>20 D<060F0F0E1E1E1C3C383830707060E0C04008117F910A>48 D E /Fh 1 82 df81 D E /Fi 2 82 df78 D<001FE00000F03C0003601B000440088008800440108004202100021021000210410002 084200010842000108820001048200010482000104820001048200010482000104820001 048200010442000108420001084100020821000210210002101080042008800440044008 8003601B0000F03C00001FE000001040000008200000042000000310000000CC0000003F F81E247F9C23>81 D E /Fj 11 95 df<70F8F8F87005057C8D0D>1 D<400004C0000C6000183000301800600C00C006018003030001860000CC000078000030 0000300000780000CC000186000303000601800C00C0180060300030600018C0000C4000 0416187A9623>I<01800180018001800180C183F18F399C0FF003C003C00FF0399CF18F C1830180018001800180018010147D9417>I<03C00FF01FF83FFC7FFE7FFEFFFFFFFFFF FFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C010127D9317>15 D<000000C0000003C000 000F0000003C000000F0000003C00000070000001C00000078000001E00000078000001E 00000078000000E0000000780000001E0000000780000001E0000000780000001C000000 0700000003C0000000F00000003C0000000F00000003C0000000C0000000000000000000 000000000000000000000000000000000000007FFFFF80FFFFFFC01A247C9C23>20 DI<00000004000000000200000000020000000001000000000080000000 00400000000020FFFFFFFFFCFFFFFFFFFC00000000200000000040000000008000000001 0000000002000000000200000000040026107D922D>33 D<003FF800FFF803C000070000 0C0000180000300000300000600000600000C00000C00000C00000FFFFF8FFFFF8C00000 C00000C000006000006000003000003000001800000C000007000003C00000FFF8003FF8 151C7C981E>50 D<400001C0000360000660000660000630000C30000C30000C18001818 00181800180FFFF00FFFF00C00300600600600600600600300C00300C001818001818001 818000C30000C30000C300006600006600006600003C00003C00003C0000180000180018 21809F19>56 DI<001000003800003800006C00006C00006C0000C60000C60001830001830001830003 01800301800600C00600C00600C00C00600C006018003018003018003030001830001860 000C60000C60000CC00006C00002171C7D9A1E>94 D E /Fk 5 111 df<0300038003000000000000000000000000001C002400460046008C000C0018001800 180031003100320032001C0009177F960C>105 D<001800380010000000000000000000 00000001C0022004300430086000600060006000C000C000C000C0018001800180018063 00E300C60078000D1D80960E>I<1F0006000600060006000C000C000C000C00181C1866 188E190C32003C003F00318060C060C460C460C8C0C8C0700F177E9612>I<383C1E0044 C6630047028100460301008E0703000C0603000C0603000C060600180C0600180C062018 0C0C20180C0C4030180440301807801B0E7F8D1F>109 D<383C0044C600470200460200 8E06000C06000C06000C0C00180C00180C40181840181880300880300F00120E7F8D15> I E /Fl 4 51 df<00300000300000300000300000300000300000300000300000300000 3000003000FFFFFCFFFFFC00300000300000300000300000300000300000300000300000 300000300000300016187E931B>43 D<07C018303018701C600C600CE00EE00EE00EE00E E00EE00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007 00070007007FF00C157E9412>I<0F8030E040708030C038E03840380038007000700060 00C00180030006000C08080810183FF07FF0FFF00D157E9412>I E /Fm 12 121 df<70F8F8F87005057C840D>58 D<70F8FCFC7404040408081010204006 0E7C840D>I<000001C00000078000001E00000078000001E00000078000000E00000038 000000F0000003C000000F0000003C000000F0000000F00000003C0000000F00000003C0 000000F0000000380000000E0000000780000001E0000000780000001E00000007800000 01C01A1A7C9723>I<0001FC0000070700001C01C0003000E000E0006001C00070038000 7007800038070000380E0000381E0000381C0000383C0000383C00003878000078780000 787800007878000078F00000F0F00000F0F00000E0F00001E0F00001C0F00003C0700003 807000070078000F0038001E0038003C001C0070000E00E0000783800001FC00001D217E 9F23>79 D<00FFF83FF8000FC00F80000F80060000078004000007C008000003C0100000 03C020000003E040000001E080000001F100000000F300000000F600000000FC00000000 78000000007C000000007C000000007C00000000BE000000011E000000021E000000061F 0000000C0F000000080F800000100780000020078000004007C000008003C000010003E0 00030003E0000F0007E000FFE01FFE00251F7F9E26>88 D<000700000C80001880003080 00308000608000610000C10000C10001C200018200038400038400038800070800071000 0720000720000E40000E80000F00000E00000E00000E00000E00001E00002E0000C60100 06030006040003180001E0001120809F13>96 D<00E001E001E000C00000000000000000 0000000000000E00130023804380438043808700070007000E000E001C001C001C203840 38403840388019000E000B1F7E9E10>105 D<0000C00001E00001E00001C00000000000 00000000000000000000000000000000001E000063000043800083800103800103800207 00000700000700000700000E00000E00000E00000E00001C00001C00001C00001C000038 0000380000380000380000700000700030700078E000F1C0006380003E00001328819E13 >I<01E0000FE00001C00001C00001C00001C00003800003800003800003800007000007 00000701E00706100E08700E10F00E20F00E40601C80001D00001E00001FC00038700038 3800383800381C20703840703840703840701880E01880600F0014207E9F18>I<1E07C0 7C00231861860023A032030043C034030043803803804380380380870070070007007007 00070070070007007007000E00E00E000E00E00E000E00E00E000E00E01C101C01C01C20 1C01C038201C01C038401C01C0184038038018801801800F0024147E9328>109 D<1E07802318C023A06043C0704380704380708700E00700E00700E00700E00E01C00E01 C00E01C00E03821C03841C07041C07081C03083803101801E017147E931B>I<03C1C00C 62201034701038F02038F020386040700000700000700000700000E00000E00000E00000 E02061C040F1C040F1C080E2C080446300383C0014147E931A>120 D E /Fn 78 128 df<001F83E000F06E3001C078780380F8780300F03007007000070070 000700700007007000070070000700700007007000FFFFFF800700700007007000070070 000700700007007000070070000700700007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E00700000700000700000700000700000700 00FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E07FC3FE1720809F19>I<003FE000 E0E001C1E00381E00700E00700E00700E00700E00700E00700E00700E00700E0FFFFE007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E07FE7FE1720809F19>I<00FC00018E00030700 0603800E03C00E03C00E03C00E03C00E03C00E03800E07000E0E00FE38000E0E000E0300 0E03800E01C00E01C00E01E00E00E00E00F00E00F00E00F00E00F00E00F00E00F00E00F0 0E00E00E71E00E71C00E7380FE3E0014207F9F17>25 D<7038F87CFC7EFC7E743A040204 0204020804080410081008201040200F0E7E9F17>34 D<0020004000800100020006000C 000C00180018003000300030007000600060006000E000E000E000E000E000E000E000E0 00E000E000E000E0006000600060007000300030003000180018000C000C000600020001 000080004000200B2E7DA112>40 D<800040002000100008000C00060006000300030001 800180018001C000C000C000C000E000E000E000E000E000E000E000E000E000E000E000 E000C000C000C001C001800180018003000300060006000C00080010002000400080000B 2E7DA112>I<000600000006000000060000000600000006000000060000000600000006 000000060000000600000006000000060000000600000006000000060000FFFFFFF0FFFF FFF000060000000600000006000000060000000600000006000000060000000600000006 00000006000000060000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F8 7005057C840D>I<03F0000E1C001C0E00180600380700700380700380700380700380F0 03C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F0 03C07003807003807003807807803807001806001C0E000E1C0003F000121F7E9D17>48 D<018003800F80F380038003800380038003800380038003800380038003800380038003 80038003800380038003800380038003800380038007C0FFFE0F1E7C9D17>I<03F0000C 1C00100E00200700400780800780F007C0F803C0F803C0F803C02007C00007C000078000 0780000F00000E00001C0000380000700000600000C0000180000300000600400C004018 00401000803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00780F80 780780780780380F80000F80000F00000F00000E00001C0000380003F000003C00000E00 000F000007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E00 1C3C0003F000121F7E9D17>I<000600000600000E00000E00001E00002E00002E00004E 00008E00008E00010E00020E00020E00040E00080E00080E00100E00200E00200E00400E 00C00E00FFFFF0000E00000E00000E00000E00000E00000E00000E0000FFE0141E7F9D17 >I<1803001FFE001FFC001FF8001FE00010000010000010000010000010000010000011 F000161C00180E001007001007800003800003800003C00003C00003C07003C0F003C0F0 03C0E00380400380400700200600100E000C380003E000121F7E9D17>I<007C00018200 0701000E03800C07801C0780380300380000780000700000700000F1F000F21C00F40600 F80700F80380F80380F003C0F003C0F003C0F003C0F003C07003C07003C0700380380380 3807001807000C0E00061C0001F000121F7E9D17>I<4000007FFFC07FFF807FFF804001 0080020080020080040000080000080000100000200000200000400000400000C00000C0 0001C0000180000380000380000380000380000780000780000780000780000780000780 00078000030000121F7D9D17>I<03F0000C0C0010060030030020018060018060018060 01807001807803003E03003F06001FC8000FF00003F80007FC000C7E00103F00300F8060 03804001C0C001C0C000C0C000C0C000C0C000806001802001001002000C0C0003F00012 1F7E9D17>I<03F0000E18001C0C00380600380700700700700380F00380F00380F003C0 F003C0F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C0000380000380 000380000700300700780600780E00700C002018001070000FC000121F7E9D17>I<70F8 F8F8700000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000 0000000070F0F8F878080808101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000 0000000000000000000000000000000000000000000000000000000000FFFFFFF07FFFFF E01C0C7D9023>61 D<000100000003800000038000000380000007C0000007C0000007C0 000009E0000009E0000009E0000010F0000010F0000010F0000020780000207800002078 0000403C0000403C0000403C0000801E0000801E0000FFFE0001000F0001000F0001000F 00020007800200078002000780040003C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC040007030C001C009C0 038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00004078000040 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000 780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E0070001E0 0F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E0 3C0001E03C0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820 000FE0001E217D9F24>III<0FFFC0007C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00203C00F83C00F83C 00F83C00F0380040780040700030E0000F800012207E9E17>IIIII<001F800000F0F00001C0380007801E000F000F000E0007001E00 07803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F800 01F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C00 03C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F80001C21 7D9F23>II82 D<07E0800C198010078030038060018060 0180E00180E00080E00080E00080F00000F000007800007F00003FF0001FFC000FFE0003 FF00001F800007800003C00003C00001C08001C08001C08001C08001C0C00180C00380E0 0300F00600CE0C0081F80012217D9F19>I<7FFFFFE0780F01E0600F0060400F0020400F 0020C00F0030800F0010800F0010800F0010800F0010000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000001F800007FFFE001C1F 7E9E21>IIII<7FFFF87C00F87000F06001E04001E0C003C0C003C0800780800F80800F00 001E00001E00003C00003C0000780000F80000F00001E00001E00003C00403C004078004 0F80040F000C1E000C1E00083C00183C0018780038F801F8FFFFF8161F7D9E1C>90 DI<080410082010201040204020804080408040B8 5CFC7EFC7E7C3E381C0F0E7B9F17>II<1FE00030 3000781800781C00300E00000E00000E00000E0000FE00078E001E0E00380E00780E00F0 0E10F00E10F00E10F01E10781E103867200F83C014147E9317>97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00 000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E00780E00 780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03F80E0C 1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03F0 10147E9314>I<000380003F800003800003800003800003800003800003800003800003 8000038000038003E380061B801C0780380380380380700380700380F00380F00380F003 80F00380F00380F003807003807003803803803807801C07800E1B8003E3F815207E9F19 >I<03F0000E1C001C0E00380700380700700700700380F00380F00380FFFF80F00000F0 0000F000007000007000003800801800800C010007060001F80011147F9314>I<007C00 C6018F038F07060700070007000700070007000700FFF007000700070007000700070007 00070007000700070007000700070007000700070007007FF01020809F0E>I<0000E003 E3300E3C301C1C30380E00780F00780F00780F00780F00780F00380E001C1C001E380033 E0002000002000003000003000003FFE001FFF800FFFC03001E0600070C00030C00030C0 0030C000306000603000C01C038003FC00141F7F9417>I<0E0000FE00000E00000E0000 0E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E81800F01C0 0F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16207F9F19>I<1C001E003E001E001C0000000000000000 00000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E00FFC00A1F809E0C>I<00E001F001F001F000E000000000000000000000 0000007007F000F000700070007000700070007000700070007000700070007000700070 00700070007000700070007000706070F060F0C061803F000C28829E0E>I<0E0000FE00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0FF00E03 C00E03000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E1E000E0E 000E07000E07800E03800E03C00E03E0FFCFF815207F9F18>I<0E00FE000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F000FE618618000E 81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C0 0F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000 E07000E0F000F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C03 80070E0001F80014147F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E 00780E00780E00780E00780E00780E00780E00700E00F00E00E00F01E00F01C00EC3000E 3E000E00000E00000E00000E00000E00000E00000E00000E0000FFE000151D7F9319>I< 03E0800619801C05803C0780380380780380700380F00380F00380F00380F00380F00380 F003807003807803803803803807801C0B800E138003E380000380000380000380000380 000380000380000380000380003FF8151D7E9318>I<0E78FE8C0F1E0F1E0F0C0E000E00 0E000E000E000E000E000E000E000E000E000E000E000E00FFE00F147F9312>I<1F9030 704030C010C010C010E00078007F803FE00FF00070803880188018C018C018E030D0608F 800D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E000E00 0E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E 01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001C20000E40000EC00007800003800003C 00007C00004E000087000107000303800201C00601E01E01E0FF07FE1714809318>II<3FFF380E200E201C40384078407000 E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314>II<30307878F87C787830300E057C9E17>127 D E /Fo 22 123 df<70F8F8F87005057C840E>46 D<008003800F80F38003800380038003800380 038003800380038003800380038003800380038003800380038003800380038003800380 038003800380038007C0FFFE0F217CA018>49 D<03F0000C1C001007002007804003C040 03C08003E0F003E0F801E0F801E0F801E02003E00003E00003C00003C000078000070000 0E00001C0000180000300000600000C00001800001000002002004002008002018006030 00403FFFC07FFFC0FFFFC013217EA018>I<007E0001C1000300800601C00E03C01C03C0 180180380000380000780000700000700000F0F800F30C00F40600F40300F80380F801C0 F001C0F001E0F001E0F001E0F001E0F001E07001E07001E07001E03801C03801C0180380 1C03000C0600070C0001F00013227EA018>54 D<01F000060C000C060018070038038070 0380700380F001C0F001C0F001C0F001E0F001E0F001E0F001E0F001E07001E07003E038 03E01805E00C05E00619E003E1E00001C00001C00001C000038000038030030078070078 0600700C002018001030000FC00013227EA018>57 D68 D72 D<03F0200C0C601802603001E07000 E0600060E00060E00060E00020E00020E00020F00000F000007800007F00003FF0001FFE 000FFF0003FF80003FC00007E00001E00000F00000F00000708000708000708000708000 70C00060C00060E000C0F000C0C80180C6070081FC0014247DA21B>83 D<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E00000E00 000E00000E00000E1F000E61C00E80600F00300E00380E003C0E001C0E001E0E001E0E00 1E0E001E0E001E0E001E0E001E0E001C0E003C0E00380F00700C80600C41C0083F001723 7FA21B>98 D<01FE000703000C07801C0780380300780000700000F00000F00000F00000 F00000F00000F00000F000007000007800403800401C00800C010007060001F80012157E 9416>I<01FC000707000C03801C01C03801C07801E07000E0F000E0FFFFE0F00000F000 00F00000F00000F000007000007800203800201C00400E008007030000FC0013157F9416 >101 D<00007001F198071E180E0E181C07001C07003C07803C07803C07803C07801C07 001C07000E0E000F1C0019F0001000001000001800001800001FFE000FFFC00FFFE03800 F0600030400018C00018C00018C000186000306000303800E00E038003FE0015217F9518 >103 D<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E00 000E00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E00700E00 700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7 FF18237FA21B>I<1C001E003E001E001C00000000000000000000000000000000000E00 FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E00FFC00A227FA10E>I<0E00FE001E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E00FFE00B237FA20E>108 D<0E1FC07F00FE60E183801E807201C00F003C 00E00F003C00E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800 E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E0 0E003800E00E003800E0FFE3FF8FFE27157F942A>I<0E1F80FE60C01E80E00F00700F00 700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00 700E00700E00700E0070FFE7FF18157F941B>I<0E3CFE461E8F0F0F0F060F000E000E00 0E000E000E000E000E000E000E000E000E000E000E000F00FFF010157F9413>114 D<02000200020002000600060006000E001E003E00FFF80E000E000E000E000E000E000E 000E000E000E000E000E040E040E040E040E040E040708030801F00E1F7F9E13>116 D<0E0070FE07F01E00F00E00700E00700E00700E00700E00700E00700E00700E00700E00 700E00700E00700E00700E00700E00F00E00F006017003827800FC7F18157F941B>I119 D<3FFFC0380380300780200700600E0040 1C00403C0040380000700000E00001E00001C0000380400700400F00400E00C01C008038 0080780180700780FFFF8012157F9416>122 D E /Fp 26 121 df<78FCFCFCFC780000 000000000000000000000000000000000078FCFCFCFC78061F7A9E12>58 D 66 D68 D77 D80 D<00FE00000303C0000C00E00010007000100038003C003C003E001C 003E001E003E001E0008001E0000001E0000001E0000001E00000FFE0000FC1E0003E01E 000F801E001F001E003E001E003C001E007C001E00F8001E04F8001E04F8001E04F8003E 04F8003E0478003E047C005E043E008F080F0307F003FC03E01E1F7D9E21>97 D<07800000FF800000FF8000000F80000007800000078000000780000007800000078000 000780000007800000078000000780000007800000078000000780000007800000078000 00078000000781FC0007860700078801C0079000E007A0007007C0007807800038078000 3C0780003C0780001E0780001E0780001F0780001F0780001F0780001F0780001F078000 1F0780001F0780001F0780001F0780001E0780003E0780003C0780003C0780007807C000 70072000F0072001E00618038006060F000401F80020327EB125>I<003F8000E0600380 180700040F00041E001E1C003E3C003E7C003E7C0008780000F80000F80000F80000F800 00F80000F80000F80000F80000F800007800007C00007C00003C00011E00011E00020F00 0207000403801800E060003F80181F7D9E1D>I<000001E000003FE000003FE0000003E0 000001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0 000001E0000001E0000001E0000001E0000001E0000001E0001F81E000F061E001C019E0 078005E00F0003E00E0003E01E0001E03C0001E03C0001E07C0001E0780001E0F80001E0 F80001E0F80001E0F80001E0F80001E0F80001E0F80001E0F80001E0F80001E0780001E0 780001E03C0001E03C0001E01C0001E01E0003E00E0005E0070009E0038011F000E061FF 003F81FF20327DB125>I<003F800000E0E0000380380007003C000E001E001E001E001C 000F003C000F007C000F0078000F8078000780F8000780F8000780FFFFFF80F8000000F8 000000F8000000F8000000F8000000F8000000780000007C0000003C0000003C0000801E 0000800E0001000F0002000780020001C00C0000F03000001FC000191F7E9E1D>I<0007 E0001C1000383800707C00E07C01E07C01C03803C00003C00003C00003C00003C00003C0 0003C00003C00003C00003C00003C00003C000FFFFC0FFFFC003C00003C00003C00003C0 0003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C0 0003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00007E0007FFF 007FFF0016327FB114>I<000000F0007F030801C1C41C0380E81C070070080F0078001E 003C001E003C003E003E003E003E003E003E003E003E003E003E003E003E001E003C001E 003C000F007800070070000780E00009C1C000087F000018000000180000001800000018 000000180000001C0000000E0000000FFFF80007FFFF0003FFFF800E000FC0180001E030 0000F070000070E0000038E0000038E0000038E0000038E0000038700000707000007038 0000E01C0001C00700070001C01C00003FE0001E2F7E9F21>I<0780000000FF80000000 FF800000000F800000000780000000078000000007800000000780000000078000000007 800000000780000000078000000007800000000780000000078000000007800000000780 000000078000000007800000000780FE00000783078000078C03C000079001E00007A001 E00007A000F00007C000F00007C000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078000F000078000F000078000F000078000F000 078000F000078000F000078000F000078000F000078000F000078000F000078000F00007 8000F000078000F0000FC001F800FFFC1FFF80FFFC1FFF8021327EB125>I<07000F801F 801F800F800700000000000000000000000000000000000000000000000780FF80FF800F 800780078007800780078007800780078007800780078007800780078007800780078007 800780078007800780078007800FC0FFF8FFF80D307EAF12>I<07800000FF800000FF80 00000F800000078000000780000007800000078000000780000007800000078000000780 00000780000007800000078000000780000007800000078000000780000007801FFC0780 1FFC078007E0078007800780060007800400078008000780100007806000078080000781 00000783800007878000078FC0000793C00007A1E00007C1F0000780F000078078000780 7C0007803C0007803E0007801F0007800F0007800F80078007C0078003C0078003E00FC0 07F8FFFC0FFFFFFC0FFF20327EB123>107 D<0780FF80FF800F80078007800780078007 800780078007800780078007800780078007800780078007800780078007800780078007 800780078007800780078007800780078007800780078007800780078007800780078007 80078007800FC0FFFCFFFC0E327EB112>I<0780FE001FC000FF83078060F000FF8C03C1 8078000F9001E2003C0007A001E4003C0007A000F4001E0007C000F8001E0007C000F800 1E00078000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E 00078000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E00 078000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E0007 8000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E000FC0 01F8003F00FFFC1FFF83FFF0FFFC1FFF83FFF0341F7E9E38>I<0780FE0000FF83078000 FF8C03C0000F9001E00007A001E00007A000F00007C000F00007C000F000078000F00007 8000F000078000F000078000F000078000F000078000F000078000F000078000F0000780 00F000078000F000078000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F0000FC001F800FFFC1FFF80FFFC1FFF 80211F7E9E25>I<001FC00000F0780001C01C00070007000F0007801E0003C01C0001C0 3C0001E03C0001E0780000F0780000F0780000F0F80000F8F80000F8F80000F8F80000F8 F80000F8F80000F8F80000F8F80000F8780000F07C0001F03C0001E03C0001E01E0003C0 1E0003C00F00078007800F0001C01C0000F07800001FC0001D1F7E9E21>I<0781FC00FF 860700FF8803C00F9001E007A000F007C00078078000780780003C0780003C0780003E07 80001E0780001F0780001F0780001F0780001F0780001F0780001F0780001F0780001F07 80001F0780003E0780003E0780003C0780007C0780007807C000F007A000F007A001E007 98038007860F000781F80007800000078000000780000007800000078000000780000007 800000078000000780000007800000078000000FC00000FFFC0000FFFC0000202D7E9E25 >I<0783E0FF8C18FF907C0F907C07A07C07C03807C00007C00007C00007800007800007 800007800007800007800007800007800007800007800007800007800007800007800007 80000780000780000780000780000FC000FFFE00FFFE00161F7E9E19>114 D<01FC100E03301800F0300070600030E00030E00010E00010E00010F00010F800007E00 003FF0001FFF000FFFC003FFE0003FF00001F80000F880003C80003C80001CC0001CC000 1CE0001CE00018F00038F00030CC0060C301C080FE00161F7E9E1A>I<00400000400000 400000400000400000C00000C00000C00001C00001C00003C00007C0000FC0001FFFE0FF FFE003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003 C00003C00003C00003C00003C00003C01003C01003C01003C01003C01003C01003C01003 C01001C02001E02000E0400078C0001F00142C7FAB19>I<078000F000FF801FF000FF80 1FF0000F8001F000078000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078000F000078000F000078000F000078001F000 078001F000078001F000038002F00003C004F00001C008F800007030FF80001FC0FF8021 1F7E9E25>I119 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 93 489 a Fp(Programmen)n(t)n(wic)n(klung)21 b(durc)n(h)g(Bew)n (eistransformation:)g(Das)544 581 y(Maximalsegmen)n(tproblem)653 707 y Fo(Helm)o(ut)13 b(Sc)o(h)o(wic)o(h)o(ten)o(b)q(erg)702 809 y(12.)j(Dezem)o(b)q(er)e(1996)59 983 y Fn(Es)20 b(ist)g(gut)g(b)q (ek)m(ann)o(t,)g(da\031)g(man)g(aus)g(einem)i(k)o(onstruktiv)o(en)e (Bew)o(eis)h(eines)g(Existenzsatzes)g(ein)-12 1040 y(Programm)14 b(zur)h(Berec)o(hn)o(ung)h(des)f(als)h(existen)o(t)f(nac)o(hgewiesenen) i(Ob)s(jekts)e(extrahieren)h(k)m(ann.)f(Diese)-12 1096 y(Art)d(der)h(Programmierung)f(b)q(ezeic)o(hnen)j(Bates)d(und)h (Constable)g(in)g([1])f(als)g(\\v)o(ery)g(high)i(lev)o(el)g(program-) -12 1153 y(ming".)h(Sie)i(erm)287 1155 y(\177)287 1153 y(oglic)o(h)o(t)f(es,)f(den)i(b)q(ew)666 1155 y(\177)666 1153 y(ahrten)f(mathematisc)o(h-logisc)o(hen)g(F)l(ormalism)o(us)g(als) g(Program-)-12 1209 y(miersprac)o(he)21 b(zu)f(b)q(en)o(utzen;)h(auf)f (diese)h(W)l(eise)g(w)o(erden)f(nac)o(h)o(tr)1141 1211 y(\177)1141 1209 y(aglic)o(he)g(Korrektheitsb)q(ew)o(eise)1715 1211 y(\177)1714 1209 y(ub)q(er-)-12 1266 y(\015)14 1268 y(\177)13 1266 y(ussig.)c(Der)g(h)252 1268 y(\177)252 1266 y(ohere)g(Aufw)o(and)g(b)q(ei)h(der)f(Erstellung)h(v)o(on)e (Programmen)g(wird)h(dadurc)o(h)h(ertr)1654 1268 y(\177)1654 1266 y(aglic)o(her,)-12 1322 y(da\031)d(man)g(Bew)o(eise)h(v)o(on)e (reinen)j(Alls)638 1324 y(\177)638 1322 y(atzen)f(nic)o(h)o(t)g(zu)f (formalisieren)h(brauc)o(h)o(t,)f(falls)h(man)f(ihre)g(Ric)o(h)o(tig-) -12 1379 y(k)o(eit)h(auf)g(andere)h(W)l(eise)g(eingesehen)h(hat.)59 1435 y(Wir)h(w)o(ollen)h(hier)g(anhand)g(eines)h(einfac)o(hen)f (Beispiels)i(einen)f(w)o(eiteren)f(Asp)q(ekt)g(dieser)g(Art)f(v)o(on) -12 1491 y(Programmiersprac)o(he)12 b(demonstrieren,)i(n)742 1493 y(\177)742 1491 y(amlic)o(h)h(die)f(M)999 1493 y(\177)999 1491 y(oglic)o(hk)o(eit,)g(allgemeine)i(Programme)c(an)h(sp)q(e-)-12 1548 y(zielle)24 b(Situationen)e(anzupassen)h(und)f(sie)g(dab)q(ei)h({) e(auc)o(h)g(extensional)i({)e(zu)h(v)o(er)1471 1550 y(\177)1471 1548 y(andern.)f(Da\031)g(dies)-12 1604 y(m)26 1606 y(\177)26 1604 y(oglic)o(h)16 b(ist,)f(wurde)g(zuerst)h(v)o(on)e(Goad)h(in)h (seiner)g(Dissertation)f([2])f(b)q(emerkt.)59 1661 y(Unser)19 b(Beispiel)k(ist)d(ein)h(einfac)o(hes,)f(ab)q(er)g(reales)g (Programmierproblem,)f(das)h(sogenann)o(te)f(Ma-)-12 1717 y(ximalsegmen)o(tproblem)f(aus)f([1)o(]:)f(Zu)h(einer)h(gegeb)q (enen)g(F)l(olge)e Fm(x)1146 1724 y Fl(0)1166 1717 y Fm(;)8 b(x)1213 1724 y Fl(1)1232 1717 y Fm(;)g(:)g(:)g(:)d(;)j(x)1360 1724 y Fk(n)1399 1717 y Fn(ganzer)17 b(Zahlen)h(ist)f(ein)-12 1774 y(maximales)f(Segmen)o(t)e(zu)i(\014nden,)g(also)f(eine)h(durc)o (h)g(Indizes)h Fm(i)d Fn(und)i Fm(k)g Fn(mit)f Fm(i)e Fj(\024)g Fm(k)j Fn(b)q(estimm)o(te)f(T)l(eilfolge)-12 1830 y(aufeinander)h(folgender)g(Glieder,)g(so)f(da\031)g(die)h(Summe)g Fm(x)1005 1837 y Fk(i)1029 1830 y Fn(+)10 b Fj(\001)e(\001)g(\001)h Fn(+)h Fm(x)1209 1837 y Fk(k)1245 1830 y Fn(maximal)16 b(ist.)59 1887 y(Zun)137 1889 y(\177)137 1887 y(ac)o(hst)f(form)o (ulieren)h(wir)g(die)g(Behauptung)g(et)o(w)o(as)e(allgemeiner)j(und)g (v)o(erw)o(enden)e(anstelle)i(v)o(on)-12 1943 y Fm(x)14 1950 y Fk(i)37 1943 y Fn(+)10 b Fj(\001)e(\001)g(\001)f Fn(+)j Fm(x)215 1950 y Fk(k)251 1943 y Fn(ein)16 b(b)q(eliebiges)i (Ma\031)13 b(seg)q(\()p Fm(i;)8 b(k)q Fn(\))13 b(f)819 1945 y(\177)818 1943 y(ur)i Fm(x)902 1950 y Fk(i)916 1943 y Fm(;)8 b(:)g(:)g(:)d(;)j(x)1044 1950 y Fk(k)1064 1943 y Fn(,)15 b(also)f(eine)i(Abbildung)h(seg)q(:)8 b Fi(N)e Fj(\002)k Fi(N)h Fj(!)i Fm(X)t Fn(,)-12 2000 y(w)o(ob)q(ei)i Fm(X)i Fn(eine)e(b)q(eliebige)i(\(partiell\))e (geordnete)f(Menge)g(ist.)g(Gesuc)o(h)o(t)f(sind)i(dann)g Fm(i;)8 b(k)14 b Fn(so)f(da\031)h(seg\()p Fm(i;)8 b(k)q Fn(\))-12 2056 y(maximal)16 b(in)g Fm(X)i Fn(ist.)d(Ein)h(Beispiel)i (ist)d(et)o(w)o(a)f Fm(x)807 2063 y Fk(i)834 2056 y Fj(2)f Fi(Q)912 2040 y Fl(+)954 2056 y Fn(und)j(seg\()p Fm(i;)8 b(k)q Fn(\))j(:=)1276 2024 y Fh(Q)1315 2068 y Fk(i)p Fg(\024)p Fk(j)r Fg(\024)p Fk(k)1427 2056 y Fm(x)1453 2063 y Fk(j)1471 2056 y Fn(.)59 2112 y(Nat)135 2114 y(\177)134 2112 y(urlic)o(h)20 b(k)m(ann)g(man)f(dieses)i(Problem)f(einfac)o(h)g (durc)o(h)g(Probieren)g(aller)h(M)1455 2114 y(\177)1455 2112 y(oglic)o(hk)o(eiten)f(l)1719 2114 y(\177)1719 2112 y(osen;)-12 2169 y(dies)e(sind)g Fm(O)q Fn(\()p Fm(n)260 2152 y Fl(2)280 2169 y Fn(\))f(viele.)h(Dieser)g(trivialen)g(L)785 2171 y(\177)785 2169 y(osung)g(en)o(tspric)o(h)o(t)f(auc)o(h)g(der)h (im)f(folgenden)i(angegeb)q(ene)-12 2225 y(Bew)o(eis)f(f)155 2227 y(\177)154 2225 y(ur)f(die)h(allgemeine)h(Behauptung.)f(Genauer)f (hei\031t)h(dies:)g(Aus)f(dem)h(k)o(onstruktiv)e(gef)1688 2227 y(\177)1687 2225 y(uhrten)-12 2282 y(Bew)o(eis)g(k)m(ann)g(man)f (einen)h(Algorithm)o(us)g(ablesen,)g(der)f(dem)h(simplen)h(Durc)o (hprobieren)f(en)o(tspric)o(h)o(t.)59 2338 y(Wir)h(w)o(ollen)h(dann)g (ansc)o(hlie\031end)i(zeigen,)e(da\031)f(f)932 2340 y(\177)931 2338 y(ur)g(unser)h(k)o(onkretes)f(Problem)h(mit)g(der)f(Summe)-12 2395 y Fm(x)14 2402 y Fk(i)35 2395 y Fn(+)7 b Fj(\001)h(\001)g(\001)e Fn(+)h Fm(x)206 2402 y Fk(k)241 2395 y Fn(als)14 b(Ma\031)f(der)h(Bew)o (eis)g(sic)o(h)h(v)o(ereinfac)o(hen)f(l)993 2397 y(\177)993 2395 y(a\031t,)g(indem)g(man)g(an)g(einer)g(geeigneten)h(Stelle)-12 2451 y(die)g(Monotonie)e(der)h(Summe)g(v)o(erw)o(endet.)f(Aus)h(diesem) h(v)o(ereinfac)o(h)o(ten)f(Bew)o(eis)h(l)1423 2453 y(\177)1423 2451 y(a\031t)e(sic)o(h)h(ein)h(b)q(esserer)892 2577 y(1)p eop %%Page: 2 2 2 1 bop -12 307 a Fn(Algorithm)o(us)17 b(ablesen,)h(der)f(n)o(ur)h(no)q (c)o(h)f Fm(O)q Fn(\()p Fm(n)p Fn(\))g(viele)h(Sc)o(hritte)g(b)q(en) 1165 309 y(\177)1165 307 y(otigt.)f(Wir)g(hab)q(en)h(also)f(hier)h (durc)o(h)-12 364 y(Anpassen)h(eines)h(allgemeinen)h(Bew)o(eises)f(an)e (eine)i(sp)q(ezielle)i(Situation)e(erreic)o(h)o(t,)e(da\031)h(der)g (aus)f(dem)-12 420 y(Bew)o(eis)e(abzulesende)h(Algorithm)o(us)f(w)o (esen)o(tlic)o(h)g(v)o(erb)q(essert)f(wurde.)59 477 y(Wir)g(skizzieren) i(zuerst)e(den)h(allgemeinen)i(\(und)d(trivialen\))h(Bew)o(eis.)g(Zu)f (zeigen)i(ist)-12 557 y Ff(Sp)q(ezi\014k)m(ation.)281 656 y Fj(8)p Fm(n)p Fj(9)p Fm(i;)8 b(k)q Fn(\()p Fm(i)k Fj(\024)h Fm(k)h Fj(\024)f Fm(n)d Fj(^)g(8)p Fm(i)718 638 y Fg(0)730 656 y Fm(;)e(k)776 638 y Fg(0)787 656 y Fn([)p Fm(i)816 638 y Fg(0)840 656 y Fj(\024)13 b Fm(k)913 638 y Fg(0)937 656 y Fj(\024)g Fm(n)g Fj(!)g Fn(seg\()p Fm(i)1178 638 y Fg(0)1189 656 y Fm(;)8 b(k)1235 638 y Fg(0)1246 656 y Fn(\))13 b Fj(\024)g Fn(seg\()p Fm(i;)8 b(k)q Fn(\)]\))p Fm(:)-12 756 y Fe(Beweis)17 b Fn(durc)o(h)h(Induktion) 485 758 y(\177)484 756 y(ub)q(er)g Fm(n)p Fn(.)g(Der)f (Induktionsanfang)h(ist)g(trivial,)g(und)h(im)f(Sc)o(hritt)g(b)q (estimm)o(t)-12 812 y(man)11 b(zun)155 814 y(\177)155 812 y(ac)o(hst)h(ein)h(maximales)f(Endsegmen)o(t)f(v)o(on)h Fm(x)922 819 y Fl(0)941 812 y Fm(;)c(:)g(:)g(:)d(;)j(x)1069 819 y Fk(n)1092 812 y Fm(;)g(x)1139 819 y Fk(n)p Fl(+1)1218 812 y Fn(und)k(bildet)h(dann)f(das)g(Maxim)o(um)-12 869 y(v)o(on)j(diesem)h(maximalen)g(Endsegmen)o(t)f(und)h(dem)g(nac)o(h)f (IH)h(gegeb)q(enen)g(maximalen)g(Segmen)o(t.)82 b Fd(\003)59 949 y Fn(Die)12 b(erste)g(F)l(eststellung)i(ist)e(hier,)h(da\031)f(man) g(so)o(wieso)g(neb)q(en)i(dem)e(gesuc)o(h)o(ten)h(maximalen)g(Segmen)o (t)-12 1006 y(auc)o(h)g(no)q(c)o(h)f(das)h(maximale)g(Endsegmen)o(t)f (b)q(erec)o(hnen)i(m)o(u\031.)e(Es)g(liegt)h(deshalb)h(nahe,)f(die)g (Sp)q(ezi\014k)m(ation)-12 1062 y(so)k(zu)h(erw)o(eitern,)f(da\031)g (neb)q(en)i(dem)f(maximalen)g(Segmen)o(t)g(auc)o(h)f(no)q(c)o(h)h(das)g (maximale)g(Endsegmen)o(t)-12 1118 y(zu)e(\014nden)g(ist.)-12 1199 y Ff(Erw)o(eiterte)h(Sp)q(ezi\014k)m(ation.)28 b Fc(F)608 1201 y(\177)607 1199 y(ur)15 b(alle)h Fm(n)g Fc(gilt)314 1298 y Fj(9)p Fm(i;)8 b(k)q Fn(\()p Fm(i)j Fj(\024)i Fm(k)h Fj(\024)f Fm(n)d Fj(^)h(8)p Fm(i)699 1279 y Fg(0)710 1298 y Fm(;)d(k)756 1279 y Fg(0)767 1298 y Fn([)p Fm(i)796 1279 y Fg(0)820 1298 y Fj(\024)13 b Fm(k)893 1279 y Fg(0)917 1298 y Fj(\024)g Fm(n)g Fj(!)g Fn(seg\()p Fm(i)1158 1279 y Fg(0)1169 1298 y Fm(;)8 b(k)1215 1279 y Fg(0)1226 1298 y Fn(\))13 b Fj(\024)g Fn(seg\()p Fm(i;)8 b(k)q Fn(\)]\))266 b(\(1\))314 1367 y Fj(9)p Fm(j)s Fj(\024)p Fm(n)p Fj(8)p Fm(j)470 1348 y Fg(0)481 1367 y Fj(\024)q Fm(n)p Fn(\(seg\()p Fm(j)663 1348 y Fg(0)674 1367 y Fm(;)8 b(n)p Fn(\))k Fj(\024)h Fn(seg\()p Fm(j;)8 b(n)p Fn(\)\))779 b(\(2\))-12 1466 y Fe(Beweis)18 b Fn(durc)o(h)h(Induktion)488 1468 y(\177)487 1466 y(ub)q(er)g Fm(n)p Fn(.)f Fe(F)m(al)r(l)23 b Fn(0.)17 b(W)852 1468 y(\177)852 1466 y(ahle)i Fm(i)f Fn(=)h Fm(k)g Fn(=)f(0.)g Fe(F)m(al)r(l)k Fm(n)13 b Fn(+)g(1.)18 b(Nac)o(h)g(IH)h(hab)q(en)g(wir) -12 1523 y(b)q(ereits)d Fm(i)152 1530 y Fk(n)175 1523 y Fm(;)8 b(k)220 1530 y Fk(n)258 1523 y Fn(so)o(wie)15 b Fm(j)397 1530 y Fk(n)420 1523 y Fn(.)59 1579 y(Wir)g(w)o(ollen)h(zun) 361 1581 y(\177)361 1579 y(ac)o(hst)f Fm(j)498 1586 y Fk(n)p Fl(+1)582 1579 y Fn(k)o(onstruieren,)g(hab)q(en)h(also)f(zu)h (zeigen)427 1679 y Fj(9)p Fm(j)s Fj(\024)p Fm(n)p Fn(+)q(1)p Fj(8)p Fm(j)642 1660 y Fg(0)653 1679 y Fj(\024)p Fm(n)p Fn(+)q(1\(seg\()p Fm(j)893 1660 y Fg(0)903 1679 y Fm(;)8 b(n)i Fn(+)g(1\))j Fj(\024)f Fn(seg)q(\()p Fm(j;)c(n)h Fn(+)h(1\)\))p Fm(:)381 b Fn(\(3\))-12 1778 y(Da)12 b(uns)h Fm(j)158 1785 y Fk(n)193 1778 y Fn(hier)h(o\013ensic)o(h)o(tlic)o(h)g (nic)o(h)o(t)f(w)o(eiterhilft,)g(v)o(erallgemeinern)h(wir)f(die)g (Behauptung)h(\(3\))d(so,)h(da\031)-12 1835 y(wir)j(sie)h(durc)o(h)g (eine)g(Neb)q(eninduktion)i(b)q(ew)o(eisen)f(k)899 1837 y(\177)899 1835 y(onnen,)f(n)1071 1837 y(\177)1071 1835 y(amlic)o(h)g(zu)383 1934 y Fj(8)p Fm(m)p Fj(\024)q Fm(n)p Fn(+)q(1)p Fj(9)p Fm(`)p Fj(\024)p Fm(m)p Fj(8)p Fm(`)733 1915 y Fg(0)745 1934 y Fj(\024)p Fm(m)p Fn(\(seg\()p Fm(`)936 1915 y Fg(0)947 1934 y Fm(;)8 b(n)i Fn(+)g(1\))i Fj(\024)h Fn(seg)q(\()p Fm(`;)8 b(n)h Fn(+)h(1\)\))p Fm(:)307 b Fn(\(3)1772 1917 y Fl(+)1801 1934 y Fn(\))-12 2033 y(Den)18 b(Bew)o(eis)g(f)253 2035 y(\177)252 2033 y(uhren)h(wir)f(durc)o(h)g(Neb)q(eninduktion)j(nac)o(h)d Fm(m)p Fn(,)f(w)o(ob)q(ei)i Fm(n)f Fn(als)g(P)o(arameter)e (festgehalten)-12 2090 y(wird.)g Fe(F)m(al)r(l)j Fn(0.)c(W)298 2092 y(\177)298 2090 y(ahle)i Fm(`)c Fn(=)h(0.)h Fe(F)m(al)r(l)20 b Fm(m)10 b Fn(+)h(1.)k(Nac)o(h)h(NIH)g(hab)q(en)h(wir)f(b)q(ereits)h (ein)g Fm(`)1444 2097 y Fk(m)1477 2090 y Fn(.)e(Ist)h(seg)q(\()p Fm(`)1672 2097 y Fk(m)1704 2090 y Fm(;)8 b(n)p Fn(\))13 b Fm(<)-12 2146 y Fn(seg\()p Fm(m)g Fn(+)g(1)p Fm(;)8 b(n)p Fn(\),)17 b(so)h(sei)i Fm(`)435 2153 y Fk(m)p Fl(+1)532 2146 y Fn(:=)f Fm(m)12 b Fn(+)h(1;)19 b(andernfalls)h(setzen)f(wir)g Fm(`)1230 2153 y Fk(m)p Fl(+1)1327 2146 y Fn(:=)g Fm(`)1413 2153 y Fk(m)1446 2146 y Fn(.)g({)f(Damit)h(ist)g(\(3)1772 2130 y Fl(+)1801 2146 y Fn(\))-12 2203 y(b)q(ewiesen,)d(und)g(mit)g Fm(m)c Fn(:=)h Fm(n)d Fn(+)h(1)k(k)624 2205 y(\177)624 2203 y(onnen)g(wir)h(unser)f(gesuc)o(h)o(tes)g Fm(j)1176 2210 y Fk(n)p Fl(+1)1260 2203 y Fn(de\014nieren)i(als)e Fm(j)1554 2210 y Fk(n)p Fl(+1)1635 2203 y Fn(:=)e Fm(`)1715 2210 y Fk(n)p Fl(+1)1784 2203 y Fn(.)59 2259 y(Jetzt)f(k)194 2261 y(\177)194 2259 y(onnen)i(wir)f Fm(i)418 2266 y Fk(n)p Fl(+1)486 2259 y Fm(;)8 b(k)531 2266 y Fk(n)p Fl(+1)611 2259 y Fn(k)o(onstruieren.)13 b(Ist)f(seg)q(\()p Fm(j)1045 2266 y Fk(n)p Fl(+1)1113 2259 y Fm(;)c(n)d Fn(+)g(1\))12 b Fm(<)h Fn(seg\()p Fm(i)1402 2266 y Fk(n)1425 2259 y Fm(;)8 b(k)1470 2266 y Fk(n)1492 2259 y Fn(\),)k(so)h(nehmen)g (wir)-12 2316 y(das)j(alte)g(maximale)g(Segmen)o(t)g(und)h(setzen)f Fm(i)794 2323 y Fk(n)p Fl(+1)877 2316 y Fn(:=)d Fm(i)954 2323 y Fk(n)978 2316 y Fn(,)i Fm(k)1030 2323 y Fk(n)p Fl(+1)1112 2316 y Fn(:=)f Fm(k)1198 2323 y Fk(n)1221 2316 y Fn(;)i(andernfalls)h(ist)f(das)g(maximale)-12 2372 y(Endsegmen)o(t)f(das)g(maximale)h(Segmen)o(t)f(und)h(wir)f (setzen)h Fm(i)1037 2379 y Fk(n)p Fl(+1)1118 2372 y Fn(:=)c Fm(j)1197 2379 y Fk(n)p Fl(+1)1266 2372 y Fn(,)j Fm(k)1318 2379 y Fk(n)p Fl(+1)1398 2372 y Fn(:=)e Fm(n)d Fn(+)h(1.)208 b Fd(\003)59 2452 y Fn(O\013en)o(bar)15 b(ist)g(der)g(diesem)i(Bew)o (eis)e(en)o(tsprec)o(hende)i(Algorithm)o(us)e(quadratisc)o(h.)892 2577 y(2)p eop %%Page: 3 3 3 2 bop 59 307 a Fn(Wir)18 b(w)o(ollen)i(jetzt)e(zeigen,)h(wie)h(man)e (b)q(ei)i(zus)888 309 y(\177)888 307 y(atzlic)o(hen)g(Kenn)o(tnissen) 1344 309 y(\177)1342 307 y(ub)q(er)g(die)f(Eingangsdaten)-12 364 y(den)d(Bew)o(eis)g(v)o(ereinfac)o(hen)g(k)m(ann.)f(In)h(unserer)g (Ausgangssituation)f(galt)111 461 y(\()p Fm(x)155 468 y Fk(i)178 461 y Fn(+)c Fj(\001)d(\001)g(\001)g Fn(+)i Fm(x)358 468 y Fk(k)392 461 y Fj(\024)j Fm(x)466 468 y Fk(j)495 461 y Fn(+)d Fj(\001)e(\001)g(\001)g Fn(+)j Fm(x)675 468 y Fk(k)696 461 y Fn(\))h Fj(!)h Fn(\()p Fm(x)828 468 y Fk(i)852 461 y Fn(+)e Fj(\001)d(\001)g(\001)g Fn(+)i Fm(x)1032 468 y Fk(k)1064 461 y Fn(+)g Fm(x)1135 468 y Fk(k)q Fl(+1)1214 461 y Fj(\024)j Fm(x)1288 468 y Fk(j)1316 461 y Fn(+)e Fj(\001)d(\001)g(\001)g Fn(+)j Fm(x)1497 468 y Fk(k)1528 461 y Fn(+)f Fm(x)1599 468 y Fk(k)q Fl(+1)1666 461 y Fn(\))p Fm(:)-12 559 y Fn(Wir)15 b(b)q(etrac)o(h)o(ten)g(deshalb)i(den)f(Sp)q(ezialfall)329 657 y Fj(8)p Fm(i;)8 b(j;)g(k)q Fn([seg)n(\()p Fm(i;)g(k)q Fn(\))j Fj(\024)i Fn(seg)q(\()p Fm(j;)8 b(k)q Fn(\))j Fj(!)i Fn(seg\()p Fm(i;)8 b(k)i Fn(+)g(1\))i Fj(\024)h Fn(seg)q(\()p Fm(j;)8 b(k)i Fn(+)g(1\)])p Fm(:)282 b Fn(\()p Fj(\003)p Fn(\))-12 755 y(Diese)17 b(Zusatzannahme)f(erm)513 757 y(\177)513 755 y(oglic)o(h)o(t)g(es)g(uns,)h(die)g(Existenz)g (\(3\))e(eines)i(maximalen)g(Endsegmen)o(ts)g(di-)-12 812 y(rekter)e(zu)g(b)q(ew)o(eisen,)i(und)f(zw)o(ar)56 902 y Fj(\017)23 b Fn(ohne)13 b(V)l(erw)o(endung)h(der)f(V)l (erallgemeinerung)i(\(3)961 885 y Fl(+)990 902 y Fn(\))e(und)g(der)g (zu)h(ihrem)f(Bew)o(eis)h(n)1543 904 y(\177)1543 902 y(otigen)f(Neb)q(en-)102 958 y(induktion,)j(ab)q(er)56 1051 y Fj(\017)23 b Fn(mit)13 b(Hilfe)h(der)f(IH)g({)g(also)g Fm(j)572 1058 y Fk(n)608 1051 y Fn({)f(und)i(der)f(F)l(allun)o(tersc)o (heidung)i(seg\()p Fm(j)1291 1058 y Fk(n)1314 1051 y Fm(;)8 b(n)d Fn(+)g(1\))13 b Fm(<)g Fn(seg)q(\()p Fm(n)5 b Fn(+)g(1)p Fm(;)j(n)d Fn(+)g(1\))102 1107 y(bzw.)15 b Fj(\025)p Fn(.)-12 1197 y(Diesen)e(durc)o(h)f(die)h(Zusatzannahme)e (\()p Fj(\003)p Fn(\))g(erm)793 1199 y(\177)793 1197 y(oglic)o(h)o(ten)i(v)o(erk)1068 1199 y(\177)1067 1197 y(urzten)f(Bew)o(eis)g(w)o(ollen)h(wir)f(jetzt)f(genauer)-12 1254 y(durc)o(hf)115 1256 y(\177)114 1254 y(uhren.)16 b(Dazu)f(mo)q(di\014zieren)i(wir)f(den)g(obigen)g(Bew)o(eis)f(wie)h(eb) q(en)h(b)q(esc)o(hrieb)q(en.)-12 1334 y Fe(V)m(erk)80 1336 y(\177)80 1334 y(urzter)f(Beweis)p Fn(.)f(Zu)h(zeigen)h(ist)f (wieder)g(\(1\))f(und)i(\(2\).)d(V)l(erw)o(endet)i(wird)g(Induktion) 1584 1336 y(\177)1583 1334 y(ub)q(er)g Fm(n)p Fn(.)g Fe(F)m(al)r(l)-12 1390 y Fn(0.)e(W)85 1392 y(\177)85 1390 y(ahle)i Fm(i)c Fn(=)h Fm(k)h Fn(=)f(0.)i Fe(F)m(al)r(l)j Fm(n)11 b Fn(+)f(1.)15 b(Nac)o(h)g(IH)h(hab)q(en)g(wir)f(b)q(ereits)h Fm(i)1181 1397 y Fk(n)1204 1390 y Fm(;)8 b(k)1249 1397 y Fk(n)1287 1390 y Fn(so)o(wie)15 b Fm(j)1426 1397 y Fk(n)1449 1390 y Fn(.)59 1447 y(Wir)g(w)o(ollen)h(zun)361 1449 y(\177)361 1447 y(ac)o(hst)f Fm(j)498 1454 y Fk(n)p Fl(+1)582 1447 y Fn(k)o(onstruieren,)g(hab)q(en)h(also)f(zu)h(zeigen) 427 1545 y Fj(9)p Fm(j)s Fj(\024)p Fm(n)p Fn(+)q(1)p Fj(8)p Fm(j)642 1526 y Fg(0)653 1545 y Fj(\024)p Fm(n)p Fn(+)q(1\(seg\()p Fm(j)893 1526 y Fg(0)903 1545 y Fm(;)8 b(n)i Fn(+)g(1\))j Fj(\024)f Fn(seg)q(\()p Fm(j;)c(n)h Fn(+)h(1\)\))p Fm(:)381 b Fn(\(3\))-12 1642 y(Die)16 b(IH)f(liefert)h(uns)g(f)365 1644 y(\177)364 1642 y(ur)f(b)q(eliebige)j Fm(j)632 1626 y Fg(0)656 1642 y Fj(\024)13 b Fm(n)691 1740 y Fn(seg)q(\()p Fm(j)793 1721 y Fg(0)803 1740 y Fm(;)8 b(n)p Fn(\))k Fj(\024)h Fn(seg\()p Fm(j)1027 1747 y Fk(n)1050 1740 y Fm(;)8 b(n)p Fn(\))-12 1838 y(und)16 b(deshalb)g(aufgrund)g(der)f(Zusatzannahme)g(\()p Fj(\003)p Fn(\))f(auc)o(h)606 1936 y(seg)q(\()p Fm(j)708 1917 y Fg(0)719 1936 y Fm(;)8 b(n)h Fn(+)i(1\))h Fj(\024)h Fn(seg\()p Fm(j)1021 1943 y Fk(n)1044 1936 y Fm(;)8 b(n)i Fn(+)g(1\))p Fm(:)560 b Fn(\(4\))59 2034 y(Ist)11 b(n)o(un)h(seg)q(\()p Fm(j)307 2041 y Fk(n)330 2034 y Fm(;)c(n)s Fn(+)s(1\))j Fm(<)i Fn(seg)q(\()p Fm(n)s Fn(+)s(1)p Fm(;)8 b(n)s Fn(+)s(1\),)i(so)h (sei)h Fm(j)976 2041 y Fk(n)p Fl(+1)1057 2034 y Fn(:=)h Fm(n)s Fn(+)s(1.)e(Dann)h(hab)q(en)g(wir)g(f)1574 2036 y(\177)1573 2034 y(ur)g(b)q(eliebiges)-12 2090 y Fm(j)10 2074 y Fg(0)34 2090 y Fj(\024)h Fm(n)d Fn(+)h(1)k(wie)h(gew)361 2092 y(\177)360 2090 y(unsc)o(h)o(t)f(stets)g(seg\()p Fm(j)712 2074 y Fg(0)723 2090 y Fm(;)8 b(n)h Fn(+)i(1\))h Fj(\024)h Fn(seg)q(\()p Fm(j)1026 2097 y Fk(n)p Fl(+1)1094 2090 y Fm(;)8 b(n)h Fn(+)i(1\):)j(im)i(F)l(all)g Fm(j)1442 2074 y Fg(0)1466 2090 y Fj(\024)d Fm(n)j Fn(folgt)e(dies)j(aus)-12 2147 y(\(4\))d(und)i(der)f(F)l(allun)o(tersc)o(heidungsannahme,)j(und)e (im)f(F)l(all)h Fm(j)1095 2130 y Fg(0)1119 2147 y Fn(=)d Fm(n)d Fn(+)h(1)k(ist)g(es)g(trivial.)59 2203 y(Ist)h(andererseits)g (seg)q(\()p Fm(n)10 b Fn(+)h(1)p Fm(;)d(n)i Fn(+)h(1\))j Fj(\024)g Fn(seg)q(\()p Fm(j)871 2210 y Fk(n)894 2203 y Fm(;)8 b(n)i Fn(+)h(1\),)k(so)h(setzen)g(wir)g Fm(j)1359 2210 y Fk(n)p Fl(+1)1442 2203 y Fn(:=)e Fm(j)1523 2210 y Fk(n)1546 2203 y Fn(.)i(Dann)g(hab)q(en)-12 2260 y(wir)h(f)83 2262 y(\177)82 2260 y(ur)g(b)q(eliebiges)j Fm(j)372 2243 y Fg(0)399 2260 y Fj(\024)c Fm(n)c Fn(+)g(1)17 b(wie)g(gew)735 2262 y(\177)734 2260 y(unsc)o(h)o(t)g(stets)g(seg\()p Fm(j)1090 2243 y Fg(0)1101 2260 y Fm(;)8 b(n)j Fn(+)h(1\))j Fj(\024)h Fn(seg)q(\()p Fm(n)11 b Fn(+)h(1)p Fm(;)c(n)i Fn(+)i(1\):)k(im)i(F)l(all)-12 2316 y Fm(j)10 2300 y Fg(0)34 2316 y Fj(\024)13 b Fm(n)i Fn(ist)g(dies)h(gerade)g(\(4\),)d (und)j(im)g(F)l(all)g Fm(j)776 2300 y Fg(0)800 2316 y Fn(=)d Fm(n)d Fn(+)g(1)15 b(ist)h(es)f(die)h(F)l(allun)o(tersc)o (heidungsannahme.)59 2373 y(Jetzt)f(k)197 2375 y(\177)197 2373 y(onnen)h(wir)f(wie)h(v)o(orher)e Fm(i)647 2380 y Fk(n)p Fl(+1)716 2373 y Fm(;)8 b(k)761 2380 y Fk(n)p Fl(+1)843 2373 y Fn(k)o(onstruieren.)685 b Fd(\003)59 2452 y Fn(O\013en)o(bar)15 b(ist)g(der)g(diesem)i(Bew)o(eis)e(en)o (tsprec)o(hende)i(Algorithm)o(us)e(linear.)892 2577 y(3)p eop %%Page: 4 4 4 3 bop 59 307 a Fn(Wir)11 b(w)o(ollen)h(an)f(dieser)h(Stelle)h(kurz)f (die)g(F)l(rage)f(diskutieren,)h(ob)f(und)h(in)o(wiew)o(eit)h(diese)f (Bew)o(eistrans-)-12 364 y(formation)e(automatisierbar)f(ist.)i(Ein)g (v)o(ollautomatisc)o(hes)f(V)l(erfahren)h(ohne)g(Hilfe)g(durc)o(h)g (den)g(Ben)o(utzer)-12 420 y(sc)o(hein)o(t)19 b(mir)g(k)m(aum)g(erreic) o(h)o(bar)h(zu)f(sein.)g(Andererseits)h(sollte)f(es)g(als)g(Hilfe)i (gen)1443 422 y(\177)1442 420 y(ugen,)d(da\031)h(man)g(die)-12 477 y(folgenden)d(aus)f(der)h(informalen)g(Analyse)g(des)f(Problems)h (o\013ensic)o(h)o(tlic)o(hen)h(Hin)o(w)o(eise)f(gibt.)43 570 y(1.)23 b(Zu)17 b(ersetzen)h(ist)f(der)g(Bew)o(eisteil,)i(der)f(im) f(Induktionssc)o(hritt)i(die)f(Existenz)g(eines)h(maximalen)102 627 y(Endsegmen)o(ts)c(liefert,)h(also)f(der)g(zu)h(\(3\))e(f)838 629 y(\177)837 627 y(uhrt.)43 721 y(2.)23 b(Der)15 b(neu)h(zu)g(f)352 723 y(\177)351 721 y(uhrende,)h(k)564 723 y(\177)563 721 y(urzere)f(Bew)o(eis)g(v)o(on)g(\(3\))f(soll)h({)g(neb)q(en)h(der)f (Zusatzannahme)f(\()p Fj(\003)p Fn(\))g(und)102 777 y(der)g(IH)h({)f (die)h(F)l(allun)o(tersc)o(heidung)h(seg)q(\()p Fm(j)843 784 y Fk(n)865 777 y Fm(;)8 b(n)i Fn(+)h(1\))h Fm(<)h Fn(seg\()p Fm(n)d Fn(+)h(1)p Fm(;)d(n)h Fn(+)h(1\))15 b(bzw.)g Fj(\025)g Fn(v)o(erw)o(enden.)-12 871 y(In)j(unserem)f(Bew)o (eissystem)h Fb(Minlog)f Fn(hab)q(en)h(wir)f(diese)i(F)l(allstudie)g (implemen)o(tiert,)f(und)g(zw)o(ar)e(mit)-12 927 y(folgendem)f (Ergebnis.)g(Aus)g(dem)f(Originalb)q(ew)o(eis)j(und)f(dem)e(un)o(ter)h (der)f(Zusatzannahme)h(v)o(erk)1694 929 y(\177)1693 927 y(urzten)-12 984 y(Bew)o(eis)23 b(hab)q(en)h(wir)e(Programme)g (extrahiert,)g(die)h(die)h(erw)o(artete)d(F)l(orm)h(hab)q(en:)h(der)g (Originalb)q(e-)-12 1040 y(w)o(eis)14 b(liefert)g(einen)i(quadratisc)o (hen)e(und)g(der)g(v)o(erk)871 1042 y(\177)870 1040 y(urzte)f(Bew)o (eis)i(einen)g(linearen)g(Algorithm)o(us.)f(F)l(erner)-12 1097 y(hab)q(en)21 b(wir)f(v)o(eri\014ziert,)h(da\031)f(sic)o(h)g(mit)h (den)f(angegeb)q(enen)i(Hilfen)f(der)g(v)o(erk)1375 1099 y(\177)1374 1097 y(urzte)f(Bew)o(eis)g(aus)g(dem)-12 1153 y(Originalb)q(ew)o(eis)e(auc)o(h)d(automatisc)o(h)g(gewinnen)h(l) 869 1155 y(\177)869 1153 y(a\031t.)-12 1296 y Fa(Literatur)-12 1398 y Fn([1])22 b(Joseph)c(L.)g(Bates)g(and)g(Rob)q(ert)g(L.)g (Constable.)28 b(Pro)q(ofs)17 b(as)h(programs.)27 b Fe(A)o(CM)17 b(T)m(r)n(ansactions)g(on)59 1454 y(Pr)n(o)n(gr)n(amming)e(L)n (anguages)g(and)i(Systems)p Fn(,)c(7\(1\):113{136,)f(Jan)o(uary)j (1985.)-12 1548 y([2])22 b(Christopher)16 b(Alan)g(Goad.)22 b Fe(Computational)17 b(uses)f(of)i(the)f(manipulation)g(of)g(formal)g (pr)n(o)n(ofs)p Fn(.)22 b(PhD)59 1605 y(thesis,)g(Stanford)g(Univ)o (ersit)o(y)l(,)g(August)g(1980.)39 b(Stanford)22 b(Departmen)o(t)f(of)h (Computer)g(Science)59 1661 y(Rep)q(ort)15 b(No.)g(ST)l(AN{CS{80{819.) 892 2577 y(4)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF