Riassunto esame Fondamenti di informatica, Prof. Cusano Claudio, libro consigliato Pensare in Python, Allen B. Downey

Def. di computer

Macchina che può essere programmata per eseguire automaticamente operazioni, che elaborano informazioni, tramite dati

Algoritmo:

procedimento di calcolo per la risoluzione di un dato problema

• progettazione / efficienza / strutt. dati / computabilità

(si può calcolare o no?)

Codifica:

consiste nell'assegnare un bit alle alternative.

• Rum.: che associa sequenze di \\ ad insiemi di "".
• lunghezza fissa / lung. variabile

+ flessibili ed efficienti.

dipende dal n° di bit

+ complesso da elaborare

Programma: sequenza di istruzioni che si eseguite, effettuano un calcolo.

L'implementazione algoritmica, ovvero: sono algoritmi in un opportuno linguaggio formale. ₁

• Regole sintattiche stringenti (simboli, struttura)

Ling. naturale: regole "elastiche"

Parsing: analisi strutturale sintattica di un ling. formale.

• Unico significato [ambiguità]
• Più conciso di ling. nat. [ridondanza]
• Significano esattamente ciò che dicono [letteralità]

Rappresentazione dei numeri con segno

"con modulo e segno, si usa il bit più significativo per codificare il segno, i bit restanti codificano il modulo del numero.

• 0 -> pos.
• 1 -> neg.

2

• → n^o medio grandi / precisione indipendente dal 1(x)
• - 0 → pos
• - 1 → neg.
• n^o binario di bit indica l’esponente della base binaria
• bit rimanenti indicano le cifre significative
• (mantissa cifre dopo la 1^a cifra)

Formati principali:

• - semplice precisione (32 bit, 1, segno, esponente, mantissa, 8, 23)
• - doppio precisione (64 bit, ?, 11, 52)
• (16 bit opure 128)

→ differenzia

↑ estiva

L+1023

+127

Tipologie di memorie:

Reg - Ram - Rom

Memoria statica: è alta e circuiti logici latching

Memoria dinamica: condensatori, è bassa.

Memoria gerarchica efficiente tramite:

• Principio località temporale: accedo ad un dato e poco dopo cerca.
• Principio località spaziale: accedo ad un dato ed ai dati vicini.

HIT => se il dato è presente nella cache

MISS => se il dato non è presente, viene copiato dalla RAM nella cache

Operazioni di scrittura:

• Write-through: i dati vengono scritti sia in memoria che nella cache.
• Write-back: linee di cache scritte in memoria solo se rimpiazzate nella cache.

Ricerca Lineare

Per l'analisi della complessità ci sono due casi:

• ricerca con successo: l'elemento cercato si può trovare in qualunque posizione e nel caso peggiore servono n iterazioni del ciclo
• ricerca con fallimento: per rendersi conto dell'assenza dell'elemento cercato occorrono n iterazioni  T(m) = O(m)

In entrambi i casi la complessità in tempo nel caso peggiore è O(n)

Per le ricerche con successo il numero medio di elementi considerati è ⁿ⁺¹/₂, quindi anche la complessità nel caso medio è O(n)