Questa pagina contiene un elenco di voci sulla Combinatoria.
Qualche decina di anni fa si sarebbe detto che la combinatoria sta alla Matematica come la sindrome del colon irritabile sta alla gastroenterologia - un'espressione per indicare problemi poco conosciuti e i relativi rimedi standard. Dal 1960 si sono però avuti grandi progressi.
Questa pagina è complementare all'elenco di voci sulla teoria dei grafi, in quanto la Teoria dei grafi è una parte della matematica combinatoria che può rivendicare lo status di disciplina a sé stante. In generale, la combinatoria riguarda sia la soluzione di problemi che la costruzione di edifici teorici.
Dato che la combinatoria è effettivamente l'ambiente per lo studio delle strutture di dati dell'Informatica, vi sono molti argomenti della prima disciplina nascono nella seconda. Discorso analogo si può fare per campi come i codici a correzione di errore e la Bioinformatica.
Principi e metodi generali di combinatoria
[modifica wikitesto]Si inizia con alcuni principi generali:
- Tentativo ed errore, Ricerca con la forza bruta, Bogosort
- Principio dei cassetti
- Induzione matematica
- Relazione di ricorrenza, Serie telescopica
- Funzione generatrice come applicazione della serie formale di potenze
- Coefficienti binomiali e loro proprietà
- Doppio conteggio, dimostrazione combinatoria
- Principio di inclusione ed esclusione
- Formula di inversione di Möbius
- Parità, Permutazioni pari
- Algebra di incidenza
- Algoritmo greedy
- Divide et impera
- Programmazione dinamica
- Branch and bound
- Attacco del compleanno, Paradosso del compleanno
- Riduzione ad algebra lineare
- Calcolo umbrale
- Algoritmo minimax
- Metodo probabilistico
- Metodi di crivello
Risoluzione di problemi come arte
[modifica wikitesto]- Euristica
- Ragionamento induttivo
- How to solve it di George Polya
- Risoluzione di problemi creativi
- Art of Problem Solving di Richard Rusczyk e Sandor Lehoczky
Alcune teorie generali
[modifica wikitesto]Operare con numeri grandi
[modifica wikitesto]- Nomi di numeri grandi
- Numero di Graham
- Numero di Moser
- Numero di Skewes
- Notazioni per numeri grandi
- Effetti per grandi numeri
Articoli
[modifica wikitesto]- Matrice binaria
- Complesso astratto simpliciale
- Catena di addizione
- Insiemi quasi disgiunti
- Anticatena
- Problema di assegnazione
- Codice a barre
- Polinomi di Bell
- Teorema binomiale
- Disegno a blocchi
- Problema booleano di soddisfacibilità
- Teorema di Bruck - Chowla - Ryser
- Numero di Catalan
- Automa cellulare
- Congettura di Collatz
- Combinazione
- Ottimizzazione combinatoria
- Ricerca combinatoria
- Problema di soddisfacimento di vincoli
- Ordine ciclico
- Identità ciclotomica
- Integrità dei dati
- Stallo
- Derangement
- Lemma di Dickson
- Ottimizzazione discreta
- Rompicapo delle otto regine
- Codifica dell'entropia
- Enumerazione
- Teorema di Erdös - Ko - Rado
- Numero di Eulero
- Formula di Faà di Bruno
- Famiglia di insiemi
- Gioco del quindici
- Geometria finita
- Proprietà dell'intersezione finita
- Algoritmo di Floyd di ricerca dei cicli
- Teoria dei giochi
- Codifica di Golomb
- Regola di Golomb
- Quadrato greco-latino
- Codice di Gray
- Matrice di Hadamard
- Distanza di Hamming
- Funzione di hash
- Problema del cappello
- Famiglia di Helly
- Identità di funzioni ipergeometriche
- Serie ipergeometrica
- Ipergrafo
- Struttura di incidenza
- Partizione di interi
- Problema dell'ago di Kakeya
- Problema di Knapsack
- Numero di Lah
- Numero grande
- Quadrato latino
- Distanza di Levenshtein
- Ordine lessicografico
- Disuguaglianza di Lubell - Yamamoto - Meshalkin (nota come disuguaglianza LYM)
- Catena di Lucas
- Quadrato magico
- Teorema del matrimonio
- Immersione di matroidi
- Array di Monge
- Ordine monomiale
- Funzione di Moreau per il conteggio delle collane
- Multiinsieme
- Problema della collana
- Insieme trascurabile
- Partizione ordinata di un insieme
- Problema di impacchettamento
- Partizione di un insieme
- Permanente
- Permutazione
- Simbolo di Pochhammer
- Poliforma
- Piano proiettivo
- Cubo di Rubik
- Algoritmo di ricerca
- Puzzle di mescolamento
- Matrice sparsa, array sparso
- Famiglia di Sperner
- Lemma di Sperner
- Problema del matrimonio stabile
- Sistema di Steiner
- Numero di Stirling
- Algoritmo stringa
- Scacchiera straddling ??
- Sottosequenza
- Problema della somma di un sottoinsieme
- Funzioni simmetriche
- Teorema di Szeméredi
- Sequenza di Thue - Morse
- Torre di Hanoi
- Tarpit di Turing ??
- Problema dell'urna (probabilità)
- Torneo pesato
- Disuguaglianza di Wigner - d'Espagnat
- Tavola di Young
Vedi anche
[modifica wikitesto]- Progetto:Matematica/Elenco di voci su fattoriali e binomiali
- Elenco di articoli su partizioni
- Elenco di articoli su puzzle.
- Progetto:Matematica/Elenco di voci sui linguaggi formali e sulle stringhe letterali
Concetti di strutture di dati
[modifica wikitesto]- Strutture di dati
- Array
- Array associativo
- Deque
- Lista
- Coda
- Pila Stack
- Strutture di dati ad albero
- Collezione automatica di rifiuti