Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università...

29
Docente: Marco Sechi ‐ Elementi di informatica e programmazione – Università degli studi di Brescia D.I.M.I Dipartimento di Ingegneria Meccanica e Industriale Dipartimento di Ingegneria Meccanica e Industriale Corso di laurea: Ingegneria Gestionale Elementi di informatica e programmazione Elementi di informatica e Programmazione Docente: Marco Sechi E‐mail: [email protected] Università degli Studi di Brescia EXCEL EXCEL Vers. 26/09/2016.R01112017

Transcript of Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università...

Page 1: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le

Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

leCo

rso di laurea

: Ing

egne

ria Gestio

nale

Elem

enti di inform

atica e prog

rammazione

Elementi di informatica e Programmazione

Docente: Marco SechiE‐mail: [email protected]

Università degli Studi di Brescia

EXCELEXCEL

Vers. 26/09/2016.R01112017

Page 2: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

2Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Archivi e fogli elettronici

Archivi monotabellari

Page 3: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

3Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Molto spesso abbiamo la necessità di creare un archivio, ad esempio, per classificare i nostri libri, per catalogare le merci in un magazzino, per registrare i nostri pazienti, etc.

Il database è uno strumento indispensabileper gestire in modo efficace e proficuo i propri dati. Prima di procedere con la spiegazione si rende necessaria una piccola premessa diretta ad illustrare cosa sia e a cosa serva un database.

Terminologia degli Archivi

Programmi specifici, progettati per gestire archivi utilizzati da gruppi di poche persone, sono Access (incluso nella suite diMicrosoft Office!)  e il suo equivalente gratuito Base (della suite di OpenOffice). Entrambi i programmi, per quanto utili, non sono propriamente user friendly e possono mettere in difficoltà un utente inesperto. Chi ha necessità "limitate" può utilizzare, in alternativa, un insieme di funzionalità messe a disposizione sia da Excel che da Calc.

L'archivio costituisce il contenitore dove inserire tutte le informazioni che descrivono il fenomeno che intendiamo gestire. Un archivio reale è solitamente composto da dati non omogenei (ad esempio Docenti, Studenti, Appelli, Esiti, etc. ). 

Page 4: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

4Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Ogni gruppo di dati omogenei viene registrato all'interno di uno stesso contenitoredetto tabella. Le proprietà che caratterizzano ogni singolo elemento (record) della stessa tabella vengono definite campi. Pensando ad un "foglio di lavoro" (contenente  dati!) le righe rappresentano i recordmentre le colonne i campi. L'insieme delle caratteristiche che descrivono i singoli campi (nome, dimensione, tipo di dato ...) prende il nome di struttura della tabella.

Un database composto da una sola tabella si dice monotabellare. Un database monotabellare di modeste dimensioni può essere gestito in modo efficace anche attraverso un foglio elettronico.

Page 5: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

5Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

L'uso di Excel/Calc per gestire degli archivi monotabellari è una pratica molto diffusa. I fogli elettronici, pur non essendo dei gestori di archivi hanno un apposito menu/ribbon "DATI" che permette di eseguire le 2 funzioni principali, tipiche dei programmi database: ricerca(filtri!) ed ordinamento.

In realtà i fogli elettronici non risultano adatti alla gestione di archivi complessi e voluminosi poiché presentano le seguenti limitazioni:

Nei fogli elettronici non è possibile definire relazioni tra le diverse tabelle. Le relazioni attivano meccanismi automatici che semplificano la gestione dell'archivio. Inoltre abbattono la ridondanza (duplicazione!) dell'informazione all'interno dell'archivio stesso.

Negli spreadsheet non è possibile definire gli indici sui campi. Gli indici consentono di velocizzare le ricerche e gli ordinamenti.

Non è possibile definire in modo esplicito il tipo di dato per i campi. La "non tipizzazione" dei dati può determinare ordinamenti sbagliati e talvolta anche risultati errati. Ad esempio l'operatore + nelle stringhe viene interpretato come operatore di concatenamento e non di addizione per cui "1"+"2"="12" e non 3.

Un DB composto da diverse tabelle in relazione tra loro si dice Relazionale. Le relazioni tra le tabelle permettono di manipolare i dati più facilmente e soprattutto evitano la duplicazione delle informazioni (ridondanza) che è inevitabile quando si opera solo con database monotabellari.

RELAZIONI TRA TABELLE

Page 6: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

6Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

ESEMPIO DI GESTIONE CON TABELLE IN RELAZIONE IN EXCEL/CALC ‐ DSCS

=CERCA.VERT()

=CERCA.VERT()

Page 7: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

7Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

ESEMPIO DI GESTIONE CON TABELLE IN RELAZIONE IN EXCEL/CALC ‐ DIMI

=CERCA.VERT()

=CERCA.VERT()

Page 8: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

8Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Un Diagramma Entità‐Relazioni (ERD o Entity‐Relationship Diagram) come quello sottostante evidenzia i collegamenti logici tra le tabelle di un database.

L’indicizzazione è una delle funzionalità più importanti nei programmi che gestiscono gli archivi. Tale funzionalità non è presente nei fogli elettronici. 

Un indice è una struttura dati (aggregato di informazioni tra loro logicamente collegate!) che permette di velocizzare le ricerche e gli ordinamenti e pertanto viene inserito nei campi sottoposti a tali attività.

INDICI SUI CAMPI

Page 9: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

9Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Se leggo l'archivio DATI usando le posizioni indicate dall'indice associato all' "Età" ottengo un elenco ordinato rispetto a quel campo

Page 10: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

10Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Se leggo invece l'archivio DATI seguendo le posizioni specificate dall'indice abbinato al "Nome" ottengo un elenco ordinato alfabeticamente per nominativo:

Page 11: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

11Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Nella figura viene mostrato come l'inserimento di un nuovo record (registrato solitamente in coda all'archivio) comporti una serie di operazioni supplementari (ad esempio lo spostamento dei contenuti dell'indice per consentire il corretto inserimento della posizione riguardante l'ultimo dato aggiunto!) che hanno lo scopo di mantenere aggiornati gli indici.

Il prezzo dell'indicizzazione è rappresentato da una maggior lentezza nelle operazioni di aggiornamento (aggiunta/modifica) dell'archivio poiché, oltre alle modifiche sui dati, occorre aggiornare tutti gli indici associati. 

Page 12: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

12Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Quando gli elenchi sono ordinati è possibile applicare una serie di algoritmi di ricerca che permettono di localizzare il dato in tempi brevissimi. L'ordinamento impiega una relazione d'ordine, esistente tra i singoli elementi, che viene descritta utilizzando gli operatori di confronto. 

La relazione d'ordine può cambiare a seconda del tipo di dato impiegato. Tipi di dato non adeguati alle nostre esigenze possono determinare ordinamenti inaspettati.

operatore Significato

> Maggiore di

>= Maggiore o uguale a

< Minore di

<= Minore o uguale a

<> Diverso 

= Uguale a

TIPI DI DATO

In un vocabolario cartaceo l'ordinamento è definito dall'alfabeto. Le parole che iniziano con una lettera posta all'inizio dell'alfabeto appaiono prima rispetto alle parole la cui iniziale è una lettera che invece si trova in fondo all'alfabeto (ordinamento lessicografico). Nel caso 2 parole inizino con la stessa lettera la relazione d'ordine viene determinata dalla 2° lettera.

"abaco" < "abadessa" < "abano" < "abarica" < "abarico" < "abate" < "abatino" < "abatterica"

Qualora le prime 2 lettere nelle due parole a confronto risultino uguali il paragone passa alla 3° lettera e prosegue eventualmente sulle successive. Questo modo di comparare le parole rappresenta la relazione d'ordine tra i vocaboli, utilizzata nell'ordinamento lessicografico.

Page 13: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

13Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Sequenze di simboli alfanumerici (lettere, numeri, punteggiatura, spazi, parentesi etc.), dette stringhe, nel calcolatore vengono ordinate utilizzando come "alfabeto di riferimento" la tabella ASCII. Pertanto la seguente relazione è corretta:

"Zorro" < "abate"

Page 14: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

14Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Sequenze di cifre possono essere interpretate in 2 modi:

CAP  "25192"Telefono  "0302918312"Password  "123456"Partita IVA  "12345678901"

Voto esame  28  calcolo la media dei miei esamiPeso  72,38  trovo il peso totale della merce acquistata

B) In termini alfanumerici ovvero come semplice sequenza di simboli (caratteri!) dove non svolgo alcun calcolo.

Si osservi come nella notazione informatica, per evidenziare che si sta utilizzando l'interpretazione "alfanumerica", la sequenza venga racchiusa tra doppi apici ". Una sequenza di simboli racchiusa tra " viene indicata con il termine: stringa.

A) in termini numerici – solitamente su informazioni di questo tipo si effettuano successivamente dei calcoli o delle statistiche

Quando sequenze di cifre vengono interpretate come valori numerici la relazione d'ordine usata è quella classica e pertanto la relazione seguente è banalmente vera.

1230 > 129 

Page 15: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

15Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

"1230" < "129" 

Quando invece le sequenze hanno una valenza simbolica, priva di significati numerici, subentra il confronto lessicografico basato sull' "alfabeto" ASCII e pertanto la relazione precedente diventa:

Infatti le 2 sequenze numeriche hanno le prime 2 cifre uguali per cui il confronto parte con il 3° simbolo. Essendo il simbolo "3", nella tabella ascii, prima del "9" (quindi: "3" < "9") segue la veridicità della relazione indicata. 

Diverse relazioni d'ordine (come quella lessicografica e numerica!) determinano ordinamenti differenti, entrambi corretti!

Sequenza ordinata di stringhe numeriche (numerali)

Sequenza ordinata di valori numerici

RAPPRESENTAZIONE DEI DATI CRONOLOGICILa notazione in base e la codifica ASCII consentono, all'interno del calcolatore, la memorizzazione delle due tipologie di dato più semplici: i numeri e i caratteri. Vediamo ora come è possibile codificare informazioni di natura temporale partendo da questi due semplici tipi di dato.Un esempio di codifica per le date, utilizzando il tipo alfanumerico, potrebbe essere rappresentato dalla sequenza di simboli ascii associati a: "giorno/mese/anno".

Page 16: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

16Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

"03/01/1964" > "02/01/2017" 

Utilizzando questa modalità di rappresentazione la data 3 gennaio 1964  diventa la stringa "03/01/1964". L'ordinamento lessicografico, tipico delle stringhe, con questa codifica non risulta però compatibile con quello cronologico ed infatti: 

In aggiunta questa codifica possiede un buon "livello di chiarezza" visto che leggendola si intuisce immediatamente quale sia il giorno a cui si riferisce. Lo svantaggio che la rende poco pratica è invece la difficoltà nell'implementare operazioni come:

OGGI+1 data di domaniOGGI‐1 data di ieriOGGI‐DATADINASCITA totale dei giorni vissuti fino a oggi

"1964/01/03" < "2016/01/02"

Se però modifichiamo la codifica invertendo l'ordine "anno/mese/giorno" l'ordinamento lessicografico diventa compatibile con quello cronologico ed infatti:

Una modalità alternativa per codificare le date, basata questa volta sul tipo numerico, è quella  che associa ad una data il numero intero ottenuto calcolando la seguente formula:

𝑎𝑛𝑛𝑜 ∗ 10000 𝑚𝑒𝑠𝑒 ∗ 100 𝑔𝑖𝑜𝑟𝑛𝑜

che ripropone la scrittura rovesciata della data, precedentemente vista con le stringhe.1964*10000+1*100+3=19640103

Alla data del 3 gennaio 1964 verrà quindi abbinata la codifica:

Page 17: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

17Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

L'ordinamento numerico, con questa codifica, risulta coerente con quello cronologico. Come nella precedente codifica alfanumerica "aaaa/mm/gg" abbiamo il vantaggio della leggibilità del dato ma anche in questo caso l'implementazione di operatori di natura "cronologica" risulta difficoltosa. Infatti aggiungendo uno alla rappresentazione di una data non otteniamo sempre la codifica del giorno successivo:

20181231+1=20181232Un'altra modalità (usata da Excel!) che utilizza il tipo numerico è quella che rappresenta una data con il numero di giorni trascorsi (o mancanti!) rispetto ad una data di rifermento che per Excel è il 1/1/1900. In Excel il numero 43.491 rappresenta la codifica del giorno 26/01/2019. Tale codifica risulta umanamente illeggibile ovvero non è immediato capire quale sia la reale data associata! Questo inconveniente viene risolto grazie all'interfaccia grafica che trasforma la rappresentazione interna in una "formato" umanamente leggibile. Il vero vantaggio di questa codifica è che gli operatori algebrici assumono un senso cronologico corretto. Infatti

26/1/2019 + 1  43491 + 1  43492  27/1/201926/1/2019 ‐ 1 43491 ‐ 1  43490  25/1/201926/1/2019 – 26/2/2018  43491 – 43157 =334

giorno successivogiorno precedentegiorno trascorsi

non è la codifica del giorno successivo!

La rappresentazione delle date in Excel è proprio questa e per dimostrarlo basta scrivere 26/1/2019 in una cella e successivamente impostare la maschera di formato in figura ("0"):

L'orario viene codificato come frazione di giorno pertanto le 18.00 corrispondono a 0,75.

20181230+1=20181231 È la codifica del giorno successivo!

Page 18: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

18Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Negli elenchi ordinati/indicizzati è possibile applicare una serie di algoritmi che abbattono i tempi di risposta nelle ricerche. In un elenco non ordinato l'unica ricerca possibile è quella sequenziale.

Algoritmi di ricerca (cenni)

Esempio: Consideriamo un elenco telefonico cartaceo dove, per semplicità,  venga gestita un'unica località. L'elenco risulta ordinato rispetto al nominativo (ovvero indicizzato per quel campo!) pertanto la ricerca del numero di telefono corrispondente ad un determinato cognome risulta immediata. Immaginiamo ora di voler conoscere il nominativo della persona che risponde ad uno specifico numero di telefono. 

Analizziamo ora due metodi (algoritmi) di ricerca.

In questo caso l'indice non ci aiuta per cui siamo costretti a scorrere l'elenco, partendo dall'inizio, un numero dopo l'altro fino a quando non individuiamo quello richiesto oppure, arrivando alla fine, comprendiamo che il telefono esaminato è inesistente. Questo metodo di ricerca, detto sequenziale, risulta poco efficiente e con tempi di risposta decisamente lunghi.

Page 19: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

19Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

La ricerca sequenziale o completa consiste nella scansione in sequenza dei record dal primo fino all'ultimo e si interrompe quando il valore cercato è stato trovato oppure quando si è sicuri che il record esaminato non sia presente in elenco. Ha il vantaggio di essere sempre applicabile, anche su archivi non ordinati, ma presenta come rovescio della medaglia un'estrema lentezza.

Iniziamo con il calcolare il numero medio di letture necessarie per individuare un record con la ricerca sequenziale.

Criteri validi per valutare la bontà di un algoritmo di ricerca sono il numero medio di letture (confronti!) oppure quello massimo che devo fare per individuare la posizione del record che mi interessa. 

RICERCA SEQUENZIALE

Le casistiche possibili che posso avere quando ricerco un record all'interno di un archivio non ordinato di N elementi sono:

• 1° casistica: trovo il record cercato dopo una sola lettura (sono fortunato! L'ho trovato al primo colpo!);

• 2° casistica: il record viene localizzato in seconda posizione, dopo 2 letture;• ... • N° casistica: il record viene localizzato dopo N letture (ad esempio quando il 

record cercato è in fondo all'archivio!) oppure si capisce che ciò che cerco non è presente in elenco.

Page 20: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

20Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

1 2 … 𝑁 1 𝑁𝑁 · 𝑁 1

2

Il numero complessivo dei confronti effettuato nelle N casistiche citate è pari a:

La formula ottenuta evidenzia come la media dei confronti (letture) aumenti in modo lineare al crescere dell'archivio rendendo la ricerca sequenziale improponibile con archivi di grandi dimensioni. Ad esempio in un archivio con un 1.000.000 di record sono necessari, in media, circa 500.000 confronti prima di individuare il record desiderato.

Il numero di letture medio si ottiene dividendo il numero complessivo dei confronti per il numero N delle casistiche analizzate da cui segue:

1 2 … 𝑁𝑁

𝑁 · 𝑁 12 · 𝑁

𝑁 12

numero medio di letture

1 2 … 𝑁 1 𝑁

Per induzione è possibile dimostrare la relazione:

Page 21: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

21Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

RICERCA CON INDICE: In un archivio ordinato (indicizzato!) il numero massimo di letture scende a:

Un esempio di ricerca con indice è rappresentato dall'algoritmo dicotomico (o binario) che è molto simile al metodo impiegato per trovare una parola in un dizionario. Sapendo che il vocabolario è ordinato alfabeticamente non inizio a cercare dal primo elemento ma parto da una posizione  centrale, cioè a metà del dizionario. 

RICERCA CON INDICE (ALGORITMO DICOTOMICO O BINARIO)

𝑙𝑜𝑔 𝑁

La basem del logaritmo è strettamente collegata al tipo di algoritmo di ricerca utilizzato.

Nella ricerca dicotomicam vale 2. Quindi con un 1.000.000 di record il numero massimo di confronti che devo effettuare per individuare un record con la ricerca binaria è pari a: 

log2 (1.000.000)=ln(1.000.000)/ln(2) ≈ 19,93 confronti. 

Una cifra irrisoria rispetto ai 500.000 confronti medi della ricerca sequenziale! Attenzione: la ricerca dicotomica è applicabile solo su archivi ordinati!

Page 22: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

22Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

L'algoritmo dicotomico/binario può essere cosi riassunto. Sia E il record cercato.

1. Indichiamo con P (estremo sinistro) il primo elemento e con U l'ultimo (estremo destro) della sequenza dove cerco E.

2. Determino l'elemento centrale M della sequenza che parte da P e finisce con U. Confronto il record E con M.

3. Se E > M significa che tutti gli elementi da P a M possono essere scartati (la sequenza è ordinata per cui sono sicuramente inferiori ad E essendo minori di M!) e pertanto sposto l'estremo sinistro P su M+1 ovvero pongo P=M+1 e salto al punto 6)

Page 23: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

23Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

4. Se E < M significa che tutti gli elementi da M a U possono essere scartati (la sequenza è ordinata per cui sono sicuramente superiori ad E essendo maggiori di M!). Sposto quindi l'estremo destro U su M‐1 ovvero pongo U=M‐1 e passo al punto 6)

5. Se M=E allora l'elemento E è stato trovato e passo al punto 8) 

6. Se P (estremo sinistro) coincide con U (estremo destro) allora l'elenco si è esaurito e l'elemento E non è stato trovato. L'algoritmo termina e pertanto salto al punto 8)

7. Ritorno al punto 2) dove viene determinato il nuovo record centrale M.

Dallo step 3.

Page 24: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

24Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Analizzando il processo di ricerca si osserva che ad ogni confronto viene scartata metà della sequenza di record rimasta da esaminare. Pertanto dopo k confronti rimangono N/2k record da controllare. Quindi la sequenza si esaurisce dopo un numero di confronti pari a:

k= log2(N) 

8. STOP Schema di flusso della ricerca dicotomica.

Dallo step 4.

Page 25: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

25Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Vediamo un esempio di ricerca all'interno di un vocabolario che abbatte ulteriormente ilnumero massimo di confronti. L'idea è quella di raggruppare i vocaboli in base alle primek lettere. In questo modo la ricerca binaria viene applicata solo su un sottoinsiemeridotto di parole e non sulla totalità dei vocaboli.

Con il primo livello (indice sulla 1° lettera) si escludono dalla ricerca circa i 25/26‐esimi (dipende dalla distribuzione delle lettere iniziali nel vocabolario italiano!) tra tutti i vocaboli presenti nella lingua italiana. Al successivo livello ottengo un'ulteriore riduzione di circa 25/26‐esimi e pertanto l'insieme finale su cui realmente si svolge la ricerca dicotomica risulta drasticamente ridotto.

o o o

Indice sulla prima lettera

Indici  sulla seconda lettera

Effettuo una ricerca binaria sui singolisottoelenchi

Effettuo una ricerca binaria sui singolisottoelenchi

Effettuo una ricerca binaria sui singolisottoelenchi

Effettuo una ricerca binaria sui singolisottoelenchi

Page 26: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

26Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Il foglio elettronico è un programma nato per automatizzare i calcoli. Il suo aspetto tabellare ha fatto si che molti utenti vedessero in lui un valido strumento per trasporre digitalmente i propri elenchi contenti dati.L'uso diffuso e sistematico del foglio elettronico come gestore di database (monotabellari!) ha portato le case produttrici ad inserire (ormai da tantissimi anni) un menu ad hoc per la gestione dei dati.

Con il pulsante "Ordina" è possibile ordinare i dati contenuti su un foglio

Excel 2016 Win

In Windows

Page 27: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

27Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Con il pulsante "Filtro" è possibile visualizzare solo le righe che soddisfano determinate condizioni di ricerca.

Excel 2016 Win

Page 28: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

28Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Utilizzando il pulsante modulopossiamo passare dalla visualizzazione "Lista" (tabellare) alla visione "Scheda" (singolo record) che consente di trattare i dati contenuti nel foglio a livello di singola riga.

Per aggiungere il pulsante "Modulo" in Excel 2016 occorre personalizzare la barra di "accesso rapido" selezionando la voce "Altri comandi". In Apple la funzionalità non è presente.

Excel 201

6 Win

Page 29: Università degli Studi di Brescia Elementi di informatica e … · 2019-08-24 · Università degli Studi di Brescia EXCEL ... che permette di eseguire le 2 funzioni principali,

29Dipa

rtim

ento di Ing

egne

ria M

eccanica e In

dustria

le –Co

rso di laurea

: Ing

egne

ria Gestio

nale 

Docente: Marco Sechi  ‐ Elementi di informatica e programmazione – Università degli studi di Brescia  D.I.M.I

Excel 201

6 Ap

ple

In Apple con la voce "Ordina …" nel menu "Dati" è possibile ordinare i dati contenuti su un foglio

Con la voce di menu "Filtro" è possibile visualizzare solo le righe che soddisfano determinate condizioni di ricerca.

Excel 201

6 Ap

ple

Excel 201

6 Ap

ple

In Apple