Torna a Matematica
Computabilita e complessita
Computabilita e complessita studiano cosa puo essere calcolato e quante risorse servono per farlo.
Interattivo
Prova subito
Modifica i dati e controlla risultato e passaggi senza aspettare il server.
- O(log n) cresce lentamente.
- O(n log n) e tipico di ordinamenti efficienti.
- O(n^2) cresce molto piu velocemente e va controllato sugli input grandi.
Teoria
- Computabilita e complessita
- Matematica Concetto Idea Uso Automa Macchina con stati e transizioni.
- Parsing e protocolli.
- Linguaggio formale Insieme di stringhe accettate da regole.
- Macchina di Turing Modello astratto di calcolo.
- Limiti del calcolo.
- P e NP Classi di problemi secondo il tempo richiesto.
- Algoritmi e sicurezza.
Esempi
- Un problema in P ha un algoritmo efficiente noto, almeno secondo la definizione teorica di tempo polinomiale.
- Le riduzioni permettono di confrontare la difficolta di due problemi.
- Un automa finito ha memoria illimitata
- Soluzione: no, ha solo un numero finito di stati.