NP completezza

  • Problemi Decidibili
    • Trattabili (complessità polinomiale)
    • Intrattabili (complessità esponenziale)
  • Problemi Indecidibili

 

  • Problemi decisionali (sì/no)
  • Ottimizzazioni (il migliore è n)

ma a ogni problema di ottimizzazione può essere associato un problema decisionale

 

  • Classe P: problemi risolvibili in tempo polinomiale O(nk)
  • Classe NP: problemi verificabili in tempo polinomiale O(nk)

P ⊆ NP

NPC???

Lista degli argomenti relativi ai grafi (per esame ASD)

  • definizione di grafo
  • grafo orientato e non orientato
  • sottografi
  • grafi aciclici
  • cammino
  • ciclo
  • cammino semplice
  • cappi
  • grado di un vertice
    • lemma della stretta di mano
  • grafi regolari
    • 2-reg: |V| = |E|
    • 3-reg: |V| pari
    • 4-reg: |E| pari
    • 6-reg: |V| pari ⇒ |E| pari, |V| dispari ⇒ |E| dispari
  • rappresentazione di grafi con matrici di adiacenza
    • indici di colonna = da, di riga = a
  • rappresentazione di grafi con liste di adiacenza
  • densità di un grafo (denso/sparso)
    • orientato:
      δ=mn2
    • non orientato:
      δ=mnn-12
  • prodotto di matrici di adiacenza
    • diagonale del risultato come grado del vertice
    • altri valori come numero di cicli con grado k (k = numero di volte che si moltiplica la matrice)
  • grafo pesato
  • isomorfismo di grafi
  • grafo complementare
  • grafo aciclico
  • grafi connessi
  • albero
  • grafo completo
  • grafo vuoto
  • grafo bipartito
  • albero di copertura minimo (MST)
  • taglio
  • arco leggero
  • teorema fondamentale degli MST
    1. A ⊆ E, A ⊆ MST
    2. t = (S, S/V) un taglio che rispetta A
    3. l'arco a che attraversa t è leggero
    4. → l'arco a è sicuro per A
  • taglia e cuci
    1. abbiamo un albero
    2. aggiungiamo un arco leggero
    3. otteniamo sicuramente un ciclo
    4. siccome l'arco precedente è più pesante di quello appena aggiunto se lo rimuovo ottengo un MST
  • corollario del teorema fondamentale degli MST
    1. A ⊆ E, A ⊆ MST
    2. C è una componente connessa di A
    3. l'arco a che collega C a un'altra componente connessa di A è leggero
    4. → l'arco a è sicuro per A
  • Kruskal O(m logm)
    • implementazione di MAKE_SET(x)
    • implementazione di UNION(x, y)
    • implementazione di FIND_SET(x)
  • Prim O(m logn)
    • implementazione della coda di vertici e della funzione EXTRACT_MIN
  • Funzioni INIT_SINGLE_SOURCE e RELAX
  • Dijkstra
    • con array O(n2) / O(n2)
    • con heap binario O(m log n) ⇒ O(n log n) / O(n2 log n)
    • Dijkstra per problemi di massimizzazione
  • Bellman-Ford O(n2) / O(n3)
    • verifica di proprietà di cicli, per esempio
      Πi=1qwxi-1xi<1
  • Floyd-Warshall O(n3)
  • Clique

Algoritmo per scovare cicli in un grafo (passo passo)

Tratto dall'esame del 27/05/2017 di Algoritmi e Strutture Dati (M. Pelillo)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.   for j = 1 to n
5.     b[i,j] = 0
6.     for k = 1 to n
7.       b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.  for j = i + 1 to n
11.     if a[i,j]*b[i,j] <> 0 then
12.return FALSE
13.return TRUE

Evidentemente l'algoritmo è composto da due parti: nella prima si crea una matriche di dimensioni uguali alla matrice di adiacenza e si fa un calcolo.
Nella seconda, si verifia la matrice ottenuta in modo che se lo stesso elemento nella matrice di adiacenza e nella matrice calcolata contiene 1 si restituisca FALSE.

Esempio


La matrice di adiacenza corrispondente è la seguente:

A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

  • i = 1
  • j = 1
  • k = 1 ⇒ 5

Matrice a

Matrice a
A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

Matrice b, k = 1
A B C D E
A 0
B
C
D
E
Matrice b, k = 2
A B C D E
A 1
B
C
D
E
Matrice b, k = 3
A B C D E
A 1
B
C
D
E
Matrice b, k = 4
A B C D E
A 1
B
C
D
E
Matrice b, k = 5
A B C D E
A 2
B
C
D
E

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

  • i = 1
  • j = 2
  • k = 1 ⇒ 5

Matrice a

Matrice a
A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

Matrice b, k = 1
A B C D E
A 2 0
B
C
D
E
Matrice b, k = 2
A B C D E
A 2 0
B
C
D
E
Matrice b, k = 3
A B C D E
A 2 0
B
C
D
E
Matrice b, k = 4
A B C D E
A 2 0
B
C
D
E
Matrice b, k = 5
A B C D E
A 2 1
B
C
D
E

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

  • i = 1
  • j = 3
  • k = 1 ⇒ 5

Matrice a

Matrice a
A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

Matrice b, k = 1
A B C D E
A 2 1 0
B
C
D
E
Matrice b, k = 2
A B C D E
A 2 1 1
B
C
D
E
Matrice b, k = 3
A B C D E
A 2 1 1
B
C
D
E
Matrice b, k = 4
A B C D E
A 2 1 1
B
C
D
E
Matrice b, k = 5
A B C D E
A 2 1 1
B
C
D
E

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

  • i = 1
  • j = 4
  • k = 1 ⇒ 5

Matrice a

Matrice a
A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

Matrice b, k = 1
A B C D E
A 2 1 1 0
B
C
D
E
Matrice b, k = 2
A B C D E
A 2 1 1 1
B
C
D
E
Matrice b, k = 3
A B C D E
A 2 1 1 1
B
C
D
E
Matrice b, k = 4
A B C D E
A 2 1 1 1
B
C
D
E
Matrice b, k = 5
A B C D E
A 2 1 1 2
B
C
D
E

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

  • i = 1
  • j = 5
  • k = 1 ⇒ 5

Matrice a

 

Matrice a
A B C D E
A - 1 0 0 1
B 1 - 1 1 1
C 0 1 - 0 0
D 0 1 0 - 1
E 1 1 0 1 -

Matrice b, k = 1
A B C D E
A 2 1 1 2 0
B
C
D
E
Matrice b, k = 2
A B C D E
A 2 1 1 2 1
B
C
D
E
Matrice b, k = 3
A B C D E
A 2 1 1 2 1
B
C
D
E
Matrice b, k = 4
A B C D E
A 2 1 1 2 1
B
C
D
E
Matrice b, k = 5
A B C D E
A 2 1 1 2 1
B
C
D
E

Qui termina l'elaborazione della prima delle cinque righe, per tutte le colonne e per tutte le adiacenze.
Cosa ci dice questo primo risultato?

Ci dice che il vertice A ha in comune:

  • con se stesso i vertici B ed E, per un totale di due
  • con B il vertice E, per un totale di uno
  • con C il vertice B per un totale di uno
  • con D i vertici B ed E, per un totale di due
  • con E il vertice B, quindi uno

Al termine del ciclo annidato, la tabella b prende i seguenti valori:

Matrice b, risultato finale
A B C D E
A 2 1 1 2 1
B 1 4 0 1 2
C 1 0 1 1 1
D 2 1 1 2 1
E 1 2 1 1 3

Possiamo osservare che anche se la matrice b contiene 25 valori, la diagonale principale rappresenta il numero di archi collegati al vertice in oggetto (es. il vertice A ha due archi, quindi il valore è 2).

Inoltre, essendo un grafo non orientato, anche la b gode della simmetria, quindi il "calcolo" vero e proprio consiste solo in 10 "celle" (n * (n-1) / 2).

Matrice b, significato di diagonale e simmetria
A B C D E
A 2 1 1 2 1
B 1 4 0 1 2
C 1 0 1 1 1
D 2 1 1 2 1
E 1 2 1 1 3

Se ora sovrapponiamo a e b (moltiplicandone i valori tra loro), otteniamo una matrice contenente alcuni archi:

Matrice a * b
A B C D E
A - 1 0 0 1
B 1 - 0 1 2
C 0 0 - 0 0
D 0 1 0 - 1
E 1 2 0 1 -

Conclusioni

Questo algoritmo serve a individuare se in un grafo sono presenti cicli composti da tre vertici.

Costi di esecuzione / esercizio

Dimostrare che11

n+10=Θn

Dobbiamo dimostrare che esistono due valori c1 e c2 tali che vale

c1nn+10c2n

Eleviamo tutto al quadrato per togliere le radici:

c12nn+10c22n

Prima dimostriamo che esiste c1

c12nn+10c12n-n10nc12-110

siccome n è sempre non negativo, ci basta verificare per quali valori di c12 il termine dentro la parentesi è positivo. Quindi con c12 ≥ 1 e n qualsiasi (es. 1) la disuguaglianza è verificata.

Poi dimostriamo che esiste c2

n+10c22n10nc22-1

In questo caso, la costante c22 va calcolata in base a n

10c22-1n

2018-06-18_2 esercizio "integer sort"

Tema

Descrivere un algoritmo che, dati n numeri interi compresi nell’intervallo da 0 a k, svolga un’analisi preliminare del suo input e poi risponda nel tempo O(1) a qualsiasi domanda su quanti degli n interi ricadono nell’intervallo [a..b] con a e b interi. Il vostro algoritmo dovrebbe impiegare un tempo È(n+k) per l’analisi preliminare.

Svolgimento

Nota: descrivere = scrivere.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N_ELEMENTS 20
#define MAX_ABS_VALUES 50

int *prepare(int values[], int size, int *min, int *max) {
	int i;
	int * aux;
	if(size == 0) {
		return NULL;
	}
	*min = values[0];
	*max = values[0];
	for(i = 0; i < size; i++) {
		if(values[i] < *min) *min = values[i]; if(values[i] > *max) *max = values[i];
	}
	aux = malloc(sizeof(int) * (*max - *min + 1));
	for(i = 0; i < *max - *min + 1; i++) aux[i] = 0;
	for(i = 0; i < size; i++) {
		aux[values[i] - (*min)]++;
	}
	for(i = 1; i < *max - *min; i++) aux[i] = aux[i] + aux[i-1];
	return aux;
}


int main(int argc, char *argv[])
{
	int *values; // contiene i valori non ordinati
	int min; // il valore più piccolo
	int max; // il valore più grande
			 // la dimensione del vettore di appoggio è data da min - max
	int *aux; // l'array ausiliario dell'integer sort
	int i;
	int da, a; // il minimo e massimo tra i valori chiesti all'utente
	int ind_da, ind_a; // gli indici più vicini a da e a
	
	values = malloc(sizeof(int) * N_ELEMENTS);
	srand(time(0));

	for(i = 0; i < N_ELEMENTS; i++)
		values[i] = rand() % (MAX_ABS_VALUES * 2) - MAX_ABS_VALUES;

	aux = prepare(values, N_ELEMENTS, &min, &max);

	for(i = 0; i < max - min; i++) printf("%d: %d\t", i+min, aux[i]);

	printf("\nInserire il primo elemento: ");
	scanf("%d", &da);
	printf("Inserire il secondo elemento: ");
	scanf("%d", &a);

	if(a - da < 0) { a = da+a; da = a-da; a = da-a;} // scambio gli elementi se a < da

	printf("La quantità di numeri compresi tra %d e %d e' %d\n", da, a, (a>=max?aux[max-min-1]:aux[a-min]) - (da<=min?0:aux[da-min-1]));

	system("PAUSE");
	return 0;
}

Commento all'algoritmo

L'algoritmo è una variante dell'integer sort.

Dati n numeri compresi tra n1 e n2 si inizializza un array di k+1 elementi indicizzati da 0 a n2 - n1 e inizializzati a zero.

Esempio (vettore n):

6 -7 5 -1 8 0 4 -2 -8 3

Per ogni elemento in n si incrementano gli indici corrispondenti come nell'integer sort:

Esempio (vettore k):

Ind: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
Val: 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1

poi si cumula la somma da n1 a n2

Ind: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
Val: 1 2 2 2 2 2 3 4 5 5 5 6 7 8 9 9 10

Questo richiede ancora un costo Θ(n+k).

In tempo O(1) si estrae l'elemento precedente di A (o zero se A è il primo) e si sottrae all'elemento B.

Esempio:

A = -2

B = 3

k[A-1] = 3

k[B] = 5

k[B] - k[A-1] = 2

Se A o B sono rispettivamente minore del più piccolo e maggiore del più grande è sufficiente considerare il primo e l'ultimo elemento.

Come richiesto, il tempo di preparazione è Θ(n+k) e quello di consultazione è O(1).

Commento al codice

Si è deciso di separare la procedura principale (il tema d'esame) da quella di appoggio, contenente l'inizializzazione e le richieste all'utente.

La chiamata prevede il ritorno di tre valori: l'array k e il minimo e il massimo. Questi due valori sono due int nella procedura di appoggio, che sono passati come puntatori alla procedura principale.

Due costanti indicano la dimensione dell'array e l'intervallo di numeri che è possibile inserire in senso assoluto (es. 5 => da -5 a +5) ottenendo un intervallo di n*2+1 valori.

Nella procedura principale, i valori di minimo e massimo vanno inizializzati con uno dei valori dell'array, poi con un ciclo si valuta se abbassare il minimo o alzare il massimo.

È necessario anche inizializzare i valori dell'array k a zero, perché c'è una probabilità non nulla che alcuni valori non compaiano mai (soprattutto se |n| è piccolo e |k| è grande).

Rispetto all'integer sort è necessario un ulteriore ciclo per calcolare il valore cumulato, che però non ha impatti sul costo asintotico.

Nella procedura principale, a parte il popolamento dell'array con valori casuali, è degno di nota il sistema per gestire la richiesta di valori minori del minimo o maggiori del massimo, che per sintesi è reso con l'utilizzo di operatori ternari.

Ultimo esercizio del compito del 28/05/2018

Dato un grafo orientato e pesato G=(V, E) con pesi positivi, cioè w(u, v) > 0 per ogni (u, v) ∈ E, si vuole determinare se esiste in G un ciclo c ≡ <x0, x1, ... xq> (con x0 = xq) per cui sia soddisfatta la seguente condizione:

Πi=1q2wxi=1xi3>2q

Si sviluppi un algoritmo per risolvere questo problema, se ne discuta la correttezza e si determini la sua complessità computazionale. (Suggerimento: si cerchi di ricondurre il problema dato ad uno noto)

Heap 09/09/2014

Dare la definizione di max-heap e dire se ‹23,17,14,6,13,10,1,5,7,12› è un max-heap giustificando la risposta.

Svolgimento

Un max-heap è un albero in cui gli elementi sono tutti non maggiori dell'elemento padre.

L'implementazione ad array di uno heap binario consiste nel posizionare come primo elemento la radice dell'albero (23, nell'esercizio) e poi per ogni livello l 2l elementi, in posizione 2l e 2l+1.

L'albero corrispondente all'array è quindi

               23
      17              14
  6        13      10     1
5   7    12

Dal momento che 7 > 6, questo non è un max-heap.

Hash - 12/06/2014

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Svolgimento

Caso A:

  1. 23 mod 17 = 6 → 6[0] = 23
  2. 40 mod 17 = 6 → 6[1] = 40
  3. 15 mod 17 = 15 → 15[0] = 15
  4. 58 mod 17 = 7 → 7[0] = 58
  5. 85 mod 17 = 0 → 0[0] = 85

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23, 40; 7: 58; 8:; 9:; 10:; 11:; 12:; 13:; 14:; 15: 15; 16:;

Caso B

  1. i = 0, k = 23: (23 mod 17 + 0 * 2*23 mod 5) mod 17 = 6
  2. i = 1, k = 40: (40 mod 17 + 1 * 2*40 mod 5) mod 17 = 6: c'è una collisione, quindi si scorre fino al numero 7
  3. i = 2, k = 15: (15 mod 17 + 2 * 2*15 mod 5) mod 17 = 15
  4. i = 3, k = 58: (58 mod 17 + 3 * 2*58 mod 5) mod 17 = 10
  5. i = 4, k = 85: (85 mod 17 + 4 * 2*85 mod 5) mod 17 = 0

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23; 7: 40; 8:; 9:; 10: 58; 11:; 12:; 13:; 14:; 15: 15; 16:;

Hash 28/01/2015

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:
18, 36, 155, 19
La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:
h(k, i) = (k mod m + i * 2k mod 5) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

i = 0, k = 18 → (18 mod 17 + 1 * 218 mod 5) mod 17 = (1 + 0 * 8) mod 17 = 1

i = 1, k = 36 → (36 mod 17 + 1 * 236 mod 5) mod 17 = (2 + 1 * 2) mod 17 = 4

i = 2, k = 155 → (155 mod 17 + 2 * 2155 mod 5) mod 17 = (2 + 2 * 1) mod 17 = 4: collisione

i = 3, k = 155 → (155 mod 17 + 3 * 2155 mod 5) mod 17 = (2 + 3 * 1) mod 17 = 5

i = 4, k = 19 → (19 mod 17 + 4 * 219 mod 5) mod 17 = (2 + 4 * 16) mod 17 = 15

La hash finale è la seguente (l'indicizzazione è 0 - n-1):

[_] [18] [_] [_] [36] [155] [_] [_] [_] [_] [_] [_] [_] [_] [_] [19] [_]

Funzioni efficienti (grafi) - 08/09/2014-2

Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):

A B C D E
A 0 3 5 11 9
B 3 0 3 9 8
C 5 3 0 +∞ 10
D 11 9 +∞ 0 7
E 9 8 10 7 0

Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.

Svolgimento

Il grafo è non orientato, poiché la matrice di adiacenza è simmetrica.

Si può utilizzare l'algoritmo di Kruskal, che è corretto, poiché è composto da

  1. un'inizializzazione con tempo O(n) che termina sicuramente, in quanto è un ciclo
  2. un ordinamento degli archi con costo O(m log(m)), che termina sicuramente, utilizzando un algoritmo di ordinamento che termina (es. mergesort o quicksort)
  3. un ciclo per ciascun arco O(m) per ciascuno dei quali è necessario verificare se i due vertici appartengono allo stesso insieme O(log(n)) ⇒ O(m log(n)), operazione che termina sicuramente
  4. l'aggiunta dell'arco e l'unione (eventuale) dei due sottoinsiemi, con costo O(log(m)), che termina sicuramente.

e che ha un costo complessivo di esecuzione O(m log(m))

  1. gli archi ordinati sono AB(3), BC(3), AC(5), DE(7), BE(8), AE(9), BD(9), CE(10), AD(11), CD(+∞)
  2. AB costituisce il primo arco aggiunto all'albero U, e A, B i primi due vertici (nota: sarebbe stato indifferente iniziare con BC, con un esito diverso ma costi uguali). Ora U = {A, B, (AB)}
  3. BC è aggiunto, in quanto C non appartiene a U. Ora U = {A, B, C, (AB), (BC)}
  4. AC non è aggiunto, in quanto sia A sia C appartengono a U
  5. DE è aggiunto - pur non essendo ancora connesso. Ora U = {A, B, C, D, E, (AB), (BC), (DE)}
  6. BE è aggiunto, perché B ed E appartengono a due set diversi. Ora U = {A, B, C, D, E, (AB), (BC), (DE), (BE)}
  7. Per brevità riportiamo in un solo passaggio AE, BD, CE, AD, CD, che non sono inclusi.

Le strade da realizzare sono quelle evidenziate in neretto:

A B C D E
A 0 3 5 11 9
B 3 0 3 9 8
C 5 3 0 +∞ 10
D 11 9 +∞ 0 7
E 9 8 10 7 0