[Giornata II] “Ordine, Caos, Complessità e Sistemica” – La prospettiva degli informatici

Postato il Aggiornato il


homepage  » 19|05|16 – giornata I // 26|05|16 – giornata II // 30|05|16 – giornata III // video e slides


CatturaLocandina jpg - Copia

Ordine, Caos, Complessità e Sistemica” – Ciclo di seminari scientifici

Giornata II: la prospettiva degli informatici

Calendar-Time26 Maggio 2016, ore 15.00 – 17.30
map-8Dipartimento di Fisica e Chimica – UNIPA, Aula A, via Archirafi, 36, Palermo
usersPer tutti gli interessati – Partecipazione libera
icon-webapp>>Website iniziativa<<
 Evento FB
business_contactmail Comitato Organizzatore

Prosegue l’iniziativa mirata all’esplorazione del concetto di Complessità nelle sue molteplici accezioni e allo studio dei sistemi complessi. La parola agli informatici !


Programma della giornata

Ore 15.00 – Apertura dei lavori                                           

  • Saluti del Comitato Organizzatore (Alberto Miserendino, Riccardo D’Elia, Mirko Zichichi)
  • Saluto istituzionale del prof. Girolamo Cirrincione, Prorettore alla Ricerca dell’UNIPA

Interventi programmati    (chairman: Mirko Zichichi)

  • “Calcolabilità e complessità: quello strano miracolo di cui parlava Gödel”

Relatore

Settimo Termini, già professore ordinario di Informatica Teorica

Dipartimento di Matematica e Informatica, Università degli Studi di Palermo, Via Archirafi, 34, Palermo, Italia

[curriculum vitae][settimo.termini[AT]unipa.it]

Abstract

I termini che incontriamo nelle varie e differenti discipline e che denotano specifici concetti scientifici non sono altro che parole prese a prestito dal linguaggio naturale (potremmo dire “rubate”) e che la genialità di alcuni scienziati ha trasformato dando loro un’accezione particolare nell’ambito di un dominio più ristretto (quello, appunto, di validità della teoria proposta); si pensi a velocità, accelerazione, forza, energia, lavoro, distanza, area, misura, vicinanza, gruppo, e tanti altri ancora. A ciascuna delle particolari “concretizzazioni” corrisponde un’accezione sua propria. Cioè, non solo i termini hanno un significato specifico e meno generale del termine usato nel linguaggio comune ma le varie teorie sviluppate determinano varie ipostatizzazioni del concetto stesso, dell’idea informale da cui si era partiti. Ci può essere qui di aiuto la distinzione proposta da Rudolf Carnap tra explicandum ed explicatum di un concetto, il primo rappresentando ciò che desideriamo spiegare scientificamente, il secondo la particolare proposta che offriamo. I termini elencati sopra riguardano tutti la fisica o la matematica ma lo stesso avviene per parole che solo più di recente sono diventate termini tecnici come retroazione, informazione, calcolabilità, complessità. Termini che appaiono tutti molto meno ancorati al reale di quelli citati prima. Tra queste ve n’è una che presenta caratteristiche particolari ed proprio quella a proposito della quale Gödel ha usato il termine miracolo, la nozione di calcolabilità. In questo caso, infatti tutte le proposte formali fatte in un certo senso coincidono; definiscono tutte, infatti, la stessa classe di oggetti. Alla nozione intuitiva – all’explicandum – di “calcolabile”, corrispondono explicata che sono tutti estensionalmente equivalenti. Questa è la ben nota Tesi di Church-Turing. La stessa cosa non avviene per complessità o informazione. Osserviamo, però, che per alcuni aspetti, almeno, della nozione informale di complessità, per alcune delle sue formalizzazioni possibili, abbiamo necessità di appoggiarci alla teoria della calcolabilità e questo avviene per la cosiddetta teoria della complessità astratta di Manuel Blum e per la complessità “strutturale” di Kolmogorov-Chaitin-Solomonoff. Senza la teoria della calcolabilità avremmo potuto tranquillamente baloccarci con le idee informali, intuitive che stanno alla loro base e anche sviluppare osservazioni, legami, considerazioni generali acute e intelligenti ma senza trovare risultati teorici estremamente innovativi e profondi. Esistono, infine, legami tra la nozione di complessità strutturale e possibili definizioni di informazione. Ricordiamo tutto questo – sia pure di sfuggita e in modo estremamente rapido – perché ci permette di fare un’ultima osservazione di carattere generale. Tutto ciò che comincia prendere forma a metà degli anni ’30 del secolo scorso (più esattamente, guardando alla pubblicazione dei risultati, nell’anno 1936) e continua, per le cose a cui si è qui accennato, fino agli anni ’60 dello stesso secolo devono essere viste come come tessere di un puzzle o di un mosaico che non è stato ancora composto nella sua interezza e di cui fanno parte le intuizioni di un altro progetto visionario oggi dimenticato, quello della Cibernetica la quale ha tentato di fornire un quadro unitario e unificante per tutti i fenomeni nei quali svolgono un ruolo importante i concetti ai quali qui abbiamo accennato, indipendentemente dalla loro natura: fisica, biologica, artificiale. Programma che non è riuscito a realizzare in modo unitario le sue ambizioni più generali ma che – disgregandosi – ha fecondato di nuove intuizioni e suggerimenti molti settori di indagine e che – soprattutto nelle pagine di Wiener – ha posto una serie di questioni e problemi di assoluto interesse e attualità riguardo ai problemi etici e alle responsabilità sociali degli sviluppi tecnologici di queste nuove discipline.

Multimedia

Disclaimer: La proprietà intellettuale dei contenuti presentati nei video e nelle slides appartiene agli autori. Qualsiasi uso delle idee presentate, in ogni pubblicazione o presentazione, deve essere corredato di un chiaro riferimento esplicito al materiale citato, indicando il nome dell'autore che presenta, il nome della conferenza, la sua posizione e la data.

[live streaming (offline)] [slides] [video]

  • “Complessità Descrittiva e Complessità Computazionale”

Relatore

Antonio Restivo, già professore ordinario di Informatica Teorica

Dipartimento di Matematica e Informatica, Università degli Studi di Palermo, Via Archirafi, 34, Palermo, Italia

[curriculum vitae][antonio.restivo[AT]unipa.it]

Abstract

La nozione di Complessità in Computer Science ha avuto diverse formalizzazioni. In questa presentazione si accennerà a tre fra le più significative:

La Complessità Computazionale di un problema misura la quantità di risorse (tempo, spazio, …) utilizzate da un algoritmo che risolve il problema. Fra le più studiate vi è la complessità di tempo di un problema, che prende in considerazione il numero di “passi elementari” necessari ad un algoritmo per risolvere il problema, in funzione della taglia dei dati in ingresso. In tale contesto, emerge il paradigma della trattabilità: un problema viene considerato “trattabile” se appartiene alla classe P dei problemi risolubili in tempo polinomiale. Viene menzionato il famoso problema “P = NP ?”, che riguarda il rapporto tra la complessità della ricerca della soluzione di un problema e quella relativa alla verifica della correttezza della soluzione. Si accenna ad alcune interessanti implicazioni in crittografia e nelle dimostrazioni interattive.

La Complessità Descrittiva classifica invece i problemi in base alla complessità (ricchezza) del linguaggio formale (logico) che permette di esprimere il problema. Classi di problemi particolarmente significative in questo approccio sono la classe MSO (problemi esprimibili nella Monadic Second Order logic) e la classe FO (problemi esprimibili nella First Order logic). Mentre per la Complessità Computazionale si può parlare di una misura dinamica di complessità, la Complessità Descrittiva rappresenta invece una misura statica. Si accenna ad alcuni risultati che collegano la Complessità Computazionale e quella Descrittiva (Teoremi di R. Buchi, di R. McNaughton, di R. Fagin), e che sono all’origine di teorie matematiche abbastanza sofisticate.

La Complessità di Kolmogorov è anch’essa, in qualche modo, una misura statica di complessità, e quindi più assimilabile alla complessità descrittiva. La Complessità di Kolmogorov è stata inizialmente formulata per le stringhe (sequenze di caratteri): essa è definita come la lunghezza minima di un programma (di una macchina di Turing universale) che genera la stringa. Si dimostra la “robustezza” di tale nozione (l’indipendenza dalla particolare macchina di Turing universale), ma anche l'”impossibilità” di calcolarla. Tale nozione è all’origine della Teoria Algoritmica dell’informazione,  e permette, in particolare, di dare una definizione rigorosa di  sequenza “casuale”. Si accenna ad importanti applicazioni di tale teoria alla compressione dati,  e ad interessanti interpretazioni nell’ambito dell’inferenza induttiva e dell’apprendimento automatico.

Multimedia

Disclaimer: La proprietà intellettuale dei contenuti presentati nei video e nelle slides appartiene agli autori. Qualsiasi uso delle idee presentate, in ogni pubblicazione o presentazione, deve essere corredato di un chiaro riferimento esplicito al materiale citato, indicando il nome dell'autore che presenta, il nome della conferenza, la sua posizione e la data.

[live streaming (offline)] [slides] [video]

  • “Automi Cellulari e Gioco della Vita”

Relatore

Marco Elio Tabacchi, research assistant in Informatica

Gruppo di Ricerca SCo², Dipartimento di Matematica e Informatica, Università degli Studi di Palermo, Via Archirafi, 34, Palermo, Italia

Direttore scientifico dell’ Istituto Nazionale di Ricerche Demopolis

[curriculum vitae][metabacchi[AT]unipa.it]

Abstract

I giochi, in special modo quelli da tavolo, sono spesso un esempio artificialmente incarnato della emergenza della complessità in natura a partire da regole semplici. Si pensi agli scacchi, dove un numero di regole tutto sommato contenuto può dar luogo a partite di estrema complessità cognitiva, o al Go, le cui regole di base possono essere riassunte in meno di una cartella di testo ma che è considerato tra i giocatori esperti ancora più complesso. Solo adesso i sistemi informatici riescono ad affrontare e talvolta superare i giocatori umani, ad ulteriore dimostrazione del fatto che tra la complessità cognitiva ed i vari tipi di complessità formale di cui hanno discusso gli altri interventi di questa sessione esiste in qualche modo un legame.

Dietro le “macchine che giocano” esistono numerose classi di algoritmi, ma i loro stati interni (grossomodo analoghi a quelli che sono gli stati interni del pensiero umano, ammesso che esistano) sono spesso rappresentati utilizzando automi. Gli automi sono sistemi formali della Teoria dell’Informazione, e possono essere visti da diverse prospettive: ad esempio come risolutori di problemi o come descrittori di situazioni dinamiche. La nomenclatura è dovuta al fatto che gli automi forniscono un meccanismo esclusivamente sintattico; la semantica, sotto forma di condizioni di base e regole di evoluzione, viene fornita da un’entità cognitiva – oggi l’essere umano, domani forse una realizzazione dell’intelligenza artificiale.

Gli automi cellulari sono una particolare classe di automi con una vasta gamma di applicazioni, soprattutto nel campo delle simulazioni, ma possono essere utilizzati per costruire una famiglia molto interessante di giochi (i cosiddetti zero-player games) basati sull’idea che il giocatore stabilisca un insieme di condizioni iniziali e di regole che sovraintendono al sistema, e quindi esso proceda autonomamente fino alla conclusione, che risulterà vittoriosa se si saranno ottenute delle condizioni finali favorevoli. Il gioco della vita di J. H. Conway è un esempio di questo tipo, diventato estremamente popolare negli anni settanta con l’avvento dei primi calcolatori digitali a disposizione di tutti. In questo seminario vedremo una breve descrizione della base di funzionamento degli automi cellulari, ed esamineremo in dettaglio la filosofia e le regole che sottendono il gioco della vita. Costruiremo alcuni esempi semplici e complessi, e termineremo chiudendo sorprendentemente il cerchio del discorso iniziato con gli altri interventi della giornata mostrando come grazie alla complessità che emerge da regole estremamente semplici si possa giungere al concetto di calcolabilità, ed ancora una volta ritorni l’idea che l’explicatum del calcolabile sia effettivamente unico.

Multimedia

Disclaimer: La proprietà intellettuale dei contenuti presentati nei video e nelle slides appartiene agli autori. Qualsiasi uso delle idee presentate, in ogni pubblicazione o presentazione, deve essere corredato di un chiaro riferimento esplicito al materiale citato, indicando il nome dell'autore che presenta, il nome della conferenza, la sua posizione e la data.

[live streaming (offline)] [slides] [video]

  • Ore 17.30 – Chiusura dei lavori
  • Visite guidate alla Collezione storica degli strumenti di Fisica con sperimentazioni  (>>info e prenotazione<<)

 Programma del ciclo di seminari

Tutte le informazioni sull’iniziativa sono riportate nella homepage dedicata.

Locandina
Clicca su per essere reindirizzato alla homepage

Scienze e non solo” nasce come spazio di condivisione online di curiosità, news ed eventi scientifici, al fine di promuovere le iniziative scientifiche locali, divulgare e sensibilizzare l’opinione comune verso tematiche scientifiche, naturalistiche e tecnologiche. Seguici!

mail facebook Telegram channel rss
Consulta il calendario con tutti gli eventi in programma!

© 2016 Scienze e non solo di Alberto Miserendino. Tutti i diritti riservati. Note legali

Annunci

5 pensieri riguardo “[Giornata II] “Ordine, Caos, Complessità e Sistemica” – La prospettiva degli informatici

    […] 26|05|2016: La prospettiva degli informatici (>>programma e abstracts<<) […]

    Mi piace

    […] – giornata I // 26|05|16 – giornata II // 30|05|16 – giornata […]

    Mi piace

    […] – giornata I // 26|05|16 – giornata II // 30|05|16 – giornata […]

    Mi piace

    […] – giornata I // 26|05|16 – giornata II // 30|05|16 – giornata III // video e […]

    Mi piace

    […] » 19|05|16 – giornata I // 26|05|16 – giornata II // 30|05|16 – giornata III // video e […]

    Mi piace

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.