Wikipedia cowiki https://co.wikipedia.org/wiki/Pagina_maestra MediaWiki 1.47.0-wmf.22 first-letter Media Speciale Discussione Utente Discussioni utente Wikipedia Discussioni Wikipedia File Discussioni file MediaWiki Discussioni MediaWiki Template Discussioni template Aiuto Discussioni aiuto Categoria Discussioni categoria TimedText TimedText talk Modulo Discussioni modulo Evento Discussioni evento 0 22039 406820 399918 2026-10-06T06:30:23Z Jfblanc 706 406820 wikitext text/x-wiki '''Antoine Ciosi''' hè un cantadore Corsu, natu lu 15 di Dicembre 1931 indè [[Sorbu è Occagnanu]] ([[Corsica suprana]]) è mortu lu 4 Ottobre 2026 a [[A Curbaghja]] ([[Corsica suprana]]). [[File:Antoine_Ciosi.png|thumb|destra|250px|Antoine Ciosi]] À u mese di Marzu 1963, uttene u Primu prezu di u primu festivale di a Canzona Corsa in l'Olympia in Parigi, per l'interpretazione di a canzona di Ghjuvanni Giocanti è Vincente Orsini, ''Paese Spentu''. Figliolu di un cultivatore di Sorbu è Occagnanu, a i mezi di l'anni 1930, urganizeghja in u so paese un meeting puliticu cù u capicochja cumunistu Jacques Duclos è chì sarà l'invitatu d'unore; purtendu à cuntradizione a u prete è u merru di u paese chì sò piuttostu di a dritta. ' Antoine Ciosi conta a so ghjuventù è u rumenu talianu-alemanu in Corsica nentru u so libru ''Une odeur de figuier sauvage - Une enfance Corse'' (Edizione Albin Michel, [[1999]]). == Discugrafia == ==== 1960 ==== * ''Le Porte-croix, ''1966 ==== 1970 ==== * ''Cursichella, ''1970 * ''Corsica amata, ''1972 * ''Ricordi di Cursichella, ''1973 * ''Ritornu à u paese, ''1974 * ''Anima corsa, ''(Puesia), 1974 * ''Le prisonnier ''1975 * ''Corsica nostra, ''1975 * ''Corsica sempre corsa, ''1976 * ''Musa di un populu, ''(poésies), 1977 * ''Ver di casa, ''1977 * ''Corsica, ''1978 * ''Corsica ! Mamma cara, ''1978 * ''Cantu per un'isula ch'ùn si vole more, ''1979 * ''Canti pupulari di Corsica ''(Cù Maryse Nicolai)'', ''1979 ==== 1980 ==== * ''Giuventù, ''1980 * ''Isula, ''1981 * ''Corsu, ''1982 * ''Kalliste, ''1982 * ''Nostalgia, ''1983 * ''20 ans de Chansons Corses, ''(Live Olympia, Maghju 1981), 1985 * ''Per tè, ''1987 * ''Mon village m'appelle, ''(Puesia), 1989 * ''Canti di a libertà, ''1989 ==== 1990 ==== * ''Chante les frères Vincenti, ''1991 * ''Natale d'amore, ''1993 * ''Tempi d'amore, ''1996 * ''Cantiques, ''1999 ==== 2000 ==== * ''Ciosi 2000'' [[2000]] * ''Per tè'', 2000, ''Natale d'Amore'' dischettu cù ''Canzona à Don-Joseph Giansily,Pampasgiolu'' (ré edizione cù 3 CD, 2002) * ''Luisa'' 2005 * ''À voce piena'' [[2008]], Casa Éditions, CDCASA25 ==== 2010 ==== * ''Una mamma''(Dischettu-Libru), 2011, Casa Éditions, CDCASA31 * ''In Bastia'', 2013 * ''[[Corsu Mezu Mezu]]'' (intruduzzione, interludiu è ''Ô Corse île d'amour'' cu [[Patrick Fiori]]) 2015 ==== 2020 ==== * ''Duetti'', (27 di e so più bedde canzone cù 21 cantadori isulani) == Publicazione == *''Notes & chansons'' - Ed. Pica, 1978. *''Une odeur de figuier sauvage'' - Edizione Albin Michel, 1999. {{ISBN|9782226108555}} *''Le chemin des sources profondes'' - Edizione Albin Michel, 2004. *''Chants d'une terre - 40 ans de chansons corses'' - Ed. DCL, 2002. *''Una mamma'' (Dischettu-Libru, 2011, Casa Edizione, CDCASA31. == Decurazione == L'8 di Dicembre [[2018]], Antoine Ciosi fù citadinu d'unore di a cità di Marsiglia.<ref>{{Lien web|url=https://www.corsematin.com/articles/antoine-ciosi-fait-citoyen-dhonneur-de-la-ville-de-marseille-89253|titre=Antoine Ciosi fait citoyen d'honneur de la ville de Marseille |site=Corse Matin |consulté le = 3 juin 2020}}</ref> == Articuli cunnessi == * [[Chant des Partisans]] == Note == <references /> [[Categoria:Cantadore|Ciosi, Antoine]] [[Categoria:Corsu|Ciosi, Antoine]] [[Categoria:Biugrafia|Ciosi, Antoine]] kfccxeu6ek6zexvo1hefcuy31ohrcmp 0 27764 406817 406816 2026-10-05T13:49:19Z Articulivitali 28749 /* Pruprietà fundamentale di l'algoritmi */ 406817 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genera unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assucia à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fasi: # sintesi (chjamata dinù disegnu o prughjettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalizazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzioni, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura chì cresce a cumplessità di u prublema, cumu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di l'espertu]] Hè definita asintoticamente per duie ragione: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura chì cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determina u numeru di bit necessarii per codificallu è, annantu à e matrici, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensioni (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indica, per ogni valore interu n (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione n. Un algoritmu pò avè un cumpurtamentu sensibilmente differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. In fatti, hè faciule di dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzioni intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di celle di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzioni <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucia à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di n si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: ella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè generalmente ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determinanu quandu l'algoritmi prisentati sò applicabili. {{vedi dinù|Regula di Cramer}} A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o à l'indietru (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Applichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tali raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] l2qbf2572u3zpm10huyv0pff8f8kbhn 406818 406817 2026-10-05T13:51:24Z Articulivitali 28749 /* Approcciu matematicu */ 406818 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalizazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzioni, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di l'espertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura chì cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determina u numeru di bit necessarii per codificallu è, annantu à e matrici, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensioni (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indica, per ogni valore interu n (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione n. Un algoritmu pò avè un cumpurtamentu sensibilmente differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. In fatti, hè faciule di dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzioni intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di celle di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzioni <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucia à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di n si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: ella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè generalmente ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determinanu quandu l'algoritmi prisentati sò applicabili. {{vedi dinù|Regula di Cramer}} A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o à l'indietru (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Applichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tali raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] rbx3v46tlj6qs5cog01y0c5nm0enkmw 406819 406818 2026-10-05T13:56:36Z Articulivitali 28749 /* Approcciu matematicu */ 406819 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalizazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzioni, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di l'espertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura chì cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determina u numeru di bit necessarii per codificallu è, annantu à e matrici, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensioni (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indica, per ogni valore interu n (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione n. Un algoritmu pò avè un cumpurtamentu sensibilmente differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. In fatti, hè faciule di dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzioni intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di celle di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzioni <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucia à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di n si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: quella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè generalmente ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determineghjanu quandu l'algoritmi prisentati sò applicabili. A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o in daretu (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Appiichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tale raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] 15gjc942bzg4h4lf1orzxstm0caw01u 406821 406819 2026-10-06T09:07:26Z Articulivitali 28749 /* Furmalizazione d'un prublema */ 406821 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalisazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzione, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di l'espertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura chì cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determina u numeru di bit necessarii per codificallu è, annantu à e matrici, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensioni (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indica, per ogni valore interu n (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione n. Un algoritmu pò avè un cumpurtamentu sensibilmente differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. In fatti, hè faciule di dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzioni intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di celle di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzioni <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucia à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di n si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: quella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè generalmente ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determineghjanu quandu l'algoritmi prisentati sò applicabili. A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o in daretu (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Appiichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tale raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] iotgdkxptuwfhi2lrzevk6tolzhgi8r 406822 406821 2026-10-06T09:11:39Z Articulivitali 28749 /* Studiu di a cumplessità computaziunale d'un algoritmu */ 406822 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalisazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzione, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di u spertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura ch'ellu cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determineghja u numeru di bit necessarii per codificà lu è, annantu à e matrice, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensione (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indicheghja, per ogni valore interu ''n'' (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione ''n''. Un algoritmu pò avè un cumpurtamentu appena differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. Di fatti, hè faciule à dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzione intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di cellule di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzione <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucieghja à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di ''n'' si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: quella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè generalmente ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determineghjanu quandu l'algoritmi prisentati sò applicabili. A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o in daretu (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Appiichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tale raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] 5da7o9975r3djhu9bczsifi9w6kjaet 406823 406822 2026-10-06T09:12:10Z Articulivitali 28749 /* Cumplessità è stabilità */ 406823 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalisazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzione, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di u spertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura ch'ellu cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determineghja u numeru di bit necessarii per codificà lu è, annantu à e matrice, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensione (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indicheghja, per ogni valore interu ''n'' (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione ''n''. Un algoritmu pò avè un cumpurtamentu appena differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. Di fatti, hè faciule à dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzione intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di cellule di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzione <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucieghja à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di ''n'' si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: quella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè di solitu ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determineghjanu quandu l'algoritmi prisentati sò applicabili. A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o in daretu (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Appiichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tale raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalogazione di l'algoritmi == L'algoritmi sò raggruppati è catalogati secondu a so funzione o e tecniche aduprate per realizalli; tuttavia, una catalogazione rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalogà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] 3hwt2d34zdgyqoyw874ejq8gaparb2h 406824 406823 2026-10-06T09:12:58Z Articulivitali 28749 /* Catalogazione di l'algoritmi */ 406824 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazione]] (dette dinù ''istruzzione'') chì permette di risolve tutti e quistione d'una stessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzione è deve sempre finisce; * ''deterministu'': partendu da e listesse dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazione ùn devenu pudè esse interpretate in modu differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriveghja da a trascrizzione [[lingua latina|latina]] di u nome di u [[matematicu]] persianu [[al-Khwarizmi]], chì campò à u [[IX seculu]], è chì hè cunsideratu unu di i primi autori à avè fattu riferenza à stu cuncettu in u so libru ''Regule di ristaurazione è riduzzione''. E prime nozione d'algoritmu si trovanu in ducumenti chì ricollanu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiru di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzione, cumpresu un prublema di multiplicazione chì u scrittore dichjara avè cupiatu da altri papiri più antichi. L'algoritmu hè un cuncettu fundamentale di l'[[informatica]], prima di tuttu perchè hè à a basa di a nuzione teorica di [[Teoria di a calculabilità|calculabilità]]: un prublema hè calculabile quandu pò esse risoltu per mezu d'un algoritmu. Inoltre, l'algoritmu hè un cuncettu centrale ancu in a fasa di [[Prugrammazione (informatica)|prugrammazione]] di u [[ciculu di vita di u software|sviluppu d'un software]]: datu un prublema da [[automatica|automatizà]], a prugrammazione cunsiste per u più in a traduzzione o [[codificazione]] d'un algoritmu per quellu prublema in [[prugramma (informatica)|prugramma]], scrittu in una certa [[lingua di prugrammazione]], chì pò dopu esse [[esecuzione (informatica)|eseguitu]] da un [[urdinatore]], riprisentendu a so logica d'[[elaburazione di dati|elaburazione]]. == Definizione == U primu algoritmu informaticu hè statu cuncipitu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu furmalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre furmalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E furmalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzione ricursive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] di u 1930, 1934 è 1935; u [[calculu lambda]] d'[[Alonzo Church]] è a [[Formulation 1]] d'[[Emil Leon Post]] di u 1936; è, infine, a [[macchina di Turing]] di u 1936–37 è di u 1939. Malgradu quessa, manca sempre una definizione furmale è micca tecnica di u cuncettu d'algoritmu. Si deve dunque ricorre à l'idea intuitiva d'un algoritmu cum'è «una sequenza urdinata è finita di passi (operazioni o istruzzioni) elementari chì cunduce à un risultatu ben determinatu in un tempu finitu». === Mudelli furmali === [[File:Quicksort example.png|thumb|Riprisentazione grafica di l'algoritmu [[Quicksort]]]] Hè statu necessariu di dispone d'una definizione più rigurosa per trattà u cuncettu d'algoritmu cù strumenti matematichi. Per quessa sò stati definiti parechji [[Mudellu matematicu|mudelli matematichi]] d'algoritmu, frà i quali unu di i più cunnisciuti hè a [[macchina di Turing]], vale à dì una spezia d'''urdinatore'' ideale dutatu d'un [[Prugramma (informatica)|prugramma]] da eseguisce. Rispettu à un urdinatore reale, a macchina di Turing hà un funziunamentu più simplice è facilmente descrivibile cù termini matematichi, aduprendu cuncetti cum'è [[inseme]], [[relazione (matematica)|relazione]] è [[funzione (matematica)|funzione]]. A [[architettura di von Neumann|macchina di Von Neumann]], chì hè u mudellu d'architettura primigeniu di tutti l'urdinatori attuali, hè equivalente, in termini di putere di calculu, à a macchina di Turing. In altre parolle, hè statu dimustratu chì un certu prublema pò esse risoltu da un urdinatore (prugrammatu apposta) [[sì è solu sì]] pò esse risoltu dinù da una macchina di Turing. In più di a macchina di Turing, pruposta da [[Alan Turing]] in u [[1936]], in u listessu periodu altri matematichi anu elaburatu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà e quale, per esempiu, u [[calculu lambda]]. Dopu à qualchì annu, hè emersu chì tutti sti mudelli eranu equivalenti: i prublemi chì una macchina di Turing pudia risolve eranu listessi à quelli chì pudia risolve una macchina di von Neumann è listessi dinù à quelli chì pudia risolve una funzione custruita cù u calculu lambda. Da sti risultati nasce, frà altre cose, a [[tesi di Church-Turing]], chì dice chì ogni algoritmu pò esse mudellizatu cù una macchina di Turing. In altri termini, sta tesi sustene ch'ellu hè essenzialmente impussibule d'imaginà un mudellu d'algoritmu più putente è, di cunsiquenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possi risolve in principiu. Ùn si tratta micca d'un [[teorema]] dimustratu matematicamente, postu chì a tesi stabilisce l'uguaglianza trà dui cuncetti, l'algoritmu è a macchina di Turing, mentre chì u primu ùn pussede micca una definizione furmale. A tesi hè oghje generalmente accettata, ancu se i prugressi di e ricerche in u settore di l'[[ipercomputazione]] parenu qualchì volta mette la in discussione. Esiste dinù l'[[algoritmu di Hirschberg]], chjamatu cusì da u so creatore Dan Hirschberg, di [[prugrammazione dinamica]], chì trova l'[[allineamentu di sequenze|allineamentu]] ottimale d'una sequenza trà duie [[Stringa (informatica)|stringhe]]. === Pruprietà fundamentale di l'algoritmi === [[File:Algoritmo para Procesar y Organizar en GTD.png|thumb|Esempiu di [[diagramma di flussu]] d'un algoritmu di u metudu [[Dettu, fattu!]]]] Da a definizione precedente d'algoritmu si ponu deduce certe pruprietà necessarie, senza e quali un algoritmu ùn pò esse definitu cum'è tale: * i passi chì u custituiscenu devenu esse «elementari», vale à dì micca più scumpunibili (''atomicità''); * i passi chì u custituiscenu devenu esse interpretabili in modu direttu è univocu da l'''esecutore'', ch'ellu sia umanu o artificiale (''assenza d'ambiguità''); * l'algoritmu deve esse cumpostu d'un numeru finitu di passi è richiede una quantità finita di dati d'entrata (''finitude''); * l'esecuzione deve finisce dopu à un tempu finitu (''terminazione''); * l'esecuzione deve purtà à un risultatu univocu (''effettività''). Cusì, per esempiu, «rompe l'ove» pò esse cunsideratu leghjittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quant'è necessariu», postu chì a spressione «quant'è necessariu» hè ambigua è ùn indicheghja micca cun precisione i passi chì devenu esse fatti per determinà a quantità necessaria. À l'istruzzione micca elementare di preparazione di a crema si puderia, però, assucià un rinviu opportunu à un'altra sezzione di u ricettariu, chì furnissi un sottu-algoritmu appostu per quessa operazione. Questu sughjerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottuprublemi specifichi, è ''urganizati gerarchicamente''. Inoltre, una ricetta chì prevede a cottura à [[microonde]] ùn pò esse preparata da un esecutore chì ùn pussede micca l'apparechju adattatu; questu rinvia à u prublema di a ''realizabilità'' di l'algoritmi, vale à dì a so cumpatibilità cù e risorse materiale è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè di solitu descrittu cum'è «prucedura di risoluzione d'un prublema». In stu cuntestu, i «prublemi» cunsiderati sò guasi sempre caratterizati da ''dati d'entrata'' ([[input]]) variabili, nantu à i quali l'algoritmu opera per ghjunghje à a suluzione. Per esempiu, u calculu di u [[Massimu cumunu divisore|massimu cumunu divisore]] trà dui numeri hè un esempiu di «prublema», è i so ''dati d'entrata'', variabili ogni volta, sò i dui numeri in quistione. À una persona chì ùn hè matematica, questu puderia parè una «famiglia di prublemi» (u prublema di calculà u massimu cumunu divisore trà 10 è 15, trà 40 è 60, trà 35 è 95, è cusì). U matematicu è l'informaticu identificheghjanu cù a parolla «prublema» a famiglia sana è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema s'è, per ogni istanza di u prublema, produce in un tempu finitu a suluzione desiderata, vale à dì un certu risultatu o datu d'uscita ([[Input/output|output]]) partendu da dati d'entrata ([[input]]). S'è st'idea avia dighjà una certa impurtanza per u calculu matematicu, l'avventu di l'informatica l'hà arricchita d'una nova impurtanza, è hè in fatti cù l'informatica chì u termine «algoritmu» hà cuminciatu à sparghje si. Difatti, s'è per ottene un certu risultatu (risolve un certu prublema) esiste una prucedura infallibile, chì pò esse descritta senza ambiguità finu à i dettagli, è chì cunduce sempre à l'ughjettivu desideratu in un tempu finitu, tandu esistenu e cundizione per affidà stu compitu à un [[urdinatore]], introducendu simpliciamente l'algoritmu in un [[Prugramma (informatica)|prugramma]] scrittu in una [[lingua di prugrammazione|lingua]] adatta è capiscitoghja da a macchina. In principu, un algoritmu pò esse descrittu cù un [[diagramma di flussu]] o per mezu d'un [[pseudocodice]]. Dopu, durante a fase di [[Prugrammazione (informatica)|prugrammazione]], l'algoritmu cusì scrittu hè traduttu in [[lingua di prugrammazione]] da un [[prugrammatore]] sottu forma di [[codice fonte]], dendu nascita à u [[prugramma (informatica)|prugramma]] chì serà [[esecuzione (informatica)|eseguitu]] da l'urdinatore, eventualmente dopu una traduzzione ulteriore in [[lingua macchina]]. Hà una particulari impurtanza teorica in questu ambitu u [[teorema di Böhm-Jacopini]], chì afferma chì ogni algoritmu pò esse implementatu aduprendu solu trè strutture, a [[sequenza (informatica)|sequenza]], a [[selezione (informatica)|selezione]] è u ciculu ([[iterazione]]), da applicà ricursivamente à a cumpusizione d'[[istruzzione (informatica)|istruzzione]] elementare. In a pratica currente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice fonte necessariu in e modalità dette dopu avè dighjà trovu a suluzione à u prublema datu. == Approcciu matematicu == Esistenu numerosi mudelli matematichi d'algoritmu. In generale, un algoritmu riceve un inseme di valori (dati) in [[input]] è ne genereghja unu in output (chjamatu suluzione). Datu dunque un algoritmu A, si denota cù f_A a funzione chì assuceghja à ogni entrata x di A l'uscita currispundente. Sta currispundenza trà input è output ùn raprisenta micca u prublema risoltu da l'algoritmu. Formalmente, un prublema hè una funzione <math>f (D_i) \to D_s</math> definita annantu à un inseme D_i d'elementi chjamati istanze, à valori annantu à un inseme D_s di suluzioni. U studiu d'un algoritmu hè spartutu in duie fase: # sintesi (chjamata dinù disegnu o prugettu): datu un prublema A, custruisce un algoritmu f per risolve A, vale à dì tale chì f=f_a; # analisi: datu un algoritmu f è un prublema A, dimustrà chì f risolve A, vale à dì f=f_a (''currettezza'') è valutà a quantità di risorse aduprate da f (''cumplessità concreta''). === Furmalisazione d'un prublema === À ogni prublema <math>\Pi</math> currisponde: <math>f \pi: D \pi \rightarrow S \pi</math> induve <math>D \pi</math> sò l'istanze di u prublema è <math>S \pi</math> sò e suluzione, è <math>\forall x \in D \pi:f \pi (x)</math> deve esse una suluzione di u prublema per l'istanza x. === Studiu di a cumplessità computaziunale d'un algoritmu === Una larga parte di a teoria di l'algoritmi hè dedicata à u studiu di a cumplessità, computaziunale è spaziale. Si vole sapè, à misura ch'ella cresce a cumplessità di u prublema, cum'ellu cresce u tempu necessariu per eseguisce l'algoritmu è u spaziu di memoria occupatu in un urdinatore. A cumplessità d'un algoritmu si misura asintoticamente. Ci sò quattru metudi per calculà a cumplessità d'un algoritmu: * metudu di sustituzione * metudu d'iterazione * metudu di l'arburu * [[metudu di u spertu]] Hè definita asintoticamente per duie raghjone: * postu chì ogni urdinatore pò implementà l'algoritmi in modu differente, ùn si pò stimà u tempu precisu; * si vole dà un'idea quantitativa di cumu l'algoritmu pò cresce in cunsumu di tempu à misura ch'ellu cresce l'input, per valori sempre più grandi. Data una funzione assuciata à un algoritmu di u tipu: <math>\phi ALG: \mathrm{InALG} \rightarrow \mathrm{OutALG}</math> si pò definisce a funzione di pesu cum'è: <math>\mathrm{WALG}: \mathrm{InALG} \rightarrow \mathbb{N}</math> chì sprime a dimensione di i dati d'entrata, vale à dì u numeru di bit necessarii per codificà i dati in input à l'algoritmu. Per esempiu, annantu à un vettore, a so lunghezza determineghja u numeru di bit necessarii per codificà lu è, annantu à e matrice, u numeru di l'ordine, vale à dì, presa per esempiu una [[matrice quadrata]], l'ordine di a stessa hè determinatu da una di e duie dimensione (orizontale o verticale). A cumplessità d'un algoritmu hè definita cum'è: <math>\mathrm{TALG}: \mathbb{N} \rightarrow \mathbb{N}</math> chì indicheghja, per ogni valore interu ''n'' (vale à dì a dimensione di u prublema), a quantità di tempu è/o spaziu aduprata da l'algoritmu per trattà dati di dimensione ''n''. Un algoritmu pò avè un cumpurtamentu appena differente ancu per istanze chì anu a listessa dimensione (vale à dì u listessu pesu). Si dimostra chì a cumplessità d'un algoritmu hè una funzione strettamente crescente, per a quale vale <math>\lim_{n\rightarrow \infty} T(x)=\infty</math>. Di fatti, hè faciule à dimustrà chì <math>S_a(x)</math> tende versu l'infinitu à misura chì cresce x (vale à dì u numeru di dati da trattà), perchè hè minorata da x (hè un <math>o(x)</math>) postu chì u numeru minimu di spazii di memoria per memorizà un inseme di dati hè a so [[cardinalità]]. Si deve nutà chì, per e [[matrice sparse|matrici sparse]], si deve cunsiderà cum'è «numeru di dati» l'elementi micca nulli. Duie misure per i sistemi di calculu sequenziale sò i valori <math>T_a(x)</math> è <math>S_a(x)</math>, chì raprisentanu rispettivamente u tempu è u spaziu di memoria richiesti da un algoritmu ''a'' annantu à l'input <math>x \in X</math>. Per a pruprietà detta sopra, u duminiu X deve dunque coincide cù l'inseme <math>\mathbb{N}</math>. Pudemu dunque cunsiderà <math>T_a(n)</math> è <math>S_a(n)</math> cum'è funzione intere pusitive chì raprisentanu u ''numeru d'operazioni'' elementari eseguite (micca u tempu d'esecuzione effettivu) è u numeru di cellule di memoria aduprate durante l'esecuzione di ''a'' annantu à l'istanza x. Descrive e funzione <math>T_a(n)</math> è <math>S_a(n)</math> pò esse assai cumplicatu, postu chì a variabile n assume valori annantu à l'inseme di tutti l'input. Una suluzione chì dà infurmazione utile annantu à <math>T_a(n)</math> è <math>S_a(n)</math> cunsiste à intruduce u cuncettu di dimensione d'una istanza, raggruppendu cusì l'input chì anu a listessa dimensione: a funzione dimensione assucieghja à ogni entrata un [[numeru naturale]] chì raprisenta intuitivamente a quantità d'infurmazione cuntenuta in u datu cunsideratu. Per esempiu, a dimensione naturale d'un interu pusitivu k hè <math>[1 + log_2{k}]</math>, vale à dì u numeru di cifre necessarie per raprisentà k in nutazione binaria. Similmente, a dimensione d'un vettore d'elementi hè di solitu custituita da u numeru di e so cumpunenti, mentre chì a dimensione d'un grafu hè data inseme da u numeru di i so nodi è di i so archi. A dimensione di ''n'' si denota cù <math>|n|</math>. Datu un algoritmu ''a'' annantu à un inseme d'input I, pò accade chì duie istanze i, i' di listessa dimensione, vale à dì <math>|i|=|i'|</math>, dighjà tempi d'esecuzione differenti per u listessu algoritmu. Si parla dunque di cumplessità di l'input è si distinguenu trè casi: # cumplessità in u casu peghju # cumplessità in u casu mediu # cumplessità in u casu megliu U casu mediu permette di studià l'algoritmu in funzione di a frequenza <math>p_i</math> cù a quale si presentanu l'input è di a cumplessità <math>c_i</math> di l'algoritmu per ognunu d'elli: <math>\mathrm{TALG} = \sum_{i=1}^n p_i c_i</math> Quandu i casi sò tutti equiprobabili, u casu mediu hè calculatu cum'è media aritmetica di a cumplessità calculata annantu à tutti l'input pussibuli: <math>\mathrm{TALG} = \frac{1}{n} \sum_{i=1}^n c_i</math> Per esempiu, in un algoritmu di [[ricerca lineare]], se l'elementu cercatu hè u primu di a lista, ci truvemu in u casu megliu, <math>T_{migliore}(n)=1</math>. A cumplessità in u casu mediu hè <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. In u casu peghju, l'elementu cercatu hè l'ultimu di a lista: in questu casu <math>T_{peggiore}(n)=n</math>, vale à dì ch'elli sò necessarii tutti l'<math>n</math> passi per truvà a suluzione. U casu peghju hè quellu chì hè di regula cunsideratu per discrive a cumplessità d'un algoritmu. In certi casi, per esempiu u [[quicksort]], si cunsidereghja u casu mediu, postu chì u casu peghju si verifica assai raramente o ancu cù probabilità nulla. === Cumplessità è stabilità === Cuntrapposta à a cumplessità d'un algoritmu hè a so [[stabilità numerica]]: quella stabilisce quantu un algoritmu hè «resistente» à certi inseme di dati. U discorsu hè di solitu ligatu à l'[[analisi numerica]] è à l'implementazione d'algoritmi annantu à macchine specifiche; tuttavia, ponu esiste algoritmi puramente matematichi chì, per certi dati, danu risultati indeterminati, cum'è <math>0 \over 0</math>, mentre chì altri algoritmi equivalenti cù i listessi dati ghjunghjenu quantunque à dà una risposta: i primi sò menu stabili cà i secondi. Un esempiu sò i limiti calculati cù u metudu canonicu o cù a [[Regula di De L'Hôpital|regula di De l'Hôpital]]. === Esempiu: studiu di a cumplessità di a risoluzione di i sistemi lineari === Si vole truvà un algoritmu ''efficiente'' per risolve un sistema lineare di n equazioni in n incognite (ancu 100, 1000...). Si deve dunque valutà, trà tutti l'algoritmi risolutivi dispunibuli, quellu chì impiega menu tempu è cunsuma menu spaziu cà l'altri. L'Algebra furnisce dui metudi risolutivi impurtanti, di grande interessu per u studiu di a cumplessità di l'algoritmi. ;NOTA: in l'esempii si suppone chì u sistema sia univucamente determinatu. In un approfondimentu si ponu studià e cundizione chì determineghjanu quandu l'algoritmi prisentati sò applicabili. A [[Regula di Cramer]] permette di risolve un sistema lineare in modu simplice per mezu d'una sola definizione: :<math>x_i = { \det(A_i) \over \det(A)}</math> induve <math>A_i</math> hè a matrice furmata rimpiazzendu a ''i-''esima culonna di A cù u vettore di i termini cunnisciuti. U determinante di a matrice pò esse calculatu à priori; dunque basta u calculu di n+1 determinanti per risolve u sistema. U determinante hè di regula definitu per mezu di u [[sviluppu di Laplace]], chì furnisce direttamente un [[algoritmu ricursivu]]: :<math>\det(A_k) = \sum_{i = 1}^n(-1)^{i+k} a_{i,k} \det(A_{i,k})</math> induve <math>a_{i,k}</math> hè l'elementu di coordinate i,k è <math>A_{i,k}</math> hè u minore ottenutu supprimendu a i-esima riga è a k-esima culonna. A cumplessità di st'algoritmu per u calculu di u determinante hè <math>O(n!)</math>, perchè per ogni determinante d'ordine m si devenu calculà m determinanti d'ordine m-1. Sò dunque aduprati altri algoritmi cù una cumplessità megliu. Incidentalmente, tali algoritmi sò dinù à a basa di metudi più efficienti per u calculu di u determinante. Unu di questi hè u [[metudu d'eliminazione di Gauss]], basatu annantu à dui principii impurtanti. U primu hè chì dui sistemi lineari :<math>\operatorname A \operatorname x = \operatorname b</math> è :<math>\operatorname U \operatorname x = \operatorname c</math> sò uguali se U hè ottenuta rimpiazzendu e righe è e culonne di A cù e so cumbinazione lineare è se l'elementi di c sò cumbinazione lineare di l'elementi di b secondu i coefficienti di U. U secondu hè chì, per risolve un sistema triangulare (induve a matrice di i coefficienti pussede a pruprietà di triangularità), basta aduprà l'algoritmu di sustituzione in avanti o in daretu (a [[Teoria di a cumplessità computaziunale|cumplessità computaziunale]] hè <math>O(n)</math>). Si dimostra chì, per trasfurmà u sistema in triangulare, hè necessariu un algoritmu cù cumplessità <math>O(n^3)</math>. Appiichendu à stu sistema l'algoritmu di sustituzione diretta si trovanu e suluzione esatte di u sistema, è si dimostra chì a cumplessità tutale di l'algoritmu di Gauss hè sempre <math>O(n^3)</math>. Per ciò chì tocca à a cumplessità spaziale: * l'algoritmu basatu annantu à a regula di Cramer richiede solu una variabile addiziunale, induve memorizà u determinante di a matrice di i coefficienti; dunque a so cumplessità hè minima: <math>O(n^2)</math> (vale à dì <math>n^2</math> per memorizà a matrice di i coefficienti, <math>2n</math> per memorizà u vettore di i termini cunnisciuti è e suluzione, più un spaziu anch'ellu paru à n per u calculu di i determinanti); * l'algoritmu di Gauss ùn richiede altru spaziu fora di quellu necessariu per memorizà a matrice di i coefficienti è u vettore di i termini cunnisciuti. À a fine di l'algoritmu, u vettore di i termini cunnisciuti cuntene a suluzione. A so cumplessità spaziale hè dunque anch'ella minima: <math>O(n^2)</math>. == Strutture di dati == A maiò parte di l'algoritmi si serve di tecniche per raprisentà è urganizà i dati aduprati in u calculu è tale raprisentazione, chjamate strutture di dati, ùn sò micca necessariamente altrettantu sofisticate chè l'algoritmu chì l'adopra: algoritmi simplici ponu richiede strutture di dati cumplesse è viceversa. Per facilità è [[Astrazione (informatica)|astratte]] a gestione è l'interazzione cù strutture di dati cumplesse, sò sviluppati algoritmi apposta chì implementanu l'operazione più cumune da fà annantu à elle. Esempii di strutture di dati cumune sò i [[Array|vettori]], e [[lista (informatica)|liste]], e [[coda (informatica)|code]], e [[pila (informatica)|pile]], l'[[albero (informatica)|arburi]] è i [[grafo|grafi]]. == Catalugazione di l'algoritmi == L'algoritmi sò raggruppati è catalugati secondu a so funzione o e tecniche aduprate per realizà li; tuttavia, una classifica rigorosa è cumpleta hè oramai diventata impussibule. In [[informatica]] hè pussibule catalugà l'algoritmi in: * [[Algoritmu iterativu|Algoritmi iterativi]] * [[Algoritmu ricursivu|Algoritmi ricursivi]] * [[Algoritmu d'urdinamentu|Algoritmi d'urdinamentu]] * [[Algoritmu di ricerca|Algoritmi di ricerca]] ** [[Ricerca sequenziale]] *** [[Ricerca sequenziale cù sentinella]] ** [[Ricerca binaria]] * [[Algoritmu geneticu|Genetichi]] evolutivi * [[Particle Swarm Optimization|Swarm Intelligence]] * [[Algoritmu cumminatoriu]] * [[Codice automudificante]] * Cunversione è codificazione ** [[UUencode/UUdecode]] ** [[Multipurpose Internet Mail Extensions|MIME]] * [[Cumpressione di dati|Algoritmi di cumpressione]] ** Senza perdita d'infurmazione: *** [[Run-length encoding]] **** [[PackBits]] **** [[PCX]] *** Codificazione à riduzzione lucale d'[[Entropia (teoria di l'infurmazione)|entropia]] **** [[Codificazione di Huffman]] **** [[Codificazione aritmetica]] *** [[Codificazione à dizziunariu]] **** [[DEFLATE]] **** [[LZ77 è LZ78]] **** [[Lempel-Ziv-Welch]] (ZIP) **** [[LZMA]] *** [[Trasfurmata di Burrows-Wheeler]] *** [[Prediction by Partial Matching|PPM]] ** Cù perdita d'infurmazione *** [[Trasfurmata discreta di u cosenu]] (DCT) **** [[MPEG]] (primu metudu di cumpressione à larga diffusione basatu annantu à DCT è [[Codificazione delta|Delta]]) **** [[Joint Photographic Experts Group|JPEG]] (cumpressione d'imaghjini basata annantu à quantificazione, DCT è Huffman) *** [[Cumpressione frattale]] **** [[Trasfurmazione frattale]] *** [[Wavelet]] **** [[MP3]] (cumpressione audio basata annantu à una cumpressione simile à wavelet è DCT) **** [[JPEG2000]] (cumpressione d'imaghjini chì adopra wavelet, Huffman è quantificazione) Parechje categurie d'algoritmi sò strettamente ligate à l'urganizazione di i dati in memoria ([[struttura di dati|strutture di dati]]). === Altri algoritmi === {{div col|cols=3}} * [[Informatica quantistica|Algoritmi quantistichi]] * [[Algoritmu Apriori]] * [[Algoritmu di Berger]] * [[Algoritmu di Sturm]] * [[Algoritmu in linea]] * [[Algoritmu di rilevazione di u pitch]] * [[Algoritmu di sommatoria di Kahan]] * [[Algoritmu d'Euclide]] * [[Algoritmu di prostaferesi]] * [[Algoritmu di pattern matching nantu à stringhe]] * [[Algoritmu Doomsday]] * [[Algoritmu di Dijkstra]] * [[Algoritmu di Boyer-Moore]] * [[Algoritmu di Knuth-Morris-Pratt]] * [[Algoritmu di Prim]] * [[Algoritmu di Gauss-Newton]] * [[Algoritmu di a linea di Bresenham]] * [[Algoritmu di u simplessu]] * [[Algoritmu di e culunie di furmicule]] * [[Algoritmu di u banchieru]] * [[Algoritmu di u panatteru]] * [[Algoritmu di l'ascensore]] * [[Algoritmu di u puzzle]] * [[Algoritmu di u bigliettu]] * [[Algoritmu di u spaccone]] {{div col end}} == Note == <references/> [[Categoria:Matematica]] [[Categoria:Informatica]] 6fr38gdxs6f8gebtwev170rljxvrpjj