[Vari] Un piccolo aiuto per esame di progettazione algoritmi

[Dani88]

Raga tra 3 gg ho l'esame di progettazione algoritmi e sto facendo un po di esercizi. Me ne sono capitati alcuni in cui proprio non so come diavolo fare e mi ci sto picchiando. Mi potreste dare delle dritte?
Il "linguaggio" che usiamo è pseudocodice misto c++ ad es

for (v appartenente a A[]) do
  ...

Vi metto le specifiche dei problemi in cui trovo difficoltà:

1) Dato un grafo aciclico orientato i cui vertici sono delle attività ed esiste un arco (i,j) se l'attività i deve essere svolta prima di j, verificare per un assegnamento di attività (ad esempio viene dato un vettore di attività) se esso soddisfa le relazioni di cui prima.
In pratica se nell'assegnamento ad un certo punto mi trovo che j è prima di i nell'assegnamento non è soddisfatto).
Un mio amico che l'ha dato mi ha detto:
"Potevi usare matrice delle diacenze o lista delle adiacenze (permetteva di usare le primitive tipo adj[v] e simili). Io ho messo l'ipotesi che mi restituisse quelli adiacenti e connessi direttamente, cioè solitamente adj[v] mi restituisce i vertici connessi tramite un solo arco a v (ovvero i vertici vicini a v), in più metto l'ipotesi che mi restituisca solo quelli che ricevono l'arco da v (ovvero mi da i vertici adiacenti a v il cui arco parte da v e arriva nel suddetto vertice) quindi solo le attività successive)"

2) E’ dato un dizionario con n parole di lunghezza massima k. Scrivere un algoritmo che, scelta una parola, cerca nel dizionario tutti i suoi anagrammi.
L'algoritmo deve essere fatto possibilmente in modo che sia O(n) ipotizzando k costante.

Il primo ho provato a farlo non so quante volte ma non riesco proprio...soprattutto seguendo il consiglio. Il secondo invece non capisco come faccio per farlo in O(n)

[banryu79]

Originariamente inviato da Dani88

Il primo ho provato a farlo non so quante volte ma non riesco proprio...soprattutto seguendo il consiglio. Il secondo invece non capisco come faccio per farlo in O(n)

Posta il tuo pseudocodice sia del primo esercizio che del secondo; in questo modo avrai molte più possibilità che qualcuno ti risponda perchè:
1) avendo la tua implementazione davanti agli occhi, chi è più esperto può darti dei consigli/suggerimenti mirati, in modo che tu capisca l'errore/gli errori.
2) è più probabile che qualcuno si fermi a leggere il pseudocodice cercando appunto quello che non funziona, piuttosto che mettersi a fare un post scrivendoti le soluzioni complete, anche perchè su questo forum è vietato dare soluzioni complete agli esercizi.

[Dani88]

no no ma infatti io nn volevo la soluzione, solo qualche suggerimento, consiglio, dritta su cm svilupparlo...anche perchè nn mi serve la pappa pronta, sennò nn capisco e nn mi è di aiuto

[banryu79]

Originariamente inviato da Dani88

no no ma infatti io nn volevo la soluzione, solo qualche suggerimento, consiglio, dritta su cm svilupparlo...anche perchè nn mi serve la pappa pronta, sennò nn capisco e nn mi è di aiuto

Perfetto, se hai prodotto del pseudocodice, anche incompleto, postalo che qualcuno ti aiuterà

[gugoXX]

Originariamente inviato da Dani88

2) E’ dato un dizionario con n parole di lunghezza massima k. Scrivere un algoritmo che, scelta una parola, cerca nel dizionario tutti i suoi anagrammi.
L'algoritmo deve essere fatto possibilmente in modo che sia O(n) ipotizzando k costante.

Il primo ho provato a farlo non so quante volte ma non riesco proprio...soprattutto seguendo il consiglio. Il secondo invece non capisco come faccio per farlo in O(n)

Prendi la tua parola e ordina i caratteri in ordine alfabetico.
Scorri tutto il dizionario ( O(n) ) per ciascuna parola ordini i suoi caratteri in ordine alfabetico, confronti le 2 stringhe ordinate e se sono uguali allora e' un anagramma (o addirittura identica)

E' quindi in realta' un
O ( n * m Log m)
dove m e' la lunghezza media di ciascuna parola.
m Log m si puo' ritenere trascurabile, essendo la lunghezza delle parole di parecchi ordini di grandezza inferiore alla lunghezza di un dizionario tipico.

Detta in altri termini, sarebbe O(n k log k), ma supponendo k costante come tutte le costanti se ne va.

[Dani88]

Originariamente inviato da gugoXX

Prendi la tua parola e ordina i caratteri in ordine alfabetico.
Scorri tutto il dizionario ( O(n) ) per ciascuna parola ordini i suoi caratteri in ordine alfabetico, confronti le 2 stringhe ordinate e se sono uguali allora e' un anagramma (o addirittura identica)

E' quindi in realta' un
O ( n * m Log m)
dove m e' la lunghezza media di ciascuna parola.
m Log m si puo' ritenere trascurabile, essendo la lunghezza delle parole di parecchi ordini di grandezza inferiore alla lunghezza di un dizionario tipico.

Detta in altri termini, sarebbe O(n k log k), ma supponendo k costante come tutte le costanti se ne va.

Sembrerebbe simile a quanto facevo io...prendevo la prima lettera e cercavo nel dizionario una parola che ce l'avesse, poi una volta trovata guardavo se erano presenti anche le altre lettere, appena trovata una che non c'era passavo alla parola dopo...però a me la complessità viene diversa...
Una cosa però: ordinando alfabeticamente non mi aumenta la complessità? xkè se lo faccio basato sul confronto non posso scendere sotto a O(n lg n).

Per il primo io avevo avuto questa mezza idea qui:
poniamo che le attività siano in un vettore, ciascuna attività del grafo ha un campo ind che inizialmente inizializzo a infinito

for (v appartenente all’assegnamento){   //per ogni attività del vettore
	i++;
   	ind[v]=i;
   	for (w appartenente ad adj[v])
   	   // qui mi blocco: l'idea è di fare un confronto, ad ese
   	   if (ind[w]<ind[v]) return false
           //però non va bene...
return true

[Dani88]

# EDIT (non serve )

[Dani88]

Raga questo è un altro esercizio

Fare algoritmo per vedere se un grafo G orientato era ciclico o aciclico 
(con dfs) e analisi

secondo voi è corretto la modifica che ho fatto all'algoritmo DFS?

**  DFS(G)
**    for each u  appartenente a G
**      color(u) = WHITE
**    for each u  appartenente a G
**      if color(u)=WHITE then 
	return DFS_VISIT(u)
**
**  DFS_VISIT(u)
**    color(u) = GREY
**    for each v  adj[u]
**      if color(v)=WHITE then DFS_VISIT(v)
**      if color(v)=GREY then return cyclic //perchè vuol dire che sono tornado indietro
**    colore(u) =BLACK  //metto nero se tutti qll vicini non sono più bianchi
**    return NIL

Analisi:
Supponendo V numero di vertici ed E numero di archi faccio V assegnamenti di 
inizializzazione, quindi O(V), poi DFS_VISIT la chiamo per ciascun nodo e il suo
 costo è determinato dal costo di esaminare la lista di adiacenza adj[u] dunque 
il tempo totale è sommatora(v∈ V) di |Adj[v]| = O(E)
Quindi la complessità finale risulta O(V*E)  
(qui sono incerto se è O(V*E) oppure O(V+E)...)