English - anglicky
Album  algoritmů a
technik
pro standardní Rexx
Vladimír Zábrodský
 
Idea, algoritmus, technika - to je také originální vamberecká krajka
 

 


Obsah Index Reflexio   Download Novinky Více hlav... Díky!

Album má dvoudimenzionální strukturu, která umožňuje procházet shromážděný materiál různými cestami. Obsah sdružuje do skupin algoritmy, které mají něco společného - nejčastěji řešený problém. Speciální skupinou jsou techniky - obecné, užitečné návody k dosažení určitého cíle: jak eliminovat rekurzi; jak napsat univerzální programovou jednotku; jak konstruovat testovací množiny ... Index je seznam algoritmů abecedně utříděný podle názvů programových jednotek (nejčastěji funkcí nebo podprogramů). Navíc, popis každého algoritmu je v části nazvané 'souvislosti' doplněn odkazy na související algoritmy nebo techniky. Album rozšiřují úvahy o programování, ty naleznete v části Reflexio

Červený špendlík  symbol pro novinku v Obsahu nebo Rejstříku nás upozorňuje na nové algoritmy. Zelený špendlík symbol pro změněné označuje změnu.

 


Programy, napsané v jazyce Rexx, jsou obvykle interpretovány a proto může jejich provedení trvat dlouho. Klíčem k rychlým skriptům je používání efektivních algoritmů. Za ta léta, co se o algoritmy zajímám, jsem si vytvořil celé malé album takových algoritmů. Věřte mi, není to jednoduchá úloha překládat do jazyka Rexx programy napsané původně v různých pseudokódech nebo programovacích jazycích jako jsou Ada, ALGOL, BASIC, C, FORTRAN, Modula, Pascal, PL/1.


'Nevýhodou je tu buď to, že neznáme včechny jazyky, nebo to, že nemáme jeden univerzální jazyk.'
Jules Verne Dvacet tisíc mil pod mořem  

Album je sestaveno jako referenční příručka algoritmů. Kód algoritmu stačí zvýraznit v prohlížeči a zkopírovat do editoru, přímo do konkrétního programu (podrobněji o tom hovořím v článku Technika: Univerzální programová jednotka). POZOR! Prosím, vidíte-li následující fragment programu zapsaný na dvou řádcích, musíte zmenšit velikost fontu ve vašem prohlížeči (díky za upozornění patří Dougu Rickmanovi doug@hotrocks.msfc.nasa.gov z NASA).


  do J = K - 1 to 1 by -1; SubSet = A.J SubSet; end

Po té, co si stáhnete album (viz download), můžete změnit vlastnosti písma úpravou souboru AATSTYLE.CSS.

Album může být užitečné při výuce algoritmů nebo jazyka Rexx. V jednom směru je velkým experimentem: používá jazyk Rexx nejen pro zápis programů, ale i pro popis a vysvětlení algoritmů. Proto se v něm dočtete, že "časová složitost je FORMAT(3*N/2-2,,0) porovnání" nebo "vzorek P. se vyskytuje s posunutím S v textu T., když 0<=S<=N-M a T.SpJ=P.J, kde SpJ označuje S+J, pro J=1,...,M". Výsledek ukazuje, že jazyk Rexx je vhodný nástroj k představení užitečných algoritmů, převzatých z různých pramenů, v jasné, stručné a jednotné formě.

Poznámka: V celém dalším textu rezervujeme symbol lgN pro označení dvojkového logaritmu čísla N.

 



7. července 2014
Felix Hofmann optimalizoval funkci NCOM.


17. září 2001
Zkrácené vyhodnocování AND, OR v Rexxu?


12. září 2001
Testovací prostředí Waltera Pachla ...


24. srpna 2001
Dokončil jsem přepsání a opravy celého alba.


3. srpna 2001
Nové řešení 3_1 do kapitoly Technika: Univerzální jednotka přidal Tobias Herp


28. července 2001
Offline verze mých stránek o jazyku Rexx a Alba algoritmů a technik byla přidána k CD OS2.cz jako freeware


1. červenec 2001 P+n trik Waltera Pachla přidán do Reflexio


18. června 2001
Na radu Waltera Pachla jsem opravil poslední číslice v hodnotě proměné V ve funkcích LN2 a PICONST.


12. březen 2001
Funkce pro výpočet obsahu trojúhelníka numericky nestabilní (HERON) a numericky stabilní (ATRIAN) metodou.


4. březen 2001
Po přečtení Kahanova eseje Matematika psaná v písku jsem změnil funkci REPOWER:

if P = "" then P = 9; P = P + 4; numeric digits P

Podrobněji Reflexio.

22. únor 2001
Danny De Wilde mě požádal o radu jak výpočítat obecnou mocninu, tedy hodnotu výrazu X**Z pro X, Z reálná čísla. To mě inspirovalo k vytvoření funkce REPOWER

1. prosinec 2003
James Barbetti mi poslal podprogram HEAPSORT_RADIX3 původně ve Visual Basicu.

 


Album jako ZIP soubor

Album algoritmů a technik pro standardní Rexx si můžete stáhnout jako ZIP soubor; sbaleno utilitou ZIP. Tato verze je z 15. července 2014, velikost 268kB.
     Protože součástí popisu algoritmů je i jejich porovnání, uvažte, že jsem použil REXX-Regina_0_08g 4.80 31 Jul 1999, od 12. srpna 2000 pak REXX-Regina_2.0 4.80 4 May 2000, od 26. června 2001 konečně REXX-Regina_2.2 4.80 17 Jun 2001 interpret Marka Hesslinga, Microsoft Windows 98 4.10.1998, PC s Cyrix 6x86MX procesorem a 32MB RAM.



 

Felix Hofmann optimalizoval funkci NCOMB.

Roderic A. Davis, New York http://freepages.genealogy.rootsweb.ancestry.com/~dav4is/ODTs/index.html#TOP
funkce D2R

Tobias Herp, Bad Homburg, Německo
přidal další řešení 3_1 do kapitoly Technika: Univerzální jednotka

Walter Pachl, Vídeň, Rakousko
Testovací prostředí a jeho P+n trik v Reflexio


Doug Rickman, Global Hydrology and Climate Center, MSFC, NASA
funkce SPLINE, SPLINT

Gerard Schildberger, Hankinson, Severní Dakota
funkce CEILING, FLOOR

James Barbetti
mi poslal modifikaci podprogramu HEAPSORT. Viz HEAPSORT_RADIX3

 



 

Michael Adams, Cologne, Německo
opravil podprogram PRIMES a upozornil na chybu ve funkci PRIMALITY_TEST

Walter Pachl, Vídeň, Rakousko
našel chyby v kódu funkce LN2 a PICONST. Prostudoval postupně celé album - 78 stránek! -, ověřil funkčnost programů v prostředí OS/2. Našel chybu v podprogramu HEAPSORT; zpřesnil obecnou definici problému nalezení k-tého nejmenšího prvku; opravil některé další chyby. Waltrovy maily mě přivedli na myšlenku projít si a přepsat kompletně celé album (červen - srpen 2001).

George W. Perry Flintstone, Georgia George Perry's Home Page
upozornil na chybu v INTERPOLATION_SEARCH

Gerard Schildberger, Hankinson, Severní Dakota
zjednodušil funkce PI a SQRT a upozornil na chybu ve funkci LN10. Chtěl bych poděkovat Gerardovi za to, že opravil řadu chyb ve více než 50ti(!) stránkách alba.

Danny De Wilde, Belgie
inspiroval mě k vytvoření funkce REPOWER

 



 

Baudoin C., Meyer B., Méthodes de programmation
Edition Eyrolles 61, Bd Saint-Germain Paris 1978

Bentley J., Programming Pearls
CACM, December 1986, Vol. 29, No. 12, p. 1161

Bentley J., Programming Pearls - A Sample of Brilliance
CACM September 1987 No. 9, p. 754-757

Bentley J., More Programming Pearls - Confession of a Coder
Addison-Wesley, 1990

Bird R. S., Notes on Recursion Elimination
CACM, June 1977, vol. 20, No. 6, pp. 434-439.

Brent R. P., Ramanujan and Euler's Constant
Computer Sciences Laboratory, Australian National University, August 1993

Cormen T. H., Leiserson Ch. E., Rivest R. L., Introduction to Algorithms
The MIT Press, Cambridge, 1990

Durstenfeld R., Random Permutation
CACM July 1964 No. 7, p. 420

Faddejev A.K., Sominskij J.S. Sbornik zadač po vyššej algebre
Nauka, Moskva 1964

Feuer A.R., Gehani N. (ed.) Comparing and Assessing Programming Languages Ada, C and Pascal
Prentice-Hall, Inc. Englewood Cliffs, New Jersey 1984

Fiala E.R., Greene D.H., Data Compression with Finite Windows
CACM, April 1989, Vol. 32, No. 4, pp. 490-505

Floyd R. W., Rivest R. L., Algorithm 489 The Algorithm SELECT - for Finding the ith Smallest of n Elements [M1]
CACM, March 1975, Vol. 18, No. 3, p. 173

Floyd R. W., Rivest R. L., Expected Time Bounds for Selection
CACM, March 1975, Vol. 18, No. 3, pp. 165-172

Gehani N., Ada - An Advanced Introduction
Prentice-Hall, Inc. Englewood Cliffs, New Jersey 1983

Jarník V., Diferenciální počet I
- Nakladatelství České Akademie Věd, Praha, 1963

Kahan W., Mathematics Written in Sand
Version of 22 Nov. 1983.
        http://www.cs.berkeley.edu/~wkahan/MathSand.pdf

Knuth D. E., Fundamental Algorithms, vol. 1 of The Art of Computer Programming
- 2nd ed. Addison-Wesley, 1973

Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973

Knuth D. E., Sorting and Searching, vol. 3 of The Art of Computer Programming
Addison-Wesley, 1973

Kruse R. L., Data Structures and Program Design
Prentice Hall International Editions, ISBN 0-13-196049-0

Lipski W., Kombinatoryka dla Programistow
Wydawnictwa Naukowo-techniczne, Warszawa, 1982

Martello S., Toth P., Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990

Park S. K., Miller K. W., Random Number Generators: Good ones are hard to find
CACM October 1988 Vol. 31 No. 10, pp. 1192-1201

Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical Recipes in C : the art of scientific computing
- 2nd ed. University Press, Cambridge, 1992

Rich R. P., Internal Sorting Methods Illustrated with PL/1 Programs
Prentice Hall, Inc., Engelwood Cliffs, 1972

Sedgewick R., Algorithms
Addison-Wesley, Reading, Massachusetts, 1984

Wirth N., Systematisches Programmieren
- 2nd ed. B.G Teubner, Stuttgart, 1975

Wirth N., Algorithms and data structure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986

Zábrodský V., Variace na klasické téma
Elektronika, c. 6, 1992, 33-34

Zábrodský V., Problém dvou loupežníků
BAJT, říjen 1993 (36), 134-136


Kam dál ... hlavní stránka english

od 1. ledna 2000, naposledy změněno 10. dubna 2015
Copyright © 2000-2015 Vladimír Zábrodský, RNDr.