Algoritmi e strutture dati

Revisionato il 23/07/2026

di Mac00

Publisher

Vota

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Appunti di algoritmi e strutture dati basati su appunti personali del publisher presi alle lezioni della prof. Mascardi, dell’università degli Studi di Genova - Unige, …

Esame Algoritmi e strutture dati

Facoltà Scienze matematiche fisiche e naturali

Dal corso del Prof. Mascardi Viviana

Università Università degli studi di Genova

A.A. 2020-2021

77 pagine

Appunto

Scarica

Estratto del documento

9/03 Introduzione al corso

Algoritmo, struttura dati ed efficienza

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° computer al mondo.
Creare tabelle ai polinomi utilizzando "il metodo delle differenze".
Fu solo progettata.

Ada Lovelace

Ada Lovelace collaborò con Babbage per la macchina analitica.

Aveva previsto la capacità dei computer di andare 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 e Halting problem

Problema → caratterizzato da dati in ingresso su cui poi un algoritmo opera.

Qualunque problema formulabile ha un algoritmo che lo risolve? → No! Come per esempio "married problem".

Halting problem → esiste un algoritmo che preso un altro algoritmo e un input, riesce a dire se quell'algoritmo su quel dato input riesce oppure no.

Scopo sistema informatico

Scopo sistema informatico: immagazzinamento e recupero dell'informazione.

9/03 Introduzione al corso

Algoritmo, struttura dati ed efficienza

Algoritmo → procedimento che risolve un determinato problema attraverso un numero finito di passi elementari.
Struttura dati → particolare organizzazione delle informazioni.
Efficienza → è legata al modo 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.
Creare tabelle di polinomi utilizzando "il metodo delle differenze".
1° computer al mondo.
Fu solo progettata.

Ada Lovelace

Ada Lovelace collaborò con Babbage per la macchina analitica.

Aveva previsto la capacità dei computer di andare al di là del calcolo numerico.

Definizione di Donald Knuth

Tempo di esecuzione di un algoritmo = Somma dei costi × frequenza di ogni operazione.

Problema e Halting problem

Problema → caratterizzato da dati in ingresso su cui poi un algoritmo opera.

Qualunque problema formulabile ha un algoritmo che lo risolve? → No! Come per esempio "matrix problem".

Halting problem → esiste un algoritmo che preso un altro algoritmo e un input, riesce a dire se quell'algoritmo su quel dato input si possa fermare o no.

Scopo sistema informatico

Scopo 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.

Tesi: tutti gli interi k≥c godono della proprietà P.

2 passaggi:

Passo base → dimostra che c gode di P.
Passo induttivo → assumo che k gode di P e dimostro che anche k+1 gode di P.

Somma(toria) primi n numeri

S_n = ∑ⁿ_t=1 = (u (u+1)) / 2.

Logaritmi

Logaritmi

log_bx=y b → base.

b^y = x x → argomento.

log₀? log_-u? esistono.

Proprietà

Log_b(xy)=log_bx + log_by.
Log_b(^x/_y)=log_bx - log_by.
Log_b(x^u)=ulog_bx.
Log_b(b)=1.
Log_b(1)=0.
Log_b(b^u)=u.

Proprietà cambiamento di base

a>0 a≠1.

log_b(x) = ^log_a(x)/_{log_a(b)} oppure log_b(x) = ^u⁄_{u b} è una costante.

¹/_{log_ab} = c → log_ax = c * log_ax.

Possiamo cambiare la base se nei nostri calcoli le costanti moltiplicative non sono interessanti ai fini del calcolo.

Dimostrazione per induzione (Sommatoria)

∀u ≥ 1 ∑_i=1^u i = u(u+1)/2.

Passo base: ∑_i=1¹ i = 1(1+1)/2 ? → 1 = 1 Sì.
Passo induttivo: ∑_i=1^u+1 i = u+1((u+1)+1)/2 = (∑_i=1^u i) + u+1 = u(u+1)/2 + u+1.

Anteprima

Vedrai una selezione di 17 pagine su 77