Storia della combinatoria: differenze tra le versioni

Versione delle 19:35, 15 set 2005

Versione attuale delle 11:36, 31 mar 2025

(37 versioni intermedie di 29 utenti non mostrate)

Riga 1:

{{stubTorna matematicaa|Combinatoria}}

Problemi combinatori sono stati studiati fin dall'antichità, ma la [[combinatoria]], come area consistente della matematica, è stata pienamente riconosciuta solo nella seconda metà del XX secolo.

Problemi combinatorici sono stati studiati fin dall'antichità, ma la combinatorica come area consistente della matematica è stata pienamente riconosciuta solo nell'ultimo cinquantennio.

== Antichità ==

Nell'antichità sembra che solo nelle civiltà orientali sia stata coltivata la combinatoria, soprattutto con lo studio di configurazioni combinatorie che contengono caratteristiche di simmetria di grande suggestione, tanto da far pensare a contenuti magici ed esoterici.

Vi sono documenti riguardanti lo studio dei [[quadrato magico|quadrati magici]] in [[Cina]] nel I secolo; non sembra invece giustificato sostenere che fosse noto fin dal 2200 a.C. il famoso

Nell'antichità sembra essere stata coltivata solo nelle civiltà orientali.

Presso gli Indù eranonote ai tempi di [[Bhaskara]] intorno al 1150 le espressioni per i numeri delle permutazioni e delle combinazioni; forse erano note anche a [[Brahamagupta]] nel [[VI secolo]].

:<math>\begin{bmatrix}

Vi sono documenti riguardanti lo studio dei [[quadrato magico|quadrati magici]] in [[Cina]] nel [[I secolo]]; non sembra giustificato sostenere che fosse noto fin dal [[2200 AC]] il famoso

::<math>

\begin{bmatrix}

8 & 1 & 6 \\

3 & 5 & 7 \\

4 & 9 & 2 \\

\end{bmatrix}.</math>

</math>

Presso gli Indù erano note ai tempi di [[Bhāskara II|Bhāskara]] intorno al 1150 le espressioni per i numeri delle permutazioni e delle combinazioni; forse erano note anche a [[Brahmagupta]] nel VI secolo.

I quadrati magici vengono studiati ampiamente in Cina negli anni tra il [[900]] e il [[1300]]. Essi sono studiati anche nel mondo islamico. In questi studi si hanno sempre toni mistici. Essi e i quadratilatini giungono in Occidente attraverso il matematico bizantino [[Moschopolous]] intorno al 1315.

I quadrati magici vengono studiati ampiamente in Cina negli anni tra il 900 e il 1300. Essi sono studiati anche nel mondo islamico. In questi studi si hanno sempre toni mistici. Essi e i quadrati latini giungono in Occidente attraverso il matematico bizantino [[Manuele Moscopulo|Moscopulo]] intorno al 1315. Un altro oggetto studiato è quello che in Italia si chiama prevalentemente [[triangolo di Tartaglia]], schieramento bidimensionale di [[Coefficiente binomiale|coefficienti binomiali]]. Noto agli indiani, si ritrova nel [[XIII secolo]] in [[Jordanus Nemorarius|Giordano Nemorario]] nell'opera dell'arabo [[Sharaf al-Dīn al-Muzaffar al-Ṭūsī|Al Tusi]] e nei testi cinesi intorno al [[1300]]; questi verosimilmente riprendono risultati ora perduti di [[Chia Hsien]] ottenuti intorno alall'anno [[1100]].

Ricordiamo infine [[Leonardo Fibonacci]] con ila suoisua [[numeriSuccessione di Fibonacci|successione di numeri]].

== [[Secolo XVII]] ==

[[Blaise Pascal]] con il Traité del 1665 analizza il triangolo ora noto giustamente con il suo nome.

[[Gottfried Wilhelm von Leibniz|Gottfried Leibniz]] con ''Dissertatio de arte combinatoria'' del 1666 (rifacendosi anche a [[Raimondo Lullo]]) propone di studiare questi argomenti, parla di [[partizioni di interi]] e di geometria della posizione.

[[Pascal]] con il Traité del [[1665]] analizza il triangolo ora noto giustamente con il suo nome.

[[Thomas Harriot]], Blaise Pascal ed [[Eulero]] chiariscono lo stretto collegamento fra sviluppi formali e cardinalità di specifiche configurazioni combinatorie, in particolare la coincidenza dei coefficienti dello [[sviluppo del binomio]] con i numeri dei sottoinsiemi delle diverse cardinalità di un insieme di data cardinalità. Questi studi avviano il collegamento fra algebra e combinatoria che porterà alla [[combinatoria algebrica]].

[[Leibniz]] con Dissertatio de arte combinatoria del [[1666]] (rifacendosi anche a [[Ramon Lull]]) propone di studiare questi argomenti, parla di [[partizioni di interi]] e di geometria della posizione.

[[Abraham de Moivre]] nel 1697 dimostra lo [[sviluppo multinomiale]]; inoltre scopre il [[principio di inclusione-esclusione]] e con esso calcola il numero delle [[dismutazioni]].

[[Harriot]], [[Pascal ed [[Eulero]] chiariscono lostretto collegamento fra sviluppo formale e lista di configurazioni combinatoriche (collegamento fra algebra e combinatorica).

== Secolo XVIII ==

[[De Moivre]] nel 1697 dimostra lo [[sviluppo multinomiale]]; inoltre scopre il [[principio di inclusione ed esclusione]] e con esso calcola il numero dei derangement.

De Moivre trova l'espressione chiusa per i numeri di Fibonacci.

Ad Eulero si devono la nascita della [[teoria dei grafi]] con il [[problema dei ponti di Königsberg]], lo studio delle partizioni con la relativa [[funzione generatrice]] e la loro connessione con le [[Funzione simmetrica|funzioni simmetriche]] e la posizione del problema dei quadrati greco-latini, ovvero delle coppie di [[quadrati latini ortogonali]].

== [[Secolo XVIII]] ==

Un altro risultato da ricordare è la [[formula di inversione di Lagrange]].

De Moivre trova l'espressione chiusa per i numeri di Fibonacci (1930).

== Secolo XIX ==

Ad Eulero si devono la nascita della teoria dei grafi con il [[problema dei ponti di Kônigsberg]], lo studio delle partizioni con la relativa [[funzione generatrice]] e la loro connessione con le [[funzioni simmetriche]] e la posizione del problema dei quadrati greco-latini, ovvero delle coppie di [[quadrati latini ortogonali]].

La combinatoria interessa attività pratiche (1818).

Si incontra nei gruppi di permutazioni, studiati da [[Joseph-Louis Lagrange|Lagrange]], [[Évariste Galois|Galois]] e [[Augustin-Louis Cauchy|Cauchy]].

[[Formula di inversione di Lagrange]].

Viene proposto il Calcolo di Blissard, sistema che porterà al [[calcolo umbrale]].

== [[Secolo XIX]] ==

Il [[permanente (matematica)|permanente]] di una matrice viene studiato da [[Jacques Philippe Marie Binet|Binet]] e Cauchy.

La combinatorica interessa attività pratiche (1818).

Si studiano il [[problema degli incontri]] e il [[problema dei ménages]].

Si incontra nei gruppi di permutazioni, studiati da [[Lagrange]], [[Galois]] e [[Cauchy]].

Attraverso la [[matematica ricreativa]] si introducono altri problemi: il problema dei grafi hamiltoniani, il problema dei 4 colori posto da [[Francis Guthrie]], le [[triple di Steiner]].

Calcolo di Blissard o [[calcolo umbrale]].

Si affronta il problema del calcolo delle orbite dei gruppi di permutazioni giungendo al lemma di Cauchy-Frobenius.

Il [[permanente]] studiato da [[Binet]] e [[Cauchy]].

Viene pubblicato il primo testo che espone con una certa sistematicità la combinatoria, dovuto a Netto.

Si studiano il [[problema degli incontri]] e il [[problema dei ménages]]

Viene affrontato il problemi degli invarianti per opera principalmente di [[Arthur Cayley|Cayley]] e [[James Joseph Sylvester|Sylvester]].

Attraverso la matematica ricreativa si introducono altri problemi: il problema dei grafi hamiltoniani, il problema dei 4 colori posto da [[Francis Guthrie]], le [[triple di Steiner]].

In questo periodo si hanno importanti contributi da parte di [[Alfredo Capelli|Capelli]], [[Carlo Emilio Bonferroni|Bonferroni]] e [[Francesco Faà di Bruno|Faà di Bruno]].

Problema del calcolo delle orbite con il lemma di Cauchy-Frobenius

Rilevanti contributi alla problematica della enumerazione sono dati da [[Percy Alexander MacMahon|MacMahon]]. il quale è anche l'autore di un secondo importante testo sulla combinatoria.

Un primo testo che ha dato peso alla combinatorica è dovuto a Netto.

== Inizio del XX secolo ==

Problemi degli invarianti Cayley, Sylvester,

Gli importanti progressi della matematica astratta che si concentra sulla costruzione di un ampio edificio formale basato su assiomi e retto da dimostrazioni di esistenza conduce ad una caduta dell'importanza dei metodi costruttivi; una sorta di colpa di questo ''squilibrio'' è attribuibile in particolare ad [[David Hilbert|Hilbert]] all'inizio del XX secolo e ai [[Nicolas Bourbaki|Bourbakisti]] a partire dagli anni 1930. Da questo punto di vista si tende a considerare i problemi combinatorici o al livello della matematica ricreativa o troppo difficili e irrisolvibili.

La combinatoria accenna a raggiungere una certa autonomia dopo la pubblicazione del testo ''[[Combinatory Analysis]]'' di [[Percy Alexander MacMahon]] nel 1915. L'importanza della disciplina cresce, ma solo gradualmente, negli anni successivi: sono da ricordare i testi di [[Dénes König]] sulla teoria dei grafi e di [[Marshall Hall]].

[[Michele Capelli]] [[Emilio Bonferroni]] [[Francesco Faà di Bruno]]

In questo periodo, comunque, si ottengono importanti risultati e si aprono nuovi importanti filoni di ricerca: a questo proposito vanno ricordati nomi quali Ramsey, Kuratowski, Polya, Renyi.

Contributi alla enumerazione da MacMahon

Inoltre molte tematiche a carattere costruttivo-algoritmico che entreranno in una combinatoria abbastanza sistematica vengono affrontate in settori consolidati della matematica e in altre discipline: teoria dei gruppi, teoria dei campi, geometria algebrica,

== Inizio del [[XX secolo]] ==

calcolo numerico, funzioni speciali, meccanica quantistica, chimica molecolare, biologia molecolare, [[ricerca operativa]], visualizzazione.

Va inoltre ricordata la nascita e il progressivo intenso sviluppo del calcolo scientifico automatico, con la sua richiesta di procedimenti costruttivi e con la sua crescente capacità di ottenere soluzioni e di esaminare configurazioni con procedimenti di matematica sperimentale (empirismo matematico).

Caduta dell'importanza dei metodi costruttivi, con una certa colpa di [[Hilbert]] e poi dei [[Bourbaki]]sti

La combinatorica accenna a raggiungere una certa autonomia dopo la pubblicazione del testo ''[[Combinatory Analysis]]'' di [[Percy Alexander MacMahon]] nel 1915.

La sua importanza è cresciuta gradualmente negli anni successivi: sono da ricordare i testi di König sulla teoria dei grafi e di Marshall Hall.

Ramsey Kuratovski

== Dopo gli anni 1960 ==

Il suo sviluppo ha ricevuto impulso dall'opera di [[Gian-Carlo Rota]], che a partire dagli [[anni 1960]], ha contribuito alla fondazione di teorie unificatrici di ampia portata e di grande chiarezza formale.

Un'altra figura influente è stata quella di [[Marcel Paul Schützenberger]], con i suoi contributi alla teoria dei codici a lunghezza variabile, ovvero alla combinatoria delle parole.

Un'azione diversa, ma molto efficace, si deve a [[Paul Erd&#337;sErdős]] e alla sua capacità di porre e risolvere problemi, i suoi contributi riguardando soprattutto problemi estremali.

Altre figure importanti: [[Izrail' Moiseevič Gel'fand]], [[László Lovász]], [[Richard P. Stanley]], [[Bela Ballobas]], [[Doron Zeilberger]], [[Noga Alon]].

[[Gel'fand]]

[[Laszlo Lovasz]]

[[Richard Stanley]] [[Bela Ballobas]]

=== Combinatorica algoritmica ===

*[[Algoritmo greedy]]

*[[Problema del commesso viaggiatore]]

*[[Teoria della complessità computazionale]]

*[[Problemi di trasporto sui grafi]], Ford e Fulkerson

*[[Combinatoria poliedrale]]

*[[Programmazione lineare]] e [[Algoritmo del simplesso|Metodo del simplesso]]

*[[Teoria dei giochi]]

=== Sistemi software per la combinatorica ===

[[Algoritmo greedy]]

ACE, Symmetrica, ...

== Bibliografia ==

[[Problema del commesso viaggiatore]]

*[[Norman L. Biggs]], [[E. Keith Lloyd]], [[Robin J. Wilson]] (1995): ''The history of combinatorics'', pp. 2163-2198 in [[Ronald Graham]], [[Martin Grötschel]], [[László Lovász]] ''Handbook of combinatorics'', North Holland

*[[Norman L. Biggs]], [[E. Keith Lloyd]], [[Robin J. Wilson]] (1976): ''Graph theory (1736-1936)'', Clarendon Press

== Voci correlate ==

[[Complessità computazionale]]

*[[05-XX]]

== Altri progetti ==

[[Problemi di trasporto sui grafi]] Ford e Fulkerson

{{interprogetto}}

{{Combinatoria}}

[[Combinatorica poliedrale]]

{{Portale|matematica}}

[[Programmazione lineare]] e [[Metodo del simplesso]]

[[Teoria dei giochi]]

=== Sistemi software per la combinatorica ===

ACE, Symmetrica, ...

== Bibliografia ==

*[[Norman L. Biggs]], [[E. Keith Lloyd]], [[Robin J. Wilson]] (1995): ''The history of combinatorics'', pp. 2163-2198 in [[Ronald Graham]], [[Martin Grötschel]], [[Laszlo Lovasz]] ''Handbook of combinatorics'', North Holland

*[[Norman L. Biggs]], [[E. Keith Lloyd]], [[Robin J. Wilson]] (1976): ''Graph theory (1736-1936)'', Clarendon Press

[[Categoria:CombinatoricaCombinatoria]]

[[Categoria:Storia della matematica]]