Algoritmi
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)
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
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
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
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
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
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
Î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. , coordonatorul principal al acestei faze regionale sau vizitând
pagina Web indicată.