Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
9/03
INTRODUZIONE AL CORSO
ALGORITMO—procedimento che risolve un determinato problema attraverso un numero finito di passi elementari
STRUTTURA DATI—particolare organizzazione delle informazioni
EFFICIENZA—è legata ai modi in cui sono strutturati i dati e ai tempi di esecuzione
CHARLES BABBAGE
- MACCHINA DIFFERENZIALE
- MACCHINA ANALITICA
macchina programmabile per eseguire ogni genere di calcolo
1° calcolatore al mondo
ADA LOVELACE
Collaborò con Babbage per la macchina analitica
avrebbe previsto la capacità del computer di elaborare al di là del calcolo numerico
DEFINIZIONE DI DONALD KNUTH
Tempo di esecuzione di un algoritmo = somma dei costi x frequenza di ogni operazione
PROBLEMA—caratterizzato dai dati, il processo su cui poi un algoritmo opera
Qualunque problema formulato ha un algoritmo che lo risolve? NO! Cauci per esempio "matematical problems"
HALTING PROBLEM
Esiste un algoritmo che prenda un altro algoritmo e un input e riesce a dire se su quel algoritmo e su quel input si diverge oppure no
SCOPI SISTEMA INFORMATICO
immagazzinamento e recupero dell'informazione
Principio di Induzione Aritmetica
∀ intero u < c
Se P è vera per u allora P è vera per u+1
Fasi: tutti gli interi k ≥ c godono della proprietà P
- Passo base: dimostra che c goda di P
- Passo induttivo: assumo che k goda di P e dimostro che anche k+1 gode di P
Somma dei Primi N Numeri
Su = Σ t=1 = u(u+1)/2
Logaritmi
logb x = 4 b -> base x -> argomento
b4 = x
log4 ? log-u ? esistono
μ = log3 (x)
μ = log2 (x)
Proprietà
- logb (xι) = logb x + logb u
- logb (x/ι) = logb x - logb ι
- logb (x-ι) = -ι logb x
- logb (b) = 1
- logb (1) = 0
- logb (bμ) = μ
Proprietà Cambiamento di Base
a > 0 a ≠ 1
logb (x) = loga (x)/loga (b) oppure logb (x) = ln x/ln b
è una costante
1/loga b = c => loga x = c * loga x
Possiamo cambiare la base se nei nostri calcoli le costanti moltiplicative non sono interessanti ai fini del calcolo.
4103
MODULARITÀ E INFORMATION HIDING
MODULO → qualunque cosa che può essere utilizzato per realizzazione di un'astrazione
- può esportare simboli, dati, identificativi
- può importare dati, funzioni, identificativi
- definisce l'unico ambiente di visibilità
Interfaccia e corpo sono separati.
- implementazione
Specificare cosa fa il modulo.
MECCANISMI PER MODULARIZZARE IL CODICE
- compilazione separata
- inclusione testuale
- uso prototipi funzioni
- uso namespace
3 file diversi per ogni codice
- file header → define/includetypedefsvariabili globaliprototipi funzioni
- file ausiliario → codice che implementainterfaccia dei prototipi delle funzioni
- main → chiama le funzioni
INFORMATION HIDING
→ nascondere all'utente quanti più dettagli implementativi possibili.
- L'utente vede solo l'interfaccia ed non gli deve importare del corpo.
INTERFACCIA → deve essere minimale e stabile nel tempo.
Il corpo può cambiare.
LISTE CIRCOLARI CON SENTINELLA
Il primo elemento non è un informazione ma una sentinella. In questo modo il primo elemento della lista non cambia mai.
CREAZIONE LISTA VUOTA
La lista vuota è rappresentata solo dalla sentinella, vale a dire se stessa.
void create_empty (basic_list & list){ cell* aux = new cell; aux -> next = aux; list = aux;}INSERIMENTO IN TESTA
void head_insert (basic_list & list, Data_Type new_value){ cell* aux = new cell; aux -> payload = new_value; cell* tmp = list -> next; list -> next = aux; aux -> next = tmp;}STAMPA ELEMENTI
void print_list (ostream & output_stream, basic_list list){ cell* aux = list -> next; while (aux != list) { write_data (output_stream, aux -> payload); aux = aux -> next; output_stream > u;for(int i = 0; i < u; i++) cout << "cucù";- 1 x C1 +
- u + 1 x C2 +
- u x C3 +
- u x C4 +
- 1 x C5
- Esercizio 3
Quanto costa?
int u;cin >> u;if(u == 2) cout
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
