Fondamenti di Informatica

ALGORITMO

Si definisce algoritmo una sequenza di azioni che trasformi i dati iniziali in un numero finito di passi,

elementari e non ambigui, per giungere al risultato finale. Questa sequenza di azioni è valida per un

insieme di dati iniziali ben definito e può essere eseguita da un opportuno esecutore.

PROPRIETÀ DEGLI ALGORITMI

- NON-AMBIGUITÀ: ogni azione deve essere univocamente interpretabile dall’esecutore;

- ESEGUIBILITÀ: ogni azione deve essere eseguibile in un tempo finito parte dell’esecutore

dell’algoritmo;

- FINITEZZA: per ogni insieme di dati di ingresso, il numero totale di azioni da eseguire deve essere

finito;

- EFFICACIA: l’algoritmo deve effettivamente risolvere il problema per il quale è stato scritto

qualsiasi sia una sua possibile istanza;

- EFFICIENZA: l’algoritmo deve risolvere il problema utilizzando al meglio le risorse a disposizione.

ISTANZA

Un istanza non è altro che un dato di input utile all’algoritmo per risolvere il problema.

COMPUTER O ELABORATORE

Strumento programmabile per rappresentare, memorizzare ed elaborare informazioni che si

compone di hardware e software.

- HARDWARE: la struttura fisica del calcolatore, costituita da componenti elettronici ed

elettromeccanici;

- SOFTWARE: l’insieme dei programmi che consentono all’hardware di svolgere dei compiti utili.

RISOLUZIONE DI PROBLEMI CON L’AUSILIO DEL CALCOLATORE

- L’elaboratore è una macchina in grado di eseguire azioni elementari su dati;

- L’esecuzione delle azioni elementari è richiesta all’elaboratore tramite comandi chiamati istruzioni;

- Le istruzioni sono espresso attraverso frasi di un opportuno linguaggio di programmazione;

- Un programma è la formulazione testuale di un algoritmo in un linguaggio di programmazione.

Appunti di Fondamenti di Informatica

FUNZIONI DI UN CALCOLATORE

- Elaborazione;

- Memorizzazione;

- Trasferimento;

- Controllo;

FUNZIONE ELABORAZIONE

L’ elaborazione è la funzione svolta dall’unità aritmetico-logica, nonché componente dell’unità

centrale di elaborazione (CPU). Le operazioni elementari di elaborazione sono, infatti, le istruzioni del

linguaggio macchina:

- operazioni aritmetiche;

- operazioni di confronto;

- operazioni booleane;

- altre operazioni;

Un calcolatore sa svolgere poche tipologie di operazioni elementari ma in modo molto efficiente.

FUNZIONE MEMORIZZAZIONE

La memorizzazione è la funzione svolta dalla memoria centrale che contiene dati e programmi per la

loro elaborazione e che svolge due operazioni:

- scrittura, ovvero, memorizzazione di un valore in un byte/word;

- lettura, ovvero, accesso al valore memorizzato in un byte/word;

La memoria centrale, infatti, è organizzata in celle o bit; gruppi di 8 bit formano un byte; un gruppo

di byte, invece, identifica un word.

FUNZIONE TRASFERIMENTO

Il trasferimento è la funzione svolta da un bus, ovvero un canale di comunicazione. Questa funzione

permette lo scambio di informazioni tra le varie componenti di un calcolatore, nonché il trasferimenti

di dati e di informazioni di controllo.

È possibile svolgere questa funzione collegando ciascun componente l’uno all’altro, ma

naturalmente l’utilizzo del bus favorisce la modularità e l’espandibilità del calcolatore.

FUNZIONE CONTROLLO

Il controllo è la funzione svolta da un unità di controllo, che è un componente dell’unità centrale di

elaborazione. Il controllo consiste nel coordinamento dell’esecuzione temporale delle operazioni,

infatti la CU coordina il flusso di dati tra il processore e gli altri componenti del calcolatore leggendo

(nella fase Fetch) ed eseguendo (nella fase Execute) le istruzioni nella memoria centrale.

RAPPRESENTAZIONE DELL’INFORMAZIONE IN UN CALCOLATORE

All’interno di un calcolatore l’unità di informazione è il bit, infatti, ogni informazione viene trasformata

in una sequenza di bit, ovvero in codice binario. Il codice binario è rappresentato tramite una

sequenza di 0 ed 1 che rappresentano due diverse tensioni elettriche (high and low). Nel contesto

della programmazione per codice binario si intende un codice eseguibile da un processore, nonché

linguaggio macchina.

ALGORITMI DI RICERCA

Data una sequenza di elementi, che può essere rappresentata attraverso l’utilizzo di un array, si può

verificare se un elemento fa parte o no della sequenza data attraverso un algoritmo.

A seconda dell’ordine della sequenza si possono utilizzare due tipi di ricerca:

- ricerca lineare o sequenziale, se la sequenza di elementi non è ordinata;

- Ricerca binaria, se la sequenza di elementi è ordinata.

Appunti di Fondamenti di Informatica

RICERCA LINEARE

Nell’algoritmo di ricerca lineare gli elementi dell’array vengono analizzati in sequenza e vengono

confrontati con l’elemento ricercato. Quando si trova un elemento uguale a quello ricercato

l’algoritmo di ricerca termina.

ALGORITMI DI ORDINAMENTO

Esistono vari tipi di algoritmo di ordinamento che ricevono in input una sequenza non ordinata di

elementi e restituiscono la sequenza ordinata. Ogni tipo di algoritmo utilizza un metodo diverso per

ordinare una sequenza di elementi; alla fine tutti generano lo stesso risultato ma ovviamente alcuni si

rivelano più efficienti di altri.

SELECTION SORT

L’algoritmo di selezione (Selection Sort) effettua l’ordinamento andando a trovare l’elemento minore

della sequenza per portarlo nella posizione iniziale, e l’elemento in posizione iniziale nella posizione

occupata dal valore minore. L’algoritmo effettua lo stesso procedimento per ogni iterazione fino ad

n-1, quando la sequenza risulta ordinata.

INSERTION SORT

L’algoritmo per inserimento (Insertion Sort) effettua l’ordinamento di una sequenza andando a

considerare gli elementi uno per volta. Questo tipo di algoritmo va a trovare la posizione in cui deve

essere posto l’elemento x e di conseguenza sposta di un posto a destra ogni elemento che risulta

essere maggiore di x. La posizione finale di inserimento sarà quella a destra del primo elemento non

maggiore di x.

BUBBLE SORT

L’algoritmo a bolle (Bubble Sort) effettua l’ordinamento andando a realizzare successive scansioni

della sequenza di elementi sino all’ordinamento. In ciascuna scansione si confrontano coppie di

elementi consecutivi scambiandoli immediatamente se non rispettano la relazione d’ordine.

MERGE SORT

L’algoritmo di fusione (Merge Sort) effettua l’ordinamento di una sequenza di elementi

suddividendola in due parti, la prima contenente i primi n/2 e la seconda contenente i rimanenti.

A questo punto si ordinano ricorsivamente le due sottosequenze e quindi la sequenza complessiva

ordinata sarà data dalla fusione delle due precedenti.

COMPLESSITÀ DEGLI ALGORITMI

La complessità (o efficienza) di un algoritmo può essere espressa come:

- complessità temporale o computazionale, che mira a caratterizzare il tempo di esecuzione

dell’algoritmo al variare della dimensione dei dati;

- complessità spaziale, che valuta l’ingombro di memoria richiesto dai dati dell’algoritmo, sempre al

variare della numerosità dei dati.

ANALISI DI COMPLESSITÀ

L’analisi degli algoritmi è indipendente sia dalla macchina (computer) che dal linguaggio di

programmazione. Gli strumenti che si utilizzano per l’analisi della complessità sono essenzialmente

due:

- RAM Model;

- Analisi asintotica del caso peggiore.

Appunti di Fondamenti di Informatica

RAM MODEL

Il modello RAM permette di studiare la complessità di un algoritmo su un’ipotetica macchina in cui

ogni operazione semplice richiede esattamente un’unità di tempo. Misurare il tempo di esecuzione

sotto queste ipotesi significa, dunque, contare il numero di istruzioni eseguite dall’algoritmo prima di

raggiungere la soluzione.

ANALISI ASINTOTICA

L’analisi asintotica della complessità degli algoritmi permette di descrivere in modo approssimativo

la complessità senza tener conto dei dati input e delle costanti.

- CASO PEGGIORE: descrive il numero massimo di passo richiesti dall’algoritmo per arrivare alla

soluzione, dunque ci si concentra sulle istanze più difficili da risolvere;

- CASO MEDIO: descrive il numero di passi che mediamente l’algoritmo impiega per risolvere il

problema;

- CASO MIGLIORE: descrive il numero minimo di passi richiesti dall’algoritmo per risolvere il

problema e ci si concentra sulle istanze più semplici da risolvere.

Spesso definire una funzione esatta della complessità di un algoritmo è troppo complicato, per

questo motivo si utilizza la notazione di O-grande. La notazione O-grande permette di analizzare il

comportamento asintotico dell’algoritmo in relazione alla dimensione dell’input (n), al posto di

definirne il numero di passi richiesti con una funzione esatta.

NOTAZIONE O-GRANDE

Una funzione f(n) = O(g(n)) (ovvero, dell’ordine di g) se esistono due costanti positive c ed n’ tali che

f(n) ≤ c*g(n).

> n’, La complessità di un algoritmo, misurata in termini di una data risorsa, è O(g)

∀n

se la quantità di risorsa richiesta per l’esecuzione dell’algoritmo è O(g). In questo caso si parla di

Upper Bound (Limite Superiore) di un algoritmo.

OPERATORE Ω GRANDE f(n) ≥ c*g(n).

Una funzione f(n) = Ω(g(n)) se esistono due costanti positive c ed n’ tali che > n’, In

∀n

questo caso si parla di un Lower Bound (Limite Inferiore) di un algoritmo.

OPERATORE Θ GRANDE

Una funzione f(n) = Θ(g(n)) se esistono tre costanti positive c , c ed n’ tali che > n’,

∀n

1 2

*g(n) ≤ f(n) ≤ *g(n).

c c In questo caso si parla di limite stretto di un algoritmo.

2 1

SISTEMA OPERATIVO

Un sistema operativo è una base sulla quale è possibile scrivere programmi applicativi le cui funzioni

sono:

- ESECUZIONE DI APPLICAZIONI;

- ACCESSO A DISPOSITIVI DI I/O;

- ARCHIVIAZIONE DI DATI E PROGRAMMI;

- CONTROLLO DI ACCESSO;

- CONTABILIZZAZIONE;

- GESTIONE DI MALFUNZIONAMENTI.

Il sistema operativo fornisce all’utente un’interfaccia conveniente da cui poter controllare e gestire

tutte le funzioni del calcolatore in modo efficiente operando al di sopra di hardware e firmware.

SOFTWARE DI BASE ED APPLICATIVO

Il software di base permette una più semplice interazione con le componenti (CPU, memorie,

periferiche, …). Il software applicativo mostra all’uten