Algoritmi e strutture dati

Revisionato il 24/06/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 -> 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

Collaborò con Babbage per la macchina analitica

avrà 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 -> 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

immagazzinamento e recupero dell'informazione

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

EFFICENZA -> è 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

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 -> 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 -> immagazzinamento e recupero dell'informazione

Principio di induzione aritmetica

∀ intero u≥c

Se P è vera per u allora P è vera per u+1

fessi: 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

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