Algoritmi e Strutture dati in Python

Ecco finalmente la guida di algoritmi e strutture dati in ptyhon!

Folder Structure

Tutte le implementazioni degli algoritmi sono nella cartella Algorithms, mentre le implementazioni della strutture dai sono nel cartella Data Strucutres. All'interno di ognuna di queste cartelle sia gli algoritmi che le strutture dati sono raggruppate ognuno in una cartelle che li rappresenta.

Il testing degli algoritmi e strutture dati implementate è nella cartella pytest

Mentre nella cartella resouces contienete tutte le immagini che utilizzate nei README

.
├── README.md
├── .gitignore
├── resources
├── algorithms
├── test
├── resources
└── data_structures

Strutture Dati

B - Beginner, A - Advanced

• B Linked List
• B Double Linked List
• B Circular Double Linked List
• B Queue - versione con array monodimesionale
• B Queue - versione con array circolare
• B Stack
• B Heap

Algoritmi

B - Beginner, A - Advanced

Algoritmi per argomento

• Math

  • A Fibonacci con Programmazione dinamica

• Sorting

  • B Bubble Sort
  • B Selection Sort
  • B Insertion Sort
  • B Heap Sort
  • B Merge Sort
  • B Quicksort - versione normale e anche la versione randomizzata
  • B Counting Sort

• Sets

  • B Maximum Subarray - versione ricorsiva
  • A Maxium Subarray - versione iterativa

• Searching

  • B Binary Search/ ricerca dicotomica
  • B Linear Search/ ricerca sequenziale
  • B Jump Search
  • B Interpolation Search
  • B Random Search
  • B Scramble Search

Algoritmi per paradigma

• Forza Bruta
  • A Linear Search
• Algoritmi Golosi (Greedy Algorithms)
• Dividi et Impera
  • A Merge Sort
  • A Quick Sort
  • A Max SubArray
  • A Moltiplicazione Matrici
• Programmazione Dinamica
  • B Fibonacci (versione programmazione dinamica)
  • A Problema dello ziano 0/1
  • A Maxsub Array(Kandane algorithm)
• Backtraking

Nozioni Basilari

Dato che per risolvere un determinato problemo molto spesso esistono molteplici algoritmi risolutori, il problema che si pone è quello di riuscire a trovare un algoritmo corretto in modo tale da portelo confrontare con un altro algoritmo anch'esso corretto e poter decidere quale sia il "miglore" per risolvere lo stesso problema.

Per fare ciò c'è bisogno di introdurre un concetto basilare che rigurda lo studio degli algoritmi cioè: la complessità computazionale

Complessità Computazionale

La complessità computazionale è lo studio della quantità di risorse (memoria e tempo di calcolo) necessari a un certo algoritmo per risolvere un problema dato.

Quindi teoricamente per ogni input bisognerebbe studiare quello che è il tempo di esecuzione di un algoritmo, ma i teorici dell’informatica hanno introdotto delle notazioni che permettono di semplificare la rappresentazione della complessità computazionale di un algoritmo.

Infatti hanno notato che il fattore determinante che ci permette di scegliere l'algoritmo migliore è il suo tasso di crescita. Per tasso di crescita si intende la velocità con cui cresce il tempo di esecuzione all'aumentare della dimensione dell'input al limite, quando la dimensione dell'input cresce senza limitazioni. Questo si chiama anche studiare l'efficenza asintotica degli algoritmi.

Le notazioni che si usano per descrivere il tempo di esecuzione asintotico sono definite in termini di funzioni il cui dominio è l'insieme dei numeri naturali. Tali notazioni sono comode per descrivere la funzione T(n), tempo di esecuzione dell'algoritmo, che di solito è definita soltanto con dimensioni intere dell'input.

Notazione Θ

Per una data funzione g(n), indichiamo con Θ(g(n)) l'insieme delle funzioni

Θ(g(n)) = { f(n) : esistono delle costanti positive c₁, c₂ e n₀ tali che 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) per ogni n ≥ n₀ }

Graficamente succede questo:

g(n) è un limite asintoticamente stretto per f(n)

Notazione O

Per una data funzione g(n), indichiamo con O(g(n)) l'insieme delle funzioni

O(g(n)) = { f(n) : esistono delle costanti positive c e n₀ tali che 0 ≤ f(n) ≤ cg(n) per ogni n ≥ n₀ }

Graficamente succede questo:

g(n) è un limite asintoticamente superiore (stretto) per f(n)

Notazione Ω

Per una data funzione g(n), indichiamo con Ω(g(n)) l'insieme delle funzioni

Ω(g(n)) = { f(n) : esistono delle costanti positive c e n₀ tali che 0 ≤ cg(n) ≤ f(n) per ogni n ≥ n₀ }

Graficamente succede questo:

g(n) è un limite asintoticamente inferiore (stretto) per f(n)

Contribuizione

Si prega di leggere CONTRIBUTING.md per i dettagli sul codice di condotta e il processo di invio delle richieste pull.

Todo

• Da migliorare la sezione delle notazioni basilari
• aggingere readme stastistiche d'ordine
• aggiunge i nuovi algoritmi alla lista iniziale

Algoritmi

• Radix sort
• Bucket sort
• Sequenza moltiplicazioni matrici (Dynamic Programming)
• Greedy Algorithms
• Algoritmi Programmazione dinamica

Strutture dati

• ALberi
  • Alberi binari
  • Alberi Radicati
  • Alberi rosso/neri
• Trie
• Tavole Hash

Test

• stack
• coda
• Dividi et impera algorithms
• counting sort
• Dynamic Programming algorithms