Portal:Informatică

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare


modificare 

Portal Informatică

Acest portal dorește să reunească articolele despre informatică, tehnologia informației, știința calculatoarelor și toate domeniile adiacente.

Coordonarea articolelor din acest domeniu se face la Proiect:Informatică.
modificare 

Articolul zilei

În matematică, algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a descris în Cărțile VII și X din Elementele.

CMMDC a două numere este cel mai mare număr care le divide pe ambele. Algoritmul lui Euclid exploatează observația că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 și 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 și 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând pașii algoritmului lui Euclid, CMMDC se poate exprima sub formă de suma celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252. Această proprietate importantă se numește identitatea lui Bézout.

Prima descriere rămasă a algoritmului lui Euclid este lucrarea lui Euclid intitulată Elementele (c. 300 î.e.n.), fiind unul dintre cei mai vechi algoritmi numerici încă utilizați. Algoritmul original a fost descris doar pentru numere naturale și lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea și la alte tipuri de numere, cum ar fi întregii Gaussieni și polinoamele de o variabilă. Aceasta a dus la noțiuni moderne de algebră abstractă, cum ar fi inelele euclidiene. Algoritmul lui Euclid s-a generalizat și pentru alte structuri matematice, cum ar fi nodurile și polinoamele multivariate.

Algoritmul lui Euclid are numeroase aplicații practice și teoretice. Este un element cheie al algoritmului RSA, o metodă de criptare cu chei publice des folosită în comerțul electronic. Este utilizat pentru a rezolva ecuațiile diofantice, cum ar fi calcularea numerelor care satisfac mai multe congruențe (Teorema chinezească a resturilor) sau inversul multiplicativ al unui corp. Algoritmul lui Euclid poate fi utilizat pentru a construi fracții continue, în metoda lanțului Sturm pentru găsirea rădăcinilor reale ale unui polinom, și în mai mulți algoritmi moderni de factorizare a întregilor. În fine, este o unealtă de bază pentru demonstrarea unor teoreme din teoria modernă a numerelor, cum ar fi teorema celor patru pătrate a lui Lagrange și teorema fundamentală a aritmeticii (factorizarea unică).

Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată un număr de pași mai mare decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg. Gabriel Lamé a demonstrat aceasta în 1844, marcând începutul teoriei complexității computaționale. În secolul al XX-lea s-au dezvoltat metode de îmbunătățire ale eficienței algoritmului.

modificare 

Imaginea zilei

modificare 

Articole selectate

Nuvola apps bookcase.png
Limbaje de programare:

ActionScript, BASIC, C, C++, C#, CLIPS, Cobol, Fortran, Haskell, Java, JavaScript, LISP, MIVA SCRIPT, PHP, Pascal, Perl, Prolog, Python, Ruby, Scriptol, Tcl/TK, Verilog, VHDL.

Nuvola apps kdmconfig.png
Personalități:

Eric Allman, Bill Gates, Steve Jobs, Donald E. Knuth, Dennis Ritchie, Andrew Tanenbaum, Linus Torvalds, Niklaus Wirth.

Nuvola apps hwinfo.png
Hardware:

Disc dur, Macintosh, Maus, Memorie cu acces aleator, Modem, Monitor, PC, Periferic, Tastatură.

Nuvola apps kalzium.png
Organisme

ApacheBSAFundația MozillaFSFICANNIEEEIETFISOUnicodeW3C.

Nuvola mimetypes binary.png
Software:

3D Studio MaxBlenderFirefoxFlashGimpGNOMEInternet ExploreriTunesKDEMicrosoft OfficeMozillaMPlayerOpenOffice.orgOperaPhotoshopVisual StudioWinampWindowsSisteme de operare, .

Wikibooks-logo.png
Wikibooks
modificare 

Categorii

modificare 

Știați că...

... Donald Knuth nu mai utilizează e-mail-ul de peste 15 ani?

... primul program scris de Bill Gates a fost X și 0?

... o adresă IPv6 este stocată pe 128 de biți?


modificare 

Asociația Wikimedia

modificare 

Alte portaluri

Curăță memoria cache