Riassunti informatica
Hardware = l'insieme delle parti fisiche di un computer
Software = l’insieme dei programmi che vengono eseguiti dal sistema
File = organizzazione di programmi e dati. Esso è un archivio organizzato secondo un certo criterio e residente in memoria.
File di dati = contengono informazioni (testi, numeri, immagini, suoni).
irectoFile di programmi = contengono sequenze di istruzioni.
Architettura di un Computer
L’architettura dell’hardware di un calcolatore reale è molto complessa: la macchina di Von Neumann è un modello semplificato dei calcolatori moderni.
Von Neumann progettò, verso il 1947, il primo calcolatore con programmi memorizzabili anziché codificati mediante cavi e interruttori.
5 tipi di componenti funzionali della macchina di Von Neumann:
- CPU (Central Processing Unit) = unità centrale di elaborazione, esegue istruzioni per l’elaborazione dei dati (contenuti nella memoria principale) e svolge anche funzioni di controllo. E’ anche detta processore.
L’elaborazione avviene in accordo a sequenze di istruzioni (istruzioni macchina).
Il linguaggio in cui si scrivono queste istruzioni viene chiamato linguaggio macchina.
Programma = specifica univoca di una serie di operazioni che l’elaboratore deve svolgere ed è costituito da una sequenza ordinata di istruzioni macchina.
Il ruolo del processore è quello di eseguire programmi in linguaggio macchina.
- memoria centrale (o RAM = Random Access Memory, memoria ad accesso casuale) = memorizza e fornisce l’accesso a dati e programmi in esecuzione. Contiene i programmi e i dati che stanno per essere elaborati dalla CPU. E’ una memoria volatile (i dati vengono persi se si spegne il computer). L’accesso all’informazione è molto rapido.
- memoria di massa = memorizza permanentemente i dati ed i programmi. Prevede accessi in lettura e scrittura. Usata per memorizzare grandi quantità di dati e programmi. Non volatile (cioè l’informazione non viene persa quando il computer viene spento). L’accesso all’informazione non è molto rapido.
- interfacce di ingresso e uscita (I/O) = componenti di collegamento con le periferiche del calcolatore. Vengono impiegati per far comunicare il calcolatore con l’ambiente esterno, cioè per accettare in ingresso i dati e per visualizzare i risultati ottenuti dall’elaborazione dei dati. Esse si dividono in:
Terminali (tastiera, mouse, monitor), stampanti, modem, …
L’unità centrale (case) ha degli ingressi detti porte in cui inserire i cavi che collegano i dispositivi di I/O.
- bus = svolge funzioni di trasferimento di dati e di informazioni di controllo tra le varie componenti funzionali.
Porte dell’Unità Centrale
La porta parallela = consente il transito in una sola direzione: dal computer alla periferica. Viene quindi usata quasi esclusivamente per il collegamento con le stampanti.
La porta seriale = collegamenti con periferiche attive, come mouse e modem.
La porta seriale USB = permette di collegare dispositivi (scanner, stampanti...) senza dover configurare e riavviare il computer. Inoltre sono molto veloci.
La porta Serial ATA (SATA "Serial Advanced Technology Attachment") = è
generalmente utilizzata per connettere hard disk o drive ottici. Ha grande velocità, cavi meno ingombranti e possibilità di hot swap. Gli hard disk esterni di ultima generazione possono essere collegati al computer tramite l'interfaccia ESATA oltre alla classica porta USB 2.0, la porta USB 3.0 o la più moderna USB 3.1.
CPU
La CPU o microprocessore è un chip integrato costituito da una piccola piastra di silicio sulla cui superficie sono stati creati milioni di transitori miniaturizzati.
Nella maggior parte dei computer sia il programma che i dati (le informazioni da elaborare) devono essere caricati (cioè, copiati) in memoria principale.
La memoria contiene almeno due tipi di informazioni:
La sequenza di istruzioni che devono essere eseguite dal processore,
L’insieme di dati (informazioni) su cui tali istruzioni operano.
Il processore è costituito da varie componenti che svolgono compiti differenti.
Componenti della CPU
Unità di controllo = esegue operazioni finalizzate al trasferimento dati o al controllo dell’esecuzione dei programmi.
Unità logico-aritmetica (ALU) = esegue operazioni matematiche e logiche sui dati che sono contenuti nei registri.
Registri = celle interne alla CPU che devono contenere l’istruzione da eseguire, i dati da elaborare, e informazioni accessorie (es. eventuali anomalie generate dall’esecuzione) sullo stato della CPU.
Lo stato della CPU è la sequenza binaria determinata dalla lettura di uno o più registri all’interno della CPU.
L’Unità di Controllo (UC)
L’Unità di Controllo (UC) si occupa di coordinare le diverse attività che vengono svolte all’interno del processore.
Il processore svolge la sua attività in modo ciclico: ad ogni ciclo corrisponde l’esecuzione di una istruzione macchina.
Ad ogni ciclo vengono svolte diverse attività controllate e coordinate dalla UC chiamate fetch-decode-execute:
- fetch = si legge, cioè si carica, dalla memoria principale la prossima istruzione da eseguire;
- decode = si decodifica l’istruzione e si caricano eventuali dati dalla memoria;
- execute = si esegue l’istruzione.
Infine, si memorizza un eventuale risultato (informazione elaborata) in memoria.
La frequenza con cui vengono eseguiti i cicli di esecuzione è scandita (sincronizzata) da una componente detta clock.
Ad ogni impulso di clock la UC esegue un ciclo di esecuzione di istruzioni macchina.
La velocità di elaborazione di un processore dipende dalla frequenza del suo clock.
I processori attuali hanno valori di frequenza di clock che variano tra i 500 MHz e 3 GHz (tra 500 e 3000 milioni di impulsi al secondo).
La frequenza di clock determina quindi la velocità della CPU.
I registri
Il processore contiene al suo interno un certo numero di registri (unità di memoria estremamente veloci).
Le dimensioni di un registro sono di pochi byte (4, 8) I registri contengono delle informazioni di necessità immediata per il processore.
Esistono due tipi di registri:
i registri speciali utilizzati dalla UC per scopi particolari,
i registri di uso generale (registri aritmetici).
Unità Logico Aritmetica (ALU)
L’Unità Logico Aritmetica (ALU) è costituita da un insieme di circuiti in grado di svolgere le operazioni di tipo aritmetico e logico.
La ALU legge i dati contenuti all'interno dei registri generali, esegue le operazioni e memorizza il risultato in uno dei registri generali.
Vi sono circuiti in grado di eseguire la somma di due numeri binari contenuti in due registri e di depositare il risultato in un registro e circuiti in grado di eseguire il confronto tra due numeri.
In alcuni elaboratori oltre alla ALU si può avere un processore specializzato per effettuare operazioni matematiche particolari, il coprocessore matematico.
I bus
Il microprocessore e gli altri componenti elettronici comunicano per mezzo di impulsi elettrici.
Questi impulsi viaggiano attraverso piste di rame tracciate sulla scheda madre, dette bus. Il numero di linee determina l’ampiezza del bus: oggi i bus possono essere a 32 o 64 bit.
Il bus che collega la CPU agli altri dispositivi del computer, fra cui la memoria centrale, si chiama system bus. In ogni istante di tempo il bus collega due unità funzionali: una trasmette i dati e l’altra li riceve, questo processo viene controllato dall’unità centrale di elaborazione.
Le linee del bus vengono suddivise in tre categorie:
- bus dati = trasferisce dati;
- bus indirizzi = trasferisce indirizzi; per esempio contenuto del registro indirizzi
dell'unità di elaborazione centrale alla memoria;
- bus controlli = trasferisce un codice corrispondente all’istruzione da eseguire.
Memoria Centrale
La memoria centrale è una sequenza di celle di memoria; ciascuna cella contiene una parola (word).
La parola è una sequenza di bit. Le parole di uno stesso calcolatore hanno tutte la stessa lunghezza. Calcolatori diversi possono avere parole di lunghezza diverse. Le lunghezze tipiche sono multipli del byte (8 bit), cioè ci sono calcolatori con parole di 8, 16, 32, 64 bit.
Ciascuna cella di memoria è identificata da un numero (indirizzo) che ne specifica l’esatta posizione all’interno della memoria
Struttura della memoria
Memoria Centrale (RAM)
La memoria centrale è detta RAM (Random Access Memory), cioè “Memoria ad accesso casuale”. Non significa che i dati sono sparpagliati a caso. Vuol dire che al processore occorre sempre lo stesso tempo per accedere a una qualsiasi, casuale, parte della memoria.
La RAM è una memoria veloce e i dati rimangono finché il computer è in funzione. Quando si spegne la RAM si svuota.
Esiste una memoria ancora più veloce della RAM: la Cache che contiene le istruzioni eseguite più recentemente.
Memoria Cache
Nello schema di funzionamento di un calcolatore il processore continuamente preleva informazioni ed istruzioni dalla memoria centrale e scrive in essa informazioni.
La memoria centrale, il bus ed il processore lavorano a velocità diverse. La velocità complessiva del sistema è determinata dal componente più lento.
Per accelerare questa interazione si impiega una memoria ad alta velocità localizzata tra processore e memoria centrale detta CACHE.
Se il processore ha bisogno di leggere un dato o un’istruzione dalla memoria centrale la cerca prima nella cache che è molto più veloce.
Se il dato o l’istruzione non si trovano memorizzati nella cache allora il processore chiede alla memoria centrale di fornire l’elemento richiesto.
Ci sono alcune tecniche per decidere cosa memorizzare nella cache.
Se dati ed istruzioni più frequentemente usati dal processore si trovano nella cache allora si ha una grande velocizzazione delle operazioni (si evita il tempo che è necessario per accedere alla RAM tramite il bus).
La memoria ROM
ROM (Read Only Memory) è una “Memoria di sola lettura” il cui contenuto è stato registrato in fase di costruzione del computer e non può essere modificata. Ogni volta che viene acceso, il computer esegue un piccolo programma contenuto nella ROM che:
identifica il processore,
controlla la quantità di RAM e ne verifica il funzionamento,
esamina l’hard disk e eventuali periferiche aggiuntive,
legge il settore dell’hard disk in cui sono contenute le istruzioni per l’avvio del sistema.
BIOS
La parte della ROM che avvia il sistema è detto BIOS (Basic Input/Output System).
In fase di avvio del PC il programma di bootstrap presente nel BIOS:
- effettua test diagnostici di base e controlla lo stato delle periferiche collegate, per permettere il caricamento del sistema operativo (POST: Power-On Self Test);
- carica nella memoria principale (RAM) la parte principale del sistema operativo (kernel).
Le memorie di Massa
La memoria di massa o memoria secondaria deve avere capacità di memorizzazione
permanente e quindi per la sua realizzazione si utilizzano tecnologie basate sul
magnetismo (dischi e nastri magnetici) o tecnologie basate sull'uso dei raggi laser (dischi ottici).
Nel primo caso si sfrutta l’esistenza di sostanze che possono essere magnetizzate. La magnetizzazione può essere di due tipi (positiva e negativa) che corrisponde ai bit 0 e 1.
Nel secondo caso si sfrutta la diversa riflessione di un raggio laser su superfici diverse e si può pensare di utilizzare delle superfici con dei piccolissimi forellini. Ogni unità di superficie può essere forata o non forata e questo corrisponde ai due bit 0 e 1.
Caratteristiche:
- I supporti di memoria di massa sono molto più lenti rispetto alla memoria principale
(presenza di dispositivi meccanici).
- Le memorie di massa hanno capacità di memorizzazione (dimensioni) molto maggiori di quelle delle tipiche memorie principali.
- Il processore non può utilizzare direttamente la memoria di massa per l'elaborazione dei dati.
- Il programma in esecuzione deve essere in memoria principale e quindi le informazioni devono essere trasferite dalla memoria secondaria a quella principale ogni volta che servono.
Il disco rigido (hard disk)
La formattazione consiste nella suddivisione del rivestimento magnetico del disco in settori e tracce concentriche.
Le informazioni vengono memorizzate per mezzo di una testina che modifica la polarità magnetica delle singole particelle per rappresentare i numeri binari.
La velocità di rotazione può variare dai 60 giri al sec. fino a 10000 rpm (revolution per minute). In media un HD ha velocità dai 4500 ai 7200 rpm.
Il tempo medio di accesso è il tempo necessario per estrarre un dato ed è dato dalla somma di:
- tempo di posizionamento = spostamento della testina in senso radiale fino a
raggiungere la traccia desiderata (seek time);
- tempo di latenza = attesa che il settore desiderato si trovi a passare sotto la testina; tale tempo dipende dalla velocità di rotazione del disco (latency time);
- tempo di lettura = necessario alla testina per leggere/scrivere dati sul disco.
I dischi hanno tempo medio di accesso dell’ordine dei 10 ms.
Dischi ottici
I dischi ottici sono basati sull’uso di un raggio laser per operazioni di lettura.
Quasi tutte le unità per dischi ottici consentono solamente operazioni di lettura poiché la scrittura è un'operazione complicata, che richiede delle modifiche fisiche del disco (CD ROM ovvero Compact Disk Read Only Memory).
Quando le unità consentono la scrittura, i dischi ottici generalmente possono essere scritti una sola volta perché le modifiche fisiche che avvengono durante la fase di scrittura sono irreversibili (CD WORM ovvero Compact Disk Write Once Read Many). Si usa un masterizzatore.
Le tecnologie dei dischi ottici sono completamente differenti e sono basate sull'uso di raggi laser.
Il raggio laser è un particolare tipo di raggio luminoso estremamente focalizzato che può essere emesso in fasci di dimensioni molto ridotte.
Il raggio laser viene riflesso in modo diverso da superfici diverse, e si può pensare di utilizzare delle superfici con dei piccolissimi forellini.
CD-ROM
I CD-ROM (Compact Disk-Read Only Memory) sono supporti ottici per la memorizzazione dei dati.
I CD-ROM dopo essere registrati una prima volta mediante un masterizzatore, possono essere utilizzati soltanto per la lettura delle informazioni memorizzate.
I bit sul CD-ROM sono codificati come aree incise (pit) e aree non incise (land) sulla superficie del disco. Per leggere l’informazione si usa un laser di bassa potenza; i pit e i land hanno angoli di rifrazione diversi e perciò si possono distinguere.
DVD-ROM
I DVD-ROM (Digital Versatile Disk) sono supporti ottici per la memorizzazione dei dati.
Sono molto simili ai CD-ROM. L’unica differenza è una capacità molto maggiore.
Nati per l’esigenza di riprodurre su supporto digitale interi film (il CD-ROM nacque per l’esigenza di un supporto digitale per la musica).
I Drives
Gli sportelli in cui si inseriscono i floppy disk, o il CD, o qualsiasi altro tipo di disco, sono detti "drives" (da non confondersi con i drivers software).
Contengono una testina di lettura/scrittura tramite cui avviene il trasferimento dei dati fra disco e macchina.
Dispositivi di Input/Output
I dispositivi di input/output (anche detti periferiche), permettono di realizzare l'interazione tra l'uomo e la macchina.
La loro funzione primaria è quella di consentire l'immissione dei dati all'interno dell'elaboratore (input), o l'uscita dei dati dall'elaboratore (output).
Solitamente hanno limitata autonomia rispetto al processore centrale (sono completamente gestiti, controllati e coordinati dal processore).
Così come le memorie di massa, anche i dispositivi di IO sono collegati a dei circuiti (CONTROLLER) che gestiscono il coordinamento tra processore, memoria e dispositivi in modo da garantire il corretto trasferimento di dati.
Una caratteristica comune a tutti i dispositivi è quella di operare in modo asincrono rispetto al processore.
Consideriamo una tastiera che produce dei dati di input. Il processore non è in grado di prevedere e di controllare il momento in cui un dato di input sarà a disposizione.
Allo stesso modo, il processore non può prevedere il momento in cui un dispositivo in output avrà terminato di produrre i dati in uscita.
Sono pertanto necessarie delle forme di sincronizzazione tra i dispositivi e il processore.
Ad ogni ciclo di clock, l'unità di controllo, prima di iniziare l'esecuzione della prossima istruzione del programma in corso, verifica se è arrivato un segnale di interrupt da parte di qualche dispositivo.
Se non c'è nessun segnale di interrupt il processore prosegue normalmente, altrimenti sospende per un attimo l'esecuzione del programma in esecuzione ed esegue le operazioni richieste dal dispositivo.
I vari dispositivi di input/output sono collegati al processore attraverso il bus, su ognuno dei quali viene inserito una componente hardware, il controller, che gestisce la comunicazione con il dispositivo.
Il mouse
Oggi quasi tutti i computer hanno un dispositivo di puntamento detto mouse che permette di trasferire un movimento su base solida lineare in uno analogo da parte di un indicatore sullo schermo del monitor detto puntatore:
- lo spostamento fisico del mouse viene comunicato al processore, che produce lo spostamento corrispondente della freccia sul video.
- Una volta raggiunta la posizione desiderata, premendo uno dei pulsanti del mouse si genera un segnale in input che può corrispondere a diverse funzioni.
Ci sono diversi tipi di mouse:
- mouse meccanici = la rotazione di una sfera viene trasmessa tramite sensori interni al processore. Molto economici ma si sporcano facilmente.
- mouse ottici = inizialmente utilizzavano un LED e un trasduttore ottico- elettrico (fotodiodo) per rilevare il movimento relativo alla superficie d'appoggio (utilizzabili solo su speciali superfici metalliche con una rete di sottili linee blu e grigie). Oggi incorporano un chip per l'elaborazione dell'immagine, in modo da poter essere utilizzati su un maggior numero di superfici comuni.
- mouse laser = sono essenzialmente mouse ottici che utilizzano un laser al posto di un LED per l'illuminazione del piano d'appoggio. Come conseguenza si ha una maggiore risoluzione nell'acquisizione dell'immagine, che si traduce in migliore precisione e sensibilità di movimento.
La tastiera
La tastiera non ha capacità di elaborazione, l'unica cosa che è in grado di fare è di avvertire il processore ogni volta che un carattere è disponibile in ingresso.
Si tratta quindi di un dispositivo di ingresso a carattere.
È compito del sistema quello di prelevare il carattere, depositarlo in una memoria temporanea ed infine, al termine dell'immissione, passare i dati di input raccolti nella memoria temporanea al programma cui erano destinati.
La tastiera è un dispositivo di input cieco, nel senso che l'utente non può vedere i dati immessi nel calcolatore.
Per questa ragione la tastiera è utilizzata insieme ad un dispositivo di output su cui vengono visualizzate le informazioni fornite tramite tastiera.
La tastiera e il video non sono direttamente collegati tra loro.
E’ compito del processore di riprodurre sul video tutte le informazioni fornite in input tramite la tastiera.
Il monitor
Dal punto di vista fisico, un video può essere visto come una matrice di punti illuminati con diversa intensità.
Ogni punto sullo schermo prende il nome di pixel e un'immagine viene quindi composta accendendo o spegnendo i pixel sullo schermo.
Esistono video a diversi livelli di risoluzione, cioè con diverse densità di pixel; nei personal sono oggi comuni video con risoluzioni che vanno da 640 x 480 fino a 4096 x 3300 pixel (altissima risoluzione).
La dimensione di un video viene misurata in pollici e fa riferimento alla lunghezza della diagonale.
Il componente principale di un monitor è il display, cioè il dispositivo elettronico per la visualizzazione. In base alla tecnologia usata si distinguono le seguenti tipologie di display:
- a tubo catodico: detti video CRT (Cathode Ray Tube),
- al plasma,
- a cristalli liquidi: detti video LCD (Liquid Crystal Display),
- a LED.
L’immagine che vediamo sul video, opportunamente codificata, viene memorizzata in una memoria specializzata detta MEMORIA VIDEO (VRAM) che è parte del controller (scheda grafica).
Scheda Madre
La scheda madre (motherboard) è il supporto per la connessione di tutti i componenti interni del computer e contiene inoltre una serie di circuiti (chipset, cache, BIOS) adibiti al controllo delle varie parti.
Come indicato dal suo nome, la scheda madre è una scheda master, a forma di un grande circuito stampato che ha soprattutto dei connettori per le schede di estensione, per la RAM, il processore, ecc. vi si trovano inoltre le prese per il collegamento dell'hard disk e dei drive per i dischi mobili (floppy e CD).
La struttura attuale delle schede di sistema dei computer è il frutto di un'evoluzione tecnologica che ha portato a definire una architettura di sistema valida, in linea di massima, per tutti i sistemi di classe personal computer o di potenza.
Architettura: tipologia di progettazione adottata dalla scheda madre per scambiare i dati tra CPU e le periferiche inserite.
L'architettura, in quest’ultimo caso, può essere:
- parallela = (parallelismo spaziale) in un unico calcolatore diverse operazioni (processi) vengono eseguite simultaneamente da più' processori; la prima macchina
(supercomputer) ad avere questa architettura fu la CDC 6600 nel 1964.
- pipeline = (parallelismo temporale) le operazioni vengono suddivise in stadi successivi da più componenti hardware.
- seriale = la CPU esegue un'operazione alla volta.
Stampanti
- laser = usano una tecnologia simile a quella delle fotocopiatrici. Riescono a stampare molto velocemente e silenziosamente, offrendo inoltre la migliore qualità di stampa.
- a getto d’inchiostro = la stampa avviene spruzzando sulla carta un sottile getto d’inchiostro liquido. Producono stampe di qualità leggermente inferiore rispetto alle stampanti laser, sono generalmente più lente, ma anche più economiche e di dimensioni più contenute.
- ad aghi = oramai quasi del tutto scomparse, utilizzano una serie di piccoli aghi con inchiostro per formare scritte e semplici disegni.
Il software
Il sistema operativo
Il sistema operativo è un programma (cioè un software) responsabile del controllo e della gestione dei componenti hardware che costituiscono un computer e dei programmi che su di esso vengono eseguiti. Il sistema operativo mette a disposizione dei programmi un’interfaccia software per accedere alle risorse hardware del sistema (dischi, memoria, I/O in generale).
Il compito di un sistema operativo è quello di permettere all’uomo di interagire direttamente con la macchina.
I software applicativi
I software applicativi, tipicamente, sono tutti gli altri programmi, in quanto gestiti dal sistema operativo e ad esso subordinati nel richiedere le risorse sottostanti.
Architettura software
Driver = sono l’insieme dei programmi usati dal sistema operativo di un computer per gestire un dispositivo a questo collegato, ovvero le istruzioni fornite al sistema operativo su come utilizzare quel dispositivo.
I programmi
Un programma, in informatica, è un software che può essere eseguito da un elaboratore per ricevere in input determinati dati di un problema automatizzabile e restituirne in output le (eventuali soluzioni).
Applicativo, applicazione, software sono diversi termini per chiamare un programma o un insieme di programmi.
Non sono propriamente sinonimi: può cambiare il contesto, lo stato del programma o semplicemente il punto di vista.
Processo = in informatica, è sostanzialmente un programma in esecuzione
Rappresentazione binaria
Tutta l’informazione interna ad un computer è codificata con sequenze di due soli simboli : 0 e 1.
E’ facile realizzare dispositivi elettronici che discriminano fra due stati, molto meno se gli stati sono tanti. L’unità elementare di informazione si chiama bit da ‘binary digit’.
Vedremo prima come rappresentare i numeri come sequenze di 0 e 1.
E poi discuteremo la rappresentazione di insiemi di oggetti finiti (caratteri, giorni della settimana, operazioni elementari etc…).
Notazione posizionale in base 10
Un numero (es. 5) può essere rappresentato in molti modi: cinque, five, 5, V.
Rappresentazioni diverse hanno proprietà diverse: moltiplicare due numeri in notazione romana è molto più difficile che moltiplicare due numeri in notazione decimale.
Noi siamo abituati a lavorare con numeri rappresentati in notazione posizionale in base 10.
La rappresentazione di un numero intero in base 10 è una sequenza di cifre scelte fra 0 1 2 3 4 5 6 7 8 9 (es: 23, 118, 4)
Il valore di una rappresentazione cN…c0 è dato da
cN * 10N + cN-1 * 10N-1 ….+ c1 * 101 + c0 * 100
es: 23 = 2*101 + 3 * 100 = 20 + 3
Vediamo alcune proprietà di questa notazione:
- Il massimo numero rappresentabile con N cifre è 99….9 (N volte 9, la cifra che vale di più), pari a 10N-1
es: su tre cifre il massimo numero rappresentabile è 999 pari a 103-1 =1000-1
Vediamo alcune proprietà di questa notazione (cont.):
Quindi se voglio rappresentare K diverse configurazioni (cioè 0 1 2 …K-1) mi servono almeno almeno x cifre dove 10x è la più piccola potenza di 10 >= K
es : se voglio 25 configurazioni diverse mi servono almeno 2 cifre perché 102=100 è la più piccola potenza di 10 maggiore di 25.
Notazione posizionale in base 2
• La rappresentazione di un numero intero in base 2 è una sequenza
di cifre scelte fra 0 e 1:
– es: 10, 110, 1
• Il valore di una rappresentazione cN…c0 è dato da cN * 2N + cN-1 * 2N-1 ….+ c1 * 21 + c0 * 20
esempi :
– 102 = 1*21 + 0 *20 = 210
– 1102 = 1*22 + 1*21 + 0 * 20 = 4 + 2 + 0 = 610
– 12 = 1 *20 = 12
Per la base due valgono proprietà analoghe a quelle viste per la base 10 :
- il massimo numero rappresentabile con N cifre è 11….1 (N volte 1, la cifra che vale di più), pari a 2N-1
es: su tre cifre il massimo numero rappresentabile è 111 pari a 23-1 = 8 - 1 = 7
Per la base due valgono proprietà analoghe a quelle viste per la base 10 (cont.):
- quindi se voglio rappresentare K diverse configurazioni (cioè 0 1 2 …K-1) mi servono almeno almeno x cifre dove 2x è la più piccola potenza di 2 >= K.
es : se voglio 25 configurazioni diverse mi servono almeno 5 cifre perché 25=32 è la più piccola potenza di 2 maggiore di 25.
Conversione da base 10 a base 2
Dato un numero X si cerca cN…c0 sua rappresentazione in base 2.
Conversione per divisione :
- si divide ripetutamente X per 2;
- il resto ottenuto nella divisione i-esima è la i-esima cifra (ci) della rappresentazione binaria
Come si converte X nella sua rappresentazione in base 2 cN…c0
usando il metodo della divisione
• Es : convertiamo il numero 13
– 13 / 2 da quoziente 6 e resto 1 (c0)
– 6 / 2 da quoziente 3 e resto 0 (c1)
– 3 / 2 da quoziente 1 e resto 1 (c2)
– 1 / 2 da quoziente 0 e resto 1 (c3)
La rappresentazione di 13 è 1101
La rappresentazione dei numeri all’interno di un computer
- Usa la notazione binaria
- Ogni numero viene rappresentato con un numero finito di cifre binarie (bit)
- Numeri di ‘tipo’ diverso hanno rappresentazioni diverse
es. interi positivi, interi (pos. e neg.), razionali, reali, complessi
Alcuni termini utili:
- byte : una sequenza di 8 bit
- word (parola) : 2 o 4 byte (dipende dalla macchina) unità minima che può essere fisicamente letta o scritta nella memoria
Tipicamente gli interi positivi si rappresentano usando 2 o 4 byte
Alcuni punti importanti:
- se uso 4 byte (32 bit) posso rappresentare solo i numeri positivi da
0 a 
-1, che sono molti ma non tutti !
- se moltiplico o sommo due numeri molto elevati posso ottenere un numero che non è rappresentabile
es: vediamo cosa succede in base 10 con solo 3 cifre :
500 + 636 = 1136 risultato 136 se uso solo 3 cifre non ho lo spazio fisico per scrivere la prima cifra (1) che viene ‘persa’, è un fenomeno chiamato overflow.
Interi positivi e negativi:
– es. il tipo int in C usa di solito 4 byte
– ci sono diverse convenzioni di rappresentazione
es: modulo e segno in cui il primo bit viene riservato al segno (1 negativo, 0 positivo) e gli altri 31 al modulo.
– rimane il problema dell’overflow
• Interi positivi e negativi: il complemento a due.
Stabilito il numero di bit, supponiamo n, il bit più significativo ha peso: -(2n-1).
Sulla base di questa considerazione possiamo riscrivere quella formula che, data la sequenza di bit, mi esprimeva il valore vero del numero:
NV = 
+ 
+ ...+ 
Data una sequenza di bit che rappresenta un numero relativo in complemento a due posso ricavare il valore vero del numero sulla base della relazione appena esposta.
Esempi:
N = 0101(
) NV = 0
+ 1
+ 0
+ 1
= 4 + 1 = 5
N = 1011() NV = -1 + 0 + 1 + 1 = -8 + 2 + 1= -5
Sulla base degli esempi possiamo osservare che anche nella rappresentazione in complemento a 2, così come valeva per la rappresentazione in modulo e segno, il primo bit mi dice se il numero è positivo o negativo, in particolare se il primo bit è 0 il numero è positivo, se il primo bit è 1 il numero è negativo.
Razionali
– numero finito di cifre periodiche dopo la virgola (ad esempio 3.12)
– rappresentazione solitamente su 4/8 byte
– rappresentazione in virgola fissa : riservo X bit per la parte frazionaria
– es : con 3 bit per la parte intera e 2 per quella frazionaria 011.11, 101.01
Come si converte in base 10 una rappresentazione in virgola fissa
es :
101.01 = 1 + 0 + 1 + 0
+ 1
= 4 + 1+ 0.25 = 5.25
dove = 1/2 = 0.5 e = 1/22 = 0.25
e in generale 
= 
Problemi della rappresentazione in virgola fissa
– overflow
– underflow = quando si scende al di sotto del minimo numero rappresentabile
• es. vediamo in base 10, con 2 cifre riservate alla parte frazionaria 0.01/2 = 0.005 non rappresentabile usando solo due cifre
Problemi della rappresentazione in virgola fissa (cont.)
– spreco di bit per memorizzare molti ‘0’ quando lavoro con numeri molto piccoli o molto grandi
• es. vediamo in base 10, con 5 cifre per la parte intera e 2 cifre riservate alla
parte frazionaria
10000.00 oppure 00000.02
– i bit vengono usati più efficientemente con la notazione esponenziale o floating point (virgola mobile)
Rappresentazione in virgola mobile (cont.)
– ogni numero N è rappresentato da una coppia (mantissa M, esponente E) con il seguente significato N = M * 2E
esempi:
1. in base 10, con 3 cifre per la mantissa e 2 cifre per l’esponente riesco a
rappresentare 349 000 000 000 = 3.49
con la coppia (3.49,11) perché M = 3.49 ed E = 11
Rappresentazione in virgola mobile (cont.)
– esempi:
2. in base 10, con 3 cifre per la mantissa e 2 per l’esponente riesco a
rappresentare
0.000 000 002 = 2.0 * 10-9 con la coppia (2.0,-9) perché M = 2.0 ed E = -9
– sia 0.000 000 002 che 349 000 000 000 non sono rappresentabili in virgola fissa usando solo 5 cifre decimali !!!
Rappresentazione di un insieme finito di oggetti
Vogliamo rappresentare i giorni della settimana {Lu, Ma, Me, Gio, Ve, Sa, Do} usando sequenze 0 e 1.
Questo significa costruire un ‘codice’, cioè una tabella di corrispondenza che ad ogni giorno associa una opportuna sequenza.
In principio possiamo scegliere in modo del tutto arbitrario….
Una possibile codifica binaria per i giorni della settimana.
Problema : la tabella di corrispondenza fra codifiche tutte di lunghezza diversa.
– spreco di memoria
– devo capire come interpretare una sequenza di codifiche
– 110000011 = Me Gio Gio
– 110000011 = Gio Gio Do Gio
Di solito si usa un numero di bit uguale per tutti : il minimo indispensabile.
Per rappresentare 7 oggetti diversi servono almeno 3 bit (minima potenza di due che supera 7 è 8= ) quindi :
000 Lunedì 110 Domenica
001 Martedì 111 non ammesso
010 Mercoledì
011 Giovedì
100 Venerdì
101 Sabato
Rappresentazione di caratteri e stringhe
Stringhe = sono generalmente sequenze di caratteri terminate in modo particolare.
Perché due diversi calcolatori si possano parlare correttamente è necessario che usino lo stesso codice. Codifiche di uso comune per i caratteri:
– il codice ASCII (American Standard code For Information Interchange) su 7 o 8 bit. È un codice di 7 bit che offre dunque la possibilità di esprimere 128 simboli diversi. In generale si utilizza il codice ASCII esteso, che utilizza 8 bit, e aggiunge altri 128 simboli specifici della nazione in cui ci si trova o del sistema operativo che si utilizza.
I primi 31 elementi del codice ASCII rappresentano codici di controllo, ad esempio il codice associato al valore 8 rappresenta il Backspace ;
– il codice UNICODE su 16 bit (più recente, permette di rappresentare anche alfabeti diversi e simboli per la scrittura di lingua orientali);
Rappresentazione di immagini
Le immagini sono un ‘continuo’ e non sono formate da sequenze di oggetti ben 口definiti come i numeri e le stringhe. Bisogna quindi prima ‘discretizzarle’, ovvero trasformarle in un insieme di parti distinte che possono essere codificate separatamente con sequenze di bit.
Consideriamo prima immagini fisse (foto etc …)
• Immagini ‘bitmap’ :
1. l’immagina viene scomposta in una griglia di elementi detti pixel
(da picture element)
000000000000000000000000
0000000000111111110000000
000000000010000010000000
000000000010000100000000
000000000010001000000000 
codifica
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
2. Ogni pixel è rappresentato da uno o più bit
Rappresentazioni dei pixel :
– la rappresentazione in ‘toni di grigio’ : un byte per pixel, con 256gradazioni di grigio per ogni punto (immagini bianco e nero), o più byte per pixel, per avere più gradazioni possibili;
– rappresentazione a colori RGB (red, green, blue): comunemente 3 byte per pixel che definiscono l’intensità di ciascun colore base. In questo modo ho circa 16 milioni di colori diversi definibili
Problema :
– la rappresentazione accurata di una immagine dipende
dal numero di pixel (definizione)
dalla codifica del pixel
– … e richiede generalmente molta memoria
Quindi si cerca di ‘risparmiare’ memoria :
– con l’uso di una ‘tavolozza’ (palette) che contiene il sottoinsieme dei colori rappresentabili che compare in una foto. Ogni pixel codifica un indice all’interno della tavolozza;
– con tecniche di compressione che non codificano ogni pixel in modo autonomo ma cercano di raggruppare le aree che hanno caratteristiche comuni.
Principali funzioni logiche
Porte Logiche = sono elementi circuitali che corrispondono alle operazioni logiche e che possono essere combinati per effettuare operazioni più complesse.
Ad esempio, tramite le porte logiche possono essere definiti circuiti sommatori.
Richiami al calcolatore
Calcolatore elettronico - Computer
strumento per la rappresentazione e l’elaborazione dell’informazione oppure esecutore di algoritmi;
l’informazione viene rappresentata con sequenze di bit (0/1).
Il Calcolatore
E’ uno strumento in grado di eseguire insiemi di azioni (“mosse”) elementari;
Le azioni vengono eseguite su oggetti (dati) per produrre altri oggetti (risultati);
L’esecuzione di azioni viene richiesta all’elaboratore attraverso frasi scritte in un qualche linguaggio (istruzioni).
Concetto di Algoritmo
Algoritmo = sequenza finita di passi che portano alla realizzazione di un compito.
Proprietà fondamentali
1) eseguibilità = ogni azione deve essere eseguibile da parte dell’esecutore dell’algoritmo in un tempo finito;
2) non-ambiguità = ogni azione deve essere univocamente interpretabile dall'esecutore;
3) finitezza = il numero totale di azioni da eseguire, per ogni insieme di dati di ingresso, deve essere finito.
Quindi un algoritmo deve:
- essere applicabile a qualsiasi insieme di dati di ingresso appartenenti al dominio di definizione dell’algoritmo;
- essere costituito da operazioni appartenenti ad un determinato insieme di operazioni fondamentali;
- essere costituito da regole non ambigue, cioè interpretabili in modo univoco qualunque sia l’esecutore (persona o “macchina”) che le legge.
Altre proprietà desiderabili: generalità, determinismo, efficienza.
Programmi e programmazione
Programmazione = è l'attività con cui si definiscono le operazioni che servono a predisporre
l'elaboratore ad eseguire un particolare insieme di azioni su particolari dati, allo
scopo di risolvere un problema. Essa è l’attività di progettare e, cioè definire le istruzioni che indicano ad un calcolatore i passi da eseguire per risolvere un problema.
Programma = sequenza di istruzioni di un linguaggio di programmazione comprensibile al
calcolatore che realizzano un compito o risolvono un problema. Esso è la descrizione di un algoritmo in un particolare linguaggio di programmazione.
Linguaggio di programmazione = è una notazione formale per descrivere algoritmi che è comprensibile ad un calcolatore.
SINTASSI e SEMANTICA
Ogni linguaggio è caratterizzato da:
- sintassi = l’insieme di regole formali per la scrittura di programmi in quel linguaggio, che
dettano le modalità per costruire frasi corrette nel linguaggio stesso.
- semantica = l’insieme dei significati da attribuire alle frasi (sintatticamente corrette) costruite nel linguaggio.
Tipi di Linguaggi di Programmazione
- Linguaggi macchina e linguaggi assembler = ogni azione è indicata in codice binario o con operazioni molto semplici e “rudimentali”: ADD X, Y oppure STORE A;
- Linguaggi imperativi (PASCAL, FORTRAN, C, BASIC, MATLAB...) = le azioni da compiere sono indicate in una sequenza che partendo dai dati si completa calcolando i risultati: if a > 0 print (“valore positivo”) else print (“valore negativo”);
- Linguaggi dichiarativi (logici - PROLOG, funzionali - LISP) = un programma è la definizione di una funzione o l’elenco delle regole logiche che portano a verificare una condizione.
- Linguaggi orientati agli oggetti (C++, Java, Smalltalk, MATLAB, ....) = sono basati sul concetto di oggetto software che rappresenta un oggetto del mondo reale (un numero, un archivio, un testo, una matrice). I dati sono rappresentati come oggetti e le azioni da compiere come operazioni da effettuare sugli oggetti. Di solito sono realizzati come estensione dei linguaggi imperativi. Un programma modella un problema reale come una collezione di oggetti software che interagiscono.
Per far eseguire un programma ad un calcolatore occorre tradurlo dal linguaggio usato nel linguaggio macchina. La traduzione avviene secondo due modalità principali:
1) Compilazione = il compilatore controlla che tutte le istruzioni del programma siano corrette e alla fine di questo controllo se non ci sono errori genera il programma eseguibile che verrà eseguito dall’esecutore.
2) Interpretazione = l’interprete controlla una per volta ogni singola istruzione del programma e se questa è corretta la traduce e la esegue. Al primo errore termina l’esecuzione del programma.
Specifica di un algoritmo
Primo approccio, scrittura diretta del programma: la soluzione coincide con la codifica:
- Causa errori difficilmente individuabili,
- Non garantisce che non esistano soluzioni chiaramente migliori,
- Non funziona con programmi grandi,
- Rende difficile cambiare linguaggio di programmazione.
- Perciò, è conveniente concentrarsi sulla specifica del problema e dell’algoritmo; la codifica dovrebbe essere solo un passo implementativo.
Linguaggio macchina
Le istruzioni elementari eseguite dalla CPU di un computer si chiamano istruzioni macchina.
L’insieme delle istruzioni macchina (instruction set ) costituiscono il linguaggio macchina.
Un linguaggio macchina:
- consente la programmazione della Macchina di von Neumann,
- è direttamente eseguibile da un calcolatore senza nessuna traduzione,
- naturalmente cambia da macchina a macchina (ad es., quello del Pentium è diverso da quello dello AMD).
Le istruzioni sono codificate in formato binario e sono composte da:
- Codice operativo (m) = indica l’istruzione da eseguire
- Operandi (n) = indicano gli operandi (indirizzi o valore)
Per semplicità ipotizziamo di avere istruzioni con solo operando.
Lunghezza delle istruzioni: I=m+n
m: num bit del codice operativo, n: num bit dell’operando.
Set di istruzioni: insieme delle operazioni del linguaggio macchina (<= 2m).
Istruzioni aritmetiche, logiche, di salto, di trasferimento dati.
Ipotesi: istruzione a 16 bit : 4 bit per il codice operativo e 12 bit per l’operando
Esecuzione delle istruzioni:
- Un programma è fatto di DATI + ISTRUZIONI.
- I dati hanno un formato e vengono scritti in memoria di massa per non perdere il loro valore.
Ciclo di esecuzione:
1. Acquisizione dell’istruzione dalla memoria centrale (fase di FETCH);
2. Interpretazione (analisi del codice operativo dell’istruzione);
3. Esecuzione (in questa fase se c’è un operando va caricato nella CPU).
Linguaggio assembler
Linguaggi Assemblatori (ASSEMBLER)
Sono linguaggi le cui istruzioni corrispondono univocamente a quelle del linguaggio macchina, ma sono espresse tramite nomi simbolici (parole chiave) invece che in binario.
Ad esempio : READ X ; MULT X, Y; LOAD Z;
Assemblatore = strumento automatico (programma) che traduce le istruzioni da formato simbolico al formato binario.
0100 1001 → READ X.
In un linguaggio Assembler:
- il programma prima di essere eseguito deve essere tradotto in linguaggio macchina dall’
Assemblatore.
- le istruzioni vengono specificate con nomi simbolici (parole chiave).
- i riferimenti alle celle di memoria (dati) sono fatti mediante nomi simbolici (identificatori).
- i modi di indirizzamento vengono indicati tramite simboli.
Il programma prima di essere eseguito deve essere tradotto in linguaggio macchina dall’
Assemblatore.
Linguaggio macchina: prodotto tra due numeri
Esempio
Programma assembler che calcola il prodotto di due numeri con il corrispondente programma in linguaggio macchina
Verso linguaggi di alto livello
- Linguaggio Macchina = conoscenza precisa dei metodi di rappresentazione e manipolazione delle informazioni utilizzate.
- Linguaggio Macchina ed Assembler = Necessità di conoscere dettagliatamente le caratteristiche della macchina (registri, dimensioni dati, set di istruzioni).
Semplici algoritmi richiedono l'uso di molte istruzioni. Linguaggi di Alto Livello
- Linguaggi ad alto livello = Il programmatore può astrarre dai dettagli legati all’architettura e può esprimere i propri algoritmi in modo simbolico. I linguaggi di alto livello sono indipendenti dalla macchina fisica (astrazione).
COME ESEGUIRE UN PROGRAMMA SCRITTO IN UN LINGUAGGIO DI ALTO LIVELLO?
Occorre tradurlo nel linguaggio macchina dello specifico processore che si sta usando.
Due possibili modi:
- Compilazione (es. C, FORTRAN, Pascal, C++, COBOL,...).
- Interpretazione (es. Basic, Perl, JavaScript, ...).
Compilatori
I compilatori traducono un intero programma dal linguaggio 
al linguaggio macchina 
della macchina prescelta:
- traduzione e esecuzione procedono separatamente,
- al termine della compilazione è disponibile la versione tradotta del programma,
- la versione tradotta è però specifica di quella macchina; per eseguire il programma basta avere disponibile la versione tradotta (non serve il programma originale!).
→
Interpreti
Gli interpreti invece traducono e immediatamente eseguono il programma istruzione per istruzione:
- traduzione ed esecuzione procedono insieme,
- al termine non vi è alcuna versione tradotta del programma originale,
- se si vuole ri-eseguire il programma occorre anche ri-tradurlo.
Fase di sviluppo di un programma
Qualunque sia il linguaggio di programmazione scelto occorre:
1. Scrivere il testo del programma e memorizzarlo su supporti di memoria permanenti (editing)
2. Se il linguaggio è compilato:
a. Tradurre il linguaggio in linguaggio macchina (compilazione);
b. Eseguire il programma tradotto.
3. Se il linguaggio è interpretato: usare l’interprete per eseguire il programma.
Formalismi per la descrizione di un algoritmo
Per descrivere i passi di un algoritmo bisogna essere precisi e non ambigui, perciò si usano due formalismi:
- diagrammi di flusso: formalismo grafico
- pseudo-codice: linguaggio con istruzioni simili a quelle dei linguaggi di programmazione
Un esempio di algoritmo
Calcolo del perimetro di un rettangolo Inizio
SCRIVI “Fornisci la misura della base”
LEGGI b
SCRIVI “Fornisci la misura dell’altezza”
LEGGI h
D1 := 2 * b
D2 := 2 * h
P := D1 + D2
SCRIVI “La misura del perimetro è”
SCRIVI P
Fine
Diagrammi di flusso
I Diagrammi di flusso sono un linguaggio grafico per la rappresentazione di un algoritmo. Il diagramma è composto da:
- blocchi che rappresentano i passi dell’algoritmo
- I blocchi hanno forme diverse in base al significato
- I blocchi contengono testo che descrive il passo da eseguire
- Utili per descrivere un algoritmo più che per eseguirlo…
Specifica di inizio e di fine
Ogni algoritmo deve avere un inizio e una fine
Input ed output di dati
Ogni algoritmo parte da dati in
ingresso per produrre dati in
uscita (problema
computazionale)
Specifica delle azioni
Ogni algoritmo specifica azioni che l’esecutore deve compiere del tipo descritto in precedenza
Diagrammi di Flusso: Strutture Avanzate
Il blocco sequenza viene utilizzato per indicare l’esecuzione consecutiva di blocchi.
Specifica delle condizioni logiche
Alcuni passi di un algoritmo si devono eseguire se sono verificate condizioni logiche su valori di variabili. In genere, questi salti dell’algoritmo sono sottoposti ad una condizione logica (risposta vero o falso); Si parla di blocchi decisionali
………
azioni
if (condizione logica) then
azioni caso vero
else
azioni caso falso
end if
azioni seguenti comuni
azioni
if (condizione logica) then
azioni caso vero
end if
azioni seguenti comuni
azioni
if (condizione logica 1) then
if (condizione logica 2) then
azioni vero 2
else
azioni falso 2
end if
else
if (condizione logica 3) then
azioni vero 3
end if
end if
azioni seguenti comuni
Flusso di esecuzione
- I singoli diagrammi devono essere uniti tramite i connettori (linee e frecce in un flow chart).
- L’esecuzione dei passi deve essere fatta sequenzialmente, ovvero seguendo i connettori, partendo dall’inizio dell’algoritmo fino a raggiungere la sua fine.
- Quando si scrive l’algoritmo bisogna fare molta attenzione alla direzione del flusso di esecuzione.
Strutture di controllo: iterazione
azioni
while (condizione logica)
azioni da ripetere
end while
azioni seguenti
Struttura di controllo: iterazioni annidate
azioni
while (condizione logica esterna)
while (condizione logica interna)
azioni iterazione interna da ripetere
end while
azioni iterazione esterna da ripetere
end while
azioni seguenti
Diagrammi di flusso strutturati
Un Diagramma di flusso si chiama strutturato se:
- ha un solo blocco START
- ha un solo blocco STOP
- utilizza solo sequenze o le strutture avanzate
■ If-then
■ If-then-else
■ While-do
■ Repeat-until
Diagrammi di flusso
Diagrammi di flusso: strutture avanzate
Teorema di Böhm-Jacopini
Qualunque diagramma di flusso può essere trasformato in un diagramma di flusso strutturato equivalente
In altre parole è possibile realizzare ogni algoritmo utilizzando solo le strutture avanzate
I Diagrammi strutturati hanno il vantaggio di essere molto più intuitivi e comprensibili.
Diagrammi di flusso ed algoritmi: concetti acquisiti
- L’algoritmo definisce una sequenza di passi che permettono all’esecutore di ottenere un
risultato in base ai dati di cui dispone.
- I Diagrammi di flusso sono un linguaggio visuale per rappresentare algoritmi
- I Diagrammi di Flusso strutturati utilizzano delle strutture avanzate per rappresentare i passi (selezione e cicli)
Sviluppo di programmi
- FASE 1: Dare un nome al problema partendo dall’analisi del problema
- FASE 2: Scrivere la specifica funzionale
- FASE 3: Scrittura dell’algoritmo
FASE 3.1: Introduzione delle variabili (contenitori di dati) necessarie e delle relative operazioni elementari
FASE 3.2: Specifica di un diagramma di flusso (o di uno pseudo codice) che descrive in modo preciso e non ambiguo la sequenza di operazioni da eseguire
- FASE 4: Traduzione del diagramma di flusso (o dello pseudo codice) in un programma in un linguaggio di programmazione
Analisi di algoritmi
- Dato un algoritmo A e un problema P dimostrare che A risolve P (correttezza) e valutare la quantità di risorse usate da A (complessità computazionale).
- Un algoritmo è corretto se, per ogni istanza di input, termina con l’output corretto.
- Per gli algoritmi studiati durante il corso saranno presentate tecniche matematiche per permettere l’analisi della complessità in modo semplice.
- Lo studio teorico dell’efficienza (performance) di un programma e dell’uso delle risorse.
Cos’è più importante della performance? Modularità correttezza funzionalità robustezza user-friendliness tempo di programmazione semplicità estensibilità affidabilità
Analisi di algoritmi: Modello di calcolo
- Modello delle risorse e dei costi dell’uso delle risorse
- Modello RAM = Random-Access Machine:
1 processore;
Istruzioni sequenziali;
Istruzioni aritmetiche (add, sub, mul, div, mod), per spostare dati (load, store), di controllo (salto [in] condizionato, chiamata a subroutine, return) -> costo costante
Memoria RAM e disco, no cache e memoria virtuale;
Complessità di un algoritmo
- T(n) = tempo di esecuzione = numero di operazioni elementari eseguite
- S(n) = spazio di memoria = numero di celle di memoria utilizzate durante l’esecuzione
- n = dimensione (taglia) dei dati di ingresso
Es. vettore di elementi: n = numero degli elementi
Es. grafo: n,m = numero dei vertici, numero archi
T(n) tempo di elaborazione
Caso peggiore: (spesso)
T(n) = tempo massimo dell’algoritmo su qualsiasi input di dimensione n
Caso medio: (talvolta)
T(n) = tempo atteso su tutti gli input di dimensione n = tempo di ogni input x la probabilità che ci sia quell’input (media pesata). È necessaria un’assunzione sulla distribuzione statistica degli input (spesso distribuzione uniforme).
Caso migliore: (fittizio = prob. non si verificherà mai).
Ingannevole per algoritmi lenti che sono veloci su qualche input.
Caso peggiore
- Generalmente si cerca un limite superiore perché:
Fornisce una garanzia all’utente (l’algoritmo non potrà impiegare più di così).
- Per alcuni algoritmi si verifica molto spesso.
- Il caso medio spesso è cattivo quasi quanto quello peggiore
Non sempre è evidente cosa costituisce un input medio
Tempo di calcolo indipendente dalla macchina
- Qual è il tempo di calcolo di un algoritmo nel caso peggiore? Dipende dal computer usato:
velocità relativa (confronto sulla stessa macchina);
velocità assoluta (su macchine diverse).
- Grande idea:
Ignorare le costanti dipendenti dalla macchina.
Studiare il tasso di crescita di T(n) con n→∞, esse prende il nome di “Analisi asintotica”.
Operazioni su variabili
Voglio ottenere il valore assoluto di una variabile ma non conosco il nome della funzione, cosa devo fare?
- Usare il comando lookfor
- Usare il comando help
- Usare il comando helpbrowser
- Usare il comando doc
Matrici
Ogni cosa in matlab è rappresentata in matrici (anche le variabili viste fin’ora sono un caso particolare di matrici, aventi dimensione 1 x 1). Una matrice contiene elemente numerati per riga e per colonna (ad esempio 
denota l’elemento alla riga i e colonna j).
Matrici con una sola dimensione
Il loro aspetto intuitivo è quello di una lista o un array (vettore).
- un array riga è una matrice 1 x n
- un array colonna è una matrice n x 1
Struttura di dati = è un particolare modo di organizzare i dati in un computer, così che tali dati possano essere utilizzati in modo efficiente.
L’array (o vettore o matrice monodimensionale) è la struttura dati principale utilizzata in matlab.
Ogni variabile può memorizzare valori di un certo tipo di dato.
In matlab il tipo di dato principale è proprio il tipo di array
Matrici con due dimensioni
Il loro aspetto intuitivo è quello di un rettangolo o un quadrato
Matrici con tre dimensioni
Il loro aspetto è quello di un parallelepipedo
Commenti
Posta un commento