Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Tommaso Bertoni - Efficienza di Elaborazione (informatica)

Tesi di Maturità 2013 di Tommaso Bertoni - Efficienza di Elaborazione (informatica)
by

Tommaso Bertoni

on 25 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Tommaso Bertoni - Efficienza di Elaborazione (informatica)

printf("H
llo World");
Computazione
Il termine “computazione” deriva dal latino “computare” (letteralmente “contare”). Nell’ambiente informatico viene utilizzato per descrivere la capacità di un computer di elaborare informazioni e processare istruzioni.
Efficienza
Algoritmi
algoritmo applicato:
L’algoritmo mostrato si basa sull’applicazione del metodo di Laplace per il calcolo del determinante di una matrice.
Esso consiste nel prendere ogni elemento (per esempio della prima riga) e moltiplicarlo per il determinante della matrice di ordine minore, alternando fra un elemento e l’altro l’operazione di sottrazione e addizione.
...non solo efficacia!
Come abbiamo potuto osservare dall’applicazione il metodo di Laplace diventa veramente pesante da elaborare, già per input di dimensioni ridotte!
Il secondo algoritmo, quello ideato da Gauss, si rivela decisamente molto più efficiente, sia nel tempo che nello spazio utilizzato in memoria!
Complessità Computazionale
teoria della complessità computazionale
La complessità computazionale è una branca della teoria della computabilità che studia le risorse necessarie per l’esecuzione di un algoritmo.
algoritmi a confronto
Mettiamo ora a confronto i due algoritmi visti prima:
metodo di Laplace:
metodo di Gauss:
Per quanto riguarda la comprensione dei successivi ragionamenti basta conoscere che la notazione O (o grande) definisce per un algoritmo una misura del numero di operazioni da eseguire nel peggiore dei casi, dato un input di dimensione N.
NB: la notazione O si dice essere asintotica, ovvero nel suo computo viene considerato soltanto il termine di grado massimo perché si vuole vedere il comportamento dell’algoritmo per N→∞.
Supercomputer
descrizione dei supercomputer
Con il termine “supercomputer” si intende una rete di computer interconnessi in grado di sviluppare enormi potenze di calcolo rispetto ai computer domestici. Esistono due tipologie fondamentali di supercomputer: grid e cluster.
I supercomputer di tipo grid sono formati da un nucleo di elaborazione centrale connesso ad altri computer dislocati: questo sistema viene utilizzato per gestire il salvataggio e il recupero di grandi quantità di dati, utilizzando quindi connessioni molto veloci. Un esempio è il supercomputer del CERN.
I supercomputer di tipo cluster, invece, sono utilizzati per la loro grande capacità di elaborazione istantanea, in quanto sono composti da un grande numero di computer comunicanti controllati da un software che suddivide il lavoro e permette l’elaborazione in parallelo (multitasking). Questo sistema viene utilizzato soprattutto nei centri di ricerca e negli osservatori.
capacità di elaborazione
Questi enormi calcolatori sono stati e lo sono tutt’ora utilizzati per previsioni del tempo, simulazioni di volo, studi sulle radiazioni, test di decodifica informatica, simulazioni di attacchi nucleari, ricerche sulle interazioni chimiche, studio della struttura del DNA e di molecole.
esempi reali
Il primo supercomputer (CDC 6600) nacque nel 1964 ed aveva una potenza di calcolo di circa 10MHz (in media uno smartphone moderno sviluppa una potenza 100 volte superiore).
Oggigiorno, date le incredibili potenze di calcolo raggiunte, si utilizza il PetaFLOPS (o PFLOPS) come unità di misura (un PFLOPS significa una potenza di un milione di miliardi di istruzioni in virgola mobile al secondo, o in forma esponenziale ).

La classifica mondiale dei supercomputer è data dalla raccolta Top500: il terzo in classifica (Sequoia) ha 1,5 milioni di cores e sviluppa una potenza di 16.3 PFLOPS; il secondo classificato (Titan), invece, dispone di un terzo dei core di Sequoia (circa 560 000) e sviluppa una potenza di 17.6 PFLOPS.
È stato da poco completato il supercomputer cinese Tianhe-2 che,
con i suoi 3 milioni di cores riesce a raggiungere la potenza di 30.65 PFLOPS posizionandosi al primo posto nella classifica.
Computer Quantistici
I computer quantistici, o computer quantici, sono dispositivi di calcolo completamente rivoluzionari che utilizzano come celle di memoria particelle elementari (i più usati sono atomi di fosforo); i bit di un computer normale equivalgono quindi ai qbit (quantum bit).

A differenza dei computer classici che lavorano utilizzando il codice binario, i computer quantistici sfruttano le proprietà della meccanica quantistica ed elaborano i dati utilizzando una logica probabilistica applicata allo stato quantico dei qbit.

Lo stato quantico di un qbit risulta comunque essere 1 o 0, ma solo dopo essere stato letto: prima della lettura viene considerato contemporaneamente 1 e 0, associando ad ogni valore una certa probabilità. Si può immaginare lo stato quantico come le coordinate geografiche.
teoria dei computer quantistici
capacità di elaborazione
La potenza dei computer quantistici deriva dal fatto che sono in grado di rappresentare più situazioni logiche contemporaneamente: per esempio un computer classico ad 8 bit può rappresentare un numero compreso fra 0 e 256,
un computer quantistico ad 8 qbit, invece, rappresenta contemporaneamente
tutti i numeri da 0 a 256.
I computer quantistici, però, non sono progettati per rimpiazzare i computer odierni! Essi, infatti, riescono a risolvere in un periodo molto minore solo alcune categorie di problemi, ma non sono progettati per essere più veloci rispetto una singola operazione!
“Quantum computers have the potential to solve problems that would take a classical computer longer than the age of the universe”.
David Deutsch

esempi reali
Algoritmi Quantistici
algoritmo di fattorizzazione di Shor
Questo algoritmo risolve il problema della fattorizzazione dei numeri interi in numeri primi e ha una complessità computazionale polinomiale, ovvero .

Nel 2001, l’algoritmo è stato applicato da un gruppo di ricerca all’IBM ed è riuscito a fattorizzare 15 in 3x5, venendo eseguito da un computer quantistico a 7 qbit.
algoritmo di ricerca di Grover
Questo algoritmo risolve il problema di ricerca in un database non ordinato di N elementi e ha una complessità computazionale temporale e spaziale .
La D-Wave System è una società di ricerca sul calcolo quantistico: nel 2011 viene annunciato il primo computer quantistico disponibile in commercio, il D-Wave One operante a 128 qbit.
Nel 2013 la NASA e Google hanno iniziato una collaborazione per la ricerca sull’intelligenza artificiale basata sul calcolo quantistico: hanno quindi ordinato alla D-Wave un computer a 512 qbit, il D-Wave Two del quale i primi test hanno mostrato che la potenza equivale al decimo supercomputer nella classifica Top500 (1,5 PFLOPS).
Entro due anni D-Wave pensa di riuscire a sviluppare un chip da 2048 qbit.
Sala server, presso CERN
Esempio di architettura Cluster
Sequoia
Titan
Tianhe-2
D-Wave Two
Il chip Veusvius a 512 qubit.
Ad oggi ne sono stati creati solo 5.
e
Full transcript