Appunti completi Fondamenti di informatica

Indice C.1

Formato di rappresentazione dei numeri interi

Numeri interi con e senza segno. Overflow in una operazione di somma tra valori codificati come interi senza segno (rapp. in forma posizionale) e in una operazione di somma tra valori codificati come interi con segno (rapp. in complemento a 2). Rappresentazione dei numeri float. Algoritmo delle moltiplicazioni successive. Componenti della CPU del processore MIPS R4000.

C.2

Cos'è una grammatica e come essa definisce un linguaggio. Semantica e sintassi delle espressioni. Puntatori. Array. Istruzioni condizionali e di iterazione. Funzione: dichiarazione, definizione e riferimento. Tecniche di cercare tra i parametri per valore e per riferimento. Stack di sistema. Tempo di vita di una variabile. Visibilità di una dichiarazione.

Indice C.1

Formato di rappresentazione dei numeri interi

Numeri con e senza segno. Overflow in una operazione di somma tra valori codificati come interi senza segno (rapp. in forma posizionale) e in una operazione di somma tra valori codificati come interi con segno (rapp. in complemento a 2). Rappresentazione dei numeri float. Algoritmo delle moltiplicazioni successive. Componenti della CPU del processore MIPS R4000.

C.2

Cos'è una grammatica e come essa definisce un linguaggio. Semantica e sintassi delle espressioni. Puntatori. Array. Istruzioni condizionali e di iterazione. Funzioni: dichiarazione, definizione e riferimento. Tecniche di copia tra i parametri per valore e per riferimento. Stack di sistema. Tempo di vita di una variabile. Visibilità di una dichiarazione.

Struttura di un programma

Dati strutturati

Lista: operazioni, rappresentazione e collegamenti. Rappresentazioni di stringhe di caratteri (libreria standard string).

C.4 Algoritmi

• Algoritmo di ricerca binaria
• Algoritmo di ordinamento sequential-sort
• Algoritmo di ordinamento bubble-sort
• Algoritmo di ordinamento merge-sort
• Algoritmo di ordinamento quick-sort

Teoria Fond. di Informatica Capitolo 1

Formato di rappresentazione dei numeri interi

Formato di rappresentazione dei numeri interi, con e senza segno, del linguaggio C: Il linguaggio C rappresenta i dati secondo tipi; un tipo è caratterizzato dai valori che può rappresentare e dalle operazioni che possono essere eseguite su di essi. Uno dei tipi elementari è il tipo "int" che rappresenta numeri interi con e senza segno.

Interi senza segno

Serve a rappresentare una variabile dichiarata su C come istanza del tipo "unsigned int": unsigned int A; Viene rappresentato su N bit di memoria che codificano il valore in forma posizionale in base 2. La rappresentazione codifica tutti e solo i naturali compresi tra 0 e (2^N-1) inclusi. Il numero di bits N può variare a seconda dell'architettura della macchina; solitamente è 32.

Intero con segno

Serve a rappresentare una variabile dichiarata in C come istanza del tipo "int". int a; Gli interi sono rappresentati su n bit usando una rappresentazione in complemento a 2. In questa codifica nello sviluppo polinomiale il bit più significativo (MSB) ha peso negativo mentre gli altri, come di solito, hanno peso positivo. I valori rappresentati sono i numeri interi da -2^n-1 fino a (2^n-1)-1, dove il minimo si ottiene asserendo solo il MSB ed il massimo si ottiene asserendo tutti i bit tranne il MSB. Il numero codificato è negativo solo se il MSB=1. L'opposto di un numero può essere ottenuto complementando tutti i bit e sommando 1. La rappresentazione in complemento a 2 ha il privilegio di unificare il trattamento di somme e sottrazioni. Oltre a "unsigned" visto nel caso precedente possono essere applicati al tipo "int" altri modificatori: "long": aumenta il numero di byte della codifica (tipicamente 8) "short": diminuisce il numero di byte della codifica (tipicamente 2).

Overflow in una operazione di somma tra valori codificati come interi senza segno

In una operazione di somma può verificarsi un overflow, ovvero il risultato può eccedere la dinamica di rappresentazione. L'overflow è manifestato dalla presenza di un riporto nella somma dei MSB: es: 1111 + 0001 = 10000.

Overflow in una operazione di somma tra valori codificati come interi con segno

In tal caso il riconoscimento dell'overflow è meno diretto. È possibile il manifestarsi di un overflow se e solo se i due addendi hanno lo stesso...