giuseppina trifiletti un bit è una cifra binaria, (in inglese "binary digit") ovvero uno dei due simboli del sistema numerico binario L’informatica pervade le discipline 4 In che senso l'informatica pervade le discipline ? Forse perché tutte utilizzano tecnologie informatiche ? La nostra idea non è questa. g. trifiletti CHIEDE LA SFINGE A PITAGORA Il pensiero, la letteratura, l'arte, ..., la natura, nascondono un cuore che pulsa al ritmo di 0 e 1 ? Oppure indossando occhiali digitali possiamo evidenziare un cuore digitale ? Gli occhiali digitali potrebbero fornire un modo di guardare il mondo più efficace di quelli utilizzati fino ad ora? IL SIGNOR Q un uomo più che discreto e … densamente razionale, pazientemente cerca … Io dico che il punto c’è. Non lo vedo ma ci credo!!! retta numerica cerca MISTER un tipo che di discreto non ha nulla ed è tutt’altro che razionale Che cerchi pure, io non sono previsto, dovrà inventarmi NON è un numero razionale, ma è irrazionale, è un numero reale r=1 0 0 2 1 2 3 2 e 3 NON sono numeri razionali, ma sono irrazionali, sono ambedue numeri reali l’insieme dei numeri reali non è numerabile, non è quindi possibile metterlo in corrispondenza biunivoca con i numeri naturali, R ha la potenza del continuo -3 -2 -1 0 1 2 3 0 1/16 1/8 1/4 1/2 2/3 5/6 11/12 1 Ci sono punti della retta a cui non corrisponde nessun numero razionale, Pitagora e quelli della sua setta rimasero folgorati da questa scoperta. 0 1 2 3 Di numeri irrazionali ce ne sono infiniti altri …, anzi ce ne sono molti di più degli stessi numeri razionali Questi non sono numeri razionali, ma numeri irrazionali, e occupano punti della retta. MA È SORPRENDENTE! È NUMERABILE HA CARDINALITÀ CIOÈ I NUMERI RAZIONALI SONO TANTI QUANTI I NUMERI NATURALI !!! CIOÈ È POSSIBILE METTERE IN CORRISPONDENZA BIUNIVOCA, UNO A UNO, I NUMERI NATURALI E I NUMERI RAZIONALI, COME SEGUE: "metodo diagonale" di Cantor La numerabilità dei razionali Il fatto che la cardinalità dei razionali sia la stessa degli interi è abbastanza sorprendente, in quanto si è passati da un insieme "discreto", cioè con punti staccati uno dall'altro, ad un insieme denso, cioè con la caratteristica che tra due numeri qualunque ce ne sono sempre infiniti. L’ IPOTESI DEL CONTINUO Cantor ipotizzò che non esistesse nessun insieme con una cardinalità intermedia compresa fra quella di ℕ e quella di ℝ (ipotesi del continuo). a segue immediatamente Così come i numeri naturali rappresentano il primo livello di infinito, i numeri reali rappresenterebbero, secondo tale ipotesi, il livello immediatamente successivo. CANTOR E L’INFINITO ATTUALE TANTI DIVERSI INFINITI, ANZI, INFINITI TRANSFINITI Così come i numeri naturali rappresentano il primo livello di infinito, i numeri reali rappresenterebbero, secondo tale ipotesi, il livello immediatamente successivo. Ma ci sono infiniti altri infiniti, basta fare l’insieme delle parti dell’insieme infinito e si aumenta di un grado l’infinito Così, ad esempio, il "numero" dei naturali è differente da quello degli insiemi di naturali e poi da quello degli insiemi di insiemi di naturali e così via, in un procedimento senza fine che produce infiniti sempre nuovi. I reali sono tanti quanti i sottoinsiemi dei naturali I fisici hanno paura degli universi discreti e basano le loro teorie sul continuo e sulla simmetria Gli universi discreti sono molto più complicati degli universi continui il continuo nasce dai numeri naturali con una serie di passi che conducono percorso postulato: alla fine del di un postulato di all’aggiunta il continuità della retta Al di là dei più appariscenti sviluppi tecnologici, la valenza culturale dell’informatica si evince dalle sue potenzialità nel favorire il dialogo fra scienze esatte e scienze umane L’Informatica non ha solo un valore tecnologico-strumentale, ma anche un valore scientifico e culturale autonomo. Fornisce una prospettiva sul mondo e una chiave di lettura della realtà originale e irriducibile a quelle fornite dalla fisica, dalla matematica e dalle altre scienze. DIO HA FATTO I NUMERI NATURALI TUTTO IL RESTO È OPERA DELL’UOMO KRONECKER Leopold Kronecker (7 dicembre 1823, Liegnitz, Prussia / Legnica, Polonia - 29 dicembre 1891, Berlino), matematico e logico tedesco, noto per la sua convinzione che l'analisi potesse essere interamente fondata sui numeri interi, convinzione che viene bene rappresentata dal suo noto aforisma: "Dio fece i numeri naturali; tutto il resto è opera dell'uomo". Questo atteggiamento pose Kronecker in conflitto con alcune delle estensioni della nozione di numero e della matematica introdotte da Georg Cantor. Kronecker, che pure era stato il maestro di Cantor durante i suoi studi universitari a Berlino, ne rifiutò le scoperte: "il lavoro di Cantor sui numeri transfiniti e sulla teoria degli insiemi non è Matematica, ma misticismo" ed aggiungeva, come già ricordato, che "i numeri interi positivi sono i soli creati da Dio; tutto il resto è opera dell'uomo e quindi sospetto". Altri grandi matematici apprezzarono invece l'opera di Cantor e la accolsero con entusiasmo. David Hilbert definiva la teoria dei cardinali "un prodotto sbalorditivo del pensiero umano" e commentava: "nessuno riuscirà mai a cacciarci dal paradiso che Cantor ha creato per noi" l’informatica si fonda sui NUMERI NATURALI trasforma tutto in numero utilizza la base 2, solo 0 e 1 La programmazione è un buon medium per riuscire ad esprimere idee confuse mal formulate nella forma di metodi chiari ed efficaci. marvin minsky gulp!?! Trova il maggiore e il minore di N oggetti diversi, ma con il minor numero di passi! Rendiamo espliciti i procedimenti semi-consci il nostro cervello risolve automaticamente ogni giorno molti problemi ma con meccanismi che non sono completamente consci e quindi non espliciti: cercare di far risolvere al computer gli stessi basilari problemi ci consente quindi di capire come il nostro cervello svolge molte funzioni I problemi proposti sono tutti impostati sul confronto di oggetti differenti: si presupponeva di avere otto oggetti differenti e di avere a disposizione soltanto una bilancia a due piatti, senza pesi, per confrontare gli oggetti. ESPLOSIONE dell’ informazione contenuta in un confronto 1. Trovare il maggiore tra un insieme di otto numeri diversi. 2. Trovare il più grande e il più piccolo tra un insieme di otto numeri diversi. 3. Trovare i due numeri più grandi tra un insieme di otto numeri diversi. 1. Presentazione del problema; 2. Analisi del problema e sviluppo di un algoritmo risolvente; 3. Ottimizzazione dell’algoritmo; 4. Analisi del numero dei confronti in funzione del numero dei dati; 5. Domanda conclusiva: si può fare meglio? Trovare il più grande numero in un insieme di otto numeri diversi, potendoli soltanto confrontare a due a due. Si può procedere confrontando tutti i numeri fra di loro ma così avremmo una sovrabbondanza di informazioni inutilizzate. Quelli che seguono sono i due alberi che schematizzano due algoritmi risolventi ottimali. ALGORITMO OTTIMALE 1 ALGORITMO OTTIMALE 1 T O R N E O D I A R T I M A R Z I A L I OPPURE TORNEO DI TENNIS Trovare il più grande e il più piccolo numero in un insieme di otto numeri diversi, confrontandoli a due a due. a sinistra procedono i perdenti P V a destra solo i vincenti Però così sovrabbondanza inutilizzate: avremmo una di informazioni dai primi quattro confronti infatti sappiamo già qual è il maggiore e il minore di ogni coppia iniziale; questa informazione ci consente quindi di eliminare i primi quattro confronti a sinistra che sono inutili. ALGORITMO OTTIMALE 2 P perdenti V vincenti Trovare i due numeri più grandi in un insieme di otto numeri arbitrari, potendoli soltanto confrontare a due a due Se il maggiore fosse S V ALGORITMO OTTIMALE 3 Se = V V S Un torneo con 8 tennisti Il confronto avviene a due a due Se si desidera trovare solo il vincitore non serve tenere conto di coloro che perdono, ma solamente di coloro che vincono al primo turno, al secondo turno, al terzo turno, quello finale. In tutto 7 confronti. Se si desidera trovare anche il peggiore, bisogna tenere conto di coloro che hanno perso al primo turno per poi confrontarli a due a due come si fa per i vincitori. In tutto 10 confronti: 7 per il migliore più 3 per trovare il peggiore tra i quattro che hanno perso al primo turno. Se si desidera trovare il primo e il secondo più bravi, bisogna ad ogni turno tenere conto non solo dei vincitori, ma anche di coloro che hanno perso, e con chi hanno perso, in modo tale che, una volta trovato il vincitore, si possano confrontare tra di loro gli unici perdenti che possono aspirare al secondo posto: coloro che hanno perso con il vincitore. In tutto 9 confronti: 7 confronti per trovare il migliore più 2 per trovare il migliore tra i tre che hanno perso con il vincitore nei tre turni per le selezioni. E se il numero di oggetti è 15 (nei nostri esempi gli oggetti sono partite) quale sarà il minor numero di confronti nei tre casi esaminati? E se il numero di oggetti è N (nei nostri esempi gli oggetti sono partite) quale sarà il minor numero di confronti nei tre casi esaminati? PRIMO PROBLEMA N-1 SECONDO ROBLEMA 1. per N pari 3/2*N-2 2. per N dispari 3/2*(N-1) TERZO PROBLEMA N-1+log2N-1 log2N pprossimato per eccesso Perché non si può fare meglio? Preziosi consigli alla nonna Appunti tratti da Progetto SeT Università di Udine e Liceo Copernico