Riassunto esame di Informatica, prof. Pozzato, libro consigliato Informatica di Base, Curtis

Informatica di base e introduzione all'informatica

Breve storia del calcolo automatico

Effettuare calcoli a mente o "a mano" è un'attività noiosa e incline all'errore. Per secoli l'uomo ha cercato di porre rimedio a questo fatto "automatizzando" il processo di calcolo.

L'abaco è la prima "macchina di calcolo" nota e i primi abachi risalgono al V millennio a.C. L'abaco non è molto diverso da un foglio di carta. La logica e la correttezza dell'operazione dipendono unicamente dall'utente.

La Pascalina, bisogna aspettare fino al XVII secolo d.C. per avere la prima vera innovazione rispetto all'abaco. La pascalina è il primo grande passo avanti: la logica dell'operazione è controllata dalla macchina. La pascalina permetteva di effettuare "solo" addizioni e sottrazioni. Moltiplicazioni e divisioni potevano essere calcolate mediante ripetizioni di addizioni e sottrazioni, ma era di nuovo l'utente a dover controllare il processo.

Si può pensare di affrontare il problema modificando la macchina in modo da introdurre la divisione e la moltiplicazione. In effetti non si sta risolvendo il problema, lo si "rimanda". Il problema vero è che la logica che governa le operazioni è "cablata" nella macchina calcolatrice. La soluzione è di trattare tale logica come parte dell'input della macchina.

La Macchina Analitica è introdotta da Charles Babbage intorno al 1840, è il primo esempio di macchina di calcolo "programmabile". Babbage era molto avanti rispetto ai suoi tempi: la tecnologia non era ancora sviluppata a sufficienza (la macchina analitica avrebbe dovuto funzionare a vapore!) l'esigenza di automatizzare il calcolo non era forte e per questi motivi le sue idee non ebbero il successo che avrebbero meritato e furono dimenticate per quasi un secolo.

Le idee di Babbage vennero "riscoperte" nella prima metà del '900 da Alan Turing e da John von Neumann.

Alan Turing è uno dei padri dell'informatica, moltissime sue idee/congetture sono attuali anche oggi, egli introduce la "macchina di Turing", la quale è un modello astratto di calcolatore:

• È un "esperimento mentale", non una macchina effettivamente costruibile. Pensata per studiare i limiti di ciò che è calcolabile automaticamente.
• È universale perché può calcolare tutto ciò che è calcolabile in modo automatico.
• Alla base del suo funzionamento c'è la stessa idea alla base della macchina analitica.

John von Neumann descrive un calcolatore effettivamente costruibile. È ancora oggi il modello su cui si basano i computer moderni.

Informatica

Information and communication technology

Informatica come tecnologia, risvolti fisico-matematici e ingegneristici del calcolo automatico; teorie e tecniche di comunicazione.

Computer science

Informatica come scienza basata su modellizzazione, formalizzazione e verifica sperimentale (teoria degli automi, logica formale, teorie del linguaggio).

Un po' di storia (tecnologia)

• 1600: macchine calcolatrici a ingranaggi (Pascal, Leibniz)
• 1800: macchine con schede perforate e primi programmi (Babbage, Lovelace (figlia di Byron))
• 1920: erano chiamati computer gli impiegati che eseguivano calcoli numerici
• 1940: macchine a relay meccanici (Bell Laboratories, Mark I presso Harvard University e IBM)
• 1950: macchine di von Neumann (schede perforate, nastri magnetici, transistor, circuiti stampati)
• 1980: microcomputer (Home computer, personal computer)

Un po' di storia (scientifica)

• 300 a.C.: algoritmo di Euclide per MCD
• 1800: Boole (metodi puramente simbolici per modellare il ragionamento)
• 1930: Church, Turing (modello formale astratto di computer; computer come macchina universale: "We are trying to build a machine to do all kinds of different things simply by programming rather than by the addition of extra apparatus" (Turing); esistono problemi che un computer non può risolvere)
• 1940: Shannon (teoria dell'informazione)
• 1950/60: Dijkstra, Kruskal, Hoare, ecc. (algoritmi fondamentali, linguaggi di programmazione, teoria dei linguaggi formali, ecc.)
• 1970: Codd, Rivest et al., McCarthy et al., Cook et al. (database relazionali, crittografia a chiave pubblica, intelligenza artificiale, complessità computazionale)

Temi dell'informatica

Calcolabilità, complessità, teoria dei linguaggi formali, algoritmi e strutture dati, linguaggi di programmazione, compilatori e interpreti, architettura dei calcolatori, sistemi operativi, ingegneria del software, reti di calcolatori, interazione uomo-macchina, sicurezza, intelligenza artificiale, basi di dati. Ciascuno di questi temi è un "edificio" più o meno complesso; ad es. Intelligenza artificiale: risoluzione dei problemi; rappresentazione della conoscenza; meccanismi di ragionamento; apprendimento automatico; pianificazione, scheduling, diagnosi, configurazione, soddisfacimento di vincoli...

Informatica: infor(mazione) (auto)matica, insieme dei processi e delle tecnologie che consentono la creazione, la raccolta, l'elaborazione, l'immagazzinamento, la diffusione dell'informazione.

Le tecnologie informatiche hanno tre funzioni principali:

• Elaborare dati per ottenere informazioni significative
• Mantenere le informazioni elaborate per utilizzarle in combinazione con altre, come dati di un nuovo processo di elaborazione
• Organizzare le informazioni in una nuova forma per renderle più comprensibili, più interessanti o più utili

N.B.: Il calcolatore non 'inventa' nuove informazioni.

Computer è il centro nevralgico dei sistemi informativi, cioè i sistemi di gestione delle informazioni:

• Elaboratore: dispositivo in grado di eseguire automaticamente una serie di istruzioni
• Elettronico: usa componenti elettronici per elaborare informazioni
• Digitale: elabora informazioni binarie (0 e 1)

Il sistema è un insieme di parti correlate tra loro che operano in maniera congiunta per svolgere una specifica funzione. Le tecnologie informatiche sono sistemi caratterizzati da 2 livelli che si integrano e si completano:

• Hardware, struttura fisica dei dispositivi informatici, costituita di norma da componenti elettronici che svolgono precise funzioni nel trattamento e nella trasmissione dell'informazione. Per hardware non si intende solo il computer con i suoi componenti (monitor, stampante), ma tutti gli elementi che collegano tra loro i sistemi informativi (cavi telefonici, antenne dei cellulari ecc.).
• Software, insieme dei programmi che fanno funzionare l'hardware. Due categorie principali di software:
  • Il sistema operativo: (Microsoft Windows o MacOS, Unix o Linux) permette di gestire le risorse hardware del computer (memoria, dischi fissi ecc.) e di installare ed eseguire i programmi applicativi che consentono all'elaboratore di svolgere le proprie funzioni.
  • I programmi applicativi svolgono i compiti più vari, in funzione delle esigenze dell'utenza (browser, videoscrittura, fogli elettronici, ecc.).

Dati sono la materia prima del trattamento dell'informazione, infatti hardware e software sono fini a se stessi e hanno lo scopo di elaborare e presentare dati. Un computer può elaborare dati di ogni genere, dati semplici: lettere e numeri; e dati complessi: suoni, immagini, filmati.

Ormai i computer sono diventati parte integrante della nostra vita, infatti, li utilizziamo nelle prenotazioni aeree, nelle previsioni del tempo, nelle casse automatiche (Bancomat, Carte di credito), nelle stampanti pubblicitarie (lettere personalizzate), nei piccoli sistemi elettronici (Orologi, Centraline auto (ABS, ASR, ESP, airbag, ...), Ricevitori digitali (es. di segnali da satellite), Videogiochi (home e portatili), Telefoni cellulari (e carte SIM), Schede telefoniche).

L'architettura del computer e la CPU

Supercomputer sono i più potenti elaboratori disponibili, hanno numerose applicazioni tecniche e scientifiche, come l'elaborazione delle previsioni del tempo, la simulazione di fenomeni fisici come la fusione nucleare ecc. Il primo in grado di eseguire più di un trilione di operazioni al secondo è stato sviluppato dalla Intel nel 1996.

I mainframe (ora noti come server) in genere sono utilizzati nelle grandi aziende per svolgere funzioni centralizzate come la gestione della contabilità e il controllo dei magazzini. Essi sono in grado di elaborare i dati immessi da centinaia o migliaia di utenti contemporaneamente.

I minicomputer (chiamati anch'essi server) sono meno potenti dei mainframe e possono essere di diverse dimensioni, spesso utilizzati nelle grandi aziende.

I personal computer (PC) possono lavorare autonomamente o elaborare dati ricevuti da altri computer ai quali sono connessi.

I terminali, simili ai PC, offrono prestazioni più limitate, dotati soltanto di uno schermo, una tastiera e dei componenti elettronici necessari per comunicare con il computer a cui sono connessi e servono esclusivamente a inviare e ricevere informazioni.

I network computer e i network PC sono un incrocio tra i PC veri e propri e i terminali: funzionano come terminali in quanto ricevono dati e programmi da computer più potenti, e come PC perché elaborano automaticamente i dati ricevuti.

Il PC più diffuso è il desktop, progettato per essere posizionato su una scrivania. Le workstation sono invece dei computer personali di alto rendimento e piccole dimensioni, utilizzate prevalentemente da scienziati, ingegneri e grafici.

I notebook sono computer portatili leggeri e maneggevoli, funzionano grazie a batterie ricaricabili oppure inseriti nella docking station, che consente di aumentarne il rendimento.

Tablet PC, computer portatili privi di tastiera, con sensori touch-screen. Computer palmari o Smartphone sono i più piccoli.

L'avvento del compact disc ha contribuito alla diffusione del concetto di elaborazione digitale che consiste nel rappresentare numeri, musica, documenti ecc. in cifre binarie, in modo che possono essere elaborati e utilizzati dalle moderne tecnologie informatiche.

I segnali analogici sono un insieme continuo di valori che trasmettono molte informazioni e sono sensibili alle interferenze. I segnali digitali possono assumere solo 2 stati: acceso e spento. Il digitale presenta 2 vantaggi rispetto all'analogico: meno interferenze e maggiore risoluzione.

Bit, unità minima del linguaggio digitale, è l'elemento di base per rappresentare le informazioni, il termine deriva dall'inglese binary digit, cifra binaria e può assumere soltanto 2 stati: acceso (1) e spento (0). 1 bit può assumere 2 valori e può rappresentare 2 informazioni; N bit possono assumere 2^N valori, che permettono di rappresentare 2^N informazioni. Quindi per rappresentare K informazioni, si devono usare N bit, in modo che 2^N ≥ K.

Per trasmettere una maggiore quantità di dati, si ricorre ad un'unità più grande. Il byte, che è costituito da 8 bit e viene utilizzato - insieme al bit - come unità di misura per esprimere la capacità della memoria, la potenza di un calcolatore, la velocità di trasmissione di una linea. Per comodità vengono usate unità di misura come il kilobyte, pari a 1024 byte, e il megabyte, ma per indicare queste unità di misura si usano di norma delle abbreviazioni: k sta per 1000, M per 1 milione, G per 1 miliardo e T per mille miliardi; la B, a seconda che compaia in maiuscolo o minuscolo, indica se si tratta di byte o di bit rispettivamente. Per esempio, 10 MB corrisponde a 10 megabyte mentre 10 Mb sono 10 megabit.

Ora vedremo come rappresentare tramite bit:

• Numeri (– Interi positivi; – Interi negativi)
• Testi
• Immagini (– in bianco e nero; – a toni di grigio; – a colori)
• Filmati
• Suoni

C'è distinzione tra numerale e numero:

• Numero: concetto che rappresenta una quantità
• Numerale: simbolo che rappresenta una quantità
• I numerali differiscono dai numeri come le parole differiscono dai concetti che rappresentano
• Es.: 6, sei, VI, six sono numerali che rappresentano tutti lo stesso numero

Il sistema di numerazione decimale:

• Decimale: "alfabeto" di 10 cifre di base --> 0, 1, 2, …, 9
• Numerale 245: – 2 centinaia, 4 decine, 5 unità cioè
• La potenza di 10 da considerare dipende dalla posizione della cifra
• Notazione posizionale: la posizione di una cifra in un numerale indica il suo peso in potenze di 10 I pesi sono:

Rappresentazione decimale: il numerale 3704 in notazione decimale (o in base 10) rappresenta la quantità:

3704 (numerale) = 3000 + 700 + 0 + 4 = 3704 (numero)

N.B.: Siamo abituati a usare il sistema a base 10 per rappresentare i numeri. Pertanto è comune "confondere" numero e numerale. Se vogliamo evitare ambiguità, usiamo la notazione.

Il sistema di numerazione binario:

• Binario: "alfabeto" di 2 cifre di base --> 0, 1
• Il numero di cifre coincide con il numero di bit
• La potenza di 2 da considerare dipende dalla posizione della cifra
• Notazione posizionale: la posizione di una cifra in un numerale indica il suo peso in potenze di 2 I pesi sono:

Rappresentazione binaria:

Massimo numero rappresentabile: il numero più grande esprimibile con un dato numero di cifre (decimali, binarie, …) NON coincide con il numero di informazioni rappresentabili! Per esempio, con 2 cifre decimali rappresento 100 numeri, ma il numero più grande (massimo numero rappresentabile) è (Si inizia a contare da 0)...

Conversione da base 2 a base 10: è sufficiente moltiplicare ogni bit per il suo peso e sommare. Esempio:

• Somma di potenze di 2!
• Osservazione: un numero binario che termina con 0 è pari, altrimenti (con 1) è dispari perché gli altri addendi sono sicuramente pari!

Per rappresentare i caratteri, occorre stabilire una convenzione per la corrispondenza tra configurazione di bit e carattere. In informatica si usano vari sistemi di codifica tra cui il codice ASCII (American Standard Code for Information Interchange), il quale usa i 7 bit meno significativi di un byte (128 caratteri) e rappresenta – oltre ad altri caratteri – le lettere dell'alfabeto anglosassone maiuscole e minuscole, le cifre, i segni di punteggiatura.

N.B.: Uno standard è necessario per permettere lo scambio di informazioni testuali. Nel codice ASCII le lettere maiuscole hanno associato un codice più piccolo delle lettere minuscole e di conseguenza, se chiediamo a un computer di ordinare alfabeticamente (lessicograficamente) le parole "abete" e "Zacinto", le metterà in questo ordine: 1. Zacinto 2. abete.

Problema: insufficiente per rappresentare i comuni segni diacritici (per es. lettere accentate)

Soluzione: codice ASCII esteso che usa 8 bit, al massimo 256 caratteri.

• 256 caratteri dell'ASCII esteso sono insufficienti per alcuni sistemi di scrittura (per es. quello cinese o giapponese), quindi non esiste un unico ASCII esteso, ma uno (o più) diverso per ogni lingua. È problematico rappresentare testi complessi, che comprendano sistemi di scrittura diversi e la soluzione è definire uno standard (cioè una convenzione) che:
  • Utilizzi più bit
  • Comprenda tutti i sistemi di scrittura

Unicode e ISO/IEC 10646, due standard (per i nostri fini) equivalenti che coprono (quasi) tutti i sistemi di scrittura (e le lingue) del mondo. Vengono utilizzati fino a 4 byte per ogni carattere (glifo) --> 8*4 bit = 32 bit per ogni carattere --> 2³² (oltre 4 miliardi) possibili caratteri rappresentabili attualmente rappresentati oltre 98000 caratteri e questi sono raggruppati in blocchi.

UTF (Unicode Transformation Format) definisce come codificare il numero di un carattere Unicode come sequenza di bit:

• UTF-8: alcuni caratteri codificati con 8 bit, altri con 16 bit, altri (pochi) con 32 bit. Compatibile con ASCII: i caratteri codificati con 8 bit coincidono con i caratteri ASCII, quindi, la più usata per e-mail e pagine web
• UTF-16: alcuni caratteri codificati con 16 bit, altri (pochi) con 32 bit. Usata internamente da Windows

Codifica delle immagini: vi sono varie tecniche utilizzate per memorizzare in modo digitale un'immagine, e poi elaborarla. Per semplificare, immaginiamo di dover codificare un'immagine in bianco e nero (dual tone, con soli due colori).

Ogni quadrato derivante da tale suddivisione viene chiamato pixel (picture element) e può essere codificato in binario con la convenzione che:

• 0 rappresenta un pixel bianco (ovvero in cui il bianco è predominante)
• 1 rappresenta un pixel nero (ovvero in cui il nero è predominante)

Con un solo bit per pixel si possono codificare solo due colori (tipicamente bianco e nero). Per codificare più informazioni, dobbiamo usare più bit. Per associare una rappresentazione binaria a ogni possibile colore di un pixel, il modello più usato è Truecolor (o RGB)

• Tre colori primari: rosso, verde e blu (Red, Green, Blue: RGB)
• N.B.: sono diversi dai colori primari usati per gli inchiostri
• Gli altri colori vengono ottenuti sommando i tre colori primari
• Monitor e televisori funzionano così.

Esistono tecniche di compressione delle immagini che consentono di ridurre la dimensione dello spazio occupato. Per esempio, una tecnica consiste nel codificare aree dello stesso colore in modo "abbreviato" ed è un esempio di tecnica lossless (gif, tiff, png), senza perdita di informazione, cioè, quando decomprimiamo l'immagine, questa è identica all'originale.