Consiglio libro algoritmi

di il
18 risposte

Consiglio libro algoritmi

Ho deciso di studiare algoritmi e strutture dati anche per fare esercizi di programmazione, ho trovato questo libro: che sembra essere buono e se non ho capito male è la versione italiana di questo: https://www.amazon.it/Introduction-Algorithms-Thomas-H-Cormen/dp/0262533057/ref=sr_1_2?ie=UTF8&qid=1543849547&sr=8-2&keywords=algorithms
In base alle vostre conoscenze mi consigliereste la versione italiana o la versione inglese? Lo chiedo principalmente per i contenuti, di solito le versioni italiane dei libri inglesi sono più ridotte.

18 Risposte

  • Re: Consiglio libro algoritmi

    Il libro che hai scelto è diffuso in ambito universitario ,per fare esercizi ti consiglierei di dare un occhio anche a Programmazione in C di King
  • Re: Consiglio libro algoritmi

    Sai, quel libro lì ce l'ho già, avendo esaurito gli esercizi, volevo passarre a fare qualcosa di più serio e produttivo.
  • Re: Consiglio libro algoritmi

    Definisci serio e produttivo.

    Ad esempio:

    potrebbe andare bene?

    O questo:
    https://www.amazon.it/Combinatorial-Optimization-Algorithms-Combinatorics-English-ebook/dp/B00FC7HIWY/ref=sr_1_3?ie=UTF8&qid=1543859005&sr=8-3&keywords=optimization
  • Re: Consiglio libro algoritmi

    Quelli che mi hai consigliato sicuramente sono ottimi libri, ma credo siano settoriali, a me serve una bella panoramica sulla teoria degli algoritmi, quelli mi sembrano troppo specifici. Co'è la convex optimization? Chiedevo infatti se il libro di cormen andasse bene per iniziare seriamente e poi il criterio per cercare libri che trattano algoritmi specifici.
  • Re: Consiglio libro algoritmi

    Https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK3/NODE125.HTM

    Inizia con il Cormen. Se e quando sarai arrivato alla fine, ed avrai capito tutto, forse ti renderai conto che la richiesta non ha molto senso.

    L'ottimizzazione convessa e' si settoriale, ma e' uno degli argomenti che studierai all'universita', cosi' come statistica, algebra astratta, teoria dei grafi, ricerca operativa, machine learning, teoria dei codici, crittografia, intelligenza artificiale, ...

    In pratica, ogni algo e' settoriale.

    Solo per gli algo di ricerca di una sottostringa c'e' un intero mondo.
    L'algo che conoscerai, se lo conosci, e' stupido. Ci sono algo ben piu' efficienti ed intelligenti

    Sempre se sceglierai un corso decente e non qualche corsetto all'acqua di rose, perche' 'gli altri sono troppo difficili'.

    Toh, ti do un problemino: generare tutti i sottoinsiemi di un insieme dato, ordinato per dimensione (se no, era facile )

    {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

    e provalo con 20 elementi O con 30
  • Re: Consiglio libro algoritmi

    Grazie innanzitutto per il link e i consigli. Vorrei scegliere un buon corso di laurea in informatica, sapresti consigliarmi quali sono le università più serie? Comunque, guardando un pò i piani di studi delle vari facoltà di informatica, ho visto che molti argomenti da te elencati non ci sono, per es. teoria dei grafi, teoria dei codici, crittografia. Molto probabilmente sono argomenti da studiare da soli, o fare corsi specifici, ma fuori dall'università.
    Proverò a svolgere il tuo problemino.
  • Re: Consiglio libro algoritmi

    Riprendo la discussione dopo un po di tempo, ora che ho più tempo da dedicare alla programmazione.
    Come richiesto da migliorabile ho risolto il problemino con un approccio iterativo.
    
    #include <iostream>
    using namespace std;
    
    bool combinazione_succ(int num_ele, int k, int *u)
    {
    	for (int i = 0; i < k; i++)
    	{
    		if (u[k - i - 1] < num_ele - i - 1) 
    		{
    			u[k - i - 1]++;
    			for (int j = k - i; j < k; j++)
    			{
    				u[j] = u[j - 1] + 1;
    			}
    			return true;                                      
    		}
    	}
    	return false;
    }
    
    
    int main()
    {
    	const int n = 5;
    	const int k = 3;
    	int v[n] = { 1, 2, 3, 4, 5 };
    	int u[k] = { 0, 1, 2 };
    		do
    		{
    			for (int i = 0; i < k; ++i)
    			{
    				cout << v[u[i]] << " ";
    			}
    			cout << endl;
    		} while (combinazione_succ(n, k, u));
    
        return 0;
    }
    
    Sicuramente esiste un modo più intelligente per farlo, magari qualche tecnica avanzata. Per questo vorrei sapere a quale categoria di algoritmi appartiene questo e in che libri si possono trovare così da approfondire l'argomento.
  • Re: Consiglio libro algoritmi

    @ migliorabile, vedo che hai letto, ma non hai risposto. Non hai proprio nulla da dirmi?
  • Re: Consiglio libro algoritmi

    La tua implementazione non centra nulla con quello che avevo chiesto.
    Ma non fa niente. Tanto era solo un esercizio.

    Non esiste una ""particolare"" categoria per questo tipi di algoritmi.
    Diciamo che fa parte di quella categoria di algoritmi che hanno a che fare con la Teoria dei Numeri, la Matematica Discreta, o, ancora, dei Problemi di tipo Combinatorio.

    In particlare, questo ""particolare"" modo di rappresentare un insieme fa uso di un sistema di rappresentazione dei numeri che si chiama "Combinatorial Number System"

    https://en.wikipedia.org/wiki/Combinatorial_number_system

    Come ben sai, i numeri si possono rappresentare in base 10, 2, 8, 16.

    Ma chi ha detto che si possono rappresentare SOLO con queste basi?

    Puoi usare un QUALUNQUE numero intero.

    Ma chi ha detto che deve essere solo uno?

    Un istante nel tempo puo' essere rappresentato come: (anno,mese,giorno,ora,minuto,secondo)

    Supponiamo, tanto per semplificare, che i mesi siano 0..11, tutti i mesi abbiano 30 giorni ed i giorni siano 0..29.

    In questo caso, cosa rappresenta la data (0,0,0,0,0,0) ? BANALMENTE il numero 0. E' ovviamente puoi continuare!

    In pratica stai rappresentatndo un intero con una base MISTA.

    Ma chi ha detto che deve per forza essere un numero FINITO di basi? Nessuno, ed infatti potresti usare
    - i numeri di fibonacci
    - i numeri primi
    - i numeri combinatori (basati sul coefficiente binomiale)

    Ma chi ha detto che devono essere tutti positivi? Ed in fatti si pososno usare sia positivi che negativi

    ecc.


    Questo per dire che NON BASTA inventarsi una soluzione, bisogna anche STUDIARE e CERCARE per vedere che cosa e' gia' stato fatto/scritto.

    Il 99% di quello che ti servira' sul posto del lavoro non lo hai studiato all'universita'.

    Ma NON E' perche' l'unversita' non insegna quello che serve per lavorare.
    E' dovuto BANALMENTE al fatto che OGNI azienda ha le sue necessita' e sarebbe IMPOSSIBILE insegnare tutto quello che serve per QUALUNQUE azienda. Ma NEMMENO per un sottoinsieme MINUSCOLO di aziende.

    Compito dell'universita' e' insegnare le BASI FONDAMENTALE dalle quali partire per imparare DA SOLI quello che manca.
    E per fare questo, ti insegna anche come AFFRONTARE il problema di COME imparare le cose che non sai. Attraverso i LIBRI.


    Piccola nota spicciola: PERCHE' i Maya pensavano che la fine del mondo avvenisse il 21 dicembre 2012?

    La risposta e' legata a come loro rappresentavano le date.
    Il calendario Maya e un calendario a 5 posizioni in base mista (un mix di 12, 18 e 20), MA l'a posizione corrispondete, in qualche modo, al "millennio" (erano dei GRANDI! Ragionavano in termini di millenni, NON di anni come i nostri politici ), e' in base 13, con le cifre che vanno da 0 a 12.

    Il 20 dicembre 2012 corrisponde alla data Maya[12, 19, 19, 17, 19]
    Il 21 dicembre 2012 corrisponde alla data Maya[13, 0, 0, 0, 0]

    MA loro non conoscevano il numero 13, per quella particolare posizione, e quindi non sarebbero stati in grado di rappresentarlo.
    OVVIAMENTE non usavano le cifre ma degli ideogrammi

    http://dm.unife.it/storia/maya.ht

    Mentre, ad esempio, la data Maya corrispondente a Maya[0,0,0,0,0] corrisponde al 11 agosto del 3113 Avanti Cristo (Prima di Cristo)

    Per le curiosita' sui calendari, c'e' questo:



    NON ragionare in termini moderni. Nel mediovevo non avevano i computer e quindi non avrebbero avuto un termine per descriverli.
    Se non c'e' una parola per descrivere qualcosa, vuol dire che non conosci nemmeno l'esistenza di quel qualcosa.


    Nota finale: queste cose non le ho studiate all'universta'! Ma e' un mix tra curiosita' e problemi al lavoro che ho risolto CERCANDO e STUDIANDO.
  • Re: Consiglio libro algoritmi

    Ok, in pratica questo genere di algoritmi lo si impara studiando quando serve per un compito specifico. Ma il problema dal quale siamo partiti era quello di generare le partizioni di un insieme, che di fatto è un problema combinatorio. Quello che volevo sapere riaguardo la mia implementazione dell'algoritmo era se fosse corretto ed efficace. Ma non sapevo l'esistenza dei numeri combinatori, quindi il problema si potrebbe risolvere scrivendo i numeri in un altra base per poterli ordinare più facilmente?
  • Re: Consiglio libro algoritmi

    L'esercizion iniziale NON ERA

    generare le partizioni di un insieme (che e' bello tosto)

    MA

    generare tutti i sottoinsiemi di un insieme dato, ordinato per dimensione (relativamente piu' semplice).

    La tua implementazione e' SBAGLIATA in ogni dimensione.

    AL PIU' sei riuscito a implementare un algoritmo per generale i sottoinsiemi di {1,2,..n} di 3 (diconsi TRE) elementi, con n che DEVE essere maggiore di 3.

    Non chiedere la risposa ad una domanda per la quale PUOI TROVARE TU STESSO la risposta.
    Leggiti la documentazione. Gli agganci ti sono stati dati.
  • Re: Consiglio libro algoritmi

    Si in quel caso la mia implementazione è limitata, ma si può generalizzare a n elementi presi a gruppi di due, di 3... di n-1. Ma l'esempio che mi hai proposto quando mi assegnato l'esercizio faceva pensare proprio alle partizioni di un insieme. (tutto sommato non era così difficile, ma neanche immediato da intuire).
  • Re: Consiglio libro algoritmi

    0) non ti ho assegnato un esercizio. Non era un compito per casa, ovviamente. Era una proposta

    1) non fa nulla anche se hai implementato una cosa totalmente diversa. Sono quelle cose che si fanno nei ritagli di tempo perche' sono simpatiche da fare

    2) la descrizione dell'esercizio e' molto precisa: la puoi interpretare male SOLO se non conosci i termini che sono stati usati. Al piu' si puo' dire che ho usato il termine dimensione (SBAGLIANDO) al posto del termine CORRETTO cardinalita'

    3) la tua implementazione NON E' generale. Dover modificare il codice perche' cambiano i dati NON E' realizzare un algoritmo generale.
    Un algoritmo DEVE ADATTARSI in modo AUTOMATICO ai dati che deve processare.

    Il modo di adattarsi consiste, fondamentalmente, nell'usare loop e ricorsione, che sono le uniche strutture di controllo che possono adattarsi al fatto che una volta devi processare 100 elementi ed un'altra 10.000.
  • Re: Consiglio libro algoritmi

    0) Certo, ma non trovavo il termine più adatto.

    2)Potresti farmi un esempio di cosa intendi per ordinato per dimsione e per cardinalità?

    3)No, la mia implementazione non è generale, è quello che ho detto nel post precedente, ma non è un problema generalizzarlo. Ho postato il codice per un caso particolare solo per mostrare che funziona, anche se l'obiettivo non era quello.
Devi accedere o registrarti per scrivere nel forum
18 risposte