Introduzione algoritmi

0 Introduzione 0.1 L’algoritmo Vogliamo cercare di creare algoritmi, ovvero soluzioni a problemi computazionali che non dipendono dal linguaggio di programmazione. 0.1.1 Definizione Procedura per risolvere un problema in un numero finito di passi (quindi un algoritmo deve finire) 0.1.2 Origine della parola Il nome “algoritmo” deriva da un nome di un matematico persiano dell 800 d.c. Muhammad ibn Musa al-Khwarizmi, che latinizzato diventa algorithmi, quindi i latini hanno creato la parola! ...

4 min Â· Xuanqiang 'Angelo' Huang

Relazioni di Ricorrenza

Iterazione Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica. slide Sostituzione (induzione) slide Analisi della relazione di ricorrenza di fibonacci Si può dimostrare utilizzando l’induzione che una relazione di questo tipo $$ T(n) = \begin{cases} O(1) \\ T(n-1) + T(n-2) + 1 \end{cases} $$Si trova che è $O(2^n), \Omega(2^{n/2})$ Analisi finale. ...

1 min Â· Xuanqiang 'Angelo' Huang

Strutture di dati elementari

3.1 Introduzione 3.1.1 Cosa sono Le strutture di dati si interessano solamente di come memorizzare i dati, non necessariamente va a memorizzare un tipo di dato concreto. Quindi + sul come - sul cosa. 3.1.2 Prototipo e implementazione Avevamo introdotto la differenza fra algoritmo e programma all’inizio del corso, andiamo ora a definire la differenza fra prototipo e implementazione: Prototipo: va a fare una descrizione dei metodi che deve avere una determinata struttura di dati. Lo puoi intendere come una specie di interfaccia. ...

4 min Â· Xuanqiang 'Angelo' Huang