Archivi categoria: informatica

In un precedente articolo abbiamo definito i problemi decisionali, e in un altro articolo abbiamo definito le classi di complessità P, NP e co-NP. Rimandiamo il lettore a quei due articoli per la discussione. Oggi riprendiamo la discussione partendo dalla … Continua a leggere→

In informatica, si sente spesso parlare di diverse classi di complessità computazionale. In questo articolo vediamo alcune di queste classi e l’idea dietro ognuna di esse.  Prima di tutto, le classi di complessità, P, NP, ecc. hanno a che fare … Continua a leggere→

Questo articolo serve da preludio al prossimo articolo, in cui spieghiamo la distinzione tra classi di complessità computazionale P, NP, ecc. Questi nomi si riferiscono a problemi decisionali. In questo articolo vediamo cosa significa e in particolare come convertire in … Continua a leggere→

Il problema degli abbinamenti stabili è un classico problema informatico la cui soluzione è un algoritmo interessante. Supponiamo di avere $N$ studenti e $N$ professori e vogliamo abbinare ogni studente con esattamente un professore (magari per fare la tesi). Ogni … Continua a leggere→

Supponiamo di avere delle serie di dati $x_1, x_2, \ldots x_N$ e $y_1, y_2, \ldots y_N$. Possiamo metterli insieme in una matrice $N \times 2$, $$X = \begin{pmatrix} x_1 & y_1 \\ x_2 & y_2 \\ \vdots & \vdots \\ … Continua a leggere→