Appunti per l'esame Algoritmi e strutture dati

O

ottimizzazione si può considerare solo i numeri dispari dopo 2.

def sieve(n):

"""

Restituisce una lista di numeri primi fno a n usando il Crivello di Eratostene,

ottimizzato per considerare solo i numeri dispari (eccetto 2).

"""

if n < 2:

return []

# Includi il 2, l'unico numero primo pari

primes = [2]

# Calcola quanti numeri dispari ci sono da 3 a n

size = (n - 1) // 2 # I numeri dispari in [3, n] sono rappresentati da: 2*i + 3, con i da 0 a size-1.

is_prime = [True] * size

# Limite per i numeri da controllare: consideriamo p = 2*i + 3, vogliamo p <= sqrt(n)

limit = int(n ** 0.5)

max_i = (limit - 3) // 2 + 1 # Indice massimo da controllare

2

for i in range(max_i):

if is_prime[i]:

p = 2 * i + 3 # p è il numero primo corrente

# p^2 corrisponde a un indice: (p*p - 3) // 2

start = (p * p - 3) // 2

for j in range(start, size, p):

is_prime[j] = False

# Aggiungi alla lista tutti i numeri dispari marcati come primi

primes.extend([2 * i + 3 for i, prime in enumerate(is_prime) if prime])

return primes

# Esempio di utilizzo:

if __name__ == "__main__":

limit = 100

primes = sieve(limit)

print(f"I numeri primi fno a {limit} sono:")

print(primes)

Altre migliorie che si possono applicare possono essere di utilizzare una ruota di

numeri primi, oppure segmentare il nostro elenco.

Sicuramente è molto semplice ed efficiente come algoritmo, ma ha come pecca l’uso

elevato della memoria, il cui costo è e non è adatto a trovare numeri primi

O(n)

molto grandi.

Tra le possibili applicazioni:

generazioni di tabelle di numeri primi

 base algoritmi di fattorizzazione

 utile alla teoria dei numeri



tra le varianti possiamo trovare:

crivello di Sundonan

 crivello di Atkin

 crivello probabilistico (meno memoria, ma potrebbe tralasciare alcuni primi)



le integrazioni possibili sono:

struttura dati compatta per risparmiare memoria

 utile come pre processore per altri algoritmi

 base per implementazioni parallele e distribuite per generare i primi



8.4.6. Sfde computazionali

Non sono problemi di natura tecnia ma pratici. La generazione dei numeri primi è

importante per: 2

numeri primi sempre più grandi

 numeri primi con forme speciali (es. gemelli)

 miglioramento efficiente test primialità

 sistemi resistenti ad attacchi crittografci



i focus attuali della teoria dei numeri:

problemi di fattorizzazione di numeri interi

 algoritmi principali

 implicazioni



8.5. Algoritmi di String Matching

Il problema dello string matching consiste nel cercare una sottostringa (pattern)

all’interno di una stringa (testo). Creare un algoritmo su questa problematica possono

migliorare in modo signifcativo le attività dei programmi. Il problema si può

sia il testo formato da un array T[1:n] di lunghezza n, il pattern con

rappsentare come:

array P[1:m] di lunghezza m<=n. gli elementi di P e T sono caratteri appartenenti ad

un alfabeto che è un insieme fnito di caratteri. Molto spesso P e T vengono

ε

chiamate stringhe di caratteri.

Tra gli algoritmi più noti troviamo:

Ricerca Naïve: Confronta il pattern in ogni possibile posizione.

 Knuth-Morris-Pratt (KMP): Pre-elabora il pattern per saltare confronti

 ridondanti.

Boyer-Moore: Utilizza euristiche (bad character e good suffix) per

 spostamenti ottimali.

Rabin-Karp: Usa l’hashing per confrontare rapidamente le sottostringhe.



8.5.1. Ricerca Naïve

Pseudocodice:

NaiveSearch(text, pattern):

n = lunghezza(text)

m = lunghezza(pattern)

per i da 0 a n-m:

per j da 0 a m-1:

se text[i+j] ≠ pattern[j]:

break

se j ha raggiunto m:

ritorna i // Pattern trovato in posizione i

ritorna -1 // Pattern non trovato

Codice Python:

def naive_search(text, pattern):

n = len(text) 2

m = len(pattern)

for i in range(n - m + 1):

match = True

for j in range(m):

if text[i + j] != pattern[j]:

match = False

break

if match:

return i

return -1

# Esempio di utilizzo:

text = "questo è un esempio di string matching"

pattern = "esempio"

print("Pattern trovato in posizione:", naive_search(text, pattern))

8.5.2. Algoritmo KMP

L’algoritmo KMP pre-elabora il pattern creando un vettore dei prefssi per evitare

ripetizioni di confronti. In pratica sfrutta le informazioni sulle corrispondenze parziali

per evitare confronti inutili.

Pseudocodice (schematico):

KMP_Search(text, pattern):

prefssi = ComputePrefx(pattern)

i = 0, j = 0

mentre i < lunghezza(text):

se text[i] == pattern[j]:

i++, j++

se j == lunghezza(pattern):

ritorna i - j // Pattern trovato

altrimenti se j > 0:

j = prefssi[j-1]

altrimenti:

i++

ritorna -1

Codice Python:

def compute_prefx(pattern):

m = len(pattern)

lps = [0] * m # longest proper prefx that is also suffix

length = 0 # lunghezza del precedente match

i = 1 2

while i < m:

if pattern[i] == pattern[length]:

length += 1

lps[i] = length

i += 1

else:

if length != 0:

length = lps[length - 1]

else:

lps[i] = 0

i += 1

return lps

def kmp_search(text, pattern):

n, m = len(text), len(pattern)

lps = compute_prefx(pattern)

i = j = 0

while i < n:

if text[i] == pattern[j]:

i += 1

j += 1

if j == m:

return i - j # Pattern trovato

else:

if j != 0:

j = lps[j - 1]

else:

i += 1

return -1

# Esempio di utilizzo:

text = "abxabcabcaby"

pattern = "abcaby"

print("KMP - Pattern trovato in posizione:", kmp_search(text, pattern))

8.5.3. Algoritmo di Booyer-Moore

Ha un alfabeto di grandi dimensioni, la complessità di questo algoritmo è O(n+m) nel

caso medio e O(n*m) nel caso peggiore.

def boyer_moore_search(text, pattern):

"""

Cerca tutte le occorrenze del pattern in text usando l'algoritmo di Boyer-Moore

2

(utilizzando la bad character rule).

Args:

text (str): Il testo in cui cercare.

pattern (str): Il pattern da cercare.

Returns:

List[int]: Lista degli indici di inizio di ogni occorrenza del pattern.

"""

m = len(pattern)

n = len(text)

if m == 0:

return []

# Pre-elaborazione: costruzione della tabella del "bad character"

bad_char = {}

for i in range(m):

bad_char[pattern[i]] = i # Memorizza l'ultima occorrenza del carattere nel pattern

indices = []

s = 0 # s: indice di shift nel testo

while s <= n - m:

j = m - 1

# Confronta il pattern con il testo da destra a sinistra

while j >= 0 and pattern[j] == text[s + j]:

j -= 1

if j < 0:

# Pattern trovato a posizione s

indices.append(s)

# Shift per il prossimo possibile match:

# Se c'è un carattere dopo il match nel testo, utilizza la bad character rule,

# altrimenti sposta di 1.

if s + m < n:

s += m - bad_char.get(text[s + m], -1)

else:

s += 1

else:

# Calcola lo shift: almeno 1, o lo spostamento basato sul mismatch

shift = max(1, j - bad_char.get(text[s + j], -1))

s += shift 2

return indices

# Esempio di utilizzo:

if __name__ == "__main__":

text = "HERE IS A SIMPLE EXAMPLE"

pattern = "EXAMPLE"

result = boyer_moore_search(text, pattern)

print("Boyer-Moore: Il pattern è stato trovato alle posizioni:", result)

8.5.4 Algoritmo di Robin-Karp

Usa l’hashing per fare rapidi confronti, la complessità è O(n+m) per il caso medio e

O(n*m) per il caso peggiore.

def rabin_karp_search(text, pattern):

"""

Cerca tutte le occorrenze del pattern in text usando l'algoritmo di Rabin-Karp.

Args:

text (str): Il testo in cui cercare.

pattern (str): Il pattern da cercare.

Returns:

List[int]: Lista degli indici di inizio di ogni occorrenza del pattern.

"""

n = len(text)

m = len(pattern)

if m == 0:

return []

# Parametri per il calcolo dell'hash

d = 256 # Dimensione dell'alfabeto (numero di caratteri possibili)

q = 101 # Un numero primo per il modulo, scelto per ridurre le collisioni

h = pow(d, m-1, q) # h = d^(m-1) % q

p_hash = 0 # Hash per il pattern

t_hash = 0 # Hash per la fnestra corrente del testo

result = []

# Calcola gli hash iniziali per il pattern e per la prima fnestra di testo

for i in range(m):

p_hash = (d * p_hash + ord(pattern[i])) % q 2

t_hash = (d * t_hash + ord(text[i])) % q

# Scorre il testo per confrontare le fnestre

for s in range(n - m + 1):

# Se gli hash corrispondono, controlla carattere per carattere

if p_hash == t_hash:

if text[s:s+m] == pattern:

result.append(s)

# Calcola l'hash per la fnestra successiva: rimuove il carattere in uscita ed aggiunge quello in

entrata

if s < n - m:

t_hash = (t_hash - ord(text[s]) * h) * d + ord(text[s + m])

t_hash %= q # Assicura che t_hash rimanga nel range [0, q-1]

return result

# Esempio di utilizzo:

if __name__ == "__main__":

text = "GEEKS FOR GEEKS"

pattern = "GEEK"

result = rabin_karp_search(text, pattern)

print("Rabin-Karp: Il pattern è stato trovato alle posizioni:", result)

8.5.5. Algoritmo di Aho-Corasick

Utilizza come tecnica la ricerca simultanea di più pattern, migliorando quindi la

complessità, che equivale a: O(n+m+z).

from collections import deque, defaultdict

class AhoCorasickNode:

def __init__(self):

self.children = {} # Dizionario: carattere -> AhoCorasickNode

self.fail = None # Failure link

self.output = [] # Lista di pattern che terminano in questo nodo

class AhoCorasick:

def __init__(self, patterns):

self.root = AhoCorasickNode()

self.build_trie(patterns)

self.build_failure_links() 2

def build_trie(self, patterns):

"""Inserisce tutti i pattern nel trie."""

for pattern in patterns:

node = self.root

for char in pattern:

if char not in node.children:

node.children[char] = AhoCorasickNode()

node = node.children[char]

node.output.append(pattern)

def build_failure_links(self):

"""Costruisce i failure links del trie utilizzando la BFS."""

queue = deque()

# Imposta il failure link dei fgli della radice a radice stessa

for child in self.root.children.values():

child.fail = self.root

queue.append(child)

while queue:

current_node = queue.popleft()

for char, child in current_node.children.items():

# Trova il failure link per il nodo chi