Algoritmi - Quali sono gli algoritmi essenziali per le olimpiadi informatiche?

Forum - Algoritmi - Quali sono gli algoritmi essenziali per le olimpiadi informatiche?

Pagine: [ 1 2 ]

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 10:08
Sabato, 12/12/2009

Salve,
dato che sono un autodidatta vorrei sapere quali sono gli algoritmi necessari per non ritrovarsi sprovveduti alle olimpiadi di informatica.
Come ad esempio quelli sui grafi, ordinamento, ecc.

Grazie.

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 10:13
Sabato, 12/12/2009

Mi è capitato di trovare Dijkstra per i grafi e poi a volte ci sono problemi di backtracking (problema delle N regine), o problemi NP come il TSM (Travelling Sales Man), il Knapsack Problem e poi algoritmi vari, come il classicissimo MCD, algoritmi di fattorizzazione, tecnica del minimax, minimum spanning tree, e qualche altro famoso...

insomma, aspettati cose non banali (se arrivi alle nazionali), altrimenti vanno bene anche gli algoritmi di base per il sorting e un po' di inventiva...

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 10:44
Sabato, 12/12/2009

Non sono ancora riuscito a capire il Dijkstra... Adesso riprovo.... (Cmq sembra molto carino e utile)

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 10:52
Sabato, 12/12/2009

Capito... ma come diavolo si può implementare? Non sembra affatto facile. Comunque questo algoritmo è davvero furbo XD

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 10:52
Sabato, 12/12/2009

beh, se te lo implemento io, poi dividiamo a metà il premio delle olimpiadi?
devi fare tutto da solo, mi spiace

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 11:32
Sabato, 12/12/2009

lo so, comunque su internet ho trovato qualche implementazione ma...

va be oggi cercherò di farcela...

cmq grazie per la risposta

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 21:22
Sabato, 12/12/2009

http://www.cs.berkeley.edu/~vazirani/algorithms.html

Ottimo libro per capire gli algoritmi.

Il mio blog: https://piero.dev

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 10:06
Domenica, 13/12/2009

bel link. Grazie mille

netarrow (Admin)
Guru^2

Messaggi: 2502
Iscritto: 12/05/2004

Postato alle 13:13
Domenica, 13/12/2009

Se vuoi leggere la bibbia sugli algoritmi ti consiglio Introduzione agli Algoritmi e Strutture Dati

Ha un approccio esageratamente matematico forse, ma è il testo più completo e fra gli autori c'è anche un certo Rivest

Pagine: [ 1 2 ]