Informatica 3CFU Unimi PDF

Preview

Summary

Informatica 3CFU Unimi
Teoria corso informatica da 3 CFU...

Description

La progettazione dei contenuti di questo insegnamento di Informatica si fonda sulla concezione dell'informatica come disciplina scientifica e non soltanto sul ruolo che l'informatica ha assunto nella società contemporanea. A tal fine, si riporta di seguito un passo significativo del Manifesto dell'Informatica, un documento ufficiale che il GRIN (http://www.grin-informatica.it), l'Associazione Italiana dei Docenti di Informatica, ha sottoscritto per definire il corretto approccio alla disciplina informatica e al suo insegnamento." L'informatica è un elemento essenziale della società moderna, non solo perché necessaria al normale svolgimento di quotidiane attività, ma anche in quanto il suo sviluppo plasma e determina quello dell'intera società. Non esiste campo dell'attività umana in cui le scoperte dell'informatica non abbiano lasciato il segno. L'uso del calcolatore, infatti, è uscito dai campi tradizionali del calcolo scientifico per entrare in tutte le aree della produzione industriale, dalla medicina all'editoria. Due miliardi di persone si collegano ad Internet. Centinaia di milioni di miliardi (il numero non è un errore di battitura) di transistor – i componenti elementari delle tecnologie dell'informazione – popolano i prodotti che ci circondano, dall'automobile all'elettrodomestico, dalla pompa di benzina al videogioco, per l'equivalente della metà del valore economico di questi oggetti. Centinaia di miliardi di istruzioni software, manifestazioni di intelligenza umana, animano questi componenti e attraverso di essi tutti i processi che caratterizzano la nostra società moderna. Nel linguaggio comune il termine “informatica” viene usato per riferirsi a tre aspetti tra loro distinti, seppur collegati:" 1. operativo: un insieme di applicazioni e manufatti (i computer);" 2. tecnologico: una tecnologia che realizza quelle applicazioni;" 3. culturale: una disciplina scientifica che fonda e rende possibile quella tecnologia." L’informatica come insieme di applicazioni è la percezione della persona comune; “conoscere l’informatica” significa “saper usare le applicazioni”. L’informatica come tecnologia è la percezione del tecnico (del perito, del laureato, dello specialista, ciascuno al suo livello di competenza); “conoscere l’informatica” significa in questo caso “saper realizzare le applicazioni”. L’informatica come scienza dovrebbe essere invece patrimonio di ogni persona con educazione superiore. Come i principi della fisica, della matematica o della chimica sono utili anche e soprattutto come modello interpretativo della realtà, e non perché chi li conosce possa diventare un fisico, un matematico, o un chimico, così i principi fondamentali dell’informatica sono in grado di fornire modelli di interpretazione e una strumentazione culturale utile nella vita comune della persona colta che deve affrontare le sfide del mondo moderno." In altre parole, si può pensare all'informatica come alla scienza che si occupa dei seguenti temi:" • lo studio dei fondamenti teorici della scienza dell'informazione;" • la definizione di algoritmi per l'elaborazione automatica delle informazioni;" • la realizzazione (implementazione) di questi algoritmi;" • e, infine, l’uso del calcolatore." In definitiva, l’informatica non riguarda i computer più di quanto l’astronomia riguardi i telescopi." Lo studio dell'informatica è quindi importante perché:" • lo sviluppo di algoritmi consente di accrescere le facoltà creative, logiche e cognitive dell'individuo;" • l’informatica è intrinsecamente multidisciplinare: ogni disciplina prevede una opportuna forma di organizzazione e trattamento delle informazioni;" • l’informatica offre strumenti per modellare i formalmente problemi e poterne affrontare la risoluzione in modo efficiente ed efficace;"

•

le tecnologie dell'informazione sono diventate strategiche in numerosi ambiti applicativi. Esse non solo semplificano lo svolgimento di compiti realizzabili anche senza calcolatore, ma offrono vantaggi sul lungo termine altrimenti non accessibili."

Nel sentire comune, l'informatica è vista come una disciplina monolitica. Ogni volta che si pensa ad un informatico, si immagina un esperto capace di risolvere qualsiasi problema legato all'uso dei calcolatori. In realtà l'informatica è una disciplina complessa dove si possono riconoscere numerose specializzazioni. Pertanto è possibile, per non dire frequente, che un esperto sviluppi le proprie competenze rispetto a un sottoinsieme di specializzazioni. " A titolo esemplificativo, senza alcuna pretesa di completezza, elenchiamo alcune specializzazioni della disciplina informatica:" • Informatica teorica" Teoria dell'informazione" ◦ Teoria della computazione" ◦ Algoritmi e strutture dati" ◦ Teoria dei linguaggi di programmazione" ◦ • Informatica applicata" Architettura dei calcolatori" ◦ Sistemi e architetture (Information Technology - IT)" ◦ Reti di calcolatori" ◦ Basi di dati" ◦ Sicurezza informatica e crittografia" ◦ Interazione uomo-macchina" ◦ Intelligenza artificiale" ◦ Elaborazione digitale dei segnali" ◦ Programmazione" ◦ Sviluppo software" ▪ Sviluppo web" ▪ Sviluppo sistemi integrati" ▪ Inoltre l'informatica può essere coniugata ad altre discipline per dare vita a branche multidisciplinari comead esempio bioinformatica, chimica computazionale, robotica, computer grafica e musicologia computazionale." Perché% si possa arrivare all'informatica come la intendiamo oggi% è stato necessario sviluppare parallelamente due diversi aspetti: quello tecnologico e quello filosofico (in particolare logico-matematico).% La serie di eventi, idee e scoperte che culmina con i moderni calcolatori ha quindi una moltitudine di protagonisti, disseminati in un arco temporale di almeno 4000 anni, con molte storie parallele. Per quanto il racconto possa essere avvincente e ricco di colpi di scena, non è questa la sede per una esposizione esaustiva. Ci si limiterà pertanto a citare solo alcuni degli aspetti cruciali: quelli più funzionali alla comprensione del pensiero informatico e del funzionamento del calcolatore." Il termine% calcolatore% designa genericamente un sistema di elaborazione dati, nato in forma%meccanica,%sviluppatosi in forma%analogica%e giunto poi alla forma%digitale." Generazione 0: I calcolatori meccanici" Il più antico strumento di calcolo fu l’abaco, in uso già 4000 anni fa in Cina. Dopo di esso molte furono le scoperte in questo ambito, ma la maggior parte di esse (come ad esempio la%pascalina%ideata nel 1642 da Blaise Pascal) non vennero mai realizzate." Nel 1702, Gottfried Wilhelm Leibniz% sviluppò la logica come disciplina matematica e formale, con i suoi scritti sul sistema numerico binario. Nel suo sistema, l'uno e lo zero

rappresentano i valori%vero%e%falso. Questo non ebbe un effetto immediato, ma fu decisivo nel secolo successivo." I primi veri progenitori dell’elaboratore moderno videro la luce agli inizi del XIX secolo. Nel 1804 Joseph Marie Jacquard introdusse una nuova tecnologia per i telai in grado di controllare il movimento di aghi, filo e tessuto attraverso schede perforate, automatizzando così la procedura di tessitura." A metà del XIX secolo, Charles Babbage elaborò una macchina di calcolo in grado di compiere operazioni aritmetiche, ma non fu mai realizzata. Fu Ada Lovelace (considerata oggi la prima programmatrice della storia), ad accorgersi delle vere potenzialità della macchina di Babbage: sebbene fosse stata progettata per svolgere solo calcoli matematici, Ada riconobbe la possibilità di% programmare% la macchina per altri fini. In questa versatilità risiede la principale differenza tra una% calcolatrice tradizionale% e un calcolatore." Nel 1854, le idee di Leibniz vennero riprese da George Boole, che pubblica la propria%algebra booleana, creando un sistema nel quale è possibile trattare ogni relazione logica attraverso l'utilizzo di formule algebriche. Le operazioni (come l'addizione, la sottrazione e la moltiplicazione) vengono sostituite da operazioni logiche con valori di congiunzione, disgiunzione e negazione utilizzando solamente numeri binari (ossia costituiti dalle sole cifre 0 e 1)." Alla fine del XIX secolo, Herman Hollerith, un funzionario statunitense dell’ufficio per il censimento, sviluppò una macchina tabulatrice, sempre a schede perforate, per automatizzare le operazioni di censimento. Il successo e la richiesta di queste macchine fu tale che nel 1896 Hollerith fondò la Tabulating Machine Company, che nel 1924 divenne la International Business Machine (IBM)." Tra gli antenati% degli anni '30 del calcolatore, figura il Memex, macchina immaginaria progettata da Vannevar Bush. L’idea era quella di un sistema di archiviazione di dati utilizzato a scopi personali. Il dispositivo era descritto come una scrivania dotata di schermi traslucidi, una tastiera, un set di pulsanti e delle leve.% Il Memex avrebbe reso possibile la creazione da parte dell'utente di collegamenti tra foto e documenti, e per questo motivo viene oggi ricordato come primo supporto per l'approccio all'ipertesto." Sempre nella prima metà degli anni '30,% Kurt Gödel enunciò i suoi famosi teoremi di incompletezza. Oltre a rappresentare un caposaldo nel campo della logica matematica, con importanti implicazioni di ordine filosofico, questi fecero da base per il lavoro di Alan Turing,% matematico, logico e crittoanalista inglese. Egli formalizzò un modello di calcolatore universale (la Macchina di Turing, mai costruita realmente), dimostrò come ogni funzione calcolabile si possa eseguire attraverso un algoritmo installato su una Macchina di Turing, ma dimostrò anche come per alcuni algoritmi non sia possibile sapere a priori se siano eseguibili in un tempo finito o infinito. Tra le implicazioni più importanti della Macchina di Turing si sottolinea come essa introduca una netta separazione tra la macchina fisica da una parte,%e i dati e gli algoritmi astratti dall'altra. Le basi teoriche per lo sviluppo dei moderni calcolatori sono ora mature."

Generazione 1: I tubi a vuoto (valvole) Nel 1939, fu la volta del matematico e fisico John Vincent Atanasoff e del suo allievo Clifford Berry i quali costruirono l’Atanasoff Berry Computer, meglio noto come ABC. Si tratta del primo calcolatore digitale totalmente elettronico, ma mai brevettato." Nel 1945, John von Neumann definisce l'architettura per calcolatori digitali programmabili tutt'ora in uso nella maggior parte dei dispositivi moderni di questo tipo. La peculiarità dell'architettura di von Neumann risiede nel fatto che dati e programmi condividono la stessa memoria."

Nel 1946 venne presentato l’ENIAC, il primo calcolatore elettronico basato interamente su tecnologia a valvole. Progettato presso l’Università della Pennsylvania, fu il primo vero calcolatore dell’era elettronica in quanto eliminava tutti i dispositivi meccanici. L’ENIAC era in grado di compiere operazioni molto complesse in pochissimo tempo per l'epoca, ma pesava 300 tonnellate e occupava 170 metri quadrati. Quella delle dimensioni rimase per lungo tempo una delle più grandi sfide dell’industria dei calcolatori." Nel 1948, Claude Shannon introdusse il termine% bit% (contrazione di% binary digit), da lui coniato per designare l'unità elementare binaria di informazione (vero%e%falso, o 0 e 1)." Generazione 2: I transistor" Nel 1954, l’IBM propose il primo calcolatore commerciale con memoria su nastro magnetico. Tra le più importanti innovazioni di quegli anni, vi furono l'uso dei transistor al posto dei tubi a vuoto e l’evoluzione dei linguaggi di programmazione." Nel 1959 venne lanciato l’IBM 705, che usava il FORTRAN, un linguaggio di programmazione molto più vicino a quello umano rispetto alle istruzioni comprensibili dal calcolatore. I problemi principali che ostacolavano la diffusione commerciale del calcolatore restavano i costi elevati e la dimensione di queste macchine." Generazione 3: I circuiti integrati" Il problema delle dimensioni durò fino al 1964, quando l'azienda italiana Olivetti introdusse% Programma 101, da molti considerato il primo personal computer (PC) della storia, in quanto disponeva delle principali caratteristiche dei grandi calcolatori dell'epoca, ma era sufficientemente compatto da stare su una scrivania. Tuttavia non aveva uno schermo: le informazioni erano trasmesse all'utente per mezzo di un nastro di carta stampata." Parallelamente, la Digital Equipement Corporation introdusse il suo primo minicomputer, il PDP-8, dotato di uno schermo molto rudimentale (sostanzialmente un oscilloscopio)." Generazione 4: Il microprocessore" Agli inizi degli anni ’70, la Intel Corporation sviluppò il% microprocessore, il primo circuito integrato capace di contenere l’intera unità di calcolo di un calcolatore. In seguito venne commercializzato quello che viene oggi considerato il primo PC della storia per come lo intendiamo oggi, l'Apple II, con il suo sistema operativo chiamato Apple Dos." Solo quattro anni dopo, nel 1981, l’IBM brevettò il suo primo PC, destinato a imporsi come standard di riferimento con il sistema operativo% MS-Dos% prodotto dalla software house Microsoft." Generazione 5: Il calcolo parallelo e la rete" Tra gli anni '80 e '90 si sono affermate in rapida successione tecnologie come le interfacce grafiche,% la possibilità di compiere più operazioni in parallelo,% e l'avvento di Internet, coadiuvate da un costante incremento della potenza di calcolo e delle capacità di memorizzazione."

Problemi, algoritmi e programmi Un% algoritmo% può essere definito come un% metodo per risolvere in modo efficiente, univoco, universale, formalmente preciso e finito un problema." Nella sua accezione più ampia, è possibile includere nella categoria degli algoritmi anche una semplice ricetta di cucina oppure il libretto di istruzioni di un elettrodomestico. Entrambi infatti sono una successione di istruzioni precise per la realizzazione di un risultato." Il termine algoritmo deriva dal nome del matematico Muhammad ibn Musa al-Khuwarizmi." Le proprietà fondamentali di un algoritmo sono:" finitezza delle operazioni da svolgere;" •

non ambiguità del linguaggio in cui sono scritte le operazioni da effettuare. Questo significa che le istruzioni devono essere scritte in un linguaggio codificato e formale;" universalità della procedura algoritmica, nel senso che essa deve valere per tutti i • problemi dello stesso genere;" completezza delle operazioni, nel senso che ogni operazione% necessaria allo • svolgimento del compito deve essere explicitamente dichiarata." Nonostante sia più semplice affrontare algoritmicamente calcoli matematici, o geometrici, è possibile affrontare nello stesso modo qualsiasi problema, a patto che se ne possa%fornirne una definizione formalmente corretta e non ambigua. Questo esercizio di formalizzazione trascende l'uso del computer e aiuta gli individui ad affrontare i problemi in modo astratto." Va notato che ogni problema può essere affrontato e descritto in molti modi diversi; quindi non esiste un unico algoritmo per la risoluzione di un problema. Questo significa che lo sviluppo di algoritmi è un'attività che richiede, tra le altre cose, creatività e ingegno. A tal proposito, vale la pena citare una famosa battuta di Bill Gates (co-fondatore della Microsoft): "Sceglierò sempre un pigro per fare un lavoro difficile perché troverà il modo più facile per farlo"." Si sottolinea inoltre come l'efficacia e la complessità di un algoritmo dipendano anche dall'organizzazione dei dati a disposizione dell'algoritmo per la risoluzione del problema. Esistono molti modi di organizzare i dati, ognuno dei quali ha pregi e difetti. In genere gli aspetti più rilevanti di cui tenere conto sono:" • la quantità di spazio occupato;" • la velocità con cui è possibile reperire un determinato dato;" • la facilità con cui si possono aggiungere, modificare o eliminare dati." Infine, un% programma% può essere definito come un algoritmo scritto in un linguaggio comprensibile al calcolatore, che utilizza dati organizzati secondo una determinata strategia ed è vincolato alle risorse disponibili e alle condizioni al contorno del calcolatore sul quale il programma viene eseguito." •

Informazione e codifica L’informazione può essere definita come un insieme di dati espressi mediante una rappresentazione simbolica ed inseriti in un contesto interpretativo. In generale, per rappresentare le informazioni è possibile adottare sistemi di simboli diversi. Ad esempio, come mostrato nella Figura 2.1, le lettere dell’alfabeto, i numeri arabi, i numeri romani o ancora i segnali stradali sono sistemi di simboli comunemente usati per rappresentare e comunicare informazioni. " Esiste dunque una corrispondenza arbitraria fra ogni singolo simbolo e l’informazione che esso intende rappresentare. Questa corrispondenza viene chiamata codi fi ca dell’informazione." Un%codice%è un insieme di simboli e di regole. Queste ultime sono necessarie a definire l’uso e il significato dei simboli. Codificare un’informazione significa determinare una corrispondenza fra i segni di un codice e i dati che costituiscono l’informazione e il suo significato." Di una stessa informazione sono possibili diverse codifiche che usano regole e segni diversi. Ad esempio, in un ristorante si può trovare un cartello con la scritta “vietato fumare” o più semplicemente il simbolo della sigaretta con il divieto.% Nonostante l’informazione sia sempre la stessa, ossia che in quel ristorante non si può fumare, per trasmetterla si possono utilizzare codici (cioè simboli) anche molto diversi tra loro." Come costruire un codice" Si voglia costruire un codice per comunicare a uno studente il voto conseguito a un esame universitario senza usare la normale numerazione in trentesimi. Le possibili informazioni che il codice deve poter rappresentare sono: “insufficiente”, i voti da diciotto a trenta e il voto “trenta e lode”." Per prima cosa, si deve individuare un insieme di simboli che costituisca il codice, avendo cura di definire un simbolo per ognuna delle informazioni da rappresentare. Ci sarà quindi bisogno di 15 simboli diversi e si dovrà associare ad ogni simbolo la corrispondente informazione, definendo un’opportuna%tabella di codifica% come nell'esempio della Figura 2.3." "

In questo modo, dato un voto (messaggio), è possibile derivarne una rappresentazione conforme al codice definito (attività di%codifica). Viceversa, dato un messaggio espresso con tale codice, è possibile ricavare il voto corrispondente (attività di% decodifica). Ad esempio, dato il simbolo #, è possibile decodificare il messaggio e affermare che il voto conseguito è 24." E’ importante che a ogni simbolo corrisponda una e una sola informazione, in modo che il messaggio non risulti mai ambiguo." Riduzione del numero di simboli" Nell'esempio della%Figura 2.3, è stato mostrato un codice che richiedeva 15 simboli per rappresentare altrettante informazioni diverse. Un codice costruito in questo modo è molto semplice e di rapida realizzazione, ma comporta che il numero di simboli che compongono il codice e la tabella di codifica crescano con il numero di informazioni da rappresentare. È facile intuire che la gestione di un codice con un elevato numero di simboli possa essere molto complessa." È possibile costruire un codice che consenta di rappresentare lo stesso numero di informazioni diverse utilizzando un numero inferiore di simboli. Ciò significa ridurre il numero di simboli a disposizione senza tuttavia ridurre il numero di informazioni che possono essere codificate. E' evidente che, avendo meno simboli a disposizione, la rappresentazione di un’informazione richiederà una combinazione di più simboli e quindi una maggiore lunghezza dei messaggi codificati." Con riferimento all'esempio del codice per rappresentare i voti di un esame universitario, si supponga di poter utilizzare soltanto i simboli ! £ $ %. Nella Figura 2.4, si mostra un esempio di tabella di codifica basata sui quattro simboli considerati."

Codifica binaria La rappresentazione dell’informazione numerica può adottare varie tecniche. Normalmente si usa la numerazione decimale posizionale, dove una cifra assume un valore dipendente dalla posizione che occupa nel numero. Per esempio, la cifra “2” nel numero 12 vale 2*100 (dove 0 è la posizione occupata dal 2 nel numero in esame) e nel numero 2987 vale 2*103 (dove 3 è la posizione occupata dal 2 nel numero in esame)." Adottando una numer...