Fondamenti di informatica

Fondamenti di informatica

Giovedì 29 settembre 2022

Cos'è informatica?

O. Hilbert (fine '800) riorganizza la geometria con 20 assiomi.

Proposizione fondamentale per riorganizzare la matematica all'inizio del secolo.

Si riesce a fornire un sistema composto solo da assiomi (conseguenze) per definire tutta l'informatica?

NO! Perché alcune affermazioni non sono vere né false al di là degli assiomi.

È possibile creare una macchina computazionale?

A. Turing ha ideato la macchina di Turing.

Con la risoluzione di alcuni problemi, Turing immaginava un computer immaginario che potesse essere complessizzato con un'infinita memoria.

A. Church - Teoria della complessità.

C. Shannon - Teoria dell'informazione.

"L'informatica non riguarda i computer più di quanto l'astronomia riguarda i telescopi" E.W. Dijkstra.

Informatica

Una scienza che studia l'informazione.

Studia sistematicamente dei processi algoritmici che descrivono e trasformano l'informazione.

Computer

Dispositivo fisico che implementa il funzionamento.

Computer ideale → macchina di Turing.

Tutto ciò che è computabile!

• Macchina che memorizza dati.
• Integra dispositivi.
• Esegue programmi.

"Che bisogno ha una persona di avere un computer a casa?"

(K. Olsen 1977)

Storia

• 2400 a.C. - Abaco.
• 1614 d.C. - Regolo.
• 1642 d.C. - Pascal crea la pascalina.
• 1843 d.C. - Ada Lovelace.
• Programmazione al mondo - Progettò una macchina per fare delle somme.
• Viste le proprie annotazioni, capacità di prevedere il primo programma del mondo.
• 1930 d.C. - Elettronica usata nei progetti elaborazione dati.
• 1940 d.C. - Prime automazioni.
• 1950 d.C. - Primi computer.
• 1962 d.C. - Primo computer elettronico per calcolo traiettorie (militare).
• 1965 d.C. - Primo computer commerciale prodotto anche in Italia da Olivetti.
• 1969 d.C. - Nasce ARPANET, futuro Internet.
• 1971 d.C. - Creato primo microprocessore.
• 1974 d.C. - Primo PC commerciale, successo industriale trasportato in America per.
• 1982 d.C. - Prima stampante laser.
• 1985 d.C. - Primi cellulari.

Fondamenti di informatica Pagina 1

Cos'è l'informatica?

O. Hilbert (fine '800) ristruttura la geometria ... 20 assiomi.

Primo problema: è possibile riorganizzare la matematica solo con assiomi?

Si riesce a costruire un sistema composto solo da assiomi per definire tutta l'informatica?

Alan Turing ha descritto la macchina di Turing.

Una macchina ideale, un modello.

Nel fare questo ha formalizzato.

Computer immaginario.

A. Church Teoria della complessità.

C. Shannon Teoria dell'informazione.

L'informatica non riguarda i computer più di quanto l'astronomia riguardi i telescopi E. W. Dijkstra.

Informatica

Studio sistematico dei processi algoritmici che descrivono e trasformano l'informazione.

Computer

Dispositivo fisico che implementa i funzionamenti della macchina di Turing.

• Macchina che memorizza dati.
• Interagisce con dispositivi.
• Esegue programmi.
• Tutto ciò che è computabile ...

"Che bisogno ha una persona di avere un computer a casa?"

(K. Olsen 1977)

Storia

• 2400 a.C. Abaco.
• 1642 d.C. Regolo.
• 1662 d.C. Pascal crea la pascalina.
• 1843 d.C. Ada Lovelace.
• 1930 d.C. Elettricità usata per attività di elaborazione dati.
• 1940 d.C. Prime automazioni.
• 1950 d.C. Primo computer (calcolo traiettorie balistiche).
• 1963 d.C. Nasce ARPANET il futuro Internet.
• 1971 d.C. Creazione primo microprocessore.
• 1976 d.C. Primo PC commerciale accessibile a privati.
• 1982 d.C. Primo stampante laser.
• 1985 d.C. Primi cellulari.
• 2001 d.C. IPOD.
• 2010 d.C. IPAD.

Cos'è un programma

Insieme di istruzioni elementari che vengano date al computer.

Elevato numero di informazioni a velocità elevatissima.

Cos'è la programmazione

Scrivere dei programmi.

Programmatore = essere biologico che trasforma caffè e pizza in programmi.

Cos'è un algoritmo

Bohm-Jacopini = ogni algoritmo/programma può essere contemporaneo a strutture con 3 algoritmi.

Non può risolvere qualsiasi cosa.

Un computer può risolvere solo problemi risolvibili manualmente.

= Il computer in sé per sé è stupido — esegue solo delle istruzioni.

Algoritmi = descrizione di un metodo di risoluzione di un problema che deriva da...

Al-Khwarizmi = step by step.

• Descrizione dettagliata.
• Pezzettini → eseguibile.
• Univoco = un solo significato.
• Deterministico = conclude con un risultato passo a passo.

Serve un linguaggio per creare un algoritmo leggibile dal computer.

• Iniziò-line.
• True/false.
• Decisione.
• Arco di flusso del controllo.

Uomo = base 10.

Macchina = base 2.

L'uomo comprende una macchina se lavora in base 2 o 2ⁿ.

A cosa servono gli algoritmi

Necessari per risolvere un problema (in generale).

Il modello di John Von Neumann (1945)

Architettura composta da 4 blocchi in comunicazione attraverso un bus.

• Unità logica e aritmetica.
• Unità di controllo.
• Memoria primaria.
• Memoria secondaria.
• Memoria di massa.
• Unità di Input/Output.
• Bus.
• CPU.
• Memoria principale RAM.
• Memoria secondaria.
• Dispositivi Input/Output.

Il bus

Bus dati, bus indirizzi bus dei segnali di controllo.

Vantaggi

• Semplicità (unico linea = meno costi).
• Estensibilità (facile aggiungere elementi).
• Standardizzabilità (regole prese per comunicazione tra dispositivi diversi).

Svantaggi

Lentezza.

Svantaggi

• Lentezza.
• Limitata capacità.
• Sovraccarico del processore.

CPU control processing unit

• Esegue le istruzioni dei programmi.
• Elaborare dati con la sua ALU (Arithmetic-logic Unit).
• Prende dati da dispositivi e ne restituisce altri.
• Costituito dal chip più collegamenti con l'esterno.
• Costituito del chip più collegamenti interni wire.

ALU —> Unit di calcolo.

CPU.

CLOCK — scandisce i tempi di lavoro (es 3 GHz) 3•10⁹ cicli/s.

REGISTRI FETCH-DECODE EXECUTE —> La posizione dell'istruzione aumenta di 1 ad ogni fine ciclo, a meno di programmi che impongano un ciclo.

• Legge le istruzioni.
• Decodifica.
• Esegue le istruzioni.

Utilizza per eseguire le istruzioni i registri.

PARALLELISMO es cpu à 8 core —> 8 processori in parallelo.

Collaborazione tra CPU per eseguire 2 istruzioni al posto di una ad ogni clock.

• Architetture pipe line.
• Multi processor / Multi calcolatori.
• Memoria comune.
• Memorie private.

Memorie del computer

Divise in celle (ognuna ha un indirizzo).

n bit = 2ⁿ combinazioni diverse.

BIT = Binary digit.

1 byte = 2⁸ combinazioni diverse.

BIT = Binary digit.

• 8 bit = 1 byte.
• 1 KB = 1•10³ byte.
• 1 MB = 1•10⁶ byte.
• 1 GB = 1•10⁹ byte.

Memoria primaria (o centrale)

RAM.

Random access memory.

ROM.

Read only memory.

Spazio di indirizzamento

Processore deve definire dove vuole mettere l'informazione.

INDIRIZZO —> NUMERO = SEQUENZA DI BIT.

Lunghezza fissata (oggi 64 bit).

Cache

Se accede ad A, gli accessi successivi saranno nelle vicinanze del primo accesso ad A.

CPU prende dati che non utilizza immediatamente.

CPU prende dati da cache e non accede direttamente alla memory.

Cache non reindirizza e non rimanda ai nuovi indirizzi ciclo macchina ma evolve.

RAM — ROM — contiene le informazioni necessarie al programma ad accesso rapido per l’avvio del computer.

BIOS — Firmware.

Usato per inizializzare (hardware preinstallato).

CPU prende dati dalla ram oltre le necessità (+5 posizioni es).

A cosa serve programmare

• Problema da risolvere.
• Algoritmo che risolve il problema.
• Rappresentazione dell'algoritmo mediante pseudo-codifica o flow chart.
• Traduzione dell'algoritmo in un programma.
• Esecuzione di programma e soluzione di problema.

Packaging

Gruppo di chip (8/16).

Es SIM/DIMM.

Chipset

Mette in comunicazione la CPU con il resto dei componenti.

Memoria secondaria (o di massa)

• HDD.
• SSD.
• USB.
• Floppy-disk.

Dati prelevati quanto necessari, posti nella RAM e riposti al loro indirizzo una volta usati.

CPU.

Registri Cache RAM/ROM memoria secondaria posti.

Gerarchia memorie.

Tracce e settori del disco

Una traccia è un frammento (pro)campione “tremoto” settori di varie dimensioni.

1.5% spazio per bubble in caso di errori: o gap o preamboli.

Nastri magnetici

Per fare backup.

Floppy disk

3 1/4.

Dimensioni del disco in pollici.

1,44 MB.

Dischi ottici

1 sola traccia a forma di spirale.

COMPACT DISC (CD).

Dispositivi di ingresso e uscita

Input/Output.

Programma controlla la periferica e riceve l'informazione di errore.

INTERRUPT carattere che termina il ciclo di lettura.

DMA direct memory access (senza passare per la CPU).

Le porte

USB unified serial bus (universal sign).

Plug and play.

U.S.B. 3.2 20 Gbit/s.

Fondamenti di Informatica Pagina 4.

Le porte

USB 3.2 20 Gbit/s.

Porta standard - molte porte sono state rimpiazzate dalle USB.

Input

• Mouse.
• Tastiere.
• Scanner (300 DPI buona scansione).

Output

• Monitor (Risoluzione/Frequenza/Dimensioni/Tipologie/pixel inch).
• Stampanti (aghi/getto d'inchiostro/laser).
• Scheda audio.

Stampanti 3D.

LES LED colori (quasi albe).

Scheda madre

Scheda madre - IC (integrated circuits) = circuiti microscopici formati da un processo chimico-fisico.

Montengano migliaia transistor.

• ATX.
• Micro-ATX.
• Mini-ITX.

Collega le componenti del computer.

Informazioni nei calcolatori

Rappresentazione binaria delle informazioni.

0, 1 → 2 livelli di tensione.

(0−g) → g livelli di tensione.

I numeri periodici non lo sono in binario.

Alcuni numeri con periodici in binario sono periodici in decimale.

Numeri in N / Z / R / caratteri

Numeri caratteri Unicode.

e.g. il 65 perch.

Problemi

• Noi usiamo lettere e numeri.
• I numeri sono infiniti.
• 1 pc capisce 0-1.
• I pc hanno bit limitati per rappresentare i numeri.

Numeri in base b

MIN MAX.

Base x.

d_o e 0 a x -1.

num =

Numeri decimali

4, 3, 2 = 4 · 10² + 3 · 10¹ + 2 · 10⁰.

7 3 6 = 7 · 10² + 3 · 10¹ + 6 · 10⁰.

Numeri binari

a, b, c = 0² · 2² + b · 2¹ + c · 2⁰.

(4, 10, 1)₁₀ = 4 · 2² + 1 · 2¹ + 0 · 2⁰ = 4₁₀.

(5)₁₀ = 1.0 · 2²₍₄₎.

(110)₂ = 1 · 2₂ + 1 · 2¹ + 0 · 2⁰ = 4 + 2 + 0.

Base binaria - base decimale

1, 1, 1, 1 = 1 · 2³ + 1 · 2² + 1 · 2¹ + 1 · 2⁰.

Base decimale base binaria

a, b, c, d, e.

Parte intera (a, b) parte frazionaria (c, d, e).

Parte binaria integrale parte binaria frazionaria.

Numeri in un'altra base

Conversione parte intera.

• Divido per 2.
• Diviso il resto.
• Ripeto.
• Controllo.
• (Fino a che il quoziente non è 0).
• Scrivo il numero con la sequenza di resti a partire dall'ultimo.

375₂ 1 11000 20192 traduzioni differenti.

Guardando si comprende.

Ma facendo che si impara.

Conversione parte frazionaria

Moltiplico per 2.

Sottraggi i dal prodotto se è maggiore di 1.

Fondamenti di informatica Pagina 6.

1. Moltiplico per 2.
2. Sottraggo 1 dal prodotto se è maggiore di 1.
3. Ripeto 2.
4. Ripeto 2.
5. Continuo fino a che non ottengo 0 o qualcosa di già ottenuto prima.
6. Scrivo il numero con la sequenza dei decimali in ordine corretto (escludendo l'ultimo valore) per i periodici, è periodico dal valore dopo il 1^o valore ripetuto.

0,35 → 2 → 0,7.

0,7 → 2 → 1,4.

0,4 → 2 → 0,8.

0,8 → 2 → 1,6.

0,6 → 2 → 1,2.

0,2 → 2 → 0,4.

0,40625 → 2 → 0,81250.

0,40625 → 2 → 0,97850.

0,97850 → 2 → 1,56250.

0,56250 → 2 → 1,1250.

0,1250 → 2 → 2,50.

0,50 → 2 → 2.

1,2 → 2.

Quanti elementi?

n bit_{[0, 2ⁿ-1]} ∩ ℤ.

n = 8 → _{[0, 2⁸-1]} = 256 numeri.

2⁸ cifre binarie → 256 numeri.

0 = 0 0 0 0 0 0 0 0.

255 = 1 1 1 1 1 1 1 1.

Problema

Allora altra soluzione.

Rappr. senza spazi.

Estremamente difficile fare le somme.

GRAVE.

Considero i complementi:

Intervallo di rappresentazione in complemento a 2

Dipende dal numero di bit a disposizione.

[_{-1, 1^k]}.

_{[-2^n-1, 2^n-1-1]}.

Calcolare -13 in complemento a 2

-13.

Calcolare -13 in complemento a 2.

+13 = 00001101.

-13 = 11110011.

Inversione complemento a 2 (1 + inversione -13).

Overflow Quando il risultato è oltre il limite di bit disponibili.

E = 2^n-1 - 1.

Z = 2^-n.

Rappresentazione in virgola mobile

1024,3 = 1024 x 10³.

Mantissa esponente.

Standard IEEE 754 Internazionale 2 formati: 32 bit / 64 bit segno esponente mantissa.

Precisione 15 decimali.

32 bit

Esponente sarà e + 127.

Per partire da 0.

Numero + piccolo 1,8 x 10^-38.

Numero + grande 3,4 x 10³⁸.

64 bit

Maggiore precisione.

Più numeri.

Rappresentazione esadecimale

16 cifre 0, 1, 2, ..., 8, 9, A, B, C, D, E, F.

0111 0101.

Lettura numero.

7 5.

Rappresentazione ottale

Rappresentazione ottale.

Prende a gruppi di 3 gli 1/0.

Rappresentazione caratteri

UNICODE: 16 bit x 1 carattere universale 65.536 caratteri totali.

ASCII American standard code for information interchange.

Sottinsieme di UNICODE - 128 caratteri.

Traduce i simboli in numeri.

• Numeri interi.
• Complementazione a 2.
• Numeri in virgola mobile.
• Esadecimale/ottale.
• Carattere.

Confrontare numeri in virgola mobile

r = √2 calcolato in double in java è un numero arrotondato.

Quindi se r² - 2 ≠ 0.

x₁ ≠ x₂ se la differenza tra loro è più piccola dell'errore di misurazione.

CONFRONTARE NUMERI IN VIRGOLA MOBILE.

ε = errore minimo delle misure in double.

|x - y| Lo permette di essere + precisi.

Es. x, y grandi → lo scarto diventa + grande perché con numeri grandi i parte + piccola conta poco.

public class Numeri { public static boolean approssEqual(double x, double y) { final double EPSILON = 1E-14; double myMax = Math.max(Math.abs(x), Math.abs(y)); return Math.abs(x - y)