Un algoritmo è una tecnica computazionale sequenziale ben definita che accetta un valore o una raccolta di valori come input e produce gli output necessari per risolvere un problema.

Oppure possiamo dire che un algoritmo si dice accurato se e solo se si ferma con l'output corretto per ciascuna istanza di input.

NECESSITÀ DEGLI ALGORITMI:

Gli algoritmi vengono utilizzati per risolvere problemi o automatizzare attività in modo sistematico ed efficiente. Sono un insieme di istruzioni o regole che guidano il computer o il software nell'esecuzione di un compito particolare o nella risoluzione di un problema.

trova nella stringa c++

Ci sono diversi motivi per cui utilizziamo gli algoritmi:

Efficienza: gli algoritmi possono eseguire attività in modo rapido e accurato, rendendoli uno strumento essenziale per attività che richiedono molti calcoli o elaborazione di dati. Coerenza: gli algoritmi sono ripetibili e producono risultati coerenti ogni volta che vengono eseguiti. Questo è importante quando si ha a che fare con grandi quantità di dati o processi complessi. Scalabilità: gli algoritmi possono essere scalati per gestire set di dati di grandi dimensioni o problemi complessi, il che li rende utili per applicazioni che richiedono l'elaborazione di grandi volumi di dati. Automazione: gli algoritmi possono automatizzare attività ripetitive, riducendo la necessità di intervento umano e liberando tempo per altre attività. Standardizzazione: gli algoritmi possono essere standardizzati e condivisi tra diversi team o organizzazioni, rendendo più semplice la collaborazione e la condivisione delle conoscenze.

Nel complesso, gli algoritmi sono uno strumento essenziale per risolvere problemi in una varietà di campi, tra cui l’informatica, l’ingegneria, l’analisi dei dati, la finanza e molti altri.

Esempio:

Considera una scatola in cui nessuno può vedere cosa sta succedendo all'interno, diciamo una scatola nera.

Diamo input alla casella e questa ci fornisce l'output di cui abbiamo bisogno, ma la procedura che potremmo aver bisogno di conoscere dietro la conversione dell'input nell'output desiderato è un ALGORITMO.

Un algoritmo è indipendente dal linguaggio utilizzato. Indica al programmatore la logica utilizzata per risolvere il problema. Quindi, è una procedura logica passo dopo passo che funge da modello per i programmatori.

Esempi di vita reale che definiscono l'uso degli algoritmi:

• Consideriamo un orologio. Sappiamo che il tempo scorre, ma come fa il produttore a impostare dadi e bulloni in modo che continui a muoversi ogni 60 secondi, la lancetta dei minuti dovrebbe muoversi e ogni 60 minuti, la lancetta delle ore dovrebbe muoversi? Quindi per risolvere questo problema, deve esserci un algoritmo dietro.
• Hai visto qualcuno cucinare il tuo cibo preferito per te? La ricetta è necessaria? Sì, è necessario poiché una ricetta è una procedura sequenziale che trasforma una patata cruda in una patata fredda. Questo è ciò che è un algoritmo: seguire una procedura per ottenere l'output desiderato. È necessario seguire la sequenza? Sì, la sequenza è la cosa più importante da seguire per ottenere ciò che vogliamo.

Tipi di algoritmi:

• Algoritmi di ordinamento: Bubble Sort, ordinamento per inserzione e molto altro. Questi algoritmi vengono utilizzati per ordinare i dati in un formato particolare.
• Algoritmi di ricerca: Ricerca lineare, ricerca binaria, ecc. Questi algoritmi vengono utilizzati per trovare un valore o un record richiesto dall'utente.
• Algoritmi grafici : Viene utilizzato per trovare soluzioni a problemi come trovare il percorso più breve tra le città e problemi della vita reale come i problemi dei venditori ambulanti.

Algoritmi di ordinamento sono algoritmi che prendono una raccolta di elementi e li riorganizzano in un ordine specificato (ad esempio ascendente o discendente). Esistono molti algoritmi di ordinamento diversi, ciascuno con i propri punti di forza e di debolezza. Alcuni degli algoritmi di ordinamento più comunemente utilizzati includono:

Ordinamento delle bolle: Un semplice algoritmo di ordinamento che scorre ripetutamente l'elenco, confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato.

Ordinamento di inserimento: Un semplice algoritmo di ordinamento che costruisce l'array ordinato finale un elemento alla volta, confrontando ogni nuovo elemento con gli elementi che sono già stati ordinati e inserendolo nella posizione corretta.

Ordinamento della selezione: Un semplice algoritmo di ordinamento che seleziona ripetutamente l'elemento minimo dalla parte non ordinata dell'array e lo sposta alla fine della parte ordinata.

Unisci ordinamento: Un algoritmo di ordinamento divide et impera che funziona dividendo l'elenco non ordinato in n sottoelenchi, ordinando ciascun sottoelenco e quindi unendoli nuovamente in un unico elenco ordinato.

Ordinamento rapido: Un algoritmo di ordinamento divide et impera che funziona selezionando un elemento pivot dall'array e suddividendo gli altri elementi in due sottoarray, a seconda che siano minori o maggiori del pivot. I sottoarray vengono quindi ordinati in modo ricorsivo.

Ciascuno di questi algoritmi ha complessità temporali e spaziali diverse, rendendone alcuni più adatti a determinati casi d'uso rispetto ad altri.

Gli algoritmi di ricerca sono algoritmi che cercano un particolare elemento o valore in una struttura dati (come un array o un elenco collegato). Alcuni degli algoritmi di ricerca più comunemente utilizzati includono:

Ricerca lineare: Un semplice algoritmo di ricerca che scorre ogni elemento di un elenco finché non trova una corrispondenza.

Ricerca binaria: Un algoritmo di ricerca che funziona dividendo ripetutamente a metà un elenco ordinato, finché non viene trovato l'elemento desiderato o si determina che l'elemento non è presente.

Salta la ricerca: Un algoritmo di ricerca che funziona saltando avanti di passi fissi nell'elenco, finché non viene trovato un candidato adatto, e poi eseguendo una ricerca lineare negli elementi circostanti.

Ricerca per interpolazione : Un algoritmo di ricerca che funziona utilizzando le informazioni sull'intervallo di valori nell'elenco per stimare la posizione dell'elemento desiderato e quindi verificando che sia effettivamente presente.

Ricerca nella tabella hash: Un algoritmo di ricerca che utilizza una funzione hash per mappare gli elementi sugli indici in un array e quindi esegue ricerche in tempo costante nell'array per trovare l'elemento desiderato.

Ciascuno di questi algoritmi ha complessità temporali e spaziali diverse, rendendone alcuni più adatti a determinati casi d'uso rispetto ad altri. La scelta dell'algoritmo da utilizzare dipende dai requisiti specifici del problema, come la dimensione della struttura dati, la distribuzione dei valori e la complessità temporale desiderata.

Gli algoritmi grafici sono un insieme di algoritmi utilizzati per elaborare, analizzare e comprendere le strutture dei dati grafici. I grafici sono strutture matematiche utilizzate per modellare le relazioni tra oggetti, dove gli oggetti sono rappresentati come vertici (o nodi) e le relazioni tra loro sono rappresentate come bordi. Gli algoritmi dei grafici vengono utilizzati in una varietà di applicazioni come l'analisi di rete, l'analisi dei social network, i sistemi di raccomandazione e in molte altre aree in cui è importante comprendere le relazioni tra gli oggetti. Alcuni degli algoritmi grafici comuni includono:

Algoritmi del cammino minimo (ad esempio Dijkstra's, Bellman-Ford, A*)
Algoritmi di Spanning Tree minimo (ad esempio Kruskal, Prim)
Algoritmi di flusso massimo (ad esempio Ford-Fulkerson, Edmonds-Karp)
Algoritmi di flusso di rete (ad esempio corrispondenza bipartita)
Algoritmi di connettività (ad es. Ricerca prima in profondità, Ricerca prima in ampiezza)

Perché usiamo gli algoritmi?

Consideriamo due bambini, Aman e Rohan, che risolvono il cubo di Rubik. Aman sa come risolverlo in un numero definito di passaggi. Rohan, invece, sa che lo farà ma non è a conoscenza della procedura. Aman risolve il cubo in 2 minuti mentre Rohan è ancora bloccato e alla fine della giornata è riuscito in qualche modo a risolverlo (potrebbe aver imbrogliato poiché la procedura è necessaria).

Quindi il tempo necessario per risolvere con una procedura/algoritmo è molto più efficace di quello senza alcuna procedura. Quindi la necessità di un algoritmo è d’obbligo.

In termini di progettazione di una soluzione a un problema IT, i computer sono veloci ma non infinitamente veloci. La memoria può essere poco costosa ma non gratuita. Quindi, il tempo di elaborazione è quindi una risorsa limitata, così come lo è lo spazio in memoria. Dovremmo quindi utilizzare queste risorse in modo saggio e algoritmi efficienti in termini di tempo e spazio ti aiuteranno a farlo.

k algoritmo del vicino più vicino

Creazione di un algoritmo:

Poiché l'algoritmo è indipendente dalla lingua, scriviamo i passaggi per dimostrare la logica alla base della soluzione da utilizzare per risolvere un problema. Ma prima di scrivere un algoritmo, tieni presente i seguenti punti:

• L’algoritmo dovrebbe essere chiaro e inequivocabile.
• Dovrebbero esserci 0 o più input ben definiti in un algoritmo.
• Un algoritmo deve produrre uno o più output ben definiti equivalenti all'output desiderato. Dopo un numero specifico di passaggi, gli algoritmi devono fermarsi.
• Algoritmi deve fermarsi o terminare dopo un numero finito di passi.
• In un algoritmo dovrebbero essere fornite istruzioni passo passo e dovrebbero essere indipendenti da qualsiasi codice informatico.

Esempio: algoritmo per moltiplicare 2 numeri e stampare il risultato:

Passo 1: Inizio
Passo 2: Ottieni la conoscenza dell'input. Qui abbiamo bisogno di 3 variabili; a e b saranno l'input dell'utente e c manterrà il risultato.
Passaggio 3: Dichiarare le variabili a, b, c.
Passaggio 4: Accetta l'input per la variabile aeb dall'utente.
Passaggio 5: Conoscere il problema e trovare la soluzione utilizzando operatori, strutture dati e logica

Dobbiamo moltiplicare le variabili a e b, quindi utilizziamo l'operatore * e assegniamo il risultato a c.
Cioè c <- a * b

Passaggio 6: Controlla come fornire l'output, qui dobbiamo stampare l'output. Quindi scrivi stampa c
Passaggio 7: FINE

Esempio 1: Scrivi un algoritmo per trovare il massimo tra tutti gli elementi presenti nell'array.
Seguire l'approccio dell'algoritmo come di seguito:

Passo 1: Avviare il programma
Passo 2: Dichiara una variabile max con il valore del primo elemento dell'array.
Passaggio 3: Confronta max con altri elementi usando loop.
Passaggio 4: Se massimo Passaggio 5: Se non rimane alcun elemento, ritorna o stampa max altrimenti vai al passaggio 3.
Passaggio 6: Fine della soluzione

Esempio 2: Scrivi un algoritmo per trovare la media di 3 soggetti.
Seguire l'approccio dell'algoritmo come di seguito:

Passo 1: Avviare il programma
Passo 2: Dichiara e leggi 3 Oggetto, diciamo S1, S2, S3
Passaggio 3: Calcolare la somma di tutti e 3 i valori Oggetto e memorizzare il risultato nella variabile Somma (Somma = S1+S2+S3)
Passaggio 4: Dividi la somma per 3 e assegnala alla variabile Media. (Media = Somma/3)
Passaggio 5: Stampa il valore di Media di 3 soggetti
Passaggio 6: Fine della soluzione

Conoscere la complessità dell'algoritmo:

La complessità negli algoritmi si riferisce alla quantità di risorse (come tempo o memoria) necessarie per risolvere un problema o eseguire un'attività. La misura più comune della complessità è la complessità temporale, che si riferisce alla quantità di tempo impiegata da un algoritmo per produrre un risultato in funzione della dimensione dell’input. La complessità della memoria si riferisce alla quantità di memoria utilizzata da un algoritmo. I progettisti di algoritmi si sforzano di sviluppare algoritmi con la minore complessità possibile di tempo e memoria, poiché ciò li rende più efficienti e scalabili.

La complessità di un algoritmo è una funzione che descrive l'efficienza dell'algoritmo in termini di quantità di dati che l'algoritmo deve elaborare.

Di solito esistono unità naturali per il dominio e l'ambito di questa funzione.

Un algoritmo viene analizzato utilizzando la complessità temporale e la complessità spaziale. Scrivere un algoritmo efficiente aiuta a consumare la quantità minima di tempo per l'elaborazione della logica. Per l'algoritmo A, viene giudicato sulla base di due parametri per un input di dimensione n :

• Complessità temporale: Tempo impiegato dall'algoritmo per risolvere il problema. Viene misurato calcolando l'iterazione dei cicli, il numero di confronti, ecc.
• La complessità temporale è una funzione che descrive la quantità di tempo impiegata da un algoritmo in termini di quantità di input per l'algoritmo.
• Il tempo può significare il numero di accessi alla memoria eseguiti, il numero di confronti tra numeri interi, il numero di volte in cui viene eseguito un ciclo interno o qualche altra unità naturale correlata alla quantità di tempo reale impiegata dall'algoritmo.
• Complessità spaziale: Spazio occupato dall'algoritmo per risolvere il problema. Include lo spazio utilizzato dalle variabili di input necessarie e qualsiasi spazio aggiuntivo (escluso lo spazio occupato dagli input) utilizzato dall'algoritmo. Ad esempio, se utilizziamo una tabella hash (un tipo di struttura dati), abbiamo bisogno di un array per memorizzare i valori
• questo è uno spazio extra occupato, quindi conterà ai fini della complessità spaziale dell'algoritmo. Questo spazio extra è noto come Spazio Ausiliario.
• La complessità dello spazio è una funzione che descrive la quantità di memoria (spazio) occupata da un algoritmo in termini di quantità di input per l'algoritmo.
• La complessità dello spazio a volte viene ignorata perché lo spazio utilizzato è minimo e/o ovvio, ma a volte diventa un problema a causa del tempo.

.La complessità temporale delle operazioni:

• La scelta della struttura dei dati dovrebbe essere basata sulla complessità temporale delle operazioni che verranno eseguite.
• La complessità temporale è definita in termini di quante volte è necessario eseguire un determinato algoritmo, in base alla lunghezza dell'input.
• La complessità temporale di un algoritmo è la quantità di tempo necessaria per il completamento di ciascuna istruzione. Dipende fortemente dalla dimensione dei dati elaborati.
• Ad esempio, se è necessario eseguire ricerche frequentemente, è necessario utilizzare un albero di ricerca binario.

.La complessità spaziale delle operazioni:

• La scelta della struttura dei dati dovrebbe essere basata sulla complessità spaziale delle operazioni che verranno eseguite.
• La quantità di memoria utilizzata da un programma per eseguirlo è rappresentata dalla sua complessità spaziale.
• Poiché un programma richiede memoria per archiviare dati di input e valori temporali durante l'esecuzione, la complessità dello spazio è ausiliaria e spazio di input.
• Ad esempio, se devi archiviare molti dati, dovresti utilizzare un array.

casi in complessità:

Esistono due casi comunemente studiati di complessità negli algoritmi:

concatenare stringhe

1.Complessità del caso migliore: Lo scenario migliore per un algoritmo è lo scenario in cui l'algoritmo esegue la quantità minima di lavoro (ad esempio impiega il minor tempo possibile, utilizza la minima quantità di memoria, ecc.).

2. Complessità del caso peggiore: Lo scenario peggiore per un algoritmo è quello in cui l'algoritmo esegue la massima quantità di lavoro (ad esempio, impiega il tempo più lungo, utilizza la maggior quantità di memoria, ecc.).

Nell'analizzare la complessità di un algoritmo, spesso è più informativo studiare lo scenario peggiore, poiché ciò fornisce un limite superiore garantito alle prestazioni dell'algoritmo. A volte viene eseguita l'analisi dello scenario migliore, ma generalmente è meno importante in quanto fornisce un limite inferiore che spesso è banale da raggiungere.

Vantaggi degli algoritmi

• Facile da capire: Poiché è una rappresentazione graduale di una soluzione a un dato problema, è facile da capire.
• Indipendente dalla lingua: Non dipende da alcun linguaggio di programmazione, quindi può essere facilmente compreso da chiunque.
• Debug/Ricerca errori: Ogni passaggio è indipendente/in un flusso, quindi sarà facile individuare e correggere l'errore.
• Sottoproblemi: È scritto in un flusso, quindi ora il programmatore può dividere i compiti rendendoli più facili da codificare.

Svantaggi degli algoritmi

• La creazione di algoritmi efficienti richiede molto tempo e buone capacità logiche.
• Brutto mostrare ramificazioni e cicli negli algoritmi.