Fondamenti di Informatica

Tipi di errori:

Syntax Errors: errori di sintassi; utilizzo errato del linguaggio di programmazione (es. definire in una funzione un argomento di ingresso che poi non verrà utilizzato; utilizzare una variabile prima di inizializzarla; ecc...) o refuso (es. assenza di virgolette).

Runtime Errors: errori che emergono durante l'esecuzione (es. riferimento di un elemento di un vettore che non esiste o moltiplicare due matrici non moltiplicabili tra loro).

Logical Errors: errori logici ovvero il programma funziona ma porta a risultati errati; più difficili da individuare in quanto il programma si esegue ma il problema sta nella logica in generale o nell'interpretazione che il programmatore ha dato circa la funzione del programma stesso; per individuarli si fanno dei test a campione. (es. per matlab è perché la prima cosa che fa è valutare se x è maggiore di 3; essendo x=-2 3

6 perciò matlab restituisce true)Warning (avvertimento) durante la compilazione di eventuali errori che si stanno commettendo.

Permette di visualizzare a video l’esecuzione di una funzione (utile per individuare eventuali errori).

Alternativamente si possono utilizzare i breakpoint per eseguire una funzione passo per passo e accedere al workspace locale.

Stringhe

Stringa: sequenza di caratteri delimitata da due virgolette; è un array di caratteri (char array) ovvero un vettore o una matrice (se le stringhe, che devono però avere lo stesso numero di caratteri ovvero di colonne, sono su più righe); può contenere lettere, numeri, segni di punteggiatura, spazi, caratteri di controllo. Si può utilizzare su di essa la funzione length o size, ottenerne la trasposta, accedere a un suo componente in una determinata posizione, concatenare più stringhe, convertirne le minuscole in maiuscole e viceversa, rimuoverne gli spazi.

Posizioni in cui inizia tale parola.

String array: sequenza di stringhe delimitate da doppie virgolette; array, ovvero vettore o matrice, di stringhe.

Sottostringa: porzione di una stringa.

Algoritmi di ordinamento

Algoritmi di ordinamento: si occupano di ordinare un insieme di elementi secondo un criterio prestabilito; sono iterativi (cicli) e seguono un preciso criterio di ordinamento basato sul confronto; i più semplici sono quelli che ordinano le sequenze numeriche in ordine crescente e sono di 3 tipi:

- Per selezione (Selection Sort): ad ogni iterazione si seleziona l'elemento più piccolo che viene spostato nella posizione i-esima. Dato il vettore di lunghezza n:

1. Trova il minimo tra gli elementi non ordinati (con i che va da k a n);
2. Sostituisce l'elemento trovato nella posizione i;
3. Incrementa l'indice k;
4. Se k<n ripete dal passo 1;
5. Fine.

- Ad inserimento (Insertion Sort): iniziando dal secondo elemento confronta l'elemento che si trova

nellaposizione k con quelli precedenti già ordinati e lo inserisce di modo che rispetti l’ordine crescente, facendoscalare gli elementi che lo seguiranno verso destra. L’algoritmo:

1. Considera l’elemento k e si individua la sua posizione p tra gli elementi già posizionati (con 1<p<(k-1))
2. Se p<k inserisce l’elemento nella posizione p e sposta gli altri (scorrono verso destra)
3. Incrementa k
4. Se k<=n ripete dal passo 1
5. Finex A bolle (Bubble Sort): confronta gli elementi adiacenti a coppie e il minore tra i due viene posizionato prima.L’eventuale scambio viene registrato in una variabile booleana. L’algoritmo:
6. Confronta i valori nelle posizioni k e k+1
7. Se valore in k+1 è minore di quello in k li scambia e pone scambio = TRUE
8. Se lo scambio è avvenuto incrementa k, ripristina scambio = FALSE e ritorna al passo 1
9. L’algoritmo finisce se tutta la sequenza viene ricontrollata e scambio == FALSE

Il Teorema del Campionamento, formulato da Shannon Nyquist, permette di campionare un segnale in codice binario e renderlo "comprensibile" all'elaboratore.

Un segnale periodico può essere scomposto in una sommatoria infinita di segnali sinusoidali, noti come armoniche, utilizzando la serie di Fourier.

Lo spettro di un segnale rappresenta il dominio della frequenza del segnale e viene ottenuto componendo il segnale nelle sue componenti basilari. Le frequenze delle armoniche, che sono multipli di una frequenza di riferimento, costituiscono la banda del segnale.

La Trasformata di Fourier permette di ricavare lo spettro del segnale a partire dal segnale in funzione del tempo. Se il tempo è discreto, si utilizza la DFT (Discrete Fourier Transform), mentre se si utilizza la FFT (Fast Fourier Transform).

Dato un segnale analogico a tempo continuo e a banda limitata, è possibile rappresentarlo completamente (e eventualmente ricostruirlo) utilizzando un segnale a tempo discreto derivato da esso.

derivato per tramite di un’operazione di campionamento; se la frequenza di campionamento è maggiore o uguale al doppio della banda del segnale allora il segnale è rappresentato esaustivamente dai suoi campioni; grazie ai filtri passa-basso il segnale originale può essere ricostruito.

Filtro passa-basso (prima era analogico, ora è digitale, il che permette di variare più facilmente il filtro): taglia tutti i segnali che hanno una frequenza maggiore di una frequenza fissata detta di taglio.

Quantizzazione: permette di trasformare i segnali analogici in bit; associa ad ogni valore campionato un valore numerico memorizzabile dall’elaboratore che gli si avvicina maggiormente; perciò memorizzando in sequenze di bit un segnale si commette un errore che è tanto più grande quanti meno sono i bit a disposizione.

Il segnale perciò è rappresentato in maniera esaustiva nelle sequenze numeriche a meno di un errore dovuto

Al processo di campionamento e di quantizzazione; esistono convertitori analogico-digitale e digitale-analogico (i secondi permettono ad esempio di creare musica elettronica).

Circuito universale: Analog Signal ADC Digital Signal Processing (microprocessore) DAC Analog Signal

La trasformazione del segnale dipende da un algoritmo.

Microprocessori di diverse categorie:

• Microprocessori di tipo generale (MP): architettura Von Neumann; istruzioni CISC o RISC.
• Microcontrollori (MCU): architettura Von Neumann o Harvard; specializzati per sistemi di controllo digitale; gestione sofisticata input-output tramite porte esterne; sistemi embedded ovvero integrati con il sistema da controllare (es. centralina di un motore termico).
• Digital Signal Processor (DSP): elaborazione di segnali digitali in tempo reale; elaborazione veloce di un numero consistente di operazioni matematiche.

OSS DSP e MCU vengono utilizzati in modo congiunto: MCU si interfaccia col mondo esterno e fa le prime

Elaborazione e il DSP esegue il grosso dei calcoli. Possono avere architettura di Von Neumann o di Harvard:

• Von Neumann: la CPU ha accesso all'unità di memoria in cui sono presenti programmi e dati.
• Harvard: la CPU ha accesso a due distinte unità di memoria, una destinata ai programmi e l'altra ai dati.

Le istruzioni dei microprocessori possono essere:

• CISC = istruzioni complesse.
• RISC = istruzioni semplici implementate (per concentrare la potenza di calcolo sulle operazioni più utilizzate).
• VLIW = istruzioni parallele.

Complessità computazionale

Necessità di stabilire quale algoritmo è il migliore per un determinato funzionamento.

Complessità computazionale: misura oggettiva della bontà/efficienza di un algoritmo, basata su parametri che ne consentano un confronto con altri algoritmi; tiene conto della quantità minima di risorse sufficienti per il calcolo: tempo (complessità temporale) e spazio nella memoria.

(complessità spaziale). Complessità temporale: la misura del tempo impiegato da un compilatore per eseguire l'algoritmo da valutare non è assoluta, in quanto può dipendere da diversi fattori: dimensione e caratteristiche dei dati di ingresso (es. possono richiedere di ripetere più volte un loop), tipo di linguaggio usato (deve o meno compilare), qualità della traduzione in sequenze di bit, velocità dell'elaboratore, tipo di microprocessore e di architettura utilizzati. Per valutare esclusivamente l'efficienza di un algoritmo, si considera il numero delle singole operazioni elementari (aritmetiche, logiche, di confronto, di assegnazione) eseguite dal programma (nello specifico di un solo sottoinsieme di operazioni che ne costituiscono la parte centrale e che sono detti "passi base") in funzione della dimensione n dei dati di ingresso. Noto il numero di passi e la lunghezza n di un vettore di ingresso, assumendo che

Per eseguire un singolo passo si impiega lo stesso tempo, si può calcolare il costo temporale di un determinato algoritmo. La valutazione viene solitamente eseguita nel worst case (ovvero quando i dati di ingresso sono i più sfavorevoli, non solo in termini di dimensioni) e utilizzando l'algebra degli O grandi.

Nel caso di programmi più semplici si può valutare la complessità temporale di un algoritmo in maniera diretta:

• Operazioni elementari: costo temporale 1; se coinvolgono un array, vanno considerate tutte le sotto-operazioni svolte con le singole entrate.
• Sequenza di operazioni elementari: costo temporale dato dalla somma dei singoli costi individuali.
• Loop: costo temporale dato dalla somma dei singoli passi, considerando il ripetersi del ciclo, a cui si aggiunge il costo della verifica della condizione di fine.
• Istruzione condizionale: ha come costo massimo ("worst case") quello del tempo di esecuzione dell'operazione più costosa all'interno del blocco condizionale.