Appunti completi con esercizi

Informatica

Informatica: scienza che studia la rappresentazione e l'elaborazione (automatica) di informazioni. Da fatto/concetto interpretato o elaborato da un essere umano o da uno strumento automatico.

Elaborazione automatica

Insieme di regole (procedimenti, programmi) per una macchina automatica. Da un insieme di informazioni iniziali, la macchina esegue le regole per ottenere un insieme di informazioni finali. Esempio: calcolo dell'area di un rettangolo.

Area = b x h

Algoritmo

Procedimento, insieme di regole, procedimento matematico per la soluzione di un problema. Un algoritmo è un insieme finito di azioni (passi di elaborazione) che risolve in modo automatico un problema.

Algoritmi deterministici

Ad esempio: Θ (n)

Come si rappresenta un algoritmo: Area = b x h è un algoritmo.

Linguaggio di descrizione degli algoritmi

Deve essere capito dalla macchina che lo esegue.

Modello di Von Neumann del 1945

Informatica: scienza che studia la rappresentazione e l'elaborazione (automatica) di informazioni. Informazione: fatto/concetto interpretato e elaborato da un essere umano o da uno strumento automatico.

Elaborazione automatica: insieme di regole (procedimenti, programmi) per una macchina automatica. Da un insieme di informazioni iniziali esegue le regole per ottenere un insieme di informazioni finali. Esempio: calcolo dell'area di un rettangolo.

Area = b . h

Programma

Schema di funzionamento dell'unità centrale:

• FETCH → reperire l'istruzione prossima in memoria
• DECODE → capire cosa significa l'operazione
• EXECUTE → esecuzione dei passi necessari per l'operazione (ci sono dei passi elementari)

La terna di operazioni è un ciclo che dura fino a che il PC è acceso.

Linguaggio dei diagrammi di flusso

Descrivere gli algoritmi, operazioni di Input/Output, operazioni logico-aritmetiche di elaborazione, operazione di selezione.

Problema: calcolare il massimo di due numeri

Dati 2 numeri interi a e b, calcolare il massimo. a=3, b=6

1. Acquisire valori di a e b
2. Se a > b il max è a
3. Se a < b il max è b

Problema: calcolare il massimo di tre numeri

Dati: 3 numeri interi, a, b, e c calcolare il massimo.

1. Inizio
2. Leggi a, b
3. Se a > b stampa a
4. Se a > c stampa a
5. Se b > c stampa b
6. Stampa c
7. Stop

Esercizio: diagramma di flusso per calcolare il mediano tra tre numeri

1. Inizio
2. Leggi a, b, c
3. Se a < c
4. Se b < c stampa c (mediano)
5. Se a < b stampa a (mediano)
6. Stampa b (mediano)
7. Stop

Problema: calcolare il massimo comune divisore (MCD)

Dati 2 numeri n e m, calcolare il MCD(t).

n mod t = 0, m mod t = 0, ∃ a₁ ∈ ℕ, n = a₁ t, m = a₂ t, t ≤ min { n, m }, t = ncd ( m, n )

1. Se n = m → t = m = n
2. Se n > m → t = ncd ( n - m, m )
3. Se m > n → t = ncd ( n, m - n )

Algoritmo di Euclide

Problema: data una sequenza di numeri interi positivi (di lunghezza arbitraria) terminata dal numero ∅, calcolare il massimo.

Ipotesi: il valore massimo di una sequenza senza elementi è ∅.

Calcolatori digitali

I calcolatori sono DIGITALI: rappresentazione binaria dell'informazione (0,1) - CODIFICA

Esempio: 5₁₀ → 101₂

15 | 7 | 13 | 11 | 10 v

15₁₀ → 1110₂

1 centinaio + 1 decina = 5 unità

15₁₀ → 1.10² + 1.10 + 5.10⁰ → 11001₂ 1.2⁴ + 1.2² + 0.2¹ + 1.2⁰

Unità di misura della memoria

• 8 bit → 1 byte
• 16 bit → 2¹⁶
• 32 bit → word 4 byte
• 64 bit → 8 byte
• 0 - 255
• 0 - 65535
• 0 - 10⁹
• 0 - 18.10¹⁸

Esempio: 1 2 3 4 5 0 1 2 3 4 5 10³ Memoria 4 byte