Algoritmi

Mircea Sabău

Pentru o viață mai bună, mulți oameni muncesc din greu.
Dar, tot pentru o viață mai bună, efortul nostru cotidian
trebuie organizat și optimizat.

După o vacanță mai mult sau mai puțin însorită, a sosit momentul să reintrăm în tiparul activităților noastre. Și, cum orice activitate eficientă presupune un anumit grad de stereotipie logic organizată, vă invit în lumea algoritmilor. Colecția de algoritmi, pe care doresc să o prezint, concentrează coduri destinate problemelor de optimizare generală și combinatorică, a teoriei grafurilor, programării liniare, satisfacerii clauzelor precum și problemelor de criptare/decriptare, sortare, căutare rapidă. În cele ce urmează, voi încerca o grupare tematică a siturilor.

Biblioteci pentru optimizare generală

Serverul NEOS (Network-Enabled Optimization System)

http://www.mcs.anl.gov/home/otc/Server

Serverul NEOS folosește resurse de calcul și algoritmice pentru rezolvarea automată a problemelor de optimizare pe baza unui set minim de date furnizate de utilizatori. Aceștia își pot rezolva problemele de optimizare prin Internet, fără să descarce cod. Gama de probleme constă din optimizări cu și fără constrângeri, programare liniară și neliniară , programare liniară și stohastică, programare semidefinită și optimizări în rețea.Biblioteci de programe și algoritmi geneticiAceste programe sunt scrise în C sau C++ și oferă interfețe, tipuri de date și structuri orientate obiect, metode de selecție, mutații, scalări precum și numeroase exemple demonstrative. Ele sunt accesibile la adresele: ftp://info.mcs.anl.gov în /pub/pgapack/pgapack.tar.Z (PGAPack), Galib http://lancet.mit.edu/ga/, ftp://lancet.mit.edu/pub/ga/ (Galib) și ftp://FTP.TECHNION.AC.IL în /pub/supported/ie/bani (gp).

Calcul combinatoryic, grafuri Bond și sisteme cu evenimente discrete

LEDA

ftp://ftp.mpi-sb.mpg.de în /pub/LEDA

Este o bibliotecă de tipuri de date și algoritmi, destinată calculului combinatoric, scrisă în C++. Oferă specificații clare și precise pentru fiecare tip de date și algoritm (mulțimi Fibonacci pentru cozi cu prioritate, arbori red-black și tabele hash pentru dicționare etc.). Chiar dacă LEDA nu se află în domeniul public, poate fi utilizată gratuit în scopuri de cercetare și educaționale.

SSS

ftp://ftp.technion.ac.ilat /pub/supported/ie/bani

Este o bibliotecă de coduri C pentru simularea sistemelor cu evenimente discrete. Biblioteca permite construirea unor coduri de simulare voluminoase. Există aici numeroase fișiere demonstrative. De asemenea, biblioteca mai conține fișierul DA.EXE, un software destinat alegerii distribuției corespunzătoare pentru simulări.

20-SIM

http://www.rt.el.utwente.nl/20sim/clp.htm

Este un pachet de simulare bazat pe grafuri Bond, dotat cu notații fără domeniu pentru elemente și fluxuri de energie, util în domenii variate. De asemenea, sunt permise și semnale de control. În viitoarele versiuni, vor fi suportate și modele fizice ideale.

Programare liniară generalizată

Programare liniară prin metodele simplex, dual-simplex și barierei logaritmice

Implementări eficiente ale acestor metode pot fi găsite la http://ecoluinfo.unige.ch/~logilab/gondzio/ , sau http://ecoluinfo.unige.ch/~logilab/software/hopdm.html (HOPDM), ftp://ftp.uu.net sau ftp://ftp.sterling.com, în /usenet/comp .sources.misc/volume7 (minit) și ftp://orly1.snu.ac.kr/pub /sal_sw/lpako/ (LPAKO).

ILPS

http://ford.ieor.berkeley.edu/~ilan/project.html

Este un server WWW care permite utilizatorilor să-și rezolve problemele de programare liniară prin metodele simplex și dual simplex.

Metoda punctului interior

Aceste programe implementează metodele de punct interior (afină primară, afină duală, afină primară-duală, barierei și barierei primară-duală) în limbajul C și rulează pe stații IBM, Silicon Graphics, HP, Sun și platforme Dos sau altele cu compilatoare C. Le puteți găsi la adresele: ftp://elib.zib-berlin.de în /pub/optnet/soft ware/loqo /1.08 (LOQO) și ftp://orly1.snu.ac.kr/pub/sal_sw/lpabo (PLABO).

Instrumente Matlab

LIPSOL

http://math.umbc.edu/~yzhang/lipsol/
ftp://ftp.math.umbc.edu în /pub/zhang/lipsol/v0.3

Iubitorilor de Matlab le pot sugera o colecție de instrumente Matlab, destinată problemelor de programare liniară, și care oferă diverse metode de calcul și algoritmi. Rulează pe platforme DEC (Ultrix), SGI (IRIX 4.1 și 5.2) și Sun Sparc (SunOS 4.1.3).Programare generală cu numere întregiopbdp http://www.mpisb.mpg.de:/guide/staff/barth/barth.html, ftp://ftp.mpisb.mpg.de. Este o implementare în C++ a unui algoritm de enumerare pentru rezolvarea problemelor de optimizare liniară 0-1. Reprezintă o generalizare a algoritmului Davis-Putnam pentru rezolvarea problemelor de satisfacere propozițională în formă clauzală. Există aici și un fișier postscript mpii952002.ps care descrie tehnicile utilizate. Programul rulează pe platforme Unix.

Teoria grafurilor

În legătură cu teoria grafurilor, puteți găsi o adevărată colecție de programe și algoritmi despre teoria computațională a grupurilor, drumuri Hamiltoniene, enumerare parțială, ponderea maximă în grafuri neorientate, cardinalitate, trasare înapoi, arbori minimali, operații pe structuri de date arborescente dinamice și multe altele. Încercați adresele: ftp://dimacs.rutgers.edu in /pub/gap (GAP), ftp://netlib.att.com in /netlib/toms (GROW, HC, MSTPAC), ftp://dimacs.rutgers.edu în /pub/challenge/graph/contributed /pardalos (pardalos3, pardalos4), ftp://dimacs.rutgers.edu în /pub/dsj/clique (dfmax, dmclique), ftp://elib.zib-berlin.de în /pub/mathprog/matching/weighted (wmatch), ftp://elib.zib- berlin.de în /pub/mathprog/matching/card1 și /pub/mathprog /matching/card2 (match, cardmp), ftp://dimacs.rutgers.edu în /pub/netflow/matching/cardinality/solver-2 (cardmatch), ftp://dimacs.rutgers.edu în /pub/challenge/graph/contributed/mor genstern/morgenstern3 (color_loop) și ftp://dimacs.rutgers.edu în /pub/netflow/program_tools/dynamic_trees (dyn_tree).

Probleme de satisfacere

Acești algoritmi rezolvă problemele de decizie pentru testarea satisfacerii clauzelor și includ proceduri pentru selecția primului atom minimal, a unui atom în cele mai scurte clauze pozitive, a unui atom cu cele mai multe apariții, a unui atom cu cea mai mare pondere Jeroslow-Wang și proceduri de căutare în adâncime Davis-Putnam. Implementările acestor algoritmi pot fi accesate la adresele ftp://dimacs.rutgers.edu în /pub/challenge/sat/contributed/zhang (sato), ftp://ftp.cis.upenn.edu în /pub/freeman/posit-1.0.tar.Z (POSIT) și ftp://esda.inesc.pt/pub/users/jpms/soft/nsat/ (NSAT/GRASP).

Probleme de criptare/decriptare, codificare, căutare și sortare

Amatorilor de programare în C, le pot recomanda adresa http://www.dc.ee/Files/Programm.C, unde, pe lângă altele, vor putea găsi coduri sursă ce implementează algoritmii Uuencode/decode (UUXFER20 .ARJ), codificarea s pentru criptarea și decriptarea fișierelor (SCO DER.ARJ), sortarea Pigeon (PIGEONS.ARJ), criptarea/decriptarea DES rapidă (CDES.ARJ), căutarea extinsă Boyer-Moore (EXTBOY .ARJ) și alți algoritmi de manipulare a arborilor binari și red-black.

Concurs de programare ACM

http://www.cs.pub.ro/acm/

În final, aș dori să vă semnalez că, în perioada 17-18 octombrie 1997, la Universitatea Politehnică București se va desfășura faza regională a Concursului de Programare ACM, la care vor participa echipe din țările din zona de sud-est a Europei (Albania, Bulgaria, Croația, Grecia, Moldova, România, Slovenia, Turcia, Ucraina, și Iugoslavia). Concursul constă în rezolvarea unui set de probleme în timp limitat. ACM (Association for Computing Machinery, http://www.acm.org/), fondată în anul 1947, este o organizație științifică și educațională internațională ce are ca scop promovarea ingineriei, științelor, artelor și aplicațiilor pentru tehnologia informației la un înalt nivel etic și profesional, fiind una dintre cele mai vechi organizații de acest gen. În acest an, prima rundă a concursului de programare va începe cu întrecerile regionale în toate colțurile lumii, care se vor desfășura în perioada septembrie-noiembrie 1997. Câștigătorii concursurilor regionale vor ajunge în faza finală care se va desfășura în Atlanta, Georgia. Cei interesați de acest concurs pot obține informații de la dl. prof. Nicolae Țăpuș, coordonatorul principal al acestei faze regionale sau vizitând pagina Web indicată.


BYTE România - septembrie 1997


(C) Copyright Computer Press Agora