Elementi di Informatica

Elementi di informatica

Mauro Costantino

Indice

• 7.4 Dichiarazione . . . . . . . . . . 28
• 1 Introduzione 2
• 1.1 Computer . . . . . . . . . . . . 2
• 7.5 Argomenti del main . . . . . . . 30
• 1.2 Algoritmi . . . . . . . . . . . . 3
• 1.3 Scratch . . . . . . . . . . . . . . 5
• 8 Istruzioni 31
• 9 Costruzione di un’applicazione 34
• 2 Architettura di un elaboratore 6
• 9.1 Pre-processore . . . . . . . . . . 34
• 10 Ricorsione e iterazione 36
• 2.1 Central Processing Unit . . . . 6
• 2.1.1 Clock . . . . . . . . . . 7
• 10.1 Ricorsione . . . . . . . . . . . . 36
• 2.1.2 Registri . . . . . . . . . 7
• 10.2 Iterazione . . . . . . . . . . . . 36
• 2.1.3 Arithmetic & Logic Unit 7
• 2.1.4 Unità di controllo . . . 7
• 2.2 Unità di I/O . . . . . . . . . . . 8
• 11 Passaggio per puntatore 38
• 2.3 Memoria centrale . . . . . . . . 8
• 11.1 Procedure . . . . . . . . . . . . 38
• 2.4 Bus di sistema . . . . . . . . . . 9
• 11.2 Puntatori . . . . . . . . . . . . 38
• 2.5 Reti di calcolatori . . . . . . . . 9
• 12 Dati strutturati 40
• 3 Sistema operativo 10
• 12.1 Array . . . . . . . . . . . . . . 40
• 3.1 Shell . . . . . . . . . . . . . . . 10
• 12.2 Array multidimensionali . . . . 42
• 3.2 File . . . . . . . . . . . . . . . . 11
• 12.3 Strutture . . . . . . . . . . . . . 42
• 4 Rappresentazione dell’informazione 13
• 13 Operazioni sui tipi di dati 44
• 13.1 Conversioni . . . . . . . . . . . 44
• 4.1 Codifica dell’informazione . . . 13
• 13.2 Tipi definiti dall’utente . . . . . 45
• 4.2 Caratteri e stringhe . . . . . . . 14
• 4.3 Immagini . . . . . . . . . . . . 15
• 14 Canali standard I/O 47
• 4.4 Suoni . . . . . . . . . . . . . . . 16
• 4.5 Informazioni numeriche . . . . . 16
• 15 Operazioni su file 50
• 4.6 Informazioni logiche . . . . . . . 18
• 15.1 File binari . . . . . . . . . . . . 51
• 4.6.1 Algebra Booleana . . . . 19
• 15.2 File di testo . . . . . . . . . . . 52
• 5 Linguaggi di programmazione 20
• 16 Algoritmi di ordinamento 54
• 5.1 Definizione formale di un linguaggio . . . . . . . . . . . . 20
• 16.1 Naïve sort . . . . . . . . . . . . 54
• 5.1.1 Backus-Naur form . . . 20
• 16.2 Bubble sort . . . . . . . . . . . 55
• 16.3 Insert sort . . . . . . . . . . . . 55
• 16.4 Quick sort . . . . . . . . . . . . 56
• 6 Il linguaggio C 22
• 16.5 Merge sort . . . . . . . . . . . . 57
• 6.1 Dati . . . . . . . . . . . . . . . 22
• 16.6 Complessità . . . . . . . . . . . 58
• 16.7 Algoritmi di ricerca . . . . . . . 58
• 6.2 Variabili e funzioni . . . . . . . 23
• 7 Funzioni 26
• 7.1 Modello cliente-servitore . . . . 26
• 17 Allocazione dinamica della memoria 59
• 7.2 Funzioni come espressioni . . . 26
• 7.3 Modello applicativo . . . . . . . 27
• 18 Liste 61

Capitolo 1

Introduzione

1.1 Computer

È uno strumento in grado di eseguire svolte su (o oggetti) per produrre mosse, dati risultati. L’esecuzione di tali mosse viene richiesta mediante scritte in qualche istruzioni linguaggio. Nel tempo, l’architettura dei calcolatori non è variata di molto, i computer di oggi sono "solo" più dotati di e, soprattutto, il che veloci, piccoli, interfacce utente evolute connessi, permette lo scambio di un’enorme quantità di dati in poco tempo. Un esempio di architettura è l’architettura di Von Neumann:

È composta da due blocchi principali, e La prima accede alla seconda per CPU RAM. scrivere dati ed è divisa in (unità di controllo) e (unità aritmetico-logica). La ALU CU ALU elabora effettivamente le operazioni, mentre la CU controlla la ALU e la riprogramma in modo da permetterle di svolgere compiti diversi, motivo per cui quest’ultima risulta essere la parte più complessa delle due. La è strutturata in di memoria numerate da 0 fino al numero massimo di celle RAM celle supportate dal calcolatore. In fase di la CPU ha il compito di specificare l’indirizzo lettura della cella contenente il dato interessato, mentre, in fase di il ruolo della CPU è scrittura, quello di fornire sia l’indirizzo della cella in cui scrivere il dato e sia il dato da scrivere. La RAM è una motivo per cui il suo contenuto si cancella allo spegnimento memoria volatile, del calcolatore. Essa però raggiunge velocità di lettura e scrittura molto più elevati di qualsiasi come hard disk o solid state drive. Il nome, Random Access Memory, memoria persistente fa riferimento alla possibilità di accedere ad ogni cella senza limitazioni, difatti il termine "Random" fu scelto per differenziarla dalle diffuse all’epoca, come a memorie sequenziali esempio i nastri. Una cosa importante da sottolineare è che il computer si limita ad eseguire istruzioni è sostanzialmente Ciò che dona "intelligenza" al calcola- molto velocemente, stupido. tore è proprio il che fornisce al computer una serie di istruzioni elementari programmatore, concatenate in modo da svolgere un compito più complesso.

I vengono processati da un che li prende in ingresso dati di input elaboratore elettronico assieme ad un o che contiene l’elenco di mosse da compiere sui dati, programma algoritmo, producendo in i risultati dell’elaborazione. I dati vengono rappresentati in output codice una serie di 1 e 0 nella quale ogni cifra corrisponde ad un (una singola unità binario, bit di informazione) che, di conseguenza, può assumere solo due valori. Prendiamo ad esempio i Ognuno di essi corrisponde ad un certo numero e ne esistono diverse caratteri alfanumerici. codifiche, ognuna con le proprie caratteristiche. La codifica più semplice è quella ASCII. Per quanto riguarda i (ad esempio un segnale audio), invece, vi è prima segnali analogici un del segnale ad una frequenza stabilita (solitamente doppia rispetto alla campionamento frequenza del segnale originale), a cui segue poi una che associa ad ogni quantizzazione elemento campionato una stringa di bit. Anche le istruzioni, oltre ai dati, possono essere rappresentate mediante codifica binaria o Tali istruzioni sono semplici e di bassissimo livello. Un esempio linguaggio macchina. di linguaggio a è l’Assembler la cui sintassi dipende dalla CPU che esegue basso livello l’istruzione. I linguaggi di programmazione ad alto livello non fanno altro che fornire funzioni per compiere operazioni "frequenti" e devono essere e formali, precisi univoci.

1.2 Algoritmi

Un algoritmo è una sequenza di mosse che risolve in un una serie di 1 algoritmo finita tempo finito problemi. È un elaboratore di dati e la sua efficienza dipende in maniera critica dal modo in cui gli stessi sono organizzati. La fase di scrittura, detta avviene mediante un insieme codifica, ordinato di scritte in un qualche linguaggio di programmazione. Un algoritmo, per istruzioni essere definito tale, deve avere le seguenti caratteristiche:

• Finitezza: deve necessariamente avere un termine.
• Generalità: deve fornire la soluzione per una risultando applicabile classe di problemi, a qualsiasi insieme di dati appartenenti al dominio dell’argomento.
• Non ambiguità: le mosse devono essere eseguite in modo univoco, evitando paradossi, contraddizioni e ambiguità.

Il concetto di algoritmo è strettamente dipendente da quello di Un algoritmo, infatti, dato. può essere visto come un in quanto, a fronte di dati in ingresso che manipolatore di dati, descrivono il problema, produce dati in uscita come risultato di un’elaborazione. Possiamo classificare le strutture di dati in due modi in base alla loro occupazione di memoria:

• Strutture dati statiche: nelle quali la quantità di memoria di cui necessitano è deter-minabile a priori (array, record).
• Strutture dati dinamiche: nelle quali la quantità di memoria di cui necessitano varia a tempo di esecuzione e può essere diversa da esecuzione ad esecuzione (liste, code).

Il vantaggio delle prime rispetto alle seconde ovviamente riguarda la velocità con la quale queste strutture di dati vengono processate, una struttura statica difatti viene processata in meno tempo rispetto ad una dinamica. Gli algoritmi, inoltre, devono essere mediante appositi linguaggi, poiché i formalizzati linguaggi naturali sono (la stessa parola può assumere significati diversi in base al ambigui contesto nel quale viene utilizzata) e (lo stesso concetto può essere espresso in ridondanti molti modi diversi). Un possibile formalismo per la descrizione degli algoritmi è il diagramma una rappresentazione grafica delle operazioni da eseguire, nel quale ogni passo è di flusso, visualizzato mediante simboli standard. Uno schema di flusso, inoltre, si dice strutturato quando soddisfa una delle seguenti proprietà:

• È uno sequenziale. schema elementare,
• È uno nel quale lo schema si divide in due parti che vengono schema di selezione, eseguite a seconda del valore di verità di una determinata condizione.
• È uno nel quale un’istruzione può non venire mai eseguita o venir schema di iterazione, eseguita più volte.

Il del 1966, affermateorema fondamentale della programmazione di Bohm/Jacopini, che ogni algoritmo può essere codificato riferendosi esclusivamente ad un algoritmo strutturato, attenendosi dunque alle tre strutture fondamentali così schematizzate:

Figura 1.2: proprietà dello schema di flusso strutturato. Nota che in un diagramma strutturato non apparirà mai un’istruzione di salto in- Gli schemi fondamentali di cui sopra possono essere concatenati o nidificati ma condizionato. non possono in nessun caso essere intrecciati o accavallati.

Programmi

Un programma è un testo scritto in accordo alla sintassi e alla semantica di un linguaggio di programmazione. Esso non è necessariamente un algoritmo in quanto può anche non ter- In fase di progettazione si preferisce evitare linguaggi troppo formali e si fa riferimento minare. allo un tipo di linguaggio più vicino al comune parlato, usato per descrivere pseudo-codice, il flusso del programma e per scomporre il problema in singoli compiti eseguibili in una mossa.

1.3 Scratch

È un ambiente di programmazione online con un linguaggio "visuale", all’interno del quale com- paiono diversi concetti fondamentali per ogni linguaggio come gli le statements, condizioni, i e le Una è essenzialmente un nome che si usa per indicare una loops variabili. variabile cella di memoria. Ad esempio, nel linguaggio C, la ha questo dichiarazione di una variabile aspetto:

int number = 34; number = 100;

Dove "int" si riferisce al della variabile, che viene assegnato a quest’ultima una volta tipo inizializzata e non può essere modificato, "34" è il assegnato alla variabile e "number" valore è il nome della stessa. La linea "number=100" è stata inserita per sottolineare che in C la variabile va dichiarata solo una volta. Essendo la variabile un’astrazione ad essa viene associato di una cella di memoria, un detto (poiché corrisponde a ciò che è a dell’uguale, indirizzo fisico, L-value sinistra nell’esempio di sopra "number"), fisso ed Quest’ultimo denota un certo immutabile. valore, detto (poiché corrisponde a ciò che è a dell’uguale, nell’esempio di sopra 34 R-value destra prima e 100 poi) che invece, come visto, può essere modificato. Altri elementi presenti in scratch e molto importanti per la programmazione, sono gli arrays, estensioni del concetto di variabile che corrispondono a locazioni di memoria contigue nelle quali sono contenuti determinati dati. In un array, o lista, ogni elemento ha una cella di memoria dedicata. Gli sprite in scratch altro non sono che dei dei programmi che vengono eseguiti threads, assieme agli altri e che comunicano tra loro mediante o variabili globali eventi.

Capitolo 2

Architettura di un elaboratore

L’architettura base di un calcolatore è ispirata al modello della macchina di Von Neumann (vedi figura 1.1), ed è composta da alcuni elementi di base quali (Central Processing Unit), CPU e Tutti questi dispositivi sono realizzati unità di I/O, memoria centrale bus di sistema. con adibita a codificare dati ed operazioni a partire da due tecnologia elettronica digitale valori distinti di grandezze fisiche:

• Tensione (V_alta , 5V).
• Tensione (V_bassa , 0V).

Ai quali vengono convenzionalmente associate le due 0 e 1: cifre binarie

• Logica Positiva: V_H ⇔ 1 , V_L ⇔ 0
• Logica Negativa: V_H ⇔ 0 , V_L ⇔ 1

Dati ed operazioni vengono codificati tramite e, poiché la CPU è in grado sequenze di bit di operare soltanto in lavorando direttamente sull’hardware l’utente è aritmetica binaria, costretto ad esprimere i propri comandi al livello della macchina, ossia mediante le sequenze di bit di cui sopra.

2.1 Central Processing Unit

Svolge le elaborazioni e il trasferimento dei dati, in altre parole Essa è esegue i programmi. ottimizzata per lavorare su motivo per cui nel corso degli anni sono state inventate dati singoli, altre processing units specializzate in tipi di dati differenti, come la adatta a lavorare GPU, con o La CPU è composta da:

• Clock.
• Registri.
• ALU.
• Unità di controllo.

2.1.1 Clock

Anche detta fornisce la base dei tempi necessaria a mantenere il frequenza operativa, sin- fra le operazioni, imponendo che l’esecuzione di ogni operazione impieghi un tempo cronismo al massimo uguale al periodo di clock. Ciò vuol dire che, qualora la CPU impiegasse metà pe- riodo di clock per eseguire un’istruzione, sarà comunque costretta ad aspettare un altro mezzo periodo di clock prima di processare l’istruzione successiva, in modo da avere la certezza che quella precedente sia terminata. Negli elaboratori moderni esistono tuttavia delle soluzioni, ad esempio l’introduzione atte a ridurre i tempi "morti" della CPU.

2.1.2 Registri

Sono di memoria usate per memorizzare dati, istruzioni o indirizzi all’interno della locazioni CPU. L’accesso a tali locazioni avviene alla velocità della CPU e ha una latenza bassissima. Sono composti al massimo da poche decine di bit e si dividono in e I generali specializzati. primi sono dei registri che contengono i necessari a compiere una determinata dati intermedi operazione. Per quanto riguarda i secondi, nel dettaglio sono:

• Program Counter (PC): indica l’indirizzo della cella di memoria che contiene la prossima istruzione da eseguire.
• Instruction Register (IR): contiene l’effettiva istruzione da eseguire.
• Registro Indirizzi (RI): contiene l’indirizzo della cella di memoria da selezionare per il trasferimento di un dato dalla memoria alla CPU (lettura) o dalla CPU alla memoria (scrittura).
• Registro Dati Accumulatore (RD): o contiene il dato attualmente in oggetto di elaborazione e il risultato al termine dell’esecuzione.
• Registro Interruzioni (RINT): gestisce gli (o interruzioni), sia hardware interrupt che software.
• Registro dei Flag (FLAG): ogni flag indica la presenza/assenza di una proprietà nell’ultimo risultato generato dalla ALU. Altri bit riassumono lo stato del processore

2.1.3 Arithmetic & Logic Unit

O aritmetiche, logiche e confronti sui dati della memoria centrale ALU, esegue operazioni o dei registri, spesso è molto complessa e sofisticata. Viene attivata da un comando della CU che specifica l’operazione da compiere.

2.1.4 Unità di controllo

Fa sostanzialmente funzionare l’elaboratore, inviando istruzioni alla ALU e riprogram- mandola di volta in volta in modo da farle svolgere adeguatamente il compito assegnatole. Da quando viene acceso ripete lo stesso ciclo / / così articolato: fetch decode execute,

• Fetch: si accede alla prossima istruzione (cella il cui indirizzo è contenuto nella PC) e la si porta dalla memoria centrale, immagazzinandola nel Registro Istruzioni.
• Decode: si il dell’istruzione in base al suo (o codice operativo), decodifica tipo OpCode una stringa di bit che esprime la categoria di operazione da eseguire.
• Execute: si i dati usati dall’istruzione, si negli opportuni individuano trasferiscono registri e si l’istruzione. esegue

Grazie ai registri un sistema è in grado di eseguire più compiti "allo stesso tempo". Salvando in memoria il contenuto di tutti i registri, infatti, è possibile accantonare un processo per passare a svolgerne un altro (salvataggio e poi, ovviamente, è possibile ripristinare lo di contesto) stato di un processo accantonato recuperando dalla memoria il contenuto dei registri sopracitati. Non è proprio esatto dire che i compiti vengono eseguiti contemporaneamente, in quanto il tempo di calcolo del processore viene condiviso da più processi in modo velocissimo, dando quindi solo l’impressione che essi vengano eseguiti allo stesso tempo.

2.2 Unità di I/O

Per consentire lo scambio di dati tra calcolatore e utente si usano delle dei dis- periferiche, positivi esterni al calcolatore (mouse, tastiera, scanner...) collegate ad esso tramite opportune interfacce.