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 10595 406801 351296 2026-10-04T16:06:02Z Fausta Samaritani 15085 file, fix 406801 wikitext text/x-wiki [[File:Arcos de Jalón (2007) 01.jpg|thumb|250px|right|Arcos de Jalón]] [[Image:{{PAGENAME}} (Soria) Mapa.svg|thumb|right|200px|{{PAGENAME}}]] '''{{PAGENAME}}''' hè una [[cumuna]] [[Spagna|spagnola]] di a [[pruvincia di Soria]], in a cumunità autonoma di [[Castiglia è León]]. == Storia == == Giugrafia == == Monumenti == == Demugrafia == == Rifarenzi == == Ligami == [[Categoria:Pruvincia di Soria]] 91jc4vf8d9tn4s4vdeanzdgf38vvwxh 0 10634 406802 332067 2026-10-04T16:09:07Z Fausta Samaritani 15085 file, fix 406802 wikitext text/x-wiki [[File:Cihuela - 006 (47207305802).jpg|thumb|250px|right|Cihuela]] [[Image:{{PAGENAME}} (Soria) Mapa.svg|thumb|right|200px|{{PAGENAME}}]] '''{{PAGENAME}}''' hè una [[cumuna]] [[Spagna|spagnola]] di a [[pruvincia di Soria]], in a cumunità autonoma di [[Castiglia è León]]. == Storia == == Giugrafia == == Monumenti == == Demugrafia == == Rifarenzi == == Ligami == [[Categoria:Pruvincia di Soria]] m5c37wuvp7lx0ly99jvqaky8u00s36t 0 14876 406809 406399 2026-10-05T07:10:22Z Fausta Samaritani 15085 fix, link 406809 wikitext text/x-wiki {{c-supranu}} [[File:revolutionary Joyce.jpg|thumb|right|200px|James Joyce]] [[Scrivanu]], dramaturgu è pueta in [[lingua inglese]]. '''James Augustine Aloysius Joyce''' hè natu à [[Dublinu]] u [[2 di ferraghju]] di u [[1882]] è hè mortu à [[Zurigu]] u [[13 di ghjennaghju]] di u [[1941]]. == Biugrafia == == Opere principale == [[File:Joyce - Dubliners, 1914 - 3690390 F.jpg|thumb|upright|''Dubliners'', [[1914]]]] === Prosa === - [[1914]]: ''Dubliners''.<br> - [[1916]]: ''A Portrait of the Artist as a Young Man''.<br> - [[1922]]: ''Ulysses''.<br> - [[1939]]: ''Finnegans Wake''.<br> - [[1944]]: ''Stephen Hero''.<br> === Puesia === - [[1907]]: ''Chamber Music''.<br> - 1914: ''Giacomo Joyce''.<br> - [[1927]]: ''Pomes Penyeach''.<br> - [[1936]]: ''Collected Poems''.<br> === Tiatru === - [[1918]]: ''Exiles''.<br> [[Categoria:Scrivanu|Joyce, James]] [[Categoria:Biugrafia|Joyce, James]] [[Categoria:Irlandesu|Joyce, James]] ez80owtl0dnejunura2owfp4obqc3l9 0 19810 406803 388232 2026-10-05T00:13:10Z InternetArchiveBot 17916 Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.6 406803 wikitext text/x-wiki In [[Corsica]], dapoi l'annu 800, assai immigrazioni ebreie si sò prudutte. Durante seculi sò vinuti da l'Egittu, da Napuli, Paduva, [[Genuva]], [[Milanu]] è [[Turinu]]. == Prima Immigrazione Mizrahim == A storia di i Ghjudei in [[Corsica]] data da l'annu 800, quandu una grande immigrazione vinuta da l'Egittu s'impiantò in u [[Pumonti]] di a [[Corsica]] ; una grande parte di issi [[ebrei]] mizrahim scrivìa è parlava l'[[ebreu]]. A più grande parte di elli si sò stallati cerca di un paese numatu [[Livìa]], lucalizatu in terre cerca di [[Portivechju]]. Più tardi, a cummunità si hè dispersa dapertuttu in [[Corsica]]. In alcuni paesi di e muntagne, chjese pussedanu sempre tracce di documenti scritti in [[ebreu]] cerca di quelli scritti in [[latinu]]. == Immigrazione di l'[[ebrei]] di l'[[Italia]] meridiunale == Tra l'anni 1500 è 1530, milli ebrei vinuti da Napuli è di L'[[Italia]] meridiunale anu fughjitu e persecuzioni è si sò stabiliti in e muntagne di u centru di a [[Corsica]]. == Immigrazione di l'ashkenaziti di Paduva è di l'[[Italia]] di u Nordu == [[File:Casata Padovani.jpg|miniatura|Casata Padovani, da l'ebrei di u Ghetto di Paduva]] === Ashkenaziti di Paduva === Tra l'annu 1590 è l'annnu 1684, l'[[ebrei]] ashkenaziti di Paduva in u [[Venetu]] sò ubbligati di vive in un ghetto dapoi 1516. Issu periodu fù pienu di viulenze contru à a cummunità ebrea. Una grande parte decide dopu issi disastrosi avvenimenti di emigrà in [[Corsica]]. L'abitanti i chjamavanu i Padovani, Issa casata ghjè assai sparsu oghje in l'isula. === Ashkenaziti di l'[[Italia]] di u Nordu === U finomenu di persecuzione cuntinua in [[Italia]] di u Nordu è l'immigrazione ghjudea a più cunnisciuta succede trà l'anni 1750 è 1769. [[Pasquale Paoli]] fù venne in [[Corsica]] trà 5000 è 10000 [[Ebrei]] di u nordu di l'[[Italia]] : da [[Milanu]], da [[Turinu]], da Paduva è da [[Genuva]], per fà rivive l'isula dopu i 4 seculi d'occupazione genuvesa. Sò cunsiderati in [[Corsica]] cume uguali, [[Pasquale Paoli]] dichjara chì "L'Ebrei anu i listelli diritti chì i Corsi perchè cundividenu a listessa sorte". L'ebrei pudìanu cusì praticà liberamente u so cultu, ciò ch'ùn era micca u casu in a più grande parte di i paesi di u mondu. == [[Israele]] == [[File:Amicizia Corsica Israele.jpg|miniatura|Associu Amicale trà a Corsica è Israele]] A [[Corsica]] hè u solu locu di tutta l'[[Auropa]] induve nessunu attu antisemitu ùn hè mai statu dichjaratu è durante a [[Siconda Guerra Mundiale]], nessunu ghjudeu di [[Corsica]] hè statu dinunciatu. In 1947, a [[Corsica]] cuntribuisce à a criazione di u Statu d'[[Israele]] è un associu [[Corsica]]-[[Israele]] si hè messa in piazza per ligà e duie cummunità. == Ligami Esterni == * http://www.terredisrael.com/infos/juifs-et-corses-freres-darmes/ {{Webarchive|url=https://web.archive.org/web/20170608060405/http://www.terredisrael.com/infos/juifs-et-corses-freres-darmes/ |date=2017-06-08 }} * [https://web.archive.org/web/20170101001140/http://larchemag.fr/2016/06/23/2615/didier-long-entre-la-corse-et-juifs-cest-une-histoire-dame/ http://larchemag.fr/Didier Long-entre la Corse et Juifs c'est une histoire d'âme/] * http://www.harissa.com/news/article/lhistoire-des-juifs-en-corse * https://jforum.fr/les-juifs-de-corse-une-histoire-si-meconnue.html == Articuli Cunnessi == * [[Storia di a Corsica]] * [[Ebrei]] * [[Israele]] * [[Corsica]] * [[Italia]] * [[Venetu]] * [[Genuva]] * [[Pasquale Paoli]] [[Categoria:Storia di a Corsica]] a8pxfarofvmywqe4qu4fkny3m1ko25a 0 20377 406814 382350 2026-10-05T11:05:40Z Fausta Samaritani 15085 fix, link 406814 wikitext text/x-wiki [[File:Muḥammad_ibn_Mūsā_al-Khwārizmī.png|thumb|200px|Ritrattu di Muhammad Ibn Mūsā al-Khuwārizmī]] '''Muhammad Ibn Mūsā al-Khuwārizmī''', generalmente chjamatu à '''Al-Khwarizmi''', natu in l'anni [[780]], originariu di Khiva in a rigione di u Khwarezm chì li hà datu u so nome, in l'attuale [[Uzbekistanu]], mortu ver' di [[850]] à [[Bagdad]], hè un [[Matematica|matematicu]], [[Geografia|geugrafu]], astrologu è [[Astrunomia|astrunomu]] persicu, membru di a Casa di a sapienza di Bagdad.<ref>'Ss'articulu pruvene in parte da l'articulu currispundente di a wikipedia in [[Lingua francese|francese]].</ref> I so scritti, ridatti in [[lingua araba]], po' tradutti in [[Lingua latina|latinu]] à parte si da u [[XII sèculu]], anu permessu l'intruduzione di l'[[algebra]] in [[Europa]]. A so vita s'hè svolta in tutalità à l'epica di a dinastia abbaside. U so nome hè à l'origine di a parola [[algoritmu]] è u titulu di unu di e so opere (Abbriviatu di u calculu da a risturazione è a cumparazione) à l'origine di a parola algebra. L'utilisazione di i cifri arabi è a so diffusione in u Mediu Oriente è in Europa sò duvute à un antru di i so libri numinatu ''Trattatu di u sistemu di numerazione di l'Indiani'' chì fubbe diffusu per via di a lingua araba in tuttu l'imperu abbaside. Al-Khawarizmi hà classificatu l'algoritmi esistenti, in particulare sient'è i so criterii di terminazione, ma ùn rivendicheghja micca a so invinzione: l'algoritmu u più cunnisciutu di u mondu hè quellu d'[[Euclide]], à u prugramma d'insignamentu di tutti i paesi, è i primi algoritmi cunnisciuti u fubbenu senza surpresa in un paese chì duvia gistisce i calculi elaburati di l'impositu : à Babilonia. Ùn ci vole micca à cunfonde 'ssu matematicu incù l'enciclopedistu persicu, Muhammad ibn Ahmad al-Khwarizmi, autore di Mafâtih al-'Olum (''E chjave di e scenze''), enciclupedia scritta in l'anni [[976]]-[[997]]. ==Biugrafia== L'avenimenti di a vita d'Al-Khwarizmi sò pocu cunnisciuti. Hè prubabilmente natu in Khiva (~780). Esistenu numerose tracce di i so travagli scentifichi. Matematicu, storicu è geografu, hè cunsideratu cum'è "u babbu di l'algebra è u prima vulgarisatore di u sistemu decimale pusiziunale" (ch' ellu improda à a cultura indiana), hè, in i so tempi, cunnisciutu in quant'è astrunomu. More ver' di [[850]]. ==Travagli== ===Matematiche=== [[Image:Image-Al-Kitāb al-muḫtaṣar fī ḥisāb al-ğabr wa-l-muqābala.jpg|thumb|250px|right|A prima pagine di u ''Kitāb al-mukhtaṣar fī ḥisāb al-jabr wa-l-muqābala''.]] Al-Khwarizmi hè l'autore di parechje opere di matematica. A più celebra, intitulata Kitābu 'l-mukhtaṣar fī ḥisābi 'l-jabr wa'l-muqābalah (كتاب المختصر في حساب الجبر والمقابلة), o ''Abbriviatu di u calculu da a risturazione è a cumparazione'', publicatu sottu à u regnu d'Al-Ma'mūn ([[813]]-[[833]]), "hè cunsideratu cum'è u prima manuale d'algebra." 'Ssu libru cuntene sei capituli. Ùn cuntene alcunu cifru. Tutte l'equazione sò sprimate incù e parole. U quatratu di a scunnisciuta hè numinatu "u quatratu" o mâl, a scunnisciuta hè "a cosa" o shay (šay), a radica hè u ghjidr, a custante hè u dirham o adǎd. U termine al-jabrn fubbe ripigliatu da l'Europei è diventò più tardi a parola algebra. [[Diofante d'Alissandria]], cunsideratu cum'è u "precursori di l'algebra", ùn fù prubabilmente micca cunnisciutu da Al-Khwarizmi. Difatti, a prima traduzzione in arabu di l'Aritmetiche ùn apparì ch'è parechji dicennii dopu à l'Abbriviatu di u calculu da a risturazione è a cumparazione, à a fine di u [[IX sèculu]], vene à dì circa cinquanta anni dopu a morte d'Al-Khwarizmi. Cusì, u so acquistu incù 'ssu "prima manuale" hè tale ch'ellu cunduce à cunsiderà Al-Khwarizmi cum'è "u babbu di l'algebra". Un antra opera, chì l'originale in arabu hè sparitu, Kitābu 'l-ĵāmi` wa 't-tafrīq bi-ḥisābi 'l-Hind (كتاب الجامع و التفريق بحساب الهند, "Libru di l'addizione è di a suttrazzione siont'è u calculu indianu"), discrive u sistemu di numerazione decimale (ch' ellu hà ossirvatu ind'è l'Indiani). Fubbe u vettore di a diffusione di 'ssi cifri in u Mediu Oriente è in u Califfatu di [[Cordova]], induve Gerbert d'Aurillac si ne face struisce. Diventatu più tardi papa di l'annu Milla sottu à u nome di [[Silvestru II]], Gerbert l'impunerà à u mondu cristianu dendu li, vistu a so pruvinienza di Cordova, u nome di cifri arabi. ===Astronumia=== Al-Khwarizmi hè l'autore di un ''zij'', publicatu in u [[830]], cunnisciutu sottu à u nome di ''Zīj al-Sindhind'' ("Tavula indiana"). 'Sse tavule, cumposte sottu à u regnu d'Al-Ma'mūnn, sò una compilazione di fonte indiane è greche. Certi elementi di e Tavule faciule di Tolomeu sò ripigliate. I metudi di calculu, in particulare l'utilisazione di u sinu sò inspirate da l'indiani è si basanu annantu à un'opera indiana offerta, in u [[773]], à u califfu Al-Mansur è tradutta da Muhammad al-Fazari. S'appoghjanu annantu à u calindariu persianu è piglianu per origine di e longitudine u meridianu d'Arimn. 'Sse tavule sò e più anziane tavule di u mondu araba chì ci fusssenu pervenute. Di tradizione indiana, vale à dì prisintendu e tecniche di calculi, senza teuria planitaria, ebbenu una grande influenza in a custituzione di e tavule astrunomiche di l'Occidente arabu. 'Ssa opera, ripigliata da l'astrunomu di Spagna Maslama al-Mayriti, po' tradutta ver' di u [[1126]] da Adelard di Bath, hè una di e trè fonte arabe principale avendu servutu à l'iniziazione di l'astrunomi latini. Entrenu per una parte in a custituzione di e Tavule di Tolede chì ebbenu una grande influenza annantu à l'astronumia europea di u [[XIII seculu]]. Al-Khwarizmi hè dinù l'autore di trè opere cunsacrate à i strumenti: un'opera minore annantu à u quadrante sulariu, un [[libru]] annantu à a rialisazione di l'astrolabiu è un libru annantu à l'usu di l'astrolabiu. A so opera annantu à u calindariu ghjudeiu hè una di i più anziani esposta annantu à u sughjettu. Ci espone u frastagliu di l'annu, a pusizione di e stelle à certi attimi chjave. Hè inoltre l'autore di e prime tavule cunnisciute per arrigulà l'ore di e prighere di a ghjurnata. Cum'è numerosi astrunomi di 'ssa epica, Al-Khwarizmi hè dinù astrologu. Sient'è u storicu Tabari, Al-Khwarizmi predisce, incù un gruppu d'astrologhi, a longa durata di vita di u califfu (è i cinquanta anni chì li rimanianu à campà) mentre quest'ultimu morse deci ghjorni dopu a predizzione. === Storia è geugrafia === U so ''Trattatu di Geugrafia'' hè inspiratu da quellu di Tolomeu, arricchitu da i rapporti di i marcanti arabi riguardu à u mondu islamicu. Ci dà a longitudine è a latitudine di punti di prima trinca di u mondu cunnisciutu (cità, muntagna, isule, è cetera). Avaria scrittu dinù una cronaca storica di a so epica chì ùn hè cunnisciuta da noi ch'è per via di i riferimenti ch'elli ne facenu i storichi più ricenti. == Omagi == * U crateru [[Al-Khwarizmi (crateru)|Al-Khwarizmi]]. * Dui astiroidi : [[(11156) Al-Khwârizmî]] è [[(13498) Al Khwârizmî]]. == Note == <references/> == Bibliugrafia == * Bartel Leendert van der Waerden, ''A History of Algebra. From al-Khwarizmi to Emmy Noether'', Springer, 1985 (in [[ingua inglese|inglese]]). * Corona Brezina, ''Al-Khwarizmi. The Inventor of Algebra'', Rosen Central, 2005 (in inglese). == Da vede dinù == * [[Algebra]] * [[Algoritmica]] * [[Cifri arabi]] * [[Matematichi arabi]] * [[Al-Khwarizmi (crateru)|Crateru Al-Khwarizmi]] [[Categoria:Matematicu]] [[Categoria:Algoritmica]] [[Categoria:Astrunomu]] [[Categoria:Biugrafia]] c1jrf75hi7dzgi5r821xn5bze8ldgwu 0 21979 406804 406649 2026-10-05T00:13:36Z InternetArchiveBot 17916 Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.6 406804 wikitext text/x-wiki {| align="right" rules="all" cellpadding="3" cellspacing="0" border="0" style="margin: 0 0 1em 1em; border: 1px solid #999; background-color: #CCFFCC" ! colspan="3" style="background:#66CC66" | {| style="background:#66CC66" align="center" width="100%" | padding=0px| ! style="background:#66CC66" width="100%" |<span style="color:white; font-size:large;">'''L'emera'''</span> | padding=0px| |} |----- | colspan=2 align="center" cellpadding="0" | [[File:Cytisus_scoparius_FlowersCloseup2_2009April26_SierraMadrona.jpg|250px]] |----- ! colspan=2 align="center" cellpadding="0" | <span style="color:black; font-size:x-small;">Cytisus scoparius</span> |----- ! colspan=2 bgcolor="lightgreen" | [[Classifica scentifica]] |----- | Regnu | ''[[Plantae]]'' |----- | Divisione | ''[[Magnoliophyta]]'' |----- | Classa | ''[[Magnoliopsida]]'' |----- | Ordine | ''[[Asterales]]'' |----- | Famiglia | ''[[Fabaceae]]'' |----- | Generu | ''[[Cytisus]]'' |----- | align="center" bgcolor="lightgreen" colspan="2" | [[Nome binuminale]] |----- | align="center" colspan="2" |''Cytisus scoparius''<br /><span style="color:black; font-size:x-small;"> [[Aiton]], 1753</span> |----- | align="center" colspan=2 align="center" cellpadding="0" | [[File:Cytisus_scoparius_0001.JPG|250px|L'emera]] |----- |} L' '''èmera''' (o ''emara'') (''[[Cytisus scoparius]]'') hè una pianta chì face parte di a famiglia di e [[Fabaceae]]. <ref>'Ss'articulu pruvene in parte da l'articulu currispundente di a wikipedia in talianu.</ref> ==Etimolugia== U nome genericu (''Cytisus'') sient'è certe etimologie vene da a parola [[Lingua greca|greca]] ''kutisus'': un nome per una spezia di trifogliulu (in riferimentu à a forma di e casce). Sient'è altre etimologie "Cytisus" hè un nome [[Lingua latina|latinu]], pruvenendu da una parola greca preesistente ''kytisos'' d'etimologia incerta (puderia pruvene di un idioma di i primi abitanti di l'Asia Minore). Sient'è altre etimologie, deriveghja dinù a parola greca ''kýtos'' (''cavità''). U nome di a spezia (''scoparius'') significheghja ''spazzola'' (o simile à una spazzola) è face allusione à u portu di a pianta. U binomiu scentificu di 'ssa pianta era à l'iniziu ''Spartium scoparium'', prupostu da u botanicu Carl von Linné ([[1707]] - [[1778]]), biolugu è scrittore svedese, cunsideratu cum'è u babbu di a classifica scentifica muderna di l'organismi vivi, in a publicazione ''Species Plantarum'' di [[1753]], mudificatu più tardi in ''Cytisus scoparius'' attualmente accittatu, prupostu da u botanicu alemanu Johann Heinrich Friedrich Link ([[1767]] - [[1851]]), biolugu è naturalistu<ref>In a publicazione ''Enumeratio Plantarum Horti Regii Berolinensis Altera''. Berolini. Berlinu - 2 : 241. 1822 di 1822.</ref>. ==Descrizzione== L'emera hà un'altezza di 60 cm à 1-3 metri. Si tratta di piante vivace, legnose à u basamentu assai ramificatu, è ancu robustu, incù i bucci di inguernamentu piazzati à un'altura cumpresa trà 12 è 20 cm sopra à a terra (50 cm massimu). Mentre a staghjone freta, e parte erbacee si disseccanu è sole e parte legnose fermanu vivi. ===Picciolu === U picciolu hè verde, erettu, angulosu (l'anguli di i rami sò taglivi), duru, incù e ramificazione dritte ma soffice. A superficia hè tisgia. ===Foglie === E foglie sò cadente, stipulate è chjuche; sò picciulate (u picciolu hè sciacciatu) è trifugliate. E casce superiore sò sessile è simplice. Taglia di i sigmenti laterali: larghezza 4-6 mm; lunghezza 10-15 mm. A cascia cintrale hè 1/3 più maiò ch'è e laterale. A pubescenza hè furmata da corti peli ricciulati annantu à i piccioli è annantu à a pagina inferiore di e casce. ===Infiuriscenza === [[File:Cytisus_scoparius_0003.JPG|thumb|150px|left|U fiore di l'emera]] L'infiuriscenza hè cumposta da fiori isulati piazzate à l'ascella di e casce nurmale. I fiori sò profumati è colurite di giallu, sò ermafroditi. Taglia di un solu fiore: 20-25 mm. U caliciu hè tisgiu ed hè di tipu tubulariu assai più longu ch'è largu è si termineghja incù 5 denti acuti; u caliciu hè in duie parte chì i 5 denti sò ragruppati in duie denti superiori corte (duie labbri corte) è trè inferiore più longhe. A lunghezza di u caliciu hè di circa 6-7 mm. A curolla pussede 5 petali. U fasciame misura trà 20 è 23 mm di longu. Dimensione di a bandera: larghezza 20 mm; lunghezza 21-23 mm. A fiuritura occorre da [[maghju]] à [[ghjugnu]]. ===I frutti === U fruttu hè un curnochjulu neru, sciacciatu è pilosu. Taglia di u curnochjulu: larghezza 10 mm; lunghezza 30-50 mm. ==Distribuzione== A zona d'origine hè europea, sottuatlantica. A spezia priferisce e terre silicee, e chjarine, i posti à mezu ombra, i boschi di culline (sempre annantu à terra [[Acidu|acida]]), ma dinù a garriga è in particulare a garriga bassa, e ghjinepare, e liccete, i vitulli è e castagnete. U substratu priferitu hè siliceu incù un pH acidu. Riguardu à a ripartizione altitudinale, 'sse piante si trovanu insin'à 1400 m d'altitudine. Friquentanu dunque i livelli di vegetazione seguenti: cullinare, muntosu è in parte subalpinu. ==Riproduzione== - Impullinazione: l'impullinazione hè effittuata da l'insetti.<br> - Riproduzione: A fecondazione s'effittueghja per u più per impullinazione di i fiori.<br> - Dispersione: i granelli caschendu in terra sò spergugliati per u più da l'insetti di a famiglia di e furmicule.<br> ==Sistematica== ===Tassonumia=== Parechji sinonimi di ''Cytisus scoparius'' sò: - ''Cytisus scoparius sulphureus'' Goldring.<br> - ''Genista andreana'' Puiss.<br> - ''Genista scoparia'' (L.) Lam.<br> - ''Sarothamnus scoparius'' (L.).<br> ===Spezie simile=== L'emera pò essa cunfusa incù l'[[urticapra]]. ===Sinonimi === ''Cytisus scoparius'' hà avutu differente numenclature in u tempu. A lista seguente indicheghja uni pochi di i più sinonimi frequenti: - ''Genista andreana'', Puiss.<br> - ''Genista scoparia'', (L.) Lam.<br> - ''Genista scoparia'', (L.) Lam. var. maritima Rouy (sinonimo della sottospecie ''maritimus'').<br> - ''Sarothamnus bourgaei'', Boiss.<br> - ''Sarothamnus oxyphyllus'', Boiss.<br> - ''Sarothamnus vulgaris'', Wimm.<br> - ''Spartium scoparium'', L.<br> ==Usi== Era imprudata l'emera per spazzà i forni. Sicondu Paulu Simonpoli<ref>Simonpoli (1982), p. 57.</ref> "Omu ni facia monduli per spazzà u fornu caldu, quandu ùn ci era micca scopa". ==Lessicu== L'emera hè ancu chjamata l'èmara o l'èrmera.<ref>U Muntesu, p. 497.</ref> == Da vede dinù == * a [[flora di Corsica]] * a [[ghjinestra]] * l'[[urticapra]] ==Note== <references/> == Bibliografia == * [https://web.archive.org/web/20120111155047/http://adecec.net/adecec-net/parutions/pdf/corsesetplantes.pdf] Conrad, Marcella, ''I corsi è e piante salvatiche, avà è innanzi'', [[1981]], Adecec. * Ciavatti, Petru (dir. redazzione) Dizziunariu ''U Muntese'', 1984, Albian. * Gamisans, Jacques (1996), ''A flora endemica di Corsica'', Edisud (in francesu). * [http://www.culturecommunication.gouv.fr/content/download/42396/338526/version/1/file/Ethno_Simonpoli_1982_072a.pdf] Paulu Simonpoli, ''E piante salvatiche - Cunniscenze è usi'', 1982, Parcu Naturale di Corsica {{Webarchive|url=https://web.archive.org/web/20120111155047/http://adecec.net/adecec-net/parutions/pdf/corsesetplantes.pdf |date=2012-01-11 }} [[Categoria:Flora di Corsica]] [[Categoria:Fabaceae]] 46gs0wxcyepnwjsqh3l5t8zysd2rca8 0 22504 406815 382385 2026-10-05T11:52:30Z Fausta Samaritani 15085 fix, link 406815 wikitext text/x-wiki Un '''numeru''' hè un ogettu [[Matematica|matematicu]] imprudatu per cuntà, misurà è etichettà.<ref>'Ss'articulu pruvene in parte da l'articulu currispundente di a wikipedia in inglese.</ref> L'esempii originali sò i numeri naturali 1, 2, 3, 4, è tira è tocca. I numeri ponu esse riprisintati in u linguaghju da parole-numeri. Più universalmente, i numeri individuali ponu esse riprisintati da simbuli, chjamati numerali; per indettu, "5" hè un numerale chì riprisenta u numeru ''cinque''. Cum'ellu ùn hè micca pussibile di mimurizà ch'è un numeru relativamente debule di simbuli, i ciffri di basa sò di solitu organizati in un sistemu numerale, chì hè una manera organizata di riprisintà qualsiasi numeru. U sistemu numerale u più currente hè u sistemu numerale indùarabu, chì permette di riprisintà qualsiasi numeru cù l'aiutu di una cumbinazione di deci simbuli numerichi fundamentali, chjamati ''ciffri''. Oltre u so usu per a cuntera è a misura, i ciffri sò à spessu usati per l'etichette (cum'è i numeri di [[telefunu]]), per i cumandi (cum'è i numeri di seria) è per i codici (cum'è l'[[ISBN]]). In l'usu currente, un numerale ùn hè micca chjaramente distintu da u numeru ch'ellu riprisenta. In matematiche, a nuzione di numeru s'hè stesa à u filu di i seculi per inchjude "0", i numeri negativi, i numeri raziunali tali una mità 1/2, i numeri reali tali a "radica quatrata" di 2 è π, è i numeri cumplessi chì stendenu i numeri reali incù una radica quatrata di -1 (è e so cumbinazione incù numeri reali aghjunghjendu ne o suttraiendu ne i so multiplici). I calculi incù i numeri sò effittuati cù l'aiutu di operazione aritmetiche, chì e più famigliare sò l'addizione, a suttrazzione, a multiplicazione, a divisione è a spunenziazione. U so studiu o u so usu hè chjamatu [[aritmetica]], un termine chì pò ancu fà riferimentu à a teuria di i numeri, u studiu di e pruprietà di i numeri. Oltre u so usu praticu, i numeri anu un significatu culturale in u mondu sanu. Per indettu, in a sucità occidentale, u numeru 13 hè à spessu cunsideratu cum'è sfurtunatu, è "un milione" pò significà "assai", piuttostu ch'è una quantità esatta. Bench'ella sia oghje cunsiderata cum'è una pseudoscenza, a cridenza in un significatu misticu di i numeri, cunnisciuta sottu u nome di numerolugia, hà impregnatu u pinsamentu anticu è [[Medioevo|medievale]]. A numerolugia hà assai influinzatu u sviluppu di e matematiche greche, stimulendu u studiu di numerosi prublemi in a teuria di i numeri chì sò sempre d'attualità. Mentre u [[XIX sèculu]], i matematichi anu cuminciatu à sviluppà numerose astrazzione differente chì spartenu certe pruprietà di i numeri, è ponu esse cunsiderate cum'è un'estinsione di u cuncettu. Frà i primi, omu trova i numeri ipercumplessi, chì cunsistenu in diverse estinsione o mudifiche di u sistemu di i numeri cumplessi. In e matematiche muderne, i sistemi di numeri (insemi) sò cunsiderati cum'è esempii spiciali impurtanti di categurie più generale tale l'anelli è i campi, è l'appiicazione di u termine "numeru" hè una quistione di cunvinzione, senza significatu fundamentale. ==Storia== ===Numeri=== Ci vole à distingue i ciffri da i numerali, i simbuli imprudati per riprisintà i numeri. L'[[Egitto|Egizziani]] anu invintatu u prima sistemu numerale ciffratu, è i [[Grecia|Grechi]] anu suvitatu fendu currisponde i so ciffri di cuntera à i santacroci ionicu è doricu. I ciffri rumani, un sistemu chì imprudava e cumbinazione di lettere di u santacroce rumanu, sò firmati duminanti in Europa sinu à a diffusione di u sistemu numerale superiore indùarabu ver' di a fine di u [[XIV sèculu]], è u sistemu numerale indùarabu ferma u sistemu u più currente per riprisintà i numeri à i ghjorni d'oghje. A chjave di l'efficenza di u sistemu era u simbulu di u zeru, chì hè statu sviluppatu da l'anziani matematichi indiani ver' di 500 dopu à GC. ===Prima utilisazione di i numeri=== L'ossi è altri artefatti sò stati scuperti incù marche tagliate in elli ch'è assai persone credenu ch'elle sò marche di punteghju. 'Sse marche di punteghju ponu esse state imprudate per cuntà u tempu sculatu, cum'è i numeri di ghjorni,d i i cicli lunarii o guardà i rigistri di quantità, cum'è animali. Un sistemu di punteghju ùn hà micca cuncettu di valore di piazza (cum'è in a nutazione decimale muderna), ciò chì limiteghja a so ripprisintazione di i grandi numeri. Però, i sistemi di punteghju sò cunsiderati cum'è u prima tipu di sistemu numerale astrattu. U prima sistemu cunnisciutu incù valore di piazza era u sistemu mesuputamicu in basa 60 (ver' di 3400 a.C.) è u più sistemu anzianu cunnisciutu in basa 10 data di 3100 a.C. in [[Egittu]]. ===Zeru=== A prima utilisazione documintata cunnisciuta di u zeru data di [[628]] d.C. è apparisce in u ''Brāhmasphuṭasiddhānta'', l'opera principale di u matematicu indianu [[Brahmagupta]]. Ci tratta u 0 cum'è un numeru è discute l'operazione cuncirnendu lu, in particulare a divisione. À quella epica (u [[VII sèculu]]), u cuncettu avia chjaramente aghjuntu u Cambogia sottu forma di ciffri khmer, è a documentazione mostra ch'è l'idea s'hè dopu sparta in [[China]] è in u mondu islamicu. [[File:Khmer_Numerals_-_605_from_the_Sambor_inscriptions.jpg|thumb|250px|right|U numeru 605 in ciffri khmer, tiratu da una scrizzione datendu di u [[683]] d.C. cù l'utilisazione prumaticcia di u zeru]] U ''Brāhmasphuṭasiddhānta'' di Brahmagupta hè u prima libru chì minziuneghja u zeru cum'è un numeru, dunque Brahmagupta hè di solitu cunsideratu cum'è u prima à furmulà u cuncettu di zeru. Hà datu e regule d'usu di zeru incù numeri negativi è pusitivi, cum'è "zeru più un numeru pusitivu hè un numeru pusitivu, è un numeru negativu più zeru hè u numeru negativu. U ''Brāhmasphuṭasiddhānta'' hè u più testu anzianu cunnisciutu à trattà u zeru cum'è un numeru à parte intiera, piuttostu ch'è cum'è un simpliciu ciffru di rimpiazzamentu in a ripprisintazione di un antru numeru, cum'elli facianu i Babiluniani, o cum'è u simbulu di una mancanza di quantità, cum'elli facianu [[Tolomeu]] è i Rumani. Cunvene di distingue l'utilisazione di u 0 in tantu ch'è ciffra di u so usu in quant'è ciffru di rimpiazzamentu in i sistemi di valori di rimpiazzamentu. Numerosi testi anziani usavanu u zeru. I testi babiluniani è egizziani l'usavanu. L'Egizziani apradavanu a parola ''nfr'', per designà u saldu nullu in a cuntabilità in parte doppia. I testi indiani apradavanu una parola sanscrita, ''Shunye'' o ''shunya'', per designà u cuncettu di biotu. In i testi matematichi, 'ssa parola face à spessu riferimentu à u numeru zeru. In listessu ordine d'idee, Pāṇini ([[V seculu a.C.]]) hà usatu l'operatore null (zeru) in l'Ashtadhyayi, un esempiu prumaticciu di grammatica [[Algebra|algebrica]] per a lingua sanscrita (vede ancu Pingala). L'archivie mostranu ch'è i grechi antichi simbravanu incerti inquantu à u statutu di 0 in tantu ch'è numeru: si dumandavanu "cume" nulla "pò esse qualcosa?", ciò chì hà datu locu à interessanti argumenti filusofichi è, à l'epica medievale, riligiosu annantu à a natura è l'esistenza di u zeru è di u biotu. I paradossi di Zenone d'Elea dipendenu in parte di l'interpritazione incerta di zeru. (I grechi antichi si dumandavanu ancu s'è 1 era un numeru). L'Olmechi tardivi di u centru di u [[Messicu]] anu cuminciatu à imprudà un simbulu per u zeru, un glifu di cunchiglia, in u Nuvellu Mondu, prubabilmente à u [[IV sèculu a.C.]], ma certamente in [[40 a.C.]], chì hè diventatu una parte integrante di i ciffri è di u [[calindariu maya]]. L'aritmetica maya usava a basa 4 è a basa 5 scritta in basa 20. [[George I. Sánchez]] hà signalatu in u [[1961]] un abacu "à diti" in basa 4 è in basa 5. In u [[130 d.C.]] Tolomeu, influinzatu da [[Ipparcu]] è i Babiluniani, imprudava un simbulu per u 0 (un picculu chjerchju incù una longa asta superiore) in un sistemu numerale sessagesimale imprudendu altrimente i ciffri alfabetichi grechi. Parch'è ellu era usatu solu, è micca cum'è un simpliciu sustitutu, 'ssu zeru ellinisticu hè statu u prima usu documintatu di un zeru sputicu in l'Anzianu Mondu. In i manuscritti bizantini ultiriori di a so/u so/sone Syntaxis Mathematica (Almagestu), u zeru ellinisticu s'hè trasfurmatu in a lettera greca ''Omicron'' (chì significheghja 70). Un antru veru zeru hè statu imprudatu in e tavule accantu à i ciffri rumani da 525 (prima utilisazione cunnisciuta da [[Dionisiu Exiguus]]), ma cum'è una parola (significhendu "niente"), è micca cum'è un simbulu. Quandu a divisione pruducìa 0 cum'è restu, omu usava nihil, chì significheghja dinò "niente". 'Ssi zeri medievali sò stati usati da tutti i futuri computisti medievali (calculadori di [[Pasqua]]). Un usu isulatu di a so iniziale, N, hè statu imprudatu in una tavula di ciffri rumani da Bede o un cullegu ver' di u [[725]], un simbulu sputicu di zeru. ===I numeri negativi=== U cuncettu astrattu di i numeri negativi hè statu ricunnusciutu da [[100 a.C.]]-[[50 a.C.]] in [[China]]. I Nove capituli annantu à l'arte matematicu cuntenenu i metudi per truvà l'arie di e figure; i bastunelli rossi eranu imprudati per designà i cuefficenti pusitivi, i neri per i negativi. U prima riferimentu in una opera occidentale ricolla à u [[III sèculu]] di a nostra epica in Grecia. Diofantu hà fattu riferimentu à l'equazione equivalente à 4x + 20 = 0 (a soluzione hè negativa) in l'[[Arithmetica]], dicendu ch'è l'equazione dava un risultatu assurdu. è I matematichi europei, per a maiò parte, anu resistutu à u cuncettu di i numeri negativi sinu à u [[XVII sèculu]], bench'è [[Fibonacci]] aghji autorizatu e soluzione negative in i prublemi finanziarii induve elle pudianu esse interpritate cum'è debiti (capitulu 13 di u ''Liber Abaci'', [[1202]]) è dopu cum'è perdite (in Flos). À listessa epica, i Chinesi indicavanu i numeri negativi traccendu un trattu diagunale à traversu u ciffru micca nullu u più à dritta di u numerale di u numeru pusitivu currispundente. U prima usu di i numeri negativi in un'opera europea hè statu fattu da Nicolas Chuquet à u [[XV sèculu]]. L'hà imprudati cum'è espunenti, ma l'hà qualificati di "numeri assurdi". À u [[XVIII sèculu]] dinù, era currente di ignurà i risultati negativi rinviati da equazione partendu di u principu ch'elli eranu spruvisti di sensu, cum'è [[René Descartes]] l'hà fattu incù e soluzione negative in un sistemu di cuurdinate cartesiane. ===I numeri raziunali=== Hè prubabile ch'è u cuncettu di numeri frazziunarii ricolla à a preistoria. L'anziani Egizziani usavanu a so nutazione frazziunaria egizziana per i numeri raziunali in testi matematichi tali u papiru matematicu di Rhind è u papiru di Kahun. I matematichi grechi è indiani classichi anu studiatu a teuria di i numeri raziunali in u quatru di u studiu generale di a teuria di i numeri, chì u più cunnisciutu n'hè l'Elementi d'[[Euclide]], datendu di circa [[300 a.C.]]. Frà i testi indiani, u più pertinente hè u ''Sthananga Sutra'', chì tratta ancu di a teuria di i numeri in u quatru di un studiu generale di e matematiche. U cuncettu di frazzione decimale hè strettamente ligatu à a nutazione decimale di u valore di piazza; e duie parenu esse si sviluppate à tempu. Per indettu, hè currente ch'è i sutras matematichi giaini inchjudenu i calculi d'apprussimazione di pi o di a radica quatrata di 2 in frazzione decimale. Listessa, i testi matematichi babiluniani usanu assai à spessu e frazzione sessagesimale (basa 60). ===Numeri irraziunali=== U prima usu cunnisciutu di i numeri irraziunali si trova in i Sulba Sutras indiani cumposti trà [[800 a.C.]] è [[500 a.C.]]. A prima prova d'esistenza di i numeri irraziunali hè di solitu attribuita à [[Pitagora]], più precisamente à u pitagoricu Hippasus di Metapontum, chì hà produttu una prova (assai prubabilmente geumetrica) di l'irraziunalità di a radica quatrata di 2. A storia conta ch'è Hippasus hà scupertu i numeri irraziunali pruvendu à riprisintà a radica quatrata di 2 cum'è una frazzione. Eppuru, Pitagora credia in l'assoluità di i numeri è ùn pudia accittà l'esistenza di numeri irraziunali. Ùn pudia micca confutà a so esistenza per via di a logica, ma ùn pudia micca accittà i numeri irraziunali, è dunque, sient'è allegazione à spessu rapurtate, hà cundannatu Hippasus à a morte per annigamentu, per impidisce a prupagazione di 'ssa nutizia scuncertante. [[File:Karl Weierstrass 2.jpg|thumb|250px|right|Karl Weierstrass]] U [[XVI sèculu]] hà arricatu l'accittazione europea finale di i numeri integrali è frazziunarii negativi. À u [[XVII sèculu]], i matematichi apradavanu di solitu e frazzione decimale incù una nutazione muderna. Eppuru, ùn hè eppuru ch'è à u XIX sèculu ch'è i matematichi anu spiccatu l'irraziunali in parte algebrichi è trascendentali, è anu torna intrapresu u studiu scentificu di l'irraziunali. Quessa era firmata guasi in sonnu dapoi Euclide. In u [[1872]], a publicazione di e teurie di [[Karl Weierstrass]] (da u so elevu E. Kossak), [[Eduard Heine]], [[Georg Cantor]], è [[Richard Dedekind]]. In u [[1869]], [[Carlu Méray]] avia pigliatu listessu puntu di partenza ch'è Heine, ma a teuria hè generalmente riferita à l'annu 1872. U metudu di Weierstrass hè statu espostu cumplittamente da [[Salvatore Pincherle]] ([[1880]]), è quellu di Dedekind hà ricevutu un'impurtanza supplementaria grazia à i travagli ultiriori di l'autore ([[1888]]) è à l'appruvazione di [[Paulu Tannery]] ([[1894]]). Weierstrass, Cantor è Heine fondanu e so teurie annantu à e serie infinite, mentre ch'è Dedekind fonda a soia annantu à l'idea di una tagliatura (Schnitt) in u sistemu di i numeri reali, spicchendu tutti i numeri raziunali in dui gruppi avendu certe pruprietà caratteristiche. U sughjettu hà ricevutu i cuntributi ultiriori da parte di Weierstrass, Kronecker, è Méray. A ricerca di e radiche di l'equazione quintiche è di gradu superiore hà custituitu un sviluppu impurtante, u teurema d'Abel-Ruffini (Ruffini [[1799]], Abel [[1824]]) hà mustratu ch'elle ùn pudianu micca esse risolte per via di i radicali (formule implichendu unicamente l'operazione aritmetiche è e radiche). Era dunque necessariu di cunsiderà l'inseme più largu di i numeri algebrichi (tutte e soluzione di l'equazione polinumiale). Galois ([[1832]]) hà culligatu l'equazione polinumiale à a teuria di i gruppi, ciò chì hà datu nascita à a teuria di Galois. E frazzione cuntinue, strettamente ligate à i numeri irraziunali (è duvute à Cataldi, [[1613]]), anu ricevutu l'attinzione da parte di Euler, è à u principiu di u XIX sèculu, sò state messe in evidenza da i scritti di Joseph Louis Lagrange. Altri cuntributi nutevuli sò stati fatti da Druckenmüller ([[1837]]), Kunze ([[1857]]), Lemke ([[1870]]), è Günther ([[1872]]). Ramus hà prima culligatu u sughjettu à i determinanti, ciò chì hà datu locu, incù i cuntributi ultiriori di Heine, Möbius è Günther, à a teuria di i Kettenbruchdeterminanten. ===Numeri trascendenti è reali=== L'esistenza di i numeri trascendenti hè stata stabilita per a prima volta da Liouville ([[1844]], [[1851]]). Hermite hà pruvatu in 1873 ch'è e hè trascendente è Lindemann hà pruvatu in [[1882]] ch'è π hè trascendente. Infine, Cantor hà mustratu ch'è l'inseme di tutti i numeri reali hè innumerevulmente infinitu ma ch'è l'inseme di tutti i numeri algebrichi hè numerevulmente infinitu, è ch'ellu esiste dunque un numeru innumerevulmente infinitu di numeri trascendenti. ===Infinitu è infinitesimali=== [[File:Aristotle_Altemps_Inv8575.jpg|thumb|right|250px|Copia rumana di u bustu d'Aristotele di [[Lisippu]]]] A più cuncezzione anziana cunnisciuta di l'infinitu matematica apparisce in u ''Yajur Veda'', un'anziana scrittura indiana, chì dichjara à un mumentu datu: "S'è voi toglite una parte di l'infinitu o aghjunghjite una parte à l'infinitu, ciò chì ferma hè l'infinitu." L'infinitu era un sughjettu di studiu filusoficu populare ind'è i matematichi giaini, ver' di [[400 a.C.]]. Distinguianu cinque tipi di infinitu: infinitu in una è dui direzzione, infinitu in superficia, infinitu dignalocu è infinitu perpetuamente. U simbulu <math>\text{∞}</math> hè à spessu imprudatu per riprisintà una quantità infinita. [[Aristotele]] hà definitu a nuzione occidentale tradiziunale di infinitu matematicu. Hà fattu a distinzione trà l'infinitu reale è l'infinitu putenziale, u cunsensu generale essendu ch'è solu quest'ultimu avia un valore reale. E Duie nuvelle scenze di [[Galileo Galilei]] abburdavanu l'idea di currispundenze biunivoche trà insemi infiniti. Ma a prossima avanzata magiore di a teuria hè stata rializata da Georg Cantor chì in u 1895, hà publicatu un libru annantu à a so nuvella teuria di l'insemi, intruducendu, frà altru, i numeri trasfiniti è furmulendu l'ipotesi di u cuntinuu. In l'[[anni 1960]], [[Abraham Robinson]] hà mustratu cume i numeri infinitamente grandi è infinitesimali ponu esse definiti di manera rigurosa è usati per sviluppà u campu di l'analisi non standard. U sistemu di i numeri iperreali riprisenta un metudu rigurosu per trattà l'idee annantu à i numeri infiniti è infinitesimali chì eranu state imprudate di manera disinvolta da i matematichi, i scentifichi è l'ingenieri dapoi l'invinzione di u calculu infinitesimale da Newton è Leibniz. Una virsione geumetrica muderna di l'infinitu hè data da a geumitria pruiettiva, chì introduttu di i "punti ideali à l'infinitu", unu per ogni direzzione spaziale. Ogni famiglia di linie parallele in una direzzione data hè supposta cunfluisce ver' di u puntu ideale currispundente. Quessa hè strettamente ligata à l'idea di punti di fughjera in u disegnu in pruspittiva. ===I numeri cumplessi=== U prima riferimentu à e radiche quatrate di i numeri negativi si trova in i travagli di u matematicu è invintore Héron d'Alissandria à u [[I sèculu]] di a nostra epica, quandu ellu hà esaminatu u vulume di un fustu di piramida impussibile. Sò diventate più impurtante quandu, à u XVI sèculu, e formule chjuse per e radiche di i pulinomii di u terzu è di u quartu gradu sò stati scuperte da matematichi taliani tali [[Niccolò Fontana Tartaglia]] è [[Gerolamo Cardano]]. Omu s'hè in freccia resu cunta ch'è 'sse formule, ancu s'è omu ùn s'intarissava ch'è à e soluzione reale, necessitavanu qualchì volta a manipulazione di radiche quatrate di numeri negativi. [[File:Carl_Friedrich_Gauss_1840_by_Jensen.jpg|thumb|250px|right|Carl Friedrich Gauss]] Era duppiamentu scuncertante chì, à l'epica, ùn cunsidaravanu mancu i numeri negativi cum'è un terrenu solidu. Quandu [[René Descartes]] hà invintatu u termine "imaginariu" per 'sse quantità in u [[1637]], l'hà vulsutu pighjurativu. (Vede numeru imaginariu per una discussione annantu à a "rialità" di i numeri cumplessi.) un'antra fonte di cunfusione era ch'è l'equazione :<math>\left ( \sqrt{-1}\right )^2 =\sqrt{-1}\sqrt{-1}=-1</math><br> simbrava capricciosamente incompatibile incù l'identità algebrica<br> :<math>\sqrt{a}\sqrt{b}=\sqrt{ab},</math><br> chì hè valevule per i numeri reali pusitivi a è b, è era ancu imprudata in i calculi di numeri cumplessi incù unu di i a, b pusitivu è l'altru negativu. L'usu scurrettu di 'ss'identità, è di l'identità cunnessa. :<math>\frac{1}{\sqrt{a}}=\sqrt{\frac{1}{a}}</math><br> in u casu induve a è b sò tremindui negativi hà ancu scumudatu Euler. 'Ssa difficultà l'hà finalmente cunduttu à imprudà u simbulu spiciale i à a piazza di <math>\sqrt{-1}</math> per evità 'ssu errore. U XVIII sèculu hà vistu i travagli d'Abraham di Moivre è di [[Leonhard Euler]]. A formula di Di Moivre (1730) enuncia: :<math>(\cos \theta + i\sin \theta)^{n} = \cos n \theta + i\sin n \theta </math><br> quandu a formula d'analisi cumplessa d'Euler (1748) dà:<br> :<math>\cos \theta + i\sin \theta = e ^{i\theta }. </math>.<br> [[Carl Friedrich Gauss]] l'hà rescuperta è popularizata une pochi di anni più tardi ([[1799]]), è a teuria di i numeri cumplessi hà cusì cunnisciutu un'espansione nutevule. L'idea di a ripprisintazione grafica di i numeri cumplessi era eppuru apparsa da [[1685]], in u ''Di algebra tractatus'' di Wallis. Sempre in u 1799, Gauss hà furnitu a prima prova di solitu accittata di u teurema fundivu di l'algebra, mustrendu ch'è ogni pulinomiu annantu à i numeri cumplessi hà unu inseme cumplettu di soluzione in 'ssu campu. L'accittazione generale di a teuria di i numeri cumplessi hè duvuta à i travagli d'[[Austinu Luigi Cauchy]] è di [[Niels Henrik Abel]], è soprattuttu di quest'ultimu, chì fubbe u prima à usà arditamente i numeri cumplessi incù un successu bellu cunnisciutu. Gauss hà studiatu i numeri cumplessi di a forma {{nowrap|''a'' + ''bi''}}, induve ''a'' è ''b'' sò integrali, o raziunali (è ''i'' hè una di e duie radiche di {{nowrap|''x''² + 1 {{=}} 0}}). U so elevu, [[Gotthold Eisenstein]], hà studiatu u tipu a + bω, induve ω hè una radica cumplessa di {{nowrap|''x''³ − 1 {{=}} 0.}}. Altre classe di 'ssu tipu (chjamate campi ciclotomichi) di numeri cumplessi deriveghjanu di e radiche di l'unità {{nowrap|''x''^''k'' − 1 {{=}} 0}} per i valori superiori di ''k''. 'Ssa generalisazione hè largamente duvuta à Ernst Kummer, chì hà ancu invintatu i numeri ideali, chì sò stati sprimati cum'è entità geumetriche da Felix Klein in u 1893. In u [[1850]], [[Victor Alexandre Puiseux]] hà pigliatu l'iniziativa di fà a distinzione trà i poli è i punti di brancamentu, è hà introduttu u cuncettu di punti singulari essenziali, ciò chì hà finalmente cunduttu à u cuncettu di pianu cumplessu stesu. ===Numeri primi=== I numeri primi sò stati studiati tuttu à longu à a storia. [[Euclide]] hà cunsacratu un libru da l'Elementi à a teuria di i numeri primi; ci hà dimustratu l'infinitezza di i numeri primi è u teurema fundamentale di l'aritmetica, è hà prisintatu l'algoritmu d'Euclide per truvà u più grande divisore cumunu di dui numeri. In u [[240 a.C.]], Eratostene hà usatu u stacciu d'Eratostene per isulà prestu i numeri primi. Ma a maiò parte di i sviluppi ultiriori di a teuria di i numeri primi in Europa datanu di a Rinascita è di l'epiche ultiriore. In u [[1796]], [[Adrien-Marie Legendre]] hà cungetturatu u teurema di i numeri primi, discrivendu a distribuzione asintotica di i numeri primi. Altri risultati cuncirnendu a distribuzione di i numeri primi inchjudenu a prova d'Euler ch'è a somma di e reciproche di i numeri primi diverge, è a cungettura di Goldbach, chì afferma ch'è ogni numeru paru sufficintamente grande hè a somma di dui numeri primi. Un'antra cungettura ligata à a distribuzione di i numeri primi hè l'ipotesi di Riemann, furmulata da Bernhard Riemann in u 1859. U teurema di i numeri primi hè, fatta fine, statu pruvatu da Ghjacumu Hadamard è Carlu di a Vallée-Poussin in u 1896. E cungetture di Goldbach è di Riemann fermanu sempre micca pruvate è micca confutate. ==Classifica maestra== I numeri ponu esse classificati in insemi, chjamati sistemi di numeri, tali i numeri naturali è i numeri reali. E principale categurie di numeri sò e seguente: ===Principali sistemi di numeri=== ===Numeri naturali=== I numeri i più famigliari sò i numeri naturali (qualchì volta chjamati numeri intieri o numeri da cuntà): 1, 2, 3, è tira è tocca. Tradiziunalmente, a siquenza di i numeri naturali principiava da 1 (0 ùn era mancu cunsideratu cum'è un numeru da i grechi antichi.) Eppuru, à u XIX sèculu, i teorichi di l'insemi è altri matematichi anu principiatu à inchjude 0 (cardinalità di l'inseme biotu, vene à dì 0 elementi, induve 0 hè dunque u più numeru chjucu cardinale) in l'inseme di i numeri naturali. Oghje, differenti matematichi usanu u termine per discrive i duie insemi, inchjudendu 0 o nò. U simbulu matematicu di l'inseme di tutti i numeri naturali hè N, ancu scrittu <math>\mathbb{N}</math>, è qualchì volta <math>\mathbb{N}_0</math> o <math>\mathbb{N}_1</math> quandu ellu hè necessariu di indicà s'è l'inseme deve cumincià da 0 o 1, rispittivamente. In u sistemu di numerazione in basa 10, usatu guasi universalmente oghje per l'operazione matematiche, i simbuli di i numeri naturali si scrivenu cù l'aiutu di deci ciffri : 0, 1, 2, 3, 4, 5, 6, 7, 8 è 9. A basa hè u numeru di ciffri singuli, cumpresu u zeru, ch'è un sistemu numericu usa per riprisintà i numeri (per u sistemu decimale, a basa hè di 10). In 'ssu sistemu di basa 10, u ciffru u più à dritta di un numeru naturale hà un valore di piazza di 1, è ogni altru ciffru hà un valore di piazza deci volta superiore à quella da u ciffru à a so dritta. In a teuria di l'insemi, chì pò serve di fundamentu assiumaticu à e matematiche muderne, i numeri naturali ponu esse riprisintati da classe d'insemi equivalenti. Per indettu, u numeru 3 pò esse riprisintatu cum'è a classa di tutti l'insemi chì anu esattamente trè elementi. Di manera alternativa, in l'aritmetica di Peano, u numeru 3 hè riprisintatu da sss0, induve s hè a funzione " successore " (vale à dì ch'è 3 hè u terzu successore di 0). Numerose ripprisintazione differente sò pussibile; tuttu ciò chì hè necessariu per riprisintà furmalmente 3 hè di iscrive trè volte un certu simbulu o una certa cunfigurazione di simbuli. ===Numeri intieri=== U negativu di un numeru intieru pusitivu hè definitu cum'è un numeru chì produce 0 quandu ellu hè aghjuntu à u numeru intieru pusitivu currispundente. I numeri negativi sò generalmente scritti incù un segnu negativu (u segnu di menu). Per indettu, u negativu di 7 si scrive -7, è 7 (-7) 0. Quandu l'inseme di i numeri negativi hè cumbinatu incù l'inseme di i numeri naturali (cumpresu 0), u risultatu hè definitu cum'è l'inseme di i numeri intieri, Z ancu scrittu <math>\mathbb{Z}</math>. A lettera Z vene da u tedescu Zahl, chì significheghja "numeru". L'inseme di i numeri intieri forma un anellu incù l'operazione d'addizione è di multiplicazione. I numeri naturali formanu un sottuinsemu di i numeri intieri. Cum'ellu ùn esiste micca una norma cumuna per l'inclusione o nò di u zeru in i numeri naturali, i numeri naturali senza zeru sò cumunamente chjamati numeri intieri pusitivi, è i numeri naturali incù zeru sò chjamati numeri intieri micca negativi. ===Numeri raziunali=== Un numeru raziunale hè un numeru chì pò esse sprimatu cum'è una frazzione incù un numeratore intieru è un dinuminatore intieru pusitivu. I dinuminatori negativi sò autorizati, ma sò di solitu evitati, chì ogni numeru raziunale hè uguale à una frazzione à dinuminatore pusitivu. E frazzione si scrivenu cum'è dui numeri intieri, u numeratore è u dinuminatore, incù un'asta di siparazione trà di elli. A frazzione {{sfrac|''m''|''n''}} riprisenta ''m'' parte di un tuttu divisu in ''n'' parte uguale. Duie frazzione differente ponu currisponde à listessu numeru raziunale ; per indettu 1/2 è 2/4 sò uguale. S'è u valore assolutu di ''m'' hè superiore à n (suppostu esse pusitivu), tandu u valore assolutu di a frazzione hè superiore à 1. E frazzione ponu esse superiore, inferiore o uguale à 1 è ponu ancu esse pusitive, negative o nulle. L'inseme di tutti i numeri raziunali cumprende l'intieri apposta chì ogni intieru pò esse scrittu sottu a forma di frazzione incù u dinuminatore 1. Per indettu, -7 pò scrive si -7/1. U simbulu di i numeri raziunali hè Q (per quoziente), ancu scrittu <math>\mathbb{Q}</math>. ===I numeri reali=== U simbulu di i numeri reali hè R, ancu scrittu sottu à a forma <math>\mathbb{R}.</math>. Cumprendenu tutti i numeri di misura. Ogni numeru reale currisponde à un puntu annantu à a dritta numerica. In u paragrafu seguente, ci interisseremu per u più à i numeri reali pusitivi. U trattamentu di i numeri reali negativi hè cunformu à e regule generale di l'aritmetica è a so denutazione cunsiste simpliciamente à prefissà u ciffru pusitivu currispundente incù un segnu di menu, per indettu -123,456. A maiò parte di i numeri reali ùn ponu esse avvicinati ch'è da ciffri decimali, in i quali un non decimale hè piazzatu à dritta di u ciffru avendu u valore di piazza 1. Ogni ciffru à dritta di u non decimale hà un valore di piazza uguale à un dicesimu di u valore di piazza da u ciffru à a so sinistra. Per indettu, 123.456 riprisenta {{sfrac|123456|1000}}, o in altri termini, centu, dui dicine, trè uni, quattru dicesimi, cinque centesimi è sei millesimi. Un numeru reale ùn pò esse sprimatu incù un numeru finitu di ciffri decimali ch'è si ellu hè raziunale è ch'è a so parte frazziunaria hà un dinuminatore chì i so fattori primi sò 2 o 5 o e dui, chì sò i fattori primi di 10, a basa di u sistemu decimale. Cusì, per indettu, a mità vale 0,5, u quintu vale 0,2, u dicesimu vale 0,1 è u cinquantesimu vale 0,02. A ripprisintazione di altri numeri reali sottu forma di decimale necessiteria una siquenza infinita di ciffri à dritta di u non decimale. S'è 'ssa siquenza infinita di ciffri suvita un mudellu, pò esse scritta incù un'ellisse o un'antra nutazione chì indicheghja u mudellu ripetitivu. Una tale decimale hè chjamata decimale ripetitiva. Cusì, {{sfrac|3}} pò esse scrittu 0,333..., incù un'ellisse per indicà ch'è u mutivu cuntinueghja. [[File:PI_constant.svg|250px|thumb|250px|rught|U numeru π]] S'avvera ch'è 'sse decimale ripetute (cumpresu a ripetizione di i zeri) designanu esattamente i numeri raziunali, vene à dì ch'è tutti i numeri raziunali sò ancu i numeri reali, ma ùn hè micca u casu ch'è ogni numeru reale sia raziunale. Un numeru reale chì ùn hè micca raziunale hè chjamatu irraziunale. Un celebru numeru reale irraziunale hè u numeru π, u rapportu trà a circumfarenza di un chjerchju qualunque è u so diamitru. Quandu pi hè scrittu sottu à a forma <math>\pi = 3.14159265358979\dots,</math> cum'ellu hè qualchì volta u casu, l'ellisse ùn significheghja micca ch'è e decimale si ripetenu (ùn si ripetenu micca), ma piuttostu ch'è ùn anu micca fine. Hè statu pruvatu ch'è π hè irraziunale. Un antru numeru bellu cunnisciutu, ch'ellu hè statu pruvatu ch'è ellu si tratta di un numeru reale irraziunale, hè <math>\sqrt{2} = 1.41421356237\dots,</math> a radica quatrata di 2, vene à dì u singulu numeru reale pusitivu chì u quatratu hè 2. 'Ssi dui numeri sò stati apprussimati (per ordinatore) à trilioni (1 trilione 1012 1000 000000 000) di ciffri. Oltre 'ssi esempii nutevuli, guasi tutti i numeri reali sò irraziunali è ùn anu cusì micca mutivi ripetitivi è dunque micca ciffru decimale currispundente. Ùn ponu esse avvicinati ch'è da ciffri decimali, designendu i numeri reali attundati o muzzati. Ogni numeru attundatu o mozzu hè necessariamente un numeru raziunale, chì ùn ne esiste ch'è un numeru innumerevule. Tutte e misure sò, par natura, apprussimazione è cumportanu sempre una margine d'errore. Cusì, 123,456 hè cunsideratu cum'è un'apprussimazione di ogni numeru reale superiore o uguale à {{sfrac|1234555|10000}} è strittamente inferiore à {{sfrac|1234565|10000}} (attundatu à 3 decimale), o di ogni numeru reale superiore o uguale à {{sfrac|123456|1000}} è strittamente inferiore à {{sfrac|123457|1000}} (troncature dopu à a 3. Decimale). I ciffri chì sugiriscenu un'accuratezza superiore à quella di a misura ella stessa devenu esse cancellati. I ciffri rimanenti sò tandu chjamati ciffri significativi. Per indettu, e misure incù una regula ponu raramente esse effittuate senza una margine d'errore di omancu 0,001 m. S'è i lati di un rettangulu sò misurati à 1,23 m è 4,56 m, a multiplicazione dà una superficia per u rettangulu cumpresa trà 5,614591 m2 è 5,603011 m2. Datu chì ancu u sicondu ciffru dopu à a decimale ùn hè micca cunsirvatu, i ciffri seguenti ùn sò micca significativi. Per via di cunsequenza, u risultatu hè generalmente attundatu à 5,61. Cum'è una stessa frazzione pò esse scritta di parechji modi, unu stessu numeru reale pò avè parechje ripprisintazione decimale. Per indettu, 0,999..., 1,0, 1,00, 1,000,..., riprisentanu tutti u numeru naturale 1. Un numeru reale datu ùn hà ch'è e ripprisintazione decimale seguente : un'apprussimazione à un numeru compiu di decimale, un'apprussimazione in a quale un mudellu hè stabilitu chì si perseguiteghja per un numeru illimitatu di decimale o un valore esattu incù sultantu un numeru finitu di decimale. In quest'ultimu casu, l'ultimu ciffru micca nullu pò esse rimpiazzatu da u ciffru unu più chjucu suvitatu da un numeru illimitatu di 9, o l'ultimu ciffru micca nullu pò esse suvitatu da un numeru illimitatu di zeri. Cusì, u numeru reale esattu 3,74 pò ancu scrive si 3,7399999999... È 3,74000000000..... Listessa, un numeru decimale cumpurtendu un numeru illimitatu di 0 pò esse turnatu à scrive cancellendu i 0 à dritta di a decimale, è un numeru decimale cumpurtendu un numeru illimitatu di 9 pò esse turnatu à scrive aumintendu di un'unità u ciffru -9 u più à dritta è trasfurmendu tutti i 9 à dritta di 'ssu ciffru in 0. Infine, una siquenza illimitata di 0 à dritta di a decimale pò esse abbandunata. Per indettu, 6,849999999999... = 6,85 è 6,850000000000... = 6,85. Infine, s'è tutti i ciffri di un numerale sò 0, u numeru hè 0, è s'è tutti i ciffri di un numerale sò una catena senza fine di 9, pudete lascià cascà i 9 à dritta di a decimale, è aghjunghje unu à a catena di 9 à manca di a decimale. Per indettu, 99,999... = 100. I numeri reali pussedenu ancu una pruprietà impurtante ma assai tecnica chjamata a pruprietà di a minima limita superiore. Omu pò mustrà ch'è ogni campu ordinatu, chì hè ancu cumplettu, hè isumorfu à i numeri reali. I numeri reali ùn sò eppuru micca un campu algebricamente chjusu, chì ùn cumprendenu micca soluzione (à spessu chjamata radica quatrata di menu unu) à l'equazione algebrica <math> x^2+1=0</math>. ===Numeri cumplessi=== Passendu à unu più grande livellu d'astrazzione, i numeri reali ponu esse stesi à i numeri cumplessi. Stu inseme di numeri hè apparsu sturicamente pruvendu à truvà e formule chjuse per e radiche di i pulinomii cubichi è quadratichi. Quessa hà cunduttu à sprissione implichendu e radiche quatrate di numeri negativi, è finalmente à a definizione di un nuvellu numeru: a radica quatrata di -1, nutata da i, un simbulu attribuitu da Leonhard Euler, è chjamata l'unità imaginaria. I numeri cumplessi sò custituiti di tutti i numeri di a forma <math>\,a + b i</math> induve ''a'' è ''b'' sò i numeri reali. Per via di quessa, i numeri cumplessi currispondenu à punti di u pianu cumplessu, un spaziu vetturiale in duie dimensione reale. In a sprissione a bi, u numeru reale a hè chjamatu a parte reale è b hè chjamatu a parte imaginaria. S'è a parte reale di un numeru cumplessu hè uguale à 0, u numeru hè chjamatu un numeru imaginariu o puramente imaginariu ; s'è a parte imaginaria hè uguale à 0, u numeru hè un numeru reale. Cusì, i numeri reali sò un sottuinsemu di i numeri cumplessi. S'è e parte reale è imaginariu di un numeru cumplessu sò tremindui numeri intieri, tandu u numeru hè chjamatu un numeru intieru gaussianu. U simbulu di i numeri cumplessi hè '''C''' o <math>\mathbb{C}</math>. U teurema fundivu di l'algebra afferma ch'è i numeri cumplessi formanu un campu algebricamente chjusu, ciò chì significheghja ch'è ogni pulinomiu à cuefficenti cumplessi hà una radica in i numeri cumplessi. Cum'è i reali, i numeri cumplessi formanu un campu, chì hè cumplettu, ma in cuntrariu di i reali, ùn hè micca ordinatu. Vene à dì ch'è ùn ci hè micca sensu cuerente à dì ch'è i hè superiore à 1, nè à dì ch'è i hè inferiore à 1. In termini tecnichi, i numeri cumplessi ùn anu micca ordine tutale compatibile incù l'operazione di u campu. ==Sottuclasse di i numeri intieri== ===Numeri pari è dispari=== Un numeru paru hè un numeru intieru chì hè "uniformemente divisibile" via dui, vene à dì divisibile via dui senza restu ; un numeru disparu hè un numeru intieru chì ùn hè micca paru. Ogni numeru disparu n pò esse custruitu da a formula {{nowrap|''n'' {{=}} 2''k'' + 1,}}, per un intieru ''k'' apprupriatu. Principiendu cù {{nowrap|''k'' {{=}} 0,}}, i primi numeri dispari micca negativi sò 1, 3, 5, 7,.... Ogni numeru paru ''m'' hà a forma {{nowrap|''m'' {{=}} 2''k''}} induve ''k'' hè di novu un numeru intieru. Listessa, i primi numeri pari micca negativi sò 0, 2, 4, 6,.... ===Numeri primi=== Un numeru prima hè un intieru superiore à 1 chì ùn hè micca u produttu di dui intieri pusitivi più chjuchi. I primi numeri primi sò 2, 3, 5, 7, è 11. Ùn esiste micca di formula cusì simplicia ch'è per i numeri pari è dispari per ingenerà i numeri primi. I numeri primi sò stati largamente studiati dapoi più di 2000 anni è anu datu locu à numerose quistione, chì certe sultantu anu truvatu una risposta. U studiu di 'sse quistione rileva di a teuria di i numeri. A cungettura di Goldbach hè un esempiu di quistione firmata senza risposta: "Ogni numeru paru hè a somma di dui numeri primi?" Una quistione a a quale ellu hè statu rispostu, à sapè s'è ogni numeru intieru superiore à un hè un produttu di numeri primi di una sola manera, eccituatu un reacconciu di i numeri primi, hè stata cunfirmata; 'ssa affirmazione pruvata hè chjamata teurema fundivu di l'aritmetica. Una prova apparisce in l'Elementi d'Euclide. ===Altre classe di intieri=== Numerosi sottuinsemi di i numeri naturali anu fattu l'ogettu di studii specifichi è sò stati numinati, à spessu siont'è u prima matematicu chì l'hà studiati. I numeri di Fibonacci è i numeri perfetti sò l'esempii di tali insemi di intieri. ==Sottuclasse di i numeri cumplessi== ===Numeri algebrichi, irraziunali è trascendentali=== I numeri algebrichi sò quelli chì sò una soluzione à un'equazione polinumiale à cuefficenti intieri. I numeri reali chì ùn sò micca numeri raziunali sò chjamati numeri irraziunali. I numeri cumplessi chì ùn sò micca algebrichi sò chjamati numeri trascendentali. I numeri algebrichi chì sò soluzione di un'equazione polinumiale monica à cuefficenti intieri sò chjamati numeri intieri algebrichi. ===Numeri custruttibili=== Mutivati da i prublemi classichi di custruzzione à a regula è à u cumpassu, i numeri custruttibili sò i numeri cumplessi chì e so parte reale è imaginarie ponu esse custruite à a regula è à u cumpassu, à parte si da un sigmentu datu di lunghezza unitaria, in un numeru finitu di tappe. ===Numeri calculevuli=== Un numeru calculevule, ancu cunnisciutu cum'è numeru ricursivu, hè un numeru reale tale ch'ellu esiste un algoritmu chì, datu un numeru pusitivu ''n'' cum'è intrata, produce i ''n'' primi ciffri di a ripprisintazione decimale di u numeru calculevule. E definizione equivalente ponu esse date usendu e funzione μ récursive, e macchine di Turing o u λ-calcul. I numeri calculevuli sò stabili per tutte l'operazione aritmetiche solite, cumpresu u calculu di e radiche di un pulinomiu, è formanu dunque un campu chjusu reale chì cuntene i numeri algebrichi reali. I numeri calculevuli ponu esse cunsiderati cum'è i numeri reali chì ponu esse riprisintati esattamente in un ordinatore : un numeru calculevule hè riprisintatu esattamente da i so primi ciffri è un prugramma per calculà i ciffri seguenti. Eppuru, i numeri calculevuli sò raramente usati in a pratica. Una di e raghjone hè ch'ellu ùn esiste nissunu algoritmu permittendu di testà l'ugualità di dui numeri calculevuli. Più precisamente, ùn pò micca esiste algoritmu chì piglia qualsiasi numeru calculevule cum'è intrata, è dicide in ogni casu s'è 'ssu numeru hè uguale à zeru o micca. L'inseme di i numeri calculevuli hà listessa cardinalità ch'è i numeri naturali. Per via di cunsequenza, guasi tutti i numeri reali ùn sò micca calculevuli. Eppuru, hè assai difficile di produce in modu esplicitu un numeru reale chì ùn sia micca calculevule. ==Estinsione di u cuncettu== ===Numeri p-adichi=== I numeri p-adichi ponu avè espansione infinitamente longhe à manca di a virgula, à listessu modu ch'è i numeri reali ponu avè di l'espansione infinitamente longhe à dritta. U sistemu di numerazione chì ne risulta dipende di a basa imprudata per i ciffri : qualsiasi basa hè pussibile, ma una basa di numeri primi offre e megliu pruprietà matematiche. L'inseme di i numeri p-adichi cuntene i numeri raziunali, ma ùn hè micca cuntenutu in i numeri cumplessi. L'elementi di un campu di funzione algebriche annantu à un corpu finitu è i numeri algebrichi anu numerose pruprietà simile (vede Analugia di i campi di funzione). Per via di cunsequenza, sò à spessu cunsiderati cum'è numeri da i teorichi di i numeri. I numeri p-adichi ghjocanu un rollu impurtendu in 'ss'analugia. ===Numeri ipercumplessi=== Certi sistemi di numeri chì ùn sò micca inchjusi in i numeri cumplessi ponu esse custruiti à parte si da i numeri reali di una manera chì generalizeghja a custruzzione di i numeri cumplessi. Sò qualchì volta chjamati numeri ipercumplessi. Inchjudenu i quaternioni H, introdutti da Sir William Rowan Hamilton, in i quali a multiplicazione ùn hè micca cummutativa, l'ottunioni, in i quali a multiplicazione ùn hè micca assuciativa in più di ùn esse micca cummutativa, è i sedenioni, in i quali a multiplicazione ùn hè micca alternativa, nè assuciativa nè cummutativa. ===Numeri trasfiniti=== Per trattà l'insemi infiniti, i numeri naturali sò stati generalizati à i numeri ordinali è à i numeri cardinali. U prima dà l'ordine di l'inseme, mentre ch'è u sicondu dà a so taglia. Per l'insemi finiti, i numeri ordinali è cardinali sò identificati à i numeri naturali. In u casu infinitu, parechji numeri ordinali currispondenu à listessu numeru cardinale. ===Numeri non-standard=== I numeri iperreali sò usati in analisi non standard. L'iperreali, o reali non standard (di solitu nutati R), designanu un campu ordinatu chì hè un'estinsione pulita di u campu ordinatu di i numeri reali R è chì suddisface à u principu di trasfirimentu. 'Ssu principu permette di reinterprità l'enunciati veri di u prima ordine cuncirnendu R cum'è l'enunciati veri di u prima ordine cuncirnendu R. I numeri superreali è soprareali stendenu i numeri reali aghjunghjendu i numeri infinitamente chjuchi è i numeri infinitamente grandi, ma formanu sempre campi. == Note == <references/> ==Da vede dinù== *[[Numeru cuncretu]] *[[Lista di i numeri]] *[[Lista di i tipi di numeri]] *[[Numeri cumplessi]] *[[Cugnizione numerica]] *[[Ordini di grandezza]] *[[Custante fisica]] *[[Nutazione posiziunale]] [[Categoria:Matematica]] hwd25h0thfqp779r6xcfy2ad8fokcj7 0 26610 406808 406600 2026-10-05T07:04:38Z Fausta Samaritani 15085 file 406808 wikitext text/x-wiki U '''1941''' (in [[nùmeri rumani]] MCMXLI) hè un [[annu]] di u XX sèculu. {{Annu|XIX sèculu|XX sèculu|XXI sèculu|1920|1930|1940|1950|1960|1937|1938|1939|1940|1941|1942|1943|1944|1945}} == Evenimenti == === [[Premiu Nobel|Prèmii Nobel]] 1941 [[Image:NobelP.png|50px]] === [[Prèmiu Nobel per a Pace]]: NO<br> [[Prèmiu Nobel per a Litteratura]]: NO<br> [[Prèmiu Nobel per a Medicina]]: NO<br> [[Prèmiu Nobel per a Fìsica]]: NO<br> [[Prèmiu Nobel per a Chìmica]]: NO<br> == Nàscite == <gallery> Placido Domingo, Buenos Aires concert 2011.jpg|<small>[[Placido Domingo]] (José Plácido Domingo Embil) ([[Madrid]], [[21 di ghjennaghju]] 1941)</small> </gallery> == Morte == <gallery> Portrait of James Joyce P529.jpg|<small>[[James Joyce]] ([[Dublinu]], [[2 di ferraghju]] [[1882]] - [[Zurigu]], [[13 di ghjennaghju]] 1941)</small> File:Rey Alfonso XIII de España, by Kaulak.jpg|<small>[[Alfonsu XIII di Spagna]] ([[Madrid]], [[17 di maghju]] [[1886]] – [[Roma]], [[28 di ferraghju]] 1941)</small> </gallery> == In Còrsica == == Riferimenti == == Ligami == [[File:Commons logo semitrans white bg.svg|12px|bord]] Commons - Category:1941 [https://commons.wikimedia.org/wiki/Category:1941] [[Categoria:Anni di u XX seculu|#]] {{c-supranu}} 85h7csimsml85e4k6rsfk8jt9j8wc4c 0 26729 406807 405655 2026-10-05T07:01:30Z Fausta Samaritani 15085 file 406807 wikitext text/x-wiki U '''1966''' (in [[nùmeri rumani]] MCMLXVI) hè un [[annu]] di u XX sèculu. {{Annu|XIX sèculu|XX sèculu|XXI sèculu|1940|1950|1960|1970|1980|1962|1963|1964|1965|1966|1967|1968|1969|1970}} == Eventi == === [[Premiu Nobel|Prèmii Nobel]] 1966 [[Image:NobelP.png|50px]] === [[Prèmiu Nobel per a Pace]]: <br> [[Prèmiu Nobel per a Litteratura]]: <br> [[Prèmiu Nobel per a Medicina]]: <br> [[Prèmiu Nobel per a Fìsica]]: <br> [[Prèmiu Nobel per a Chìmica]]: <br> == Nàscite == <gallery> </gallery> == Morte == <gallery> Buster Keaton, film actor (SAYRE 3998).jpg|<small>[[Buster Keaton]] (Joseph Frank Keaton) (Piqua ([[Kansas]]), [[4 uttrovi]] [[1895]] - Woodland Hills ([[California]]), [[1 di ferraghju]] [[1966]])</small> Walt Disney 1946.JPG|<small>[[Walt Disney]] ([[Chicago]] ([[Illinois]]), [[5 di dicembre]] [[1901]] - Burbank ([[California]]), [[15 di dicembre]] 1966)</small> </gallery> == In Còrsica == == Riferimenti == == Ligami == [[File:Commons logo semitrans white bg.svg|12px|bord]] Commons - Category:1966 [https://commons.wikimedia.org/wiki/Category:1966] [[Categoria:Anni di u XX seculu|#]] {{c-supranu}} shr9pscd2uf7fhs6rhxj3bgq2j43e3d 0 26743 406806 404455 2026-10-05T06:59:55Z Fausta Samaritani 15085 file 406806 wikitext text/x-wiki U '''1973''' (in [[nùmeri rumani]] MCMLXXIII) hè un [[annu]] di u XX sèculu. {{Annu|XIX sèculu|XX sèculu|XXI sèculu|1950|1960|1970|1980|1990|1969|1970|1971|1972|1973|1974|1975|1976|1977}} == Eventi == === [[Premiu Nobel|Prèmii Nobel]] 1973 [[Image:NobelP.png|50px]] === [[Prèmiu Nobel per a Pace]]: <br> [[Prèmiu Nobel per a Litteratura]]: <br> [[Prèmiu Nobel per a Medicina]]: <br> [[Prèmiu Nobel per a Fìsica]]: <br> [[Prèmiu Nobel per a Chìmica]]: <br> == Nàscite == <gallery> </gallery> == Morte == <gallery> John Ford 4 Allan Warren.jpg|<small>[[Jhon Ford]] (John Martin Feeney) (Cape Elizabeth ([[Maine]]), [[1 di ferraghju]] [[1894]] - Palm Desert ([[California]]), [[31 d'aostu]] [[1973]])</small> §Gadda, Carlo Emilio (1893-1973) - Tomba al Cimitero acattolico, Roma - Foto di Massimo Consoli 01-4-2006 01.jpg|<small>[[Carlu Emiliu Gadda]] ([[Milanu]], [[14 nuvembri]] [[1893]] - [[Roma]], [[21 di maghju]] 1973)</small> El Joven Allende.jpg|<small>[[Salvador Allende]] ([[Santiago del Cile]], [[26 di ghjugnu]] [[1908]] - Santiago del Cile, [[11 di settembre]] 1973)</small> </gallery> == In Còrsica == == Riferimenti == == Ligami == [[File:Commons logo semitrans white bg.svg|12px|bord]] Commons - Category:1973 [https://commons.wikimedia.org/wiki/Category:1973] [[Categoria:Anni di u XX seculu|#]] {{c-supranu}} ijdbrhxz0n4kje9299kn57ivbv7l0b2 0 27131 406810 403861 2026-10-05T07:26:13Z Fausta Samaritani 15085 file, fix 406810 wikitext text/x-wiki {{c-supranu}} U '''1847''' (MDCCCXLVII in [[nùmeri rumani]]) è un [[annu]] di u XIX sèculu. {{Annu|XVIII sèculu|XIX sèculu|XX sèculu|1820|1830|1840|1850|1860|1843|1844|1845|1846|1847|1848|1849|1850|1851}} [[File:Battle Molino del Rey.jpg|thumb|350px|right|Guerra mexico-americana, a battaglia di ''Molino del Rey'', 1847]] == Evenimenti == == Nàscite == <gallery> </gallery> == Morte == <gallery> Felix Mendelssohn Bartholdy - Wilhelm Hensel 1847.jpg|<small>[[Felix Mendelssohn]] (Jakob Ludwig Felix Mendelssohn Bartholdy) ([[Amburgu]], [[3 di ferraghju]] [[1809]] - [[Lipsia]], [[4 nuvembri]] 1847)</small> </gallery> == In Córsica == == Riferimenti == == Ligami == [[File:Commons logo semitrans white bg.svg|12px|bord]] Commons - Category:1847 [https://commons.wikimedia.org/wiki/Category:1847] [[Categoria:Anni di u XIX seculu|#]] 0wduy63motevfmt6mldohfolwsenvxa 0 27219 406805 406640 2026-10-05T06:57:52Z Fausta Samaritani 15085 file 406805 wikitext text/x-wiki {{c-supranu}} U '''1874''' (MDCCCLXXIV in [[nùmeri rumani]]) è un [[annu]] di u XIX sèculu. {{Annu|XVIII sèculu|XIX sèculu|XX sèculu|1850|1860|1870|1880|1890|1870|1871|1872|1873|1874|1875|1876|1877|1878}} [[File:Doitsukokukan naibu kikai-The Interior Works of an Armed German Battleship MET DP147740.jpg|thumb|450px|right|''Interior machinery of a German warship'', incisione ([[Giappone|giapponese]])]] == Evenimenti == [[File:Telemaco Signorini acquaforte, via di Calimala, 1874.jpg|thumb|200px|right|[[Telemacu Signorini]], ''[[Firenze]] via di Calimala'', acquaforti (1874)]] == Nàscite == <gallery> Nicola Perscheid - Hugo von Hofmannsthal 1910.jpg|<small>[[Hugo von Hofmannsthal]] ([[Vienna]], [[1 di ferraghju]] 1874 - Vienna, [[15 di lugliu]] [[1929]])</small> Sir Winston Churchill - 19086236948.jpg|<small>[[Winston Churchill]] (Winston Leonard Spencer Churchill) ([[Woodstock]], [[30 di nuvembri]] 1874 - [[Londra]], [[24 di ghjennaghju]] [[1965]])</small> </gallery> == Morte == <gallery> </gallery> == In Córsica == == Riferimenti == == Ligami == [[File:Commons logo semitrans white bg.svg|12px|bord]] Commons - Category:1874 [https://commons.wikimedia.org/wiki/Category:1874] [[Categoria:Anni di u XIX seculu|#]] 6cxmdlmlq0e52j9csp9i5nrg4utooiy 0 27764 406811 2026-10-05T08:46:42Z Articulivitali 28749 Pàgina creata cù "In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazioni]] (dette dinù ''istruzzioni'') chì permette di risolve tutti i quistioni d'una listessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzioni è deve sempre finisce; * ''deterministu'': partendu da i listessi dati d'Input/output|entr..." 406811 wikitext text/x-wiki In [[matematica]] è [[informatica]], un '''algoritmu''' hè a specificazione d'una [[Istruzzione (informatica)|sequenza finita d'operazioni]] (dette dinù ''istruzzioni'') chì permette di risolve tutti i quistioni d'una listessa classa o di calculà u risultatu d'una spressione matematica. Un algoritmu deve esse: * ''finitu'': hè custituitu d'un numeru finitu d'istruzzioni è deve sempre finisce; * ''deterministu'': partendu da i listessi dati d'[[Input/output|entrata]], si devenu ottene i listessi risultati; * ''senza ambiguità'': l'operazioni ùn devenu pudè esse interpretate in manere differente; * ''generale'': deve esse applicabile à tutti i prublemi di a classa à a quale si riferisce o à i casi di a spressione matematica. U termine deriva 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 risturazione è riduzzione''. E prime nozioni d'algoritmu si trovanu in ducumenti chì risalenu à u [[XVII seculu a.C.]], cunnisciuti cum'è i papiri d'[[Ahmes]], chjamati dinù [[Papiro di Rhind|papiri di Rhind]], chì cuntenenu una cullezzione di prublemi cù e so suluzioni, cumpresu un prublema di multiplicazione chì u scrittore dichjara d'avè copiatu 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 fase 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 essenzialmente 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 ideatu da a matematica britannica [[Ada Lovelace]] per u calculu di i numeri di Bernoulli. À u [[XX seculu]], u cuncettu d'algoritmu hè statu formalizatu per risolve u prublema matematicu di a «decisione» (''[[Entscheidungsproblem]]''), postu da [[David Hilbert]] in u 1928. Altre formalizazione successive sò ghjunte cù u sviluppu di i cuncetti di «[[effective calculability|calculabilità effettiva]]» è di «metudu effettivu». E formalizazione matematiche più cunnisciute sò e [[funzione ricursive|funzioni 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 què, 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è necessariu dispunì d'una definizione più rigorosa 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 matematici anu elaboratu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà i quali, 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 cunsiguenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possa 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, d'[[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ù scomponibili (''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 legittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quantu basta», postu chì a spressione «quantu basta» hè ambigua è ùn indica cun precisione quali passi 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 suggerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottu-prublemi 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 materiali è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve u listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè generalmente 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 identificanu cù a parolla «prublema» l'intera famiglia è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema se, 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]]). Se st'idea avia digià 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 à sparghjesi. Difatti, se 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, allora esistenu e cundizioni 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 principiu, 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 surghjente]], 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)|istruzzioni]] elementari. In a pratica corrente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice surghjente necessariu in e modalità dette dopu avè digià 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/> adb853bhadcr2vjx71d1wpdej6kojgx 406812 406811 2026-10-05T08:50:34Z Articulivitali 28749 406812 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è necessariu dispunì d'una definizione più rigorosa 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 matematici anu elaboratu diverse riprisentazione furmale di u cuncettu d'algoritmu, frà i quali, 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 cunsiguenza, chì nisuna macchina puderà mai risolve prublemi chì una macchina di Turing ùn possa 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, d'[[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ù scomponibili (''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 legittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quantu basta», postu chì a spressione «quantu basta» hè ambigua è ùn indica cun precisione quali passi 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 suggerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottu-prublemi 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 materiali è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve u listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè generalmente 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 identificanu cù a parolla «prublema» l'intera famiglia è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema se, 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]]). Se st'idea avia digià 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 à sparghjesi. Difatti, se 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, allora esistenu e cundizioni 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 principiu, 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 surghjente]], 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)|istruzzioni]] elementari. In a pratica corrente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice surghjente necessariu in e modalità dette dopu avè digià 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/> 4lcmxdcuvvyax2z6sptyuqofbyct3pp 406813 406812 2026-10-05T09:18:11Z Articulivitali 28749 /* Mudelli furmali */ 406813 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ù scomponibili (''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 legittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quantu basta», postu chì a spressione «quantu basta» hè ambigua è ùn indica cun precisione quali passi 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 suggerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottu-prublemi 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 materiali è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve u listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè generalmente 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 identificanu cù a parolla «prublema» l'intera famiglia è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema se, 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]]). Se st'idea avia digià 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 à sparghjesi. Difatti, se 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, allora esistenu e cundizioni 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 principiu, 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 surghjente]], 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)|istruzzioni]] elementari. In a pratica corrente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice surghjente necessariu in e modalità dette dopu avè digià 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/> bsqubm6u24u048zs630le4o41motxux 406816 406813 2026-10-05T11:58:01Z Fausta Samaritani 15085 categuria 406816 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ù scomponibili (''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 legittimamente un passu elementare d'un «algoritmu per a cucina» (una ricetta), ma ùn puderia micca esse tale «aghjunghje sale quantu basta», postu chì a spressione «quantu basta» hè ambigua è ùn indica cun precisione quali passi 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 suggerisce chì, per facilità d'implementazione, l'algoritmi ponu esse ''modulari'', vale à dì orientati à risolve sottu-prublemi 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 materiali è temporale dispunibule. Infine, ponu esiste parechji algoritmi validi per risolve u listessu prublema, ma ognunu cù un gradu d'''efficienza'' differente. L'algoritmu hè generalmente 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 identificanu cù a parolla «prublema» l'intera famiglia è cù «istanza» o «x» ognuna di e quistione specifiche ottenute fissendu dui valori particulari. Dati sti presupposti, un algoritmu risolve un prublema se, 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]]). Se st'idea avia digià 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 à sparghjesi. Difatti, se 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, allora esistenu e cundizioni 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 principiu, 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 surghjente]], 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)|istruzzioni]] elementari. In a pratica corrente, u prugrammatore prufessiunale face automaticamente stu prucessu di traduzzione in u so travagliu, scrivendu direttamente u codice surghjente necessariu in e modalità dette dopu avè digià 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]] bg1zhxy5u79u0ee7ir4ppcq0aoo0aua