home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: LaTeX Document
(document/latex).
You can browse this item here: intro.tex
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| LaTeX Document (document/latex)
| magic
| Supported |
| 1%
| dexvert
| Corel 10 Texture (image/corel10Texture)
| ext
| Unsupported |
| 1%
| dexvert
| Croteam texture file (image/croteamTextureFile)
| ext
| Unsupported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| LaTeX document, ASCII text
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| x-fmt/111 Plain Text File
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 7b 5c 6d 61 67 74 77 6f | 20 49 6e 74 72 6f 64 75 |{\magtwo| Introdu|
|00000010| 63 74 69 6f 6e 7d 0a 0a | 4f 6e 65 20 6f 66 20 74 |ction}..|One of t|
|00000020| 68 65 20 6d 61 6a 6f 72 | 20 64 69 66 66 65 72 65 |he major| differe|
|00000030| 6e 63 65 73 20 62 65 74 | 77 65 65 6e 20 63 6f 6d |nces bet|ween com|
|00000040| 62 69 6e 61 74 6f 72 69 | 61 6c 20 63 6f 6d 70 75 |binatori|al compu|
|00000050| 74 69 6e 67 0a 61 6e 64 | 20 6f 74 68 65 72 20 61 |ting.and| other a|
|00000060| 72 65 61 73 20 6f 66 20 | 63 6f 6d 70 75 74 69 6e |reas of |computin|
|00000070| 67 20 73 75 63 68 20 61 | 73 20 73 74 61 74 69 73 |g such a|s statis|
|00000080| 74 69 63 73 2c 20 6e 75 | 6d 65 72 69 63 61 6c 0a |tics, nu|merical.|
|00000090| 61 6e 61 6c 79 73 69 73 | 20 61 6e 64 20 6c 69 6e |analysis| and lin|
|000000a0| 65 61 72 20 70 72 6f 67 | 72 61 6d 6d 69 6e 67 20 |ear prog|ramming |
|000000b0| 69 73 20 74 68 65 20 75 | 73 65 20 6f 66 20 63 6f |is the u|se of co|
|000000c0| 6d 70 6c 65 78 20 64 61 | 74 61 20 74 79 70 65 73 |mplex da|ta types|
|000000d0| 2e 20 0a 57 68 69 6c 73 | 74 20 74 68 65 20 62 75 |. .Whils|t the bu|
|000000e0| 69 6c 74 2d 69 6e 20 74 | 79 70 65 73 2c 20 73 75 |ilt-in t|ypes, su|
|000000f0| 63 68 20 61 73 20 69 6e | 74 65 67 65 72 73 2c 20 |ch as in|tegers, |
|00000100| 72 65 61 6c 73 2c 20 76 | 65 63 74 6f 72 73 2c 20 |reals, v|ectors, |
|00000110| 61 6e 64 20 6d 61 74 72 | 69 63 65 73 2c 0a 75 73 |and matr|ices,.us|
|00000120| 75 61 6c 6c 79 20 73 75 | 66 66 69 63 65 20 69 6e |ually su|ffice in|
|00000130| 20 74 68 65 20 6f 74 68 | 65 72 20 61 72 65 61 73 | the oth|er areas|
|00000140| 2c 20 63 6f 6d 62 69 6e | 61 74 6f 72 69 61 6c 20 |, combin|atorial |
|00000150| 63 6f 6d 70 75 74 69 6e | 67 20 72 65 6c 69 65 73 |computin|g relies|
|00000160| 20 68 65 61 76 69 6c 79 | 20 0a 6f 6e 20 74 79 70 | heavily| .on typ|
|00000170| 65 73 20 6c 69 6b 65 20 | 73 74 61 63 6b 73 2c 20 |es like |stacks, |
|00000180| 71 75 65 75 65 73 2c 20 | 64 69 63 74 69 6f 6e 61 |queues, |dictiona|
|00000190| 72 69 65 73 2c 20 73 65 | 71 75 65 6e 63 65 73 2c |ries, se|quences,|
|000001a0| 20 73 6f 72 74 65 64 20 | 73 65 71 75 65 6e 63 65 | sorted |sequence|
|000001b0| 73 2c 20 0a 70 72 69 6f | 72 69 74 79 20 71 75 65 |s, .prio|rity que|
|000001c0| 75 65 73 2c 20 67 72 61 | 70 68 73 2c 20 70 6f 69 |ues, gra|phs, poi|
|000001d0| 6e 74 73 2c 20 73 65 67 | 6d 65 6e 74 73 2c 20 24 |nts, seg|ments, $|
|000001e0| 5c 6c 64 6f 74 73 24 0a | 49 6e 20 74 68 65 20 66 |\ldots$.|In the f|
|000001f0| 61 6c 6c 20 6f 66 20 31 | 39 38 38 2c 20 77 65 20 |all of 1|988, we |
|00000200| 73 74 61 72 74 65 64 20 | 61 20 70 72 6f 6a 65 63 |started |a projec|
|00000210| 74 20 28 63 61 6c 6c 65 | 64 20 7b 5c 62 66 20 4c |t (calle|d {\bf L|
|00000220| 45 44 41 7d 20 66 6f 72 | 20 4c 69 62 72 61 72 79 |EDA} for| Library|
|00000230| 20 6f 66 0a 45 66 66 69 | 63 69 65 6e 74 20 44 61 | of.Effi|cient Da|
|00000240| 74 61 20 74 79 70 65 73 | 20 61 6e 64 20 41 6c 67 |ta types| and Alg|
|00000250| 6f 72 69 74 68 6d 73 29 | 20 74 6f 20 62 75 69 6c |orithms)| to buil|
|00000260| 64 20 61 20 73 6d 61 6c | 6c 2c 20 62 75 74 20 67 |d a smal|l, but g|
|00000270| 72 6f 77 69 6e 67 20 6c | 69 62 72 61 72 79 20 0a |rowing l|ibrary .|
|00000280| 6f 66 20 64 61 74 61 20 | 74 79 70 65 73 20 61 6e |of data |types an|
|00000290| 64 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 69 6e 20 |d algori|thms in |
|000002a0| 61 20 66 6f 72 6d 20 77 | 68 69 63 68 20 61 6c 6c |a form w|hich all|
|000002b0| 6f 77 73 20 74 68 65 6d | 20 74 6f 20 62 65 20 75 |ows them| to be u|
|000002c0| 73 65 64 20 62 79 20 0a | 6e 6f 6e 2d 65 78 70 65 |sed by .|non-expe|
|000002d0| 72 74 73 2e 20 57 65 20 | 68 6f 70 65 20 74 68 61 |rts. We |hope tha|
|000002e0| 74 20 74 68 65 20 73 79 | 73 74 65 6d 20 77 69 6c |t the sy|stem wil|
|000002f0| 6c 20 6e 61 72 72 6f 77 | 20 74 68 65 20 67 61 70 |l narrow| the gap|
|00000300| 20 62 65 74 77 65 65 6e | 20 61 6c 67 6f 72 69 74 | between| algorit|
|00000310| 68 6d 73 0a 72 65 73 65 | 61 72 63 68 2c 20 74 65 |hms.rese|arch, te|
|00000320| 61 63 68 69 6e 67 2c 20 | 61 6e 64 20 69 6d 70 6c |aching, |and impl|
|00000330| 65 6d 65 6e 74 61 74 69 | 6f 6e 2e 20 54 68 65 20 |ementati|on. The |
|00000340| 6d 61 69 6e 20 66 65 61 | 74 75 72 65 73 20 6f 66 |main fea|tures of|
|00000350| 20 4c 45 44 41 20 61 72 | 65 3a 0a 0a 5c 62 65 67 | LEDA ar|e:..\beg|
|00000360| 69 6e 69 74 65 6d 0a 5c | 69 74 65 6d 7b 31 29 7d |initem.\|item{1)}|
|00000370| 20 20 0a 7b 41 20 63 6c | 65 61 72 20 73 65 70 61 | .{A cl|ear sepa|
|00000380| 72 61 74 69 6f 6e 20 62 | 65 74 77 65 65 6e 20 28 |ration b|etween (|
|00000390| 61 62 73 74 72 61 63 74 | 29 20 64 61 74 61 20 74 |abstract|) data t|
|000003a0| 79 70 65 73 20 61 6e 64 | 20 74 68 65 20 64 61 74 |ypes and| the dat|
|000003b0| 61 20 73 74 72 75 63 74 | 75 72 65 73 20 0a 75 73 |a struct|ures .us|
|000003c0| 65 64 20 74 6f 20 69 6d | 70 6c 65 6d 65 6e 74 20 |ed to im|plement |
|000003d0| 74 68 65 6d 2e 20 20 54 | 68 69 73 20 64 69 73 74 |them. T|his dist|
|000003e0| 69 6e 63 74 69 6f 6e 20 | 69 73 20 66 72 65 71 75 |inction |is frequ|
|000003f0| 65 6e 74 6c 79 20 6e 6f | 74 20 6d 61 64 65 20 69 |ently no|t made i|
|00000400| 6e 20 74 68 65 20 0a 63 | 6f 6d 62 69 6e 61 74 6f |n the .c|ombinato|
|00000410| 72 69 61 6c 20 61 6c 67 | 6f 72 69 74 68 6d 73 20 |rial alg|orithms |
|00000420| 6c 69 74 65 72 61 74 75 | 72 65 2c 20 62 75 74 20 |literatu|re, but |
|00000430| 69 73 20 63 72 75 63 69 | 61 6c 20 66 6f 72 20 61 |is cruci|al for a|
|00000440| 20 6c 69 62 72 61 72 79 | 2e 7d 0a 0a 5c 69 74 65 | library|.}..\ite|
|00000450| 6d 20 7b 32 29 7d 20 20 | 0a 7b 47 65 6e 65 72 69 |m {2)} |.{Generi|
|00000460| 63 20 64 61 74 61 20 74 | 79 70 65 73 3a 20 4d 6f |c data t|ypes: Mo|
|00000470| 73 74 20 6f 66 20 74 68 | 65 20 64 61 74 61 20 74 |st of th|e data t|
|00000480| 79 70 65 73 20 69 6e 20 | 4c 45 44 41 20 68 61 76 |ypes in |LEDA hav|
|00000490| 65 20 74 79 70 65 20 70 | 61 72 61 6d 65 74 65 72 |e type p|arameter|
|000004a0| 73 2e 0a 46 6f 72 20 65 | 78 61 6d 70 6c 65 2c 20 |s..For e|xample, |
|000004b0| 61 20 64 69 63 74 69 6f | 6e 61 72 79 20 68 61 73 |a dictio|nary has|
|000004c0| 20 61 20 6b 65 79 20 74 | 79 70 65 20 24 4b 24 20 | a key t|ype $K$ |
|000004d0| 61 6e 64 20 61 6e 20 69 | 6e 66 6f 72 6d 61 74 69 |and an i|nformati|
|000004e0| 6f 6e 0a 74 79 70 65 20 | 24 49 24 20 61 6e 64 20 |on.type |$I$ and |
|000004f0| 61 20 73 70 65 63 69 66 | 69 63 20 64 69 63 74 69 |a specif|ic dicti|
|00000500| 6f 6e 61 72 79 20 74 79 | 70 65 20 69 73 20 6f 62 |onary ty|pe is ob|
|00000510| 74 61 69 6e 65 64 20 62 | 79 20 73 65 74 74 69 6e |tained b|y settin|
|00000520| 67 2c 0a 73 61 79 2c 20 | 24 4b 24 20 74 6f 20 7b |g,.say, |$K$ to {|
|00000530| 5c 62 66 20 69 6e 74 7d | 20 61 6e 64 20 24 49 24 |\bf int}| and $I$|
|00000540| 20 74 6f 20 7b 5c 62 66 | 20 72 65 61 6c 7d 2e 20 | to {\bf| real}. |
|00000550| 7d 0a 0a 5c 69 74 65 6d | 7b 33 29 7d 20 0a 7b 4c |}..\item|{3)} .{L|
|00000560| 45 44 41 20 69 73 20 65 | 78 74 65 6e 64 69 62 6c |EDA is e|xtendibl|
|00000570| 65 3a 20 55 73 65 72 73 | 20 63 61 6e 20 69 6e 63 |e: Users| can inc|
|00000580| 6c 75 64 65 20 6f 77 6e | 20 64 61 74 61 20 74 79 |lude own| data ty|
|00000590| 70 65 73 20 65 69 74 68 | 65 72 20 62 79 20 69 6d |pes eith|er by im|
|000005a0| 70 6c 65 6d 65 6e 74 69 | 6e 67 0a 64 61 74 61 20 |plementi|ng.data |
|000005b0| 73 74 72 75 63 74 75 72 | 65 73 20 66 72 6f 6d 20 |structur|es from |
|000005c0| 73 63 72 61 74 63 68 20 | 69 6e 20 5c 43 43 20 20 |scratch |in \CC |
|000005d0| 6f 72 20 62 79 20 63 6f | 6d 62 69 6e 69 6e 67 20 |or by co|mbining |
|000005e0| 61 6c 72 65 61 64 79 20 | 65 78 69 73 74 69 6e 67 |already |existing|
|000005f0| 20 4c 45 44 41 20 0a 64 | 61 74 61 20 74 79 70 65 | LEDA .d|ata type|
|00000600| 73 2e 20 7d 0a 0a 5c 69 | 74 65 6d 7b 34 29 7d 20 |s. }..\i|tem{4)} |
|00000610| 0a 7b 45 61 73 65 20 6f | 66 20 75 73 65 3a 20 41 |.{Ease o|f use: A|
|00000620| 6c 6c 20 64 61 74 61 20 | 74 79 70 65 73 20 61 6e |ll data |types an|
|00000630| 64 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 61 72 65 |d algori|thms are|
|00000640| 20 70 72 65 63 6f 6d 70 | 69 6c 65 64 20 5c 43 43 | precomp|iled \CC|
|00000650| 20 6d 6f 64 75 6c 65 73 | 20 0a 77 68 69 63 68 20 | modules| .which |
|00000660| 63 61 6e 20 62 65 20 6c | 69 6e 6b 65 64 20 77 69 |can be l|inked wi|
|00000670| 74 68 20 61 70 70 6c 69 | 63 61 74 69 6f 6e 20 70 |th appli|cation p|
|00000680| 72 6f 67 72 61 6d 73 2e | 20 7d 0a 0a 5c 65 6e 64 |rograms.| }..\end|
|00000690| 69 74 65 6d 0a 0a 54 68 | 69 73 20 6d 61 6e 75 61 |item..Th|is manua|
|000006a0| 6c 20 63 6f 6e 74 61 69 | 6e 73 20 74 68 65 20 73 |l contai|ns the s|
|000006b0| 70 65 63 69 66 69 63 61 | 74 69 6f 6e 73 20 6f 66 |pecifica|tions of|
|000006c0| 20 61 6c 6c 20 64 61 74 | 61 20 74 79 70 65 73 20 | all dat|a types |
|000006d0| 61 6e 64 20 61 6c 67 6f | 72 69 74 68 6d 73 20 0a |and algo|rithms .|
|000006e0| 63 75 72 72 65 6e 74 6c | 79 20 61 76 61 69 6c 61 |currentl|y availa|
|000006f0| 62 6c 65 20 69 6e 20 4c | 45 44 41 2e 20 55 73 65 |ble in L|EDA. Use|
|00000700| 72 73 20 73 68 6f 75 6c | 64 20 62 65 20 66 61 6d |rs shoul|d be fam|
|00000710| 69 6c 69 61 72 20 77 69 | 74 68 20 74 68 65 20 5c |iliar wi|th the \|
|00000720| 43 43 20 0a 70 72 6f 67 | 72 61 6d 6d 69 6e 67 20 |CC .prog|ramming |
|00000730| 6c 61 6e 67 75 61 67 65 | 20 28 73 65 65 20 5b 53 |language| (see [S|
|00000740| 38 36 5d 20 6f 72 20 5b | 4c 38 39 5d 29 2e 20 54 |86] or [|L89]). T|
|00000750| 68 65 20 6d 61 69 6e 20 | 63 6f 6e 63 65 70 74 73 |he main |concepts|
|00000760| 20 61 6e 64 20 73 6f 6d | 65 20 0a 69 6d 70 6c 65 | and som|e .imple|
|00000770| 6d 65 6e 74 61 74 69 6f | 6e 20 64 65 74 61 69 6c |mentatio|n detail|
|00000780| 73 20 6f 66 20 4c 45 44 | 41 20 61 72 65 20 64 65 |s of LED|A are de|
|00000790| 73 63 72 69 62 65 64 20 | 69 6e 20 5b 4d 4e 38 39 |scribed |in [MN89|
|000007a0| 5d 2e 20 54 68 65 20 6d | 61 6e 75 61 6c 20 69 73 |]. The m|anual is|
|000007b0| 20 0a 73 74 72 75 63 74 | 75 72 65 64 20 61 73 20 | .struct|ured as |
|000007c0| 66 6f 6c 6c 6f 77 73 3a | 20 49 6e 20 63 68 61 70 |follows:| In chap|
|000007d0| 74 65 72 20 6f 6e 65 2c | 20 77 68 69 63 68 20 69 |ter one,| which i|
|000007e0| 73 20 61 20 70 72 65 72 | 65 71 75 69 73 69 74 65 |s a prer|equisite|
|000007f0| 20 66 6f 72 20 61 6c 6c | 0a 6f 74 68 65 72 20 63 | for all|.other c|
|00000800| 68 61 70 74 65 72 73 2c | 20 77 65 20 64 69 73 63 |hapters,| we disc|
|00000810| 75 73 73 20 74 68 65 20 | 62 61 73 69 63 20 63 6f |uss the |basic co|
|00000820| 6e 63 65 70 74 73 20 61 | 6e 64 20 6e 6f 74 61 74 |ncepts a|nd notat|
|00000830| 69 6f 6e 73 20 75 73 65 | 64 20 69 6e 20 4c 45 44 |ions use|d in LED|
|00000840| 41 2e 0a 54 68 65 20 6f | 74 68 65 72 20 63 68 61 |A..The o|ther cha|
|00000850| 70 74 65 72 73 20 64 65 | 66 69 6e 65 20 74 68 65 |pters de|fine the|
|00000860| 20 64 61 74 61 20 74 79 | 70 65 73 20 61 6e 64 20 | data ty|pes and |
|00000870| 61 6c 67 6f 72 69 74 68 | 6d 73 20 61 76 61 69 6c |algorith|ms avail|
|00000880| 61 62 6c 65 20 69 6e 0a | 4c 45 44 41 20 61 6e 64 |able in.|LEDA and|
|00000890| 20 67 69 76 65 20 65 78 | 61 6d 70 6c 65 73 20 6f | give ex|amples o|
|000008a0| 66 20 74 68 65 69 72 20 | 75 73 65 2e 20 54 68 65 |f their |use. The|
|000008b0| 73 65 20 63 68 61 70 74 | 65 72 73 20 63 61 6e 20 |se chapt|ers can |
|000008c0| 62 65 20 63 6f 6e 73 75 | 6c 74 65 64 0a 69 6e 64 |be consu|lted.ind|
|000008d0| 65 70 65 6e 64 65 6e 74 | 6c 79 20 66 72 6f 6d 20 |ependent|ly from |
|000008e0| 6f 6e 65 20 61 6e 6f 74 | 68 65 72 2e 0a 0a 5c 76 |one anot|her...\v|
|000008f0| 66 69 6c 6c 5c 65 6a 65 | 63 74 0a 0a 0a 5c 76 67 |fill\eje|ct...\vg|
|00000900| 6c 75 65 20 31 30 63 6d | 0a 5c 76 66 69 6c 6c 5c |lue 10cm|.\vfill\|
|00000910| 65 6a 65 63 74 0a | |eject. | |
+--------+-------------------------+-------------------------+--------+--------+
