Algoritmul matematică

Algoritm, procedură sistematică care produce - într-un număr finit de pași - răspunsul la o întrebare sau soluția unei probleme. Numele derivă din traducerea latină, Algoritmi de numero Indorum, din tratatul aritmetic al matematicianului musulman al secolului al IX-lea al-Khwarizmi „Al-Khwarizmi referitor la arta hindusă a socoteala”.

informatică: algoritmi și complexitate

Un algoritm este o procedură specifică pentru rezolvarea unei probleme de calcul bine definite. Dezvoltarea și analiza algoritmilor este fundamentală

Pentru întrebări sau probleme cu doar un set fin de cazuri sau valori, există întotdeauna un algoritm (cel puțin în principiu); este format dintr-un tabel cu valorile răspunsurilor. În general, nu este o procedură atât de banală să răspunzi la întrebări sau probleme care au un număr infinit de cazuri sau valori de luat în considerare, cum ar fi „Este numărul natural (1, 2, 3 …) un prim?” sau „Care este cel mai mare divizor comun al numerelor naturale a și b?” Prima dintre aceste întrebări aparține unei clase numite hotărâtoare; un algoritm care produce un răspuns da sau nu se numește procedura de decizie. A doua întrebare aparține unei clase numite computabile; un algoritm care duce la un răspuns la un număr specific se numește procedură de calcul.

Algoritmi există pentru multe astfel de clase infinite de întrebări; Elementele lui Euclid, publicate aproximativ 300 BC, conțineau unul pentru găsirea celui mai mare divizor comun cu două numere naturale. Fiecare elev din școala elementară este găurit în diviziune lungă, ceea ce reprezintă un algoritm pentru întrebarea „La împărțirea unui număr natural a la un alt număr natural b, care sunt coeficientul și restul?” Utilizarea acestei proceduri de calcul duce la răspunsul la întrebarea hotărâtă „Împparte b?” (răspunsul este da, dacă restul este zero). Aplicarea repetată a acestor algoritmi produce în cele din urmă răspunsul la întrebarea hotărâtă „Este un prim?” (răspunsul este nu dacă a este divizibil cu un număr natural mai mic în afară de 1).

Uneori nu poate exista un algoritm pentru rezolvarea unei clase infinite de probleme, în special atunci când se face o altă restricție la metoda acceptată. De exemplu, două probleme din vremea lui Euclid care necesitau doar o busolă și o dreaptă (riglă nemarcată) - vizionarea unui unghi și construirea unui pătrat cu o suprafață egală cu un cerc dat - au fost urmărite timp de secole înainte ca acestea să fie dovedite imposibile. La sfârșitul secolului XX, influentul matematician german David Hilbert a propus 23 de probleme pentru matematicieni să rezolve în secolul viitor. A doua problemă din lista sa a cerut o investigare a coerenței axiomelor aritmeticii. Cei mai mulți matematicieni au avut puține îndoieli despre atingerea acestui obiectiv până în 1931, când logicianul originar din Austria, Kurt Gödel, a demonstrat rezultatul surprinzător că trebuie să existe propuneri sau întrebări aritmetice care nu pot fi dovedite sau respinse. În esență, orice astfel de propunere duce la o procedură de determinare care nu se termină niciodată (o condiție cunoscută sub numele de problema de oprire). În efortul eșuat de a stabili cel puțin propunerile care sunt de nerezolvat, matematicianul și logicianul englez Alan Turing au definit cu rigurozitate conceptul slab înțeles al unui algoritm. Deși Turing a sfârșit dovedind că trebuie să existe propuneri nedecidibile, descrierea sa a caracteristicilor esențiale ale oricărei mașini cu algoritm cu scop general sau mașină Turing, a devenit fundamentul științei computerizate. Astăzi problemele de determinabilitate și computabilitate sunt centrale pentru proiectarea unui program de calculator - un tip special de algoritm.