Esame parte teorica - Fondamenti di informatica, prof. Cusano

Teoria

Numeri

> Grande numero con k cifre —> base^k-1

• Range modulo e segno: [-base^k-1+1, base^k-1]
• Range C1: [-base^k-1+1, base^k-1-1]
• Range C2: [-base^k-1+1, base^k-1-1]

All'ampio intervallo di valori

Complessità Algoritmi

• Selection Sort Θ(n²)
• Insertion Sort Θ(n²)
• Bubble Sort Θ(n²)
• Merge Sort Θ(n log n)
• Quick Sort O(n²)

Ultimo elemento O(n)

Dimensione a complessità Θ, per inserimento e l'inserimento in testa

Complessità in Tempo e Spazio

Numero max celle coinvolgimento.

Architettura Von-Neumann

CPU

• Decodifica (istruzioni coordinate e dette componendi). Uunità logico aritmetica
• Uunità di controllo

Holaria centrale ≠ holaria secondaria

La periferia dei dati

Holaria cache ha funzione di accelerare accesso alla memoria

Codifica Unicode per caratteri testuali

10 log n

Algoritmo stabile quando mantiene ordine relativa tra elementi equivalenti

Algoritmo escluso = nodo, canello di catostenza = individuo n° figli

Nodi interni hanno essottimeente due figli

Pratica

Tabelle Conversione

• Come ottenere dominio sempre
  • Da base N a C2:
  • Numero₁₀ ➔ Numero₀₂ (inverte bit se negativo e somma +1)
  • Da HS a C2:
  • Se HS positivo ➔ conforme a C2
  • Se HS negativo ➔ 10^bit vuote, restanti bit C1 infine sommo -1
• N₁₀
  • Se decimale positivo ➔ porto a binario HS e C2 (10^bit 2⁸)
  • Da HS negativo a 10 ➔ 10^bit segno resto il modulo negativo

Algoritmi di Ordinamento

• Insertion Sort:
  • Passo 1 confronta secondo elemento col primo e posiziona
  • terzo elemento con i primi due ...
• Selection Sort:
  • Passo 1 elemento più piccolo posizione 1 scambiandolo con elemento
  • Passo 2 secondo più piccolo posizione 2 ...
• Bubble Sort:
  • Primo con secondo elemento; riscrivo; secondo con terzo; riscrivo;
  • così via fino a fine vettore ➔ rinito passo 1 terminato il vettore

Algebra di Boole

AND Proprietà

• x · 0 = 0
• x · 1 = x
• x · x = x

OR Proprietà

• x + 0 = x
• x + 1 = 1
• x + x = x

NOT Proprietà

• x · x' = 0
• x + x' = 1

XOR Proprietà

• x ⊕ x = 0
• x ⊕ 0 = x
• x ⊕ 1 = x'
• x ⊕ y = x' y + x y'

Altre Proprietà

• Distribuitiva:
  • x · (y + z) = (x · y) + (x · z)
  • x + (y · z) = (x + y) · (x + z)
• Associativo:
  • x + x = x
  • (x + x) = (x)
• Assorbimento:
  • x · (x + y)' = x
  • x · (x' + y)' = x · y
• De Morgan:
  • x' y' = (x + y)'
  • x'y = x'y'

Fusione:

• x · y + x' · y = x
• (x + y) · x' + y' = x · y

DISPOSITIVI DI MEMORIZZAZIONE

• MEMORIA STATICA
• MEMORIA DINAMICA
• MEMORIA RAM
• MEMORIA SECONDARIA

PRESTAZIONI:

• 10^-15 RAM STATICA
• 10^-9 RAM DINAMICA
• 10^-6 DISCO MAGNETICO
• 10^-3 NASTRO MAGNETICO

MEMORIA CENTRALE / MEMORIA SEC. LA PERSISTENZA DEI DATI

FUNZIONE: ACCESSO, ACCESSO ALLA MEMORIA

ALGORITMI

DIAGRAMMI DI FLUSSO

• TERMINAZIONE
• ELABORAZIONE
• DECISIONE
• INPUT/OUTPUT

PROGRAMMAZIONE STRUTTURATA

STRUTTURE DI CONTROLLO

• SEQUENZA
• SELEZIONE
• ITERAZIONE

BLOCCO "IF-THEN-ELSE"

LOOP "DO-WHILE"

CODIFICA DELL'INFORMAZIONE NEGLI ELABORATORI

• CODICE ASCII
• UNICODE

IMMAGINI

INFORMAZIONI VISUALI

Risoluzione Esercizi Esame

• Esercizi sulle Conversioni

Calcolo espressioni contenenti da base 10 a complemento a due usando numero bit specificato per il complemento a due.

Ricordo il passaggio più rapido da decimale a complemento a due:

numero₁₀ → numero₂ (inverto bit segno e sommando 1)

(-5)₁₀ + (2)₁₀ = (11011)_c2 + (00010)_c2 =

A questo punto siamo in questa situazione:

(-5)₁₀ + (2)₁₀ → (11011)_c1 + (00010)_c2 =

Semmai sapessi quando fare le

Conversione da modulo e segno a complemento a due con bit specificati

Se il numero in modulo e segno è positivo (primo bit 0) rimane uguale; dunque allo stesso modo nel caso del complemento a due:

(000110)_MS = (000110)_c2

(010100)_MS = (010100)_c2

Nel caso di primo bit negativo (1) modulo e segno:

(111001)_MS = (000110 + 1 = (---001)_c2

Tabella con tutte le conversioni possibili

Tabella tipo 1

Tabella tipo 2

Tabella tipo 1 Esempio:

29

Step 1: Trovo il numero binario

Step 2: Trovo il numero binario

Step 3: Trovo (N1)₂ e (N16)

2 3 19

Esercizio di esame con ragionamento simile

#include <stdio.h>

1. int f (int x)
   • return x * (x + 1) / 2

void g (int d + u, int m + v)

• int k;
• k = f(u, v);
• v = f(k);

int main()

• int c;
• int b = 3;
• int a = 7;
• c = 8;
• c = f(a);
• printf(c / d % d / a fin, b, b, c);
• g(b, c, a); Questo istruzione richiamo seconda funzione
• printf(c / d / % d / a fin, ab, b, 2bc);
• return 0;

Su nessuna istruzione

1. 3 3 3
2. 3 2

Esempio con ciclo

#include <stdio.h>

1. int f (int x)
   • int z = a;
   • while (y = 20)
   • y = x;
   • y = a;
   • return z;

void g (int d + u, int m + v)

• a = f(u, a, v);
• b = f(a, v + m);

int main()

• int c = 3;
• int b = 2;
• int a = 8;
• c = 8;
• c = f(c(a), b, b);
• printf(c / d % d = a l, b, b, c);
• g(c, 8, c); Questo istruzione richiamo seconda funzione
• printf(c / d % d / a l, b, b, c);
• return 0;

Non apposita suo

1. 12 12 12
2. 12