# data[].attributes.body
Grafi orientati e aciclici
Un ordinamento topologico di un grafo orientato e aciclico è un ordinamento dei suoi vertici tale
che, se essi vengono posti su una linea secondo quest’ordine, tutti gli archi sono diretti da sinistra
verso destra.

Proposta di visualizzazione
determina un ordinamento topologico dei vertici di un grafo,
provate a visualizzarlo: dato in input un grafo orientato aciclico, create un video in cui si mostri
come vengono ordinati i suoi vertici per formare un ordinamento topologico.

# data[].attributes.headline
6- Copertura massimale di vertici in un grafo

# data[].attributes.subject
6- Copertura massimale di vertici in un grafo

# data[].attributes.body
Una copertura di vertici di un grafo G=(V,E) è un sottoinsieme di vertici C tale che, comunque si scelga un arco di G, almeno uno dei suoi estremi si trova in C.

Proposta di visualizzazione
Creare un video in cui viene mostrato come vengono scelti i vertici di una copertura

# data[].attributes.body
La colorazione dei vertici di un grafo è un'assegnazione di etichette, tradizionalmente chiamate "colori", ai vertici di un grafo tale che nessuna coppia di vertici adiacenti condivida lo stesso colore. L’obiettivo è quello di usare il minor numero possibile di colori.

Pensare ad un possibile algoritmo

Proposta di visualizzazione
Se vi è chiaro il metodo con cui si colorano in modo goloso i nodi di un grafo, provate a
visualizzarlo: dato in input un grafo, create un video in cui si mostri come scegliere i colori per i suoi vertici.

# data[].attributes.body
Dati n punti nel piano è il più piccolo poligono convesso che contiene gli n punti dati

Proposta di visualizzazione
L’'algoritmo di Graham, considerate n punti del piano e
provate a produrre un video che visualizzi il funzionamento dell’algoritmo che ne trova
l’inviluppo convesso.

# data[].attributes.body
Un ladro che deruba un negozio trova n oggetti. L’i-esimo oggetto vale e i euro e pesa p i chili. Il ladro vuole prendere il maggior valore possibile con il minor peso. Sapendo che il suo zaino può sopportare un peso massimo P, quali oggetti dovrà scegliere?

Per risolvere la versione frazionaria, calcoliamo il valore per chilo di ogni oggetto: e i /p i . La strategia migliore è che il ladro cominci a prendere la maggior quantità possibile dell’oggetto con massimo valore per chilo. Se tale oggetto viene tutto incluso e ancora c’è spazio nello zaino, il
ladro prenderà quanto più possibile dell’oggetto con secondo valore per chilo, e così via, fino a raggiungere il limite P dello zaino. Poiché gli elementi vanno ordinati rispetto al loro valore per chilo, il costo di questo algoritmo dipenderà dal tempo necessario per ordinare gli n oggetti.

Proposta di visualizzazione
calcolare una soluzione dello zaino frazionario, data un’istanza del problema (un intero n, n valori e i , n valori p i ed un valore soglia P) provate a produrre un video che visualizzi il funzionamento dell’algoritmo goloso che trova la soluzione ottima.

# data[].attributes.body
Un numero naturale maggiore o uguale a 2 è primo se ammette solo due divisori: 1 e se stesso.

Un metodo per trovare tutti i numeri primi fino ad un fissato limite superiore N

1. Cerchia il 2 ed elimina tutti i multipli presenti fino ad N

2. Cerchia il 3 ed elimina tutti i multipli presenti fino ad N

3. Cerchia il 5 ed elimina tutti i multipli presenti fino ad N

4. --------

Algoritmo

si cerchia il primo numero non setacciato;

si eliminano tutti i suoi multipli

Proposta di visualizzazione

Crivello di Eratostene, provate a visualizzarlo: dato in input un numero (intero) n, create un video in cui si mostri come elencare tutti i numeri primi da 1 a n.

# data[].attributes.body
Proposta di visualizzazione
Visualizzate l’algoritmo per contare in binario: dato in input un numero (decimale) n, create un
video in cui si mostra come contare in binario da 0 a n.

# data[].attributes.body
Il bubblesort effettua all'incirca N^2/2 confronti ed N^2/2 scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è Ө(n^2).

# data[].attributes.body
Si divide il vettore dei dati in due parti ordinate separatamente, quindi si fondono le parti per ottenere un vettore ordinato globalmente - complessità  Ө(n).

# data[].attributes.body
Mergesort

Bubblesort

# data[].attributes.body
Un algoritmo, dato un input, genera un output proseguendo per passi successivi
Tre proprietà:

1. Definitezza : ogni passo deve essere definito in modo chiaro e non ambiguo, dando luogo alla stessa sequenza di operazioni, indipendentemente da chi lo esegue e in quale momento

2. Finitezza: l’algoritmo deve terminare dopo l’esecuzione di un numero finito di passi

3. Effettività: deve essere effettivamente eseguibile, ovvero ogni operazione deve essere sufficientemente basilare da poter essere eseguita “a carta e penna” in una quantità finita di tempo

# data[].attributes.body
Ciclo

Ciclo minimo

# data[].attributes.body
Cammino tra due nodi

Cammino minimo tra due nodi

# data[].attributes.body
Ө(logn) nel caso peggiore (l’elemento non c’è);

# data[].attributes.body
scorri i numeri da sinistra verso destra, finché non trovi quello cercato o un numero più grande

Al più n operazioni elementari (confronti)

la complessità del caso peggiore è un Ө(n).

# data[].attributes.body
Ricerca sequenziale

Ricerca binaria

# data[].attributes.body
Operazioni elementari: operazioni di confronto, di assegnazione, aritmetico/logiche...

Contiamo il numero di operazioni elementari compiute da un algoritmo

Se lo ripetiamo per diverse dimensioni dell’input, otteniamo una funzione che misura l’efficienza dell’algoritmo

Quanto meno la funzione cresce al crescere della dimensione dell’input, tanto più l’algoritmo verrà considerato efficiente

# data[].attributes.attachment_link.title
La Copertura di Vertici - Fun With Algorithms - ASL 2017