[OT] Progetto a lungo termine in C++

[RooccoXXI]

Ciao a tutti.

Avrei voglia di creare qualcosa di utile in C++ (non necessariamente qualcosa di innovativo), per mantenermi un po' allenato nell'ambito della programmazione. Inoltre mi piacerebbe che fosse qualcosa che andrebbe anche documentato o spiegato (contenente magari anche un [bel] po' di matematica), così da continuare a utilizzare anche LaTeX.

Tutto questo perché è appena finito il mio lavoro di fine liceo, ma all'università manca ancora parecchio e non vorrei far arrugginire le mie conoscenze o perdere l'allenamento.

Il problema è che non ho nessuna idea di cosa "creare" (difficile mettere assieme "lungo" e "non troppo complesso"). Qualcuno ha qualche idea/proposta?!

[GliderKite]

Premettendo che la tua richiesta sembra decisamente troppo vaga, ti butto giù un paio di idee (mi sono venute in mente giusto perchè non è passato molto tempo da quando ci ho messo mano).

Tieni presente però che per fare quello che sto per indicarti ti servirebbe un minimo di base teorica, anche perchè senza queste faresti comunque poca strada. Non basta limitarsi alla conoscenza di un linguaggio in se per poterne sfruttare a pieno la potenza.

1) Sviluppare un applicazione che basandosi su un algoritmo di tipo greedy utilizzi l'algoritmo di Huffman per comprimere file utilizzando in parallelo un algoritmo che crittografi l'informazione possibilmente tramite l'aggiunta di rumore per mezzo di funzioni pseudocasuali riproducibili (una sorta di funzione di hash modulare, adattata solo teoricamente, al caso in questione).

2) Visto che non è STL, implementare un container che raggruppi (nel modo più standard, sicuro, ed efficiente possibile) la possibilità di utilizzo di strutture dati (ADT di prima categoria) quali: BST, 2-3-4 top-down (magari tramite RedBlak) e BTree. Lo sviluppo di un contenitore del genere sarebbe, a mio parere, molto interessante, visto che io in giro di queste cose non ne ho trovate.

[deleted_29]

Originariamente inviato da GliderKite

1) Sviluppare un applicazione che basandosi su un algoritmo di tipo greedy utilizzi l'algoritmo di Huffman per comprimere file utilizzando in parallelo un algoritmo che crittografi l'informazione possibilmente tramite l'aggiunta di rumore per mezzo di funzioni pseudocasuali riproducibili (una sorta di funzione di hash modulare, adattata solo teoricamente, al caso in questione).

Ma che senso ha? Non puoi comprimere un "qualcosa" che è stato criptato (vagamente bene), lo dice Shannon
Prima lo comprimi, poi lo cripti.
Interamente, o a blocchi.

2) Visto che non è STL, implementare un container che raggruppi (nel modo più standard, sicuro, ed efficiente possibile) la possibilità di utilizzo di strutture dati (ADT di prima categoria) quali: BST, 2-3-4 top-down (magari tramite RedBlak) e BTree. Lo sviluppo di un contenitore del genere sarebbe, a mio parere, molto interessante, visto che io in giro di queste cose non ne ho trovate.

significa reinventare la ruota.

---
modesto suggerimento: cercati un qualsiasi cosa che puoi VENDERE.

[MItaly]

Originariamente inviato da GliderKite
2) Visto che non è STL, implementare un container che raggruppi (nel modo più standard, sicuro, ed efficiente possibile) la possibilità di utilizzo di strutture dati (ADT di prima categoria) quali: BST, 2-3-4 top-down (magari tramite RedBlak) e BTree. Lo sviluppo di un contenitore del genere sarebbe, a mio parere, molto interessante, visto che io in giro di queste cose non ne ho trovate.

[Parzialmente OT] http://stackoverflow.com/questions/2...ree-containers [/Parzialmente OT]

[deleted_29]

Originariamente inviato da MItaly
[Parzialmente OT] http://stackoverflow.com/questions/2...ree-containers [/Parzialmente OT]

[totalmente OT]: quando iniziai a studiare il C++ la STL neppure esisteva ( o meglio non era mai stata rilasciata al pubblico ) si dava per scontato che "chiunque" sapesse (nel senso "dovesse avere la capacità, altriment meglio cambiar strada) scriversela [/totalmente OT]

[MItaly]

Originariamente inviato da franzauker
[totalmente OT]: quando iniziai a studiare il C++ la STL neppure esisteva ( o meglio non era mai stata rilasciata al pubblico ) si dava per scontato che "chiunque" sapesse (nel senso "dovesse avere la capacità, altriment meglio cambiar strada) scriversela [/totalmente OT]

[ancora più OT] non ne dubito, dicevo soltanto che contenitori implementati come alberi nella STL sono effettivamente inclusi [/ancora più OT]

[RooccoXXI]

Originariamente inviato da GliderKite
Premettendo che la tua richiesta sembra decisamente troppo vaga, ti butto giù un paio di idee (mi sono venute in mente giusto perchè non è passato molto tempo da quando ci ho messo mano).

Tieni presente però che per fare quello che sto per indicarti ti servirebbe un minimo di base teorica, anche perchè senza queste faresti comunque poca strada. Non basta limitarsi alla conoscenza di un linguaggio in se per poterne sfruttare a pieno la potenza.

1) Sviluppare un applicazione che basandosi su un algoritmo di tipo greedy utilizzi l'algoritmo di Huffman per comprimere file utilizzando in parallelo un algoritmo che crittografi l'informazione possibilmente tramite l'aggiunta di rumore per mezzo di funzioni pseudocasuali riproducibili (una sorta di funzione di hash modulare, adattata solo teoricamente, al caso in questione).

2) Visto che non è STL, implementare un container che raggruppi (nel modo più standard, sicuro, ed efficiente possibile) la possibilità di utilizzo di strutture dati (ADT di prima categoria) quali: BST, 2-3-4 top-down (magari tramite RedBlak) e BTree. Lo sviluppo di un contenitore del genere sarebbe, a mio parere, molto interessante, visto che io in giro di queste cose non ne ho trovate.

Le tue proposte non sono male. Però io pensavo più a qualche classe (o magari addirittura a qualche libreria! ) matematica (non estremamente complessa). Qualche idea in questo senso?!

[GliderKite]

Originariamente inviato da franzauker
Ma che senso ha? Non puoi comprimere un "qualcosa" che è stato criptato (vagamente bene), lo dice Shannon
Prima lo comprimi, poi lo cripti.
Interamente, o a blocchi.

Non ti rispondo nemmeno perchè mi fai pensare ad qualcuno che o non capisce quello che legge o non se ne rende conto perchè non sa di cosa si sta parlando.


@MItaly: Ho letto il tuo link, però mi restano alcuni dubbi, se potessi aiutarmi te ne sarei grato.

1) Se avessi bisogno di un contenitore che, se costruito con N chiavi casuali, abbia una search-hit che richieda meno di 2 ln(N) confronti, e che soprattutto mi permetta di poter inserire un nuovo nodo come nuovo primo elemento del contenitore a chi dovrei rivolgermi?

2) Se avessi bisogno di unire due contenitori (che mi offrano le caratteristiche di cui parlavo prima) in modo tale che l'operazione di join abbia nel caso peggiore complessità O(n)?

3) Se avessi invece bisogno di un semplice contenitore che abbia le caratteristiche di BST randomizzato, o di uno splay BST, dove posso cercare?

4) Non ho idea di come siano stati implementati set e map, per ora non ho visto niente, ma che tu sappia garantiscono effettivamente che ogni link nullo appartenga ad un nodo che abbia la stessa distanza dalla radice di tutto gli altri? Cioè in pratica, mediamente, i confronti per effettuare una ricerca possono dirsi inferiori a k ln(N) confronti (con N numero di chiavi inserite casuali, e K minore di 1)?

5) Se cosi fosse quanto bisognerebbe "pagare" in memoria aggiuntiva per garantire queste caratteristiche?

6) Ma vediamo a cose più serie: dove posso trovare un contenitore che sia in grado di garantirmi la possibilità di poter decidere quale sia il suo ordine (M-ario) e soprattuto in grado di garantirmi che la ricerca richieda un numeo di sondaggi compreso tra log (base M) N e log (base M/2) (N), praticamente un numero costante per ogni qualsivoglia scopo pratico. Dove M è appunto l'ordine ed N il numero di elementi.



@RoccoXII
Ho provato a proporti quello che mi era venuto subito in mente, dovresti specificare meglio cosa intendi per matematica perchè è un campo decisamente vasto. Ma forse dovresti chiedere a persone come franzauker che dall'alto della loro onniscenza sarebbero capaci di risponderti con grandi parole, che però nello specifico non significano niente. Discussione chiusa. Naturalmente se vuoi qualche chiarimento chiedi pure.

[MItaly]

@GliderKite: ora non ho tempo per documentarmi su tutto, comunque le complessità asintotiche di tutte le operazioni sui container STL sono specificate nello standard (di cui puoi trovare le bozze gratuitamente un po' dovunque), che tuttavia non impone un'implementazione sottostante specifica, ma dice appunto solo gli O grandi delle operazioni (poi vabbé, in genere c'è un solo modo di implementare i vari container in modo che abbiano quelle complessità asintotiche).

@RooccoXXI: se vuoi lavorare per la gloria, potresti dare un'occhiata alla boost wishlist. Se vuoi fare soldi, non saprei che suggerirti.

[alka]

Visto che dall'OT siamo andati ancora più OT fino a sfociare nel più profondo OT, chiudo.

Ricordo che l'OT in questa sezione deve essere comunque vagamente correlato all'argomento principale: può essere OT chiedere lumi su un problema che affligge il compilatore che si sta usando, ad esempio, anche se non riguarda nello specifico un errore riscontrato nel proprio codice sorgente, ma chiedere la musica preferita che si ascolta quando si programma, o il gusto delle patatine che si mangiano mentre si scrive il codice, o quale progetto realizzare per espandere le proprie conoscenze, sono tutti argomenti troppo "esterni", che andrebbero affrontati in Discussioni off topic (sezione frequentata anche da utenti che partecipano a quest'area del forum).