_info-01-Algoritmi.pdf

7/26/2019 _info-01-Algoritmi.pdf

1/20

Informatica: cenni storici

Il concetto di algoritmo

InformaticaDocente: Giuliano Armano

Corso di Laurea in Ing. Meccanica e Ing. AmbienteA.A. 2011/2012

Per gentile concessione di Giorgio Fumera


2/20

La preistoria dell'informatica

calculus


3/20

Primi strumenti di ausilio al calcolo

abaco romano (circa 2000 anni fa)


4/20


5/20


6/20


7/20

I primi calcolatori elettromeccanici

Mark I (1944)


8/20


9/20

La nascita dell'informatica

Alan Turing (1912 - 1954)

Quali calcoli possono essere svoltida una macchina?

Il concetto di algoritmo

John von Neumann (1903 - 1957)

Come progettare una macchina in gradodi eseguire qualsiasi algoritmo?

Concetto di calcolatore programmabile


10/20


11/20

Evoluzione dei calcolatori...

Tecnologia:

! meccanica (XVII sec. - anni 30 XX sec.)

! elettromeccanica (anni 30-40 XX sec.)

! elettronica (anni 40 XX sec. - oggi)

Conseguenze:

! riduzione dei costi di produzione, del consumo di energia, delle

dimensioni! incremento della velocit di calcolo e della capacit di

memorizzazione

! estensione degli ambiti applicativi e del numero di utenti


12/20

... e dell'informatica

Algoritmi estrutture dati

Architettura deicalcolatori

Sistemi operativi e

softwaredi rete

Linguaggi diprogrammazione

Basi di dati e sistemi per ilrecupero di informazioni

Ingegneria delsoftware

Intelligenzaartificiale

Graficacomputerizzata

(informatica grafica)


13/20

Algoritmo: definizione informale

Descrizione della sequenza di azioniche portano alla realizzazione

di un dato compito in un tempo finito


14/20

Esempi di compiti descrivibili da algoritmi

! preparare una torta di mele

! usare un videoregistratore

! prelevare denaro da uno sportello Bancomat

! cercare un nome in un elenco telefonico

! disporre una sequenza di nomi in ordine alfabetico

! trovare il percorso pi breve tra due citt attraverso una mappastradale

!

sommare due numeri interi! estrarre la radice quadrata di un numero reale non negativo

! calcolare gli zeri di unequazione di secondo grado a coefficientireali


15/20

Algoritmi ed esecutori

Scopo principale della formulazione di algoritmi:comunicare a un esecutore(unaltra persona,o una macchina) il procedimento per

realizzare un dato compito

Due problemi principali:

! quale linguaggio conosce?! quali azioni sa eseguire?


16/20

Algoritmo: definizione formale

Descrizione del procedimento per la realizzazione di undato compito,

espressa in modo non ambiguo,

in un linguaggio comprensibile dallesecutore,in termini di una sequenza finita di operazioni che

l'esecutore sia in grado di eseguire


17/20

Algoritmi e informatica

Quali sono i compiti di interesse per linformatica?

Elaborazione di informazione

un procedimentorisolutivodati di ingresso risultati


18/20

Esercizio

Quali dei seguenti compiti possono essere formulati comeproblemi di elaborazione di informazione?Ove possibile, indicare i dati di partenza e il risultato

!preparare una torta di mele!usare un videoregistratore!prelevare denaro da uno sportello Bancomat!cercare un nome in un elenco telefonico!disporre una sequenza di nomi in ordine alfabetico!

trovare il percorso pi breve tra due citt tramite una mappa stradale!sommare due numeri interi!estrarre la radice quadrata di un numero reale non negativo!calcolare gli zeri di unequazione di secondo grado a coefficienti reali


19/20


20/20

Esercizio

Formulare un algoritmo per la risoluzione del seguente problema:ordinare in senso crescente una sequenza di cinque numeri interi

Traccia:! quali operazioni eseguireste voi?! come potreste descriverle?! la vostra descrizione un algoritmo?

- chi lesecutore?

- in grado di comprendere il linguaggio che avete usato?

- la vostra descrizione presenta delle ambiguit?- lesecutore in grado di eseguire tutte le operazioni indicate?

- il numero di operazioni richieste finito?! il vostro algoritmo corretto? cio, consente di ordinare come

richiesto qualsiasi sequenza di cinque numeri interi?

_info-01-Algoritmi.pdf

Documents

Transcript of _info-01-Algoritmi.pdf