ALGORITMI DISCRETI, MA
IN PRIMA PAGINA
Raffaele Giancarlo
Dipartimento di Matematica ed Informatica
Università di Palermo
…circa 1200 anni fa
Abu Abdullah Muhammad bin Musa alKhwarizmi
Algoritmo-Intuizione
Esempio: Preparare il caffè
Anni Trenta
Algoritmi-formalizzazione…Turing,
Post….
Church,
Kleene,
Godel,
Una sequenza ordinata finita di passi, ognuno di essi effettivamente
eseguibile in tempo finito, che produce un risultato in tempo finito
Anni 40
Kissing The War GoodBye
Prova in Itinere
(a)Si sono conosciuti
via Facebook ?
(b) Quanto e’ durata la
loro relazione ?
the fab 60s
Non solo algoritmi
buoni algoritmi e metodologie teoriche per il
loro progetto ed analisi: Knuth, Tarjan,
Hopcroft
Algoritmi Discreti
strutture matematiche discrete: buoni modelli
per rappresentare problemi computazionali
•
•
Esempio: Grafi
Algoritmi Discreti
strutture
matematiche
discrete:
organizzazione efficace dell’informazione
•
•
Esempio: Alberi
Quando Finisce la Presentazione?
-ALGORITMI: ok
- DISCRETI: ok
-IN PRIMA PAGINA: Il nuovo
comincia bene per gli algoritmi
millennio
Il Nuovo Millennio
Persone dell’ Anno 2005 per il Finantial Times
-Innovazione con successo istantaneo:in sette anni,
da studenti brillanti a persone d’influenza planetaria
Sorting and searching ai tempi di Internet
Sorting and Searching nel Nuovo
Millennio
Sorting and Searching nel Nuovo Millennio
Prova in itinere-Quali delle due seguenti attività
richiede piu’ risorse di calcolo:
Cercare velocemente su
Internet “pianeta Luna,
Pizzeria Carmine”
(A)
(B) Andare direttamente in
pizzeria…sulla luna
Sorting and Searching nel Nuovo
Millennio
-Google affronta problemi classici di algoritmi
in maniera nuova:

La quantità di dati da gestire è cambiata
radicalmente negli ultimi 50 anni, con
accellerazione negli ultimi 15.


Indice di Google richiede piu’ di 100.000.000 di Gb di
memoria ed e’ stato costruito usando 1.000.000 di
ore macchina su processori con velocita’ nei gigahertz
Apollo 11 spacecraft control: 64kb di memoria e
processore con velocità di 0.043MHz
Il Nuovo Millennio
Vincitori Premio Nobel per la Chimica 2013
Levitt, Karpus, Warshel
-Innovazione
con lungimiranza, perseveranza e pazienza:
dagli
anni
70,
hanno
insegnato
la
chimica
al
computer…mentre altri continuavano ad usare le provette
Biologia Computazionale e Bioinformatica
Biologia Computazionale e Bioinformatica
1953-Scoperta la struttura
Tridimensionale del DNA
-Il codice genetico degli esseri viventi è
contenuto nel genoma, una sequenza di
lettere, che in natura vive in forma
tridimensionale
Biologia Computazionale e Bioinformatica
2001-si ottiene la sequenza di lettere del
genoma umano
-Sequenziamento
genomico-Contributo
essenziale degli algoritmi
Biologia Computazionale e Bioinformatica
•
Perche’ sequenziamento genomico ?
•
•
•
Capire come funzionano gli esseri viventi
Capire basi molecolari di patologie
Medicina personalizzata
Perche’
Biologia
Bioinformata?
•
•
Computazionale
e
Dedurre da osservazioni di biologia molecolare
richiede gestione ed analisi di quantità di dati
confrontabile con Internet…e il CERN
Il Nuovo Millennio
-Prossimi argomenti non trattati nei libri di testo che ho studiato
-Promemoria: Richiedere, con urgenza, nuovi libri e aggiornarsi
Il Nuovo Millennio
BUONGIORNO ALGORITMI DELL’AMORE
La Stampa Nazionale ha parlato molto del
prossimo algoritmo
Analisi Strutturale di Reti Sociali
Quanta informazione circa noi stessi riveliamo
con le nostre sole connessioni sociali ?
Relazioni importanti???
Input
•
Nodo u e il suo network di conoscenze
•
u dichiara che il suo patner e’ nel network
Domanda
Esiste un algoritmo che, con un buon livello
di confidenza, identifichi il patner di u solo
utilizzando le informazioni date in input ?
•
Ovviamente si, ma noi vogliamo valutare la
bonta’ del nuovo algoritmo
•
Algoritmo-Intuizione
•
…non c’e bisogno di Facebook
Una misura di Dispersione
•
Osservazione:
•
I vicini comuni di u ed il suo patner v non sono
ben connessi gli uni con gli altri, e quindi u e v
agiscono
congiuntamente
come
i
soli
intermediari tra queste due parti del network
Tale osservazione puo’ essere formalizzata
usando la teoria dei grafi e poi calcolata
velocemente
•
Dispersione
•
Performance: validazione sperimentale
•
•
Nel 50% dei casi, si riesce ad identificare
correttamente il patner
Altre misure si fermano al 28%
Esiste una correlazione tra dispersione in una
coppia e durata della relazione ? Si, ma questa
e’ solo una piccola parte dello studio
•
Analisi di reti
Dov’e la novita? (in fin dei conti l’idea poteva
venire anche ad un matrimonio…)
•


La quantita’ di dati dispinibili, organizzati in
maniera coerente, rende agevole fare delle
ipotesi e testarle su dati reali. Cio’ vale anche
per reti biologiche.
Si confronti la “Dispersione” con gli studi sui “six
degrees of separation”
Messaggio da portare a casa
La tecnologia apre orizzonti inimaginabili fino
a qualche decennio fa…ma crea anche seri
problemi
ai
fondamenti
dell’Informatica…compreso gli algoritmi
•
FONDAMENTI: CONOSCERE I VECCHI, COSTRUIRNE DI
NUOVI