Algorisme

Un algorisme és una estratègia que s’utilitza per resoldre un problema i consisteix en una seqüència finita d’operacions (també anomenades instruccions), que permet resoldre totes les preguntes de la mateixa classe. Ha de ser:

finit, és a dir, quan consta d’un nombre finit d’instruccions i té un final;
determinista, és a dir, a partir de les mateixes dades d' entrada , s'obtenen els mateixos resultats de sortida;
sense ambigüitats, les operacions han de poder ser interpretades de la mateixa manera per tothom encara que l'executor sigui diferent;
general, és a dir, quan la solució és la mateixa per a tots els problemes de la mateixa classe.

El terme deriva de la transcripció llatina del nom del matemàtic persa al-Khwarizmi , ^{[1] que va} viure al segle IX dC , que es considera un dels primers autors que es va referir a aquest concepte quan va escriure el llibre Restauració i reducció regles .

Les primeres nocions d’algoritme es troben en documents que es remunten al segle XVII aC , coneguts com a papirs d’ Ahmes , que contenen una col·lecció de problemes amb la seva solució, inclòs un problema de multiplicació que l’escriptor afirma haver copiat d’altres papirs anteriors als dotze segles. .

L’algorisme és un concepte fonamental d’ informàtica , en primer lloc perquè és la base de la noció teòrica de computabilitat : es pot calcular un problema quan es pot resoldre mitjançant un algorisme. A més, l'algorisme és un concepte clau fins i tot en la fase de programació del desenvolupament de programari : prenent un problema per automatitzar-se , la programació constitueix essencialment la traducció o codificació d'un algorisme per a aquest problema en un programa , escrit en un idioma determinat, que pot per tant, serà executat eficaçment per un ordinador representant la seva lògica de processament .

Definició

Al segle XX , el concepte d'algorisme es va formalitzar per resoldre el problema matemàtic de "decisió" ( Entscheidungsproblem ), plantejat per David Hilbert el 1928, i altres formalitzacions posteriors van venir amb el desenvolupament dels conceptes de " computabilitat efectiva " ^[2] i de "mètode efectiu" ^[3] . Les formalitzacions matemàtiques més famoses són les funcions recursives de Gödel - Herbrand - Kleene de 1930, 1934 i 1935; El càlcul lambda d' Alonzo Church i la formulació 1 d' Emil Post del 1936; i, finalment, la màquina de Turing de 1936–37 i 1939. Malgrat això, encara falta una definició del concepte d’algoritme formal i no tècnica ^[4] i, per tant, es veu obligat a conformar-se amb la idea intuïtiva de Algorisme com "una seqüència ordenada i finita de passos elementals (operacions o instruccions) que condueix a un resultat ben determinat en un temps finit".

Models formals

Representació gràfica de l'algorisme Quicksort

El mateix tema en detall: teoria de la computabilitat § Què és un algorisme .

La definició d’algoritme que s’acaba d’informar és força informal, mentre que era necessari tenir una definició més rigorosa per tractar el concepte d’algoritme amb eines matemàtiques. Per a això, s’han definit alguns models d’ algoritmes matemàtics , entre els quals un dels més famosos és la màquina de Turing . Representa una mena d’ ordinador ideal equipat amb un programa per executar-lo, però, en comparació amb un ordinador real, la màquina de Turing té un funcionament extremadament més senzill que es pot descriure fàcilment amb termes matemàtics, fent ús de conceptes com ara conjunt , relació i funció .

La màquina de Von Neumann , que és el model arquitectònic primitiu de tots els ordinadors actuals, és equivalent, en termes de potència de càlcul, a la màquina de Turing. Dit d'una altra manera, s'ha demostrat que un determinat problema pot ser resolt per un ordinador (adequadament programat) si i només si també pot ser resolt per una màquina de Turing. A més de la màquina de Turing, proposada per Alan Turing el 1936 , en el mateix període altres matemàtics van desenvolupar diverses representacions formals del concepte d’algorisme, entre les quals recordem, per exemple, el càlcul lambda . Al cap d’uns anys, va sorgir que tots aquests models eren equivalents: els problemes que podia resoldre una màquina de Turing eren els mateixos que podia resoldre una màquina de von Neumann i també els mateixos que podrien resoldre una funció construïda amb càlcul lambda ^{[ sense font ]} .

Entre altres coses, d’aquests resultats va sorgir la tesi Church-Turing , que afirma que qualsevol algorisme es pot modelar amb una màquina de Turing. En altres paraules, aquesta tesi argumenta que és essencialment impossible intentar imaginar un model d'algoritme més potent i, en conseqüència, que cap màquina mai podrà resoldre problemes que una màquina de Turing no pot resoldre en principi. Aquest no és un teorema demostrat matemàticament, ja que la tesi estableix la igualtat de dos conceptes, l'algorisme i la màquina de Turing, però el primer no té una definició formal. La tesi ara es comparteix generalment, tot i que, de vegades, els avenços en la investigació en el camp de la hipercomputació semblen posar-ho en dubte.

Propietats fonamentals dels algorismes

A partir de la definició anterior d’algorisme podem deduir algunes propietats necessàries, sense les quals no es pot definir un algorisme com a tal:

els passos constitutius han de ser "elementals", és a dir, no es poden desglossar ( atomicitat );
els passos constitutius han de ser interpretables de manera directa i unívoca per l' executor , ja sigui humà o artificial ( sense ambigüitats );
l'algorisme ha d'estar compost per un nombre finit de passos i requereix una quantitat finita de dades d'entrada ( finitud )
l'execució ha de finalitzar després d'un temps finit ( finalització );
l'execució ha de donar lloc a un resultat únic ( efectivitat ).

Exemple de diagrama de flux d'un algorisme de mètode Dit, fet!

Així, per exemple, "trencar els ous" es pot considerar legítimament un pas elemental d'un "algorisme de cocció" (recepta), però "afegir prou sal" no ho podria ser, ja que l'expressió "prou" és ambigua i ho fa no indiqui amb precisió quins passos calen per determinar la quantitat necessària. No es pot considerar legítim un pas com "preparar una paella de flam" perquè es pot desglossar en suboperacions (encendre el foc, ajustar la flama, posar la paella a l'estufa, etc.) i també perquè conté ambigüitats (no especifica quant de gran ha de ser el cassó, quant s’ha d’omplir de nata, etc.). Al contrari, "continuar remenant a foc fort fins que el compost agafi un color marró" és una instrucció iterativa acceptable, que implica un nombre finit d'operacions (agitades) tot i que aquest nombre no es coneix a priori, perquè depèn del que sigui anomenada entrada (el grau d’humitat de la farina a la barreja, la força de la flama, etc.).

No obstant això, la instrucció no elemental per preparar la crema es podria associar a una referència adequada a una altra secció del llibre de receptes, que proporciona un subalgorisme específic per a aquesta operació específica. Això suggereix que, per facilitar la seva implementació, els algorismes poden ser modulars , és a dir, orientats a resoldre subproblemes específics i organitzats jeràrquicament . A més, una recepta que inclou la cuina al microones no pot ser preparada per un intèrpret sense l'aparell adequat; això fa referència al problema de la viabilitat dels algoritmes o de la seva compatibilitat amb els recursos materials i temporals disponibles. Finalment, pot haver-hi diversos algoritmes vàlids per resoldre el mateix problema, però cadascun amb un grau d’ eficiència diferent.

Generalment, l'algorisme es descriu com un "procés de resolució de problemes". En aquest context, els "problemes" considerats es caracteritzen gairebé sempre per dades d' entrada variables, sobre les quals operarà el propi algorisme per arribar a la solució. Per exemple, el càlcul del màxim comú divisor de dos nombres és un exemple de "problema", i les seves dades d'entrada , que varien de tant en tant, són els dos nombres en qüestió. Per a un no matemàtic, això podria aparèixer com una "família de problemes" (el problema de calcular el màxim divisor comú entre 10 i 15, el problema de calcular-lo entre 40 i 60, entre 35 i 95, etc.). El matemàtic i l'informàtic identifiquen amb la paraula "problema" tota la família i amb "instància" o "x" cadascuna de les preguntes específiques obtingudes fixant dos valors particulars. Tenint en compte aquesta premissa, un algorisme resol un problema si per a qualsevol instància del problema en un temps finit produeix la solució desitjada, o un determinat resultat o dades de sortida ( sortida ) a partir de les dades d' entrada ( entrada ).

Si aquesta idea ja tenia una certa importància per al càlcul matemàtic, l’aparició de la informàtica l’ha enriquit amb una nova importància, i és de fet amb la informàtica que s’ha començat a estendre el terme “algorisme”. De fet, si per obtenir un resultat determinat (resoldre un determinat problema) hi ha un procediment infal·lible, que es pot descriure sense ambigüitats fins als detalls, i sempre condueix a l’objectiu desitjat en un temps finit, existeixen les condicions per confiar-ho tasca a un ordinador , simplement introduint l'algorisme en qüestió en un programa escrit en un llenguatge adequat que la màquina pugui entendre.

Un algorisme es pot descriure inicialment mitjançant l’ús d’un diagrama de flux o mitjançant un pseudocodi . Posteriorment, en la fase de programació , l'algorisme així escrit serà traduït al llenguatge de programació per un programador en forma de codi font, donant vida al programa que executarà l'ordinador, possiblement després d'una nova traducció al llenguatge màquina . El teorema de Böhm-Jacopini assumeix una rellevància teòrica particular en aquest context, que afirma que qualsevol algorisme es pot implementar utilitzant només tres estructures, la seqüència , la selecció i el bucle ( iteració ), que s’aplicaran recursivament a la composició d’ instruccions elementals. A la pràctica actual, el programador professional en el seu treball realitza automàticament aquest procés de traducció escrivint directament el codi font necessari en les modalitats esmentades, ja que ha trobat la solució al problema donat.

Enfocament matemàtic

Hi ha nombrosos models matemàtics d'algorisme. En general, un algorisme rep un conjunt de valors (dades) en entrada i en genera un en sortida (anomenada solució). Per tant, donat un algorisme A, la funció que associa la sortida corresponent a cada entrada x d'A es denota per f _A.

Aquesta correspondència entre entrada i sortida no és el problema resolt per l'algorisme. Formalment, un problema és una funció $f(D_{i})\to D_{s}$ ${\ displaystyle f (D_ {i}) \ a D_ {s}}$ $f (D_ {i}) \ a D_ {s}$ definit en un conjunt D _i d’elements que anomenarem restances, a valors en un conjunt D _s de resolucions.

L'estudi d'un algorisme es divideix en dues fases:

síntesi (també anomenada disseny o projecte): donat un problema A, creeu un algorisme f per resoldre A, és a dir, tal que f = f _a .
anàlisi: donat un algorisme f i un problema A, demostreu que f resol A, és a dir, f = f _a ( correcció ) i avalueu la quantitat de recursos utilitzats per f ( complexitat concreta ).

Formalització d’un problema

A cada problema $\Pi$ ${\ displaystyle \ Pi}$ $\ Pi$ tenim això: $f\pi :D\pi \rightarrow S\pi$ ${\ displaystyle f \ pi: D \ pi \ rightarrow S \ pi}$ $f \ pi: D \ pi \ rightarrow S \ pi$ on és $D\pi$ ${\ displaystyle D \ pi}$ $D \ pi$ són els casos del problema e $S\pi$ ${\ displaystyle S \ pi}$ $S \ pi$ són les solucions i $\forall x\in D\pi :f\pi (x)$ ${\ displaystyle \ forall x \ in D \ pi: f \ pi (x)}$ $\ forall x \ in D \ pi: f \ pi (x)$ és una solució al problema per exemple x.

Estudi de la complexitat computacional d’un algorisme

El mateix tema en detall: teoria de la complexitat computacional .

Una gran part de la teoria d'algoritmes és l'estudi de la complexitat, computacional i espacial. En altres paraules, volem saber, a mesura que augmenta la complexitat del problema, com augmenta el temps necessari per executar l'algorisme i l'espai de memòria ocupat en un ordinador.

La complexitat d’un algorisme es mesura de forma asimptòtica. Hi ha quatre mètodes per calcular la complexitat d’un algorisme:

mètode de substitució
mètode d'iteració
mètode d'arbre
mètode expert

Es defineix asintòtic per dos motius

ja que cada ordinador pot implementar algoritmes de manera diferent, no es pot estimar el temps precís
volem donar una idea quantitativa de com l'algorisme pot créixer en el consum de temps a mesura que augmenta l'entrada, per obtenir valors cada vegada més grans.

Prenent una funció associada a un algorisme del tipus:

$\phi ALG:\mathrm {InALG} \rightarrow \mathrm {OutALG}$ ${\ displaystyle \ phi ALG: \ mathrm {InALG} \ rightarrow \ mathrm {OutALG}}$ $\ phi ALG: {\ mathrm {InALG}} \ rightarrow {\ mathrm {OutALG}}$

podeu definir la funció de pes com a

$\mathrm {WALG} :\mathrm {InALG} \rightarrow \mathbb {N}$ ${\ displaystyle \ mathrm {WALG}: \ mathrm {InALG} \ rightarrow \ mathbb {N}}$ ${\ mathrm {WALG}}: {\ mathrm {InALG}} \ rightarrow {\ mathbb {N}}$

que expressa la mida de les dades d’entrada, és a dir, el nombre de bits que s’utilitzen per codificar les dades d’entrada a l’algorisme. Per exemple, en un vector la longitud del mateix determinarà el nombre de bits necessaris per codificar-lo i en les matrius el nombre de l'ordre, és a dir, prenent per exemple una matriu quadrada l'ordre del mateix està determinat per un dels dos dimensions (horitzontals o verticals).

La complexitat d'un algorisme es defineix com:

$\mathrm {TALG} :\mathbb {N} \rightarrow \mathbb {N}$ ${\ displaystyle \ mathrm {TALG}: \ mathbb {N} \ rightarrow \ mathbb {N}}$ ${\ mathrm {TALG}}: {\ mathbb {N}} \ rightarrow {\ mathbb {N}}$ que indica per a cada valor enter n (és a dir, la mida del problema) la quantitat de temps i / o espai que utilitza l'algorisme per processar dades de mida n. Un algorisme es pot comportar de manera significativa de manera diferent fins i tot en casos que tinguin la mateixa mida (és a dir, el mateix pes).

Es demostra que la complexitat d'un algorisme és una funció estrictament creixent, per a la qual manté $\lim _{n\rightarrow \infty }T(x)=\infty$ ${\ displaystyle \ lim _ {n \ rightarrow \ infty} T (x) = \ infty}$ $\ lim _ {{n \ rightarrow \ infty}} T (x) = \ infty$

De fet, és trivial demostrar-ho $S_{a}(x)$ ${\ displaystyle S_ {a} (x)}$ $S_ {a} (x)$ tendeix a l'infinit a mesura que creix $x$ ${\ displaystyle x}$ $x$ (és a dir, el nombre de dades a processar), perquè es redueix en $x$ ${\ displaystyle x}$ $x$ (és un $o(x)$ ${\ displaystyle o (x)}$ $o (x)$ ) ja que el nombre mínim d’espais de memòria per emmagatzemar un conjunt de dades és la seva cardinalitat . Tingueu en compte que per a matrius disperses, cal considerar elements no nuls com el nombre de dades .

Dues mesures per als sistemes de càlcul seqüencial són els valors $T_{a}(x)$ ${\ displaystyle T_ {a} (x)}$ $T_ {a} (x)$ I $S_{a}(x)$ ${\ displaystyle S_ {a} (x)}$ $S_ {a} (x)$ que representen respectivament el temps i l’espai de memòria requerits per un algorisme $a$ ${\ displaystyle a}$ $a$ a l'entrada $x\in X$ ${\ displaystyle x \ a X}$ $x \ en X$ . Per a la propietat esmentada el domini $X$ ${\ displaystyle X}$ $X$ per tant, ha de coincidir amb el conjunt $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ . Per tant, podem considerar-ho $T_{a}(n)$ ${\ displaystyle T_ {a} (n)}$ $T_ {a} (n)$ I $S_{a}(n)$ ${\ displaystyle S_ {a} (n)}$ $S_ {a} (n)$ com a funcions enteres positives que representen el nombre d'operacions elementals (no el temps real d'execució) realitzades i el nombre de cel·les de memòria utilitzades durant l'execució de $a$ ${\ displaystyle a}$ $a$ instantàniament $x$ ${\ displaystyle x}$ $x$ .

Descriviu les funcions $T_{a}(n)$ ${\ displaystyle T_ {a} (n)}$ $T_ {a} (n)$ I $S_{a}(n)$ ${\ displaystyle S_ {a} (n)}$ $S_ {a} (n)$ pot ser molt complicat ja que la variable $n$ ${\ displaystyle n}$ $n$ assumeix valors al conjunt de totes les entrades. Una solució que proporciona bona informació sobre $T_{a}(n)$ ${\ displaystyle T_ {a} (n)}$ $T_ {a} (n)$ I $S_{a}(n)$ ${\ displaystyle S_ {a} (n)}$ $S_ {a} (n)$ consisteix a introduir el concepte de dimensió d’una instància, agrupant així les entrades que tenen la mateixa dimensió: la funció de dimensió associa a cada entrada un nombre natural que representa intuïtivament la quantitat d’informació continguda en les dades considerades. Per exemple, la mida natural d'un enter positiu $k$ ${\ displaystyle k}$ $k$ I $[1+log_{2}{k}]$ ${\ displaystyle [1 + log_ {2} {k}]}$ $[1 + registre_ {2} {k}]$ , és a dir, el nombre de dígits necessaris per representar $k$ ${\ displaystyle k}$ $k$ en notació binària. De la mateixa manera, la mida d'un vector d'elements sol estar constituïda pel nombre de components, mentre que la mida d'un gràfic ve donada conjuntament pel nombre dels seus nodes i els seus arcs. La mida de $n$ ${\ displaystyle n}$ $n$ denota amb $|n|$ ${\ displaystyle | n |}$ $| n |$ .

Donat un algorisme $a$ ${\ displaystyle a}$ $a$ en un conjunt d’entrades $EL$ ${\ displaystyle I}$ $EL$ , pot passar que hi hagi dues instàncies $el$ ${\ displaystyle i}$ $el$ , ${el}^{'}$ ${\ displaystyle i '}$ $el '$ d'igual mida, és a dir $|i|$ ${\ displaystyle | i |}$ $| i |$ . = $|i'|$ ${\ displaystyle | i '|}$ $| i '|$ . donen lloc a temps d’execució diferents per al mateix algorisme. Per tant, parlem de la complexitat de l’entrada i es distingeixen tres casos:

complexitat en el pitjor dels casos
complexitat en el cas mitjà
complexitat en el millor dels casos

El cas mitjà ens permet estudiar l'algorisme en funció de la freqüència $p_{i}$ ${\ displaystyle p_ {i}}$ $Pi}$ amb la qual es produeixen les entrades i la complexitat $c_{i}$ ${\ displaystyle c_ {i}}$ $allà}$ de l'algorisme per a cadascun d'ells:

$\mathrm {TALG} =\sum _{i=1}^{n}p_{i}c_{i}$ ${\ displaystyle \ mathrm {TALG} = \ sum _ {i = 1} ^ {n} p_ {i} c_ {i}}$ ${\ mathrm {TALG}} = \ sum _ {{i = 1}} ^ {n} p_ {i} c_ {i}$

Quan tots els casos són iguals probables, el cas mitjà es calcula com la mitjana aritmètica de la complexitat calculada en totes les entrades possibles:

$\mathrm {TALG} ={\frac {1}{n}}\sum _{i=1}^{n}c_{i}$ ${\ displaystyle \ mathrm {TALG} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} c_ {i}}$ ${\ mathrm {TALG}} = {\ frac {1} {n}} \ sum _ {{i = 1}} ^ {n} c_ {i}$

Per exemple, en un algorisme de cerca lineal , si l'element cercat és el primer de la llista, en el millor dels casos, $T_{migliore}(n)=1$ ${\ displaystyle T_ {best} (n) = 1}$ $T _ {{best}} (n) = 1$ . La complexitat en el cas mitjà és $T_{medio}(n)={\frac {1}{n}}\sum _{i=1}^{n}i=(n+1)/2$ ${\ displaystyle T_ {average} (n) = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} i = (n + 1) / 2}$ $T _ {{mitjana}} (n) = {\ frac {1} {n}} \ sum _ {{i = 1}} ^ {n} i = (n + 1) / 2$ . En el pitjor dels casos, l'element cercat és l'últim de la llista: en aquest cas $T_{peggiore}(n)=n$ ${\ displaystyle T_ {pitjor} (n) = n}$ $T _ {{pitjor}} (n) = n$ , és a dir, tots els $n$ ${\ displaystyle n}$ $n$ passos per trobar la solució.

El pitjor dels casos és el que normalment es considera per descriure la complexitat d'un algorisme. En alguns casos (per exemple, quicksort ) es considera el cas mitjà, ja que el pitjor dels casos es produeix molt rarament o fins i tot amb probabilitat nul·la.

Complexitat i estabilitat

La contrapartida de la complexitat d'un algorisme és la seva estabilitat numèrica : estableix quant un algorisme és "resistent" a determinats conjunts de dades. Viouslybviament, el discurs generalment està relacionat amb l’anàlisi numèrica i amb la implementació d’algoritmes en màquines específiques, però hi podria haver algorismes purament matemàtics que per a algunes dades proporcionin resultats indeterminats, com ara $0 \over 0$ ${\ displaystyle 0 \ over 0}$ ${0 \ sobre 0}$ , mentre que altres algoritmes equivalents amb les mateixes dades encara aconsegueixen donar respostes: els primers són menys estables que els segons. Un exemple són els límits calculats amb el mètode canònic o amb el mètode De l'Hôpital .

Exemple: estudi de la complexitat de la resolució de sistemes lineals

El mateix tema en detall: Conjunt d’equacions lineals .

Volem trobar un algorisme eficient per resoldre un sistema lineal de $n$ ${\ displaystyle n}$ $n$ equacions en $n$ ${\ displaystyle n}$ $n$ incògnites (fins i tot 100, 1000 ...). Dit d’una altra manera, hem d’avaluar, entre tots els algorismes de solució disponibles, el que triga menys temps i consumeix menys espai que els altres. Àlgebra ens ofereix dos mètodes importants de solució d’enorme interès per estudiar la complexitat dels algorismes.

NOTA: en els exemples es té en compte que el sistema està determinat de manera única. Durant l’anàlisi és possible conèixer quines són les condicions perquè els algoritmes que estem a punt d’exposar siguin aplicables

El mateix tema en detall: la regla de Cramer .

La regla de Cramer permet la solució d’un sistema lineal de la manera més senzilla gràcies a una única definició:

x_{i}={\det(A_{i}) \over \det(A)}

{\ displaystyle x_ {i} = {\ det (A_ {i}) \ over \ det (A)}}

x_ {i} = {\ det (A_ {i}) \ over \ det (A)}

on és $A_{i}$ ${\ displaystyle A_ {i}}$ $Fins al}$ és la matriu formada per la substitució de la i- e columna de $A$ ${\ displaystyle A}$ $A$ amb el vector de termes coneguts. El determinant de la matriu es pot calcular a priori, per tant només el càlcul de $n+1$ ${\ displaystyle n + 1}$ $n + 1$ decisiu per resoldre el sistema. El determinant sol definir-se pel desenvolupament de Laplace , que proporciona directament un algorisme recursiu :

\det(A_{k})=\sum _{i=1}^{n}(-1)^{i+k}a_{i,k}\det(A_{i,k})

{\ displaystyle \ det (A_ {k}) = \ sum _ {i = 1} ^ {n} (- 1) ^ {i + k} a_ {i, k} \ det (A_ {i, k}) }

\ det (A_ {k}) = \ sum _ {{i = 1}} ^ {n} (- 1) ^ {{i + k}} a _ {{i, k}} \ det (A _ { {i, k}})

on és $a_{i,k}$ ${\ displaystyle a_ {i, k}}$ $a _ {{i, k}}$ és l'element de coordenades $el, k$ ${\ displaystyle i, k}$ $jo, k$ I $A_{i,k}$ ${\ displaystyle A_ {i, k}}$ $A _ {{i, k}}$ és el menor que s'obté suprimint el fitxer $el$ ${\ displaystyle i}$ $el$ -la línia i la $k$ ${\ displaystyle k}$ $k$ -a columna. La complexitat d’aquest algorisme per calcular el determinant és $O(n!)$ ${\ displaystyle O (n!)}$ $O (n!)$ , perquè per a cada determinant de l'ordre $m$ ${\ displaystyle m}$ $m$ s’ha de calcular $m$ ${\ displaystyle m}$ $m$ determinants de l’ordre $m-1$ ${\ displaystyle m-1}$ $m-1$ .

Per tant, s’utilitzen altres algoritmes amb millor complexitat. (Per cert, aquests algoritmes també són la base de mètodes més eficients per calcular el determinant). Un d’ells és el mètode d’eliminació de Gauss , que es basa en dos principis importants.

El primer és que hi ha dos sistemes lineals

\operatorname {A} \operatorname {x} =\operatorname {b}

{\ displaystyle \ operatorname {A} \ operatorname {x} = \ operatorname {b}}

\ operatorname A \ operatorname x = \ operatorname b

I

\operatorname {U} \operatorname {x} =\operatorname {c}

{\ displaystyle \ operatorname {U} \ operatorname {x} = \ operatorname {c}}

\ operatorname U \ operatorname x = \ operatorname c

són iguals si $\operatorname {U}$ ${\ displaystyle \ operatorname {U}}$ $\ operatorname U$ s'obté substituint les files i columnes de $\operatorname {A}$ ${\ displaystyle \ operatorname {A}}$ $\ operatorname A$ amb les seves combinacions lineals i els elements de $\operatorname {c}$ ${\ displaystyle \ operatorname {c}}$ $\ operatorname c$ són combinacions lineals dels elements de $\operatorname {b}$ ${\ displaystyle \ operatorname {b}}$ $\ operatorname b$ basat en els coeficients de $\operatorname {U}$ ${\ displaystyle \ operatorname {U}}$ $\ operatorname U$ .

La segona és que per resoldre un sistema triangular (és a dir, on la matriu de coeficients té la propietat de la triangularitat) és suficient utilitzar l’algorisme de substitució cap endavant o cap enrere (la complexitat computacional és $O(n)$ ${\ displaystyle O (n)}$ $O (n)$ ).

Es demostra que per transformar el sistema en un triangular es requereix un algorisme la complexitat del qual sigui $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ . En aplicar l’algorisme de substitució directa a aquest sistema, es troben les solucions exactes del sistema, i es demostra que la complexitat total de l’algorisme de Gauss sempre és $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ .

Quant a la complexitat espacial:

l'algorisme basat en la regla de Cramer només requereix una variable addicional, on emmagatzemar el determinant de la matriu de coeficients, per tant la seva complexitat és mínima: $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ (això és $n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$ per emmagatzemar la matriu de coeficients, $2n$ ${\ displaystyle 2n}$ $2n$ per emmagatzemar el vector dels termes coneguts i les solucions, més un espai igual a $n$ ${\ displaystyle n}$ $n$ per al càlcul de determinants)
L'algoritme de Gauss no requereix cap altre espai que el necessari per emmagatzemar la matriu dels coeficients i el vector dels termes coneguts. Al final de l'algorisme, el vector de termes coneguts contindrà la solució. Per tant, la seva complexitat espacial també és mínima: $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ .

Estructures de dades

El mateix tema en detall: Estructura de dades .

La majoria d’algoritmes utilitzen tècniques per representar i organitzar les dades utilitzades en càlcul i aquestes representacions, anomenades estructures de dades, no són necessàriament tan sofisticades com l’algorisme que les utilitza: els algorismes senzills poden requerir estructures de dades complexes i viceversa.

Per facilitar i resumir la gestió i la interacció d’estructures de dades complexes, es desenvolupen algoritmes especials que implementen les operacions més habituals que s’hi han de realitzar. Exemples d’estructures de dades habituals són vectors , llistes , cues , piles , arbres i gràfics .

Catalogació d'algorismes

Els algoritmes s’agrupen i es cataloguen segons la seva funció o les tècniques que s’utilitzen per crear-los, però ara s’ha convertit en impossible una catalogació rigorosa i completa.

En informàtica és possible catalogar algoritmes en:

Algorismes iteratius
Algorismes recursius
Algorismes d’ordenació
Algorismes de cerca
- Cerca seqüencial
  - Cerca seqüencial amb sentinella
- Cerca binària
Genètica evolutiva
Intel·ligència de l’eixam
Algorisme combinatori
Codi que es modifica automàticament
Conversió i codificació
- UUencode / UUdecode
- Mímica
Algorismes de compressió
- Sense pèrdua d'informació:
  - Codificació de llargada
    - PackBits
    - PCX
  - Codificació local de reducció d' Entropia
    - Codificació Huffman
    - Codificació aritmètica
  - Codificació del diccionari
    - DESGRAFAR
    - LZ77 i LZ78
    - Lempel-Ziv-Welch (ZIP)
    - LZMA
  - Transformada de Burrows-Wheeler
  - PPM
- Amb pèrdua d’informació
  - Transformada de cosinus discret (DCT)
    - MPEG (primer mètode de compressió d'alta difusió basat en DCT i Delta )
    - JPEG (compressió d’imatges basada en la quantització, DCT i Huffman)
  - Compressió fractal
    - Transformació fractal
  - Onada
    - MP3 (compressió d'àudio basada en una compressió similar a l'ona d'ona i DCT)
    - JPEG2000 (compressió d'imatges mitjançant wavelet, Huffman i quantització)

Moltes categories d’algoritmes estan estretament relacionades amb l’organització de dades a la memòria ( estructures de dades ).

Altres algorismes

Nota

↑ Luca Serianni , Gramàtica italiana , ed. UTET-De Agostini, Torino, 2010, ISBN 978-88-6008-057-8 , p. 104.
^ Kleene 1943 in Davis 1965:274
^ Rosser 1939 in Davis 1965:225
^ Yiannis N. Moschovakis, What is an algorithm? , in B. Engquist e W. Schmid (a cura di), Mathematics Unlimited — 2001 and beyond , Springer, 2001, pp. 919–936 (Part II).

Bibliografia

Robert Sedgewick , Algoritmi in C++ , Addison-Wesley, ISBN 88-7192-153-4
( EN ) Robert Sedgewick , Philippe Flajolet (1996): An Introduction to the Analysis of Algorithms , Addison-Wesley, ISBN 0-201-40009-X
Alessandra D'Alessio, Lezioni di Calcolo Numerico e Matlab , Liguori Editore, ISBN 88-207-3459-1
Fabrizio Luccio , La struttura degli Algoritmi , Boringhieri, ISBN 88-339-5265-7
Thomas H. Cormen , Charles E. Leiserson, Ronald Rivest , Introduzione agli algoritmi
Paolo Zellini , La dittatura del calcolo , Adelphi, 2018, ISBN 978-8845932403

Voci correlate

Altri progetti

Wikiquote contiene citazioni di o su algoritmo
Wikibooks contiene testi o manuali su algoritmo
Wikizionario contiene il lemma di dizionario « algoritmo »
Wikimedia Commons contiene immagini o altri file sugli algoritmi

Collegamenti esterni

Algoritmo , su Treccani.it – Enciclopedie on line , Istituto dell'Enciclopedia Italiana .
( EN ) Algoritmo , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
Algoritmo - in Wehardware.it - Il diagramma a blocchi nella descrizione dell'algoritmo
( ES ) Mis algoritmos Procedure di base in parecchi linguaggi di programmazione.
( EN ) Dizionario degli algoritmi e delle strutture dati , su nist.gov .

Controllo di autorità	Thesaurus BNCF 21026 · LCCN ( EN ) sh85003487 · GND ( DE ) 4001183-5 · BNF ( FR ) cb119358199 (data) · BNE ( ES ) XX527980 (data) · NDL ( EN , JA ) 00560337

Portale Informatica

Portale Matematica

[1] Luca Serianni , Gramàtica italiana , ed. UTET-De Agostini, Torino, 2010, ISBN 978-88-6008-057-8 , p. 104.

[2] Kleene 1943 in Davis 1965:274

[3] Rosser 1939 in Davis 1965:225

[4] Yiannis N. Moschovakis, What is an algorithm? , in B. Engquist e W. Schmid (a cura di), Mathematics Unlimited — 2001 and beyond , Springer, 2001, pp. 919–936 (Part II).

[1] que va

[2]

[3]

[4]