Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- fisica:informatica:201819:esercitazioni:esercitazione11l [20/03/2019 alle 09:30 (6 anni fa)] – creata Susanna Pelagatti
+++ fisica:informatica:201819:esercitazioni:esercitazione11l [20/03/2019 alle 11:05 (6 anni fa)] (versione attuale) – [Esercizio 3: Hash o non Hash ?] Alessio Conte
@@ Linea 15: / Linea 15: @@
 Osservare le differenze di performance tra i due algoritmi al crescere di n (e.g., n > 1000000) misurando il tempo necessario all'ordinamento
+===== Esercizio 2: Ordinato è meglio ? =====
+Dato un array di interi ordinato, come posso verificare se contiene un intero x?
+Devo davvero leggere ogni valore, o esiste un modo più veloce?
+===== Esercizio 3: Hash o non Hash ?=====
+Scrivere un programma che legga da tastiera una sequenza di ''n'' interi NON distinti e li inserisca (senza duplicati) in una tabella hash di dimensione $m=2n$ utilizzando liste di trabocco per risolvere conflitti.
+Utilizzare la funzione hash $h(x) = ((ax + b) \% p)\%m$ dove $p$ è il numero primo $999149$ e $a$ e $b$ sono interi positivi minori di 10.000 scelti casualmente.
+Una volta inseriti tutti gli interi, stampare
+  -  gli elementi nella tabella
+  -  il numero totale di conflitti,
+  -  la lunghezza massima delle liste e
+  -  il numero di elementi distinti nella tabella.
+Provare lo stesso con funzione hash $h(x) = x\%m$ e osservare se c’è differenza nella performance.