COS'È L'ALGORITMO | INTRODUZIONE AGLI ALGORITMI - TECHCODEVIEW.COM

Definizione di algoritmo

La parola Algoritmo significa Un insieme di regole o istruzioni finite da seguire nei calcoli o in altre operazioni di risoluzione dei problemi
O
Una procedura per risolvere un problema matematico in un numero finito di passaggi che spesso implica operazioni ricorsive .

Pertanto l'algoritmo si riferisce a una sequenza di passaggi finiti per risolvere un particolare problema.

Utilizzo degli algoritmi:

Gli algoritmi svolgono un ruolo cruciale in vari campi e hanno molte applicazioni. Alcune delle aree chiave in cui vengono utilizzati gli algoritmi includono:

Informatica: Gli algoritmi costituiscono la base della programmazione informatica e vengono utilizzati per risolvere problemi che vanno dal semplice ordinamento e ricerca a compiti complessi come l'intelligenza artificiale e l'apprendimento automatico.
Matematica: Gli algoritmi vengono utilizzati per risolvere problemi matematici, come trovare la soluzione ottimale per un sistema di equazioni lineari o trovare il percorso più breve in un grafico.
Ricerche operative : gli algoritmi vengono utilizzati per ottimizzare e prendere decisioni in campi quali i trasporti, la logistica e l'allocazione delle risorse.
Intelligenza artificiale: Gli algoritmi sono il fondamento dell'intelligenza artificiale e dell'apprendimento automatico e vengono utilizzati per sviluppare sistemi intelligenti in grado di eseguire compiti come il riconoscimento delle immagini, l'elaborazione del linguaggio naturale e il processo decisionale.
Scienza dei dati: Gli algoritmi vengono utilizzati per analizzare, elaborare ed estrarre informazioni da grandi quantità di dati in settori quali marketing, finanza e sanità.

Questi sono solo alcuni esempi delle molteplici applicazioni degli algoritmi. L’uso degli algoritmi è in continua espansione man mano che emergono nuove tecnologie e campi, rendendoli una componente vitale della società moderna.

ops in Java

Gli algoritmi possono essere semplici e complessi a seconda di ciò che si desidera ottenere.

Lo si può capire prendendo l'esempio di cucinare una nuova ricetta. Per cucinare una nuova ricetta, si leggono le istruzioni e i passaggi e li si esegue uno per uno, nella sequenza indicata. Il risultato così ottenuto è che la nuova pietanza sia cotta alla perfezione. Ogni volta che usi il telefono, il computer, il laptop o la calcolatrice stai utilizzando degli algoritmi. Allo stesso modo, gli algoritmi aiutano a svolgere un compito di programmazione per ottenere l'output previsto.

Gli algoritmi progettati sono indipendenti dal linguaggio, ovvero sono semplici istruzioni che possono essere implementate in qualsiasi linguaggio, eppure l'output sarà lo stesso, come previsto.

Qual è la necessità degli algoritmi?

Gli algoritmi sono necessari per risolvere problemi complessi in modo efficiente ed efficace.
Aiutano ad automatizzare i processi e a renderli più affidabili, più veloci e più facili da eseguire.
Gli algoritmi consentono inoltre ai computer di eseguire attività che sarebbero difficili o impossibili da svolgere manualmente per gli esseri umani.
Vengono utilizzati in vari campi come la matematica, l'informatica, l'ingegneria, la finanza e molti altri per ottimizzare i processi, analizzare dati, fare previsioni e fornire soluzioni ai problemi.

Quali sono le caratteristiche di un algoritmo?

Caratteristiche di un algoritmo

Perché per cucinare la ricetta non si seguirebbero istruzioni scritte, ma solo quelle standard. Allo stesso modo, non tutte le istruzioni scritte per la programmazione sono un algoritmo. Affinché alcune istruzioni siano un algoritmo, devono avere le seguenti caratteristiche:

Chiaro e inequivocabile : L'algoritmo dovrebbe essere inequivocabile. Ciascuno dei suoi passi deve essere chiaro in tutti gli aspetti e deve condurre ad un solo significato.
Input ben definiti : Se un algoritmo dice di prendere input, dovrebbero essere input ben definiti. Potrebbe ricevere input oppure no.
Risultati ben definiti: L'algoritmo deve definire chiaramente quale output verrà prodotto e dovrebbe anche essere ben definito. Dovrebbe produrre almeno 1 output.
Finitezza: L'algoritmo deve essere finito, ovvero deve terminare dopo un tempo finito.
Fattibile: L'algoritmo deve essere semplice, generico e pratico, in modo tale da poter essere eseguito con le risorse disponibili. Non deve contenere alcuna tecnologia futura o altro.
Indipendente dalla lingua: L'algoritmo progettato deve essere indipendente dalla lingua, ovvero devono essere semplici istruzioni che possono essere implementate in qualsiasi lingua, e tuttavia l'output sarà lo stesso, come previsto.
Ingresso : Un algoritmo ha zero o più input. Ciascuno che contiene un operatore fondamentale deve accettare zero o più input.
Produzione : Un algoritmo produce almeno un output. Ogni istruzione che contiene un operatore fondamentale deve accettare zero o più input.
Definitività: Tutte le istruzioni in un algoritmo devono essere inequivocabili, precise e facili da interpretare. Facendo riferimento a una qualsiasi delle istruzioni di un algoritmo si può capire chiaramente cosa bisogna fare. Ogni operatore fondamentale nell'istruzione deve essere definito senza alcuna ambiguità.
Finitezza: Un algoritmo deve terminare dopo un numero finito di passaggi in tutti i casi di test. Ogni istruzione che contiene un operatore fondamentale deve essere terminata entro un tempo finito. I cicli infiniti o le funzioni ricorsive senza condizioni di base non possiedono finitezza.
Efficacia: Un algoritmo deve essere sviluppato utilizzando operazioni basilari, semplici e fattibili in modo che sia possibile tracciarlo utilizzando solo carta e matita.

Proprietà dell'algoritmo:

Dovrebbe terminare dopo un tempo limitato.
Dovrebbe produrre almeno un output.
Dovrebbe richiedere zero o più input.
Dovrebbe essere deterministico significa fornire lo stesso output per lo stesso caso di input.
Ogni passaggio dell'algoritmo deve essere efficace, ovvero ogni passaggio dovrebbe svolgere un certo lavoro.

Tipi di algoritmi:

Sono disponibili diversi tipi di algoritmi. Alcuni algoritmi importanti sono:

1. Algoritmo della forza bruta :

È l'approccio più semplice a un problema. Un algoritmo di forza bruta è il primo approccio che si presenta quando vediamo un problema.

2. Algoritmo ricorsivo :

Si basa su un algoritmo ricorsivo ricorsione . In questo caso, un problema viene suddiviso in diverse sottoparti e richiamata più e più volte la stessa funzione.

3. Algoritmo di backtracking :

L'algoritmo di backtracking costruisce la soluzione cercando tra tutte le possibili soluzioni. Utilizzando questo algoritmo, continuiamo a costruire la soluzione seguendo criteri. Ogni volta che una soluzione fallisce, risaliamo al punto di fallimento, costruiamo sulla soluzione successiva e continuiamo questo processo finché non troviamo la soluzione o finché non vengono prese in considerazione tutte le possibili soluzioni.

4. Algoritmo di ricerca :

Gli algoritmi di ricerca sono quelli utilizzati per cercare elementi o gruppi di elementi da una particolare struttura dati. Possono essere di diverse tipologie in base all'approccio o alla struttura dati in cui si deve trovare l'elemento.

5. Algoritmo di ordinamento :

L'ordinamento consiste nel disporre un gruppo di dati in un modo particolare in base al requisito. Gli algoritmi che aiutano a svolgere questa funzione sono chiamati algoritmi di ordinamento. Generalmente gli algoritmi di ordinamento vengono utilizzati per ordinare gruppi di dati in modo crescente o decrescente.

6. Algoritmo di hashing :

Gli algoritmi di hashing funzionano in modo simile all'algoritmo di ricerca. Ma contengono un indice con un ID chiave. Nell'hashing, una chiave viene assegnata a dati specifici.

7. Algoritmo 'dividi e conquista'. :

Questo algoritmo suddivide un problema in sottoproblemi, risolve un singolo sottoproblema e unisce le soluzioni per ottenere la soluzione finale. Consiste nei seguenti tre passaggi:

Dividere
Risolvere
Combina

8. Algoritmo goloso :

In questo tipo di algoritmo la soluzione viene costruita parte per parte. La soluzione per la parte successiva è costruita in base al beneficio immediato della parte successiva. La soluzione che offre il massimo vantaggio verrà scelta come soluzione per la parte successiva.

9. Algoritmo di programmazione dinamica :

Questo algoritmo utilizza il concetto di utilizzare la soluzione già trovata per evitare calcoli ripetitivi della stessa parte del problema. Divide il problema in sottoproblemi sovrapposti più piccoli e li risolve.

10. Algoritmo randomizzato :

Nell'algoritmo randomizzato, utilizziamo un numero casuale in modo che dia un vantaggio immediato. Il numero casuale aiuta a decidere il risultato atteso.

Per approfondire le tipologie di algoritmi fare riferimento all'articolo su Tipi di algoritmi .

Vantaggi degli algoritmi:

È facile da capire.
Un algoritmo è una rappresentazione passo-passo di una soluzione ad un dato problema.
In un algoritmo il problema è suddiviso in parti o passaggi più piccoli, quindi è più facile per il programmatore convertirlo in un programma vero e proprio.

Svantaggi degli algoritmi:

Scrivere un algoritmo richiede molto tempo, quindi richiede molto tempo.
Comprendere la logica complessa attraverso gli algoritmi può essere molto difficile.
Le istruzioni di ramificazione e looping sono difficili da mostrare negli algoritmi (imp) .

Come progettare un algoritmo?

Per scrivere un algoritmo, sono necessari come prerequisiti i seguenti elementi:

IL problema che deve essere risolto da questo algoritmo, ovvero una chiara definizione del problema.
IL vincoli del problema deve essere considerato durante la risoluzione del problema.
IL ingresso da intraprendere per risolvere il problema.
IL produzione è prevedibile quando il problema sarà risolto.
IL soluzione a questo problema rientra nei limiti dati.

Quindi l'algoritmo viene scritto con l'aiuto dei parametri di cui sopra in modo tale da risolvere il problema.

Esempio: Considera l'esempio per aggiungere tre numeri e stampare la somma.

come controllare le dimensioni dello schermo

Passaggio 1: soddisfare i prerequisiti

Come discusso in precedenza, per scrivere un algoritmo è necessario che i suoi prerequisiti siano soddisfatti.

Il problema che deve essere risolto da questo algoritmo : Somma 3 numeri e stampa la loro somma.
I vincoli del problema che devono essere considerati durante la risoluzione del problema : i numeri devono contenere solo cifre e nessun altro carattere.
L'input da prendere per risolvere il problema: I tre numeri da sommare.
L'output previsto una volta risolto il problema: La somma dei tre numeri presi come input, ovvero un singolo valore intero.
La soluzione a questo problema, nei vincoli dati: La soluzione consiste nell'addizionare i 3 numeri. Può essere fatto con l'aiuto dell'operatore '+', o bit-wise, o qualsiasi altro metodo.

Passaggio 2: progettazione dell'algoritmo

Ora progettiamo l'algoritmo con l'aiuto dei prerequisiti di cui sopra:

Algoritmo per sommare 3 numeri e stamparne la somma:

INIZIO
Dichiarare 3 variabili intere num1, num2 e num3.
Prendi i tre numeri da sommare come input rispettivamente nelle variabili num1, num2 e num3.
Dichiara una somma variabile intera per memorizzare la somma risultante dei 3 numeri.
Somma i 3 numeri e memorizza il risultato nella variabile somma.
Stampa il valore della variabile somma
FINE

Passaggio 3: testare l'algoritmo implementandolo.

Per testare l'algoritmo, implementiamolo in linguaggio C.

Programma:

C++

 // C++ program to add three numbers // with the help of above designed  // algorithm #include  using namespace std;   int main() {    // Variables to take the input of   // the 3 numbers  int num1, num2, num3;    // Variable to store the resultant sum  int sum;    // Take the 3 numbers as input  cout << 'Enter the 1st number: ';  cin>> numero1;  cout<< ' ' << num1 << endl;    cout << 'Enter the 2nd number: ';  cin>> numero2;  cout<< ' ' << num2 << endl;    cout << 'Enter the 3rd number: ';  cin>>num3;  cout<< ' ' << num3;    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;    // Print the sum  cout << '
Sum of the 3 numbers is: '   << sum;    return 0; } // This code is contributed by shivanisinghss2110>

 // C program to add three numbers // with the help of above designed algorithm #include  int main() {  // Variables to take the input of the 3 numbers  int num1, num2, num3;  // Variable to store the resultant sum  int sum;  // Take the 3 numbers as input  printf('Enter the 1st number: ');  scanf('%d', &num1);  printf('%d
', num1);  printf('Enter the 2nd number: ');  scanf('%d', &num2);  printf('%d
', num2);  printf('Enter the 3rd number: ');  scanf('%d', &num3);  printf('%d
', num3);  // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  // Print the sum  printf('
Sum of the 3 numbers is: %d', sum);  return 0; }>

Giava

 // Java program to add the three numbers // with the help of above designed // algorithm import java.util.*; class GFG {  public static void main(String[] args)  {    // Variable to store the resultant sum  int sum = 0;    // Declare the object and initialize with  // predefined standard input object  Scanner sc  = new Scanner(System.in); // Scanner definition    // Variables to take the input of  // the 3 numbers  System.out.println('Enter the 1st number: ');  int num1 = sc.nextInt();     // input is an Integer  // read by nextInt() function  System.out.println(' ' + num1);  System.out.println('Enter the 2nd number: ');  int num2 = sc.nextInt();  System.out.println(' ' + num2);  System.out.println('Enter the 3rd number: ');  int num3 = sc.nextInt();  System.out.println(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  System.out.println('Sum of the 3 numbers is = '  + sum);  } } /*This code is contributed by Rishab Dugar*/>

Pitone

 # Python3 program to add three numbers # with the help of above designed # algorithm if __name__ == '__main__': # Variables to take the input of # the 3 numbers num1 = num2 = num3 = 0 # Variable to store the resultant sum sum = 0 # Take the 3 numbers as input num1 = int(input('Enter the 1st number: ')) num2 = int(input('Enter the 2nd number: ')) num3 = int(input('Enter the 3rd number: ')) # Calculate the sum using + operator # and store it in variable sum sum = num1 + num2 + num3 # Print the sum print('
Sum of the 3 numbers is:', sum)>

 // C# program to add the three numbers // with the help of above designed // algorithm using System; class GFG {  static public void Main ()  {    // Variable to store the resultant sum  int sum = 0;    // Variables to take the input of  // the 3 numbers  Console.Write('Enter the 1st number: ');  int num1 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num1);  Console.Write('Enter the 2nd number: ');  int num2 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num2);  Console.Write('Enter the 3rd number: ');  int num3 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  Console.WriteLine('Sum of the 3 numbers is = '  + sum);  } } /*This code is contributed by Pushpesh Raj*/>

Javascript

  // Javascript program to add three numbers  // with the help of above designed  // algorithm    // Variables to take the input of  // the 3 numbers  let num1 = 0, num2 = 0, num3 = 0;    // Variable to store the resultant sum  let sum = 0;    // Take the 3 numbers as input  console.log('Enter the 1st number: ');  num1 = parseInt(prompt());  console.log(' ' + num1 + ' ');    console.log('Enter the 2nd number: ');  num2=parseInt(prompt());  console.log(' ' + num2 + ' ');    console.log('Enter the 3rd number: ');  num3=parseInt(prompt());  console.log(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;    // Print the sum  console.log(' Sum of the 3 numbers is: ' + sum);    // This code is contributed by Aman Kumar>

Produzione

Inserisci il 1° numero: 0 Inserisci il 2° numero: 0 Inserisci il 3° numero: -1577141152 La somma dei 3 numeri è: -1577141152

Ecco l'algoritmo passo passo del codice:

Dichiarare tre variabili num1, num2 e num3 per memorizzare i tre numeri da sommare.
Dichiarare una somma variabile per memorizzare la somma dei tre numeri.
Utilizzare l'istruzione cout per richiedere all'utente di inserire il primo numero.
Utilizzare l'istruzione cin per leggere il primo numero e memorizzarlo in num1.
Utilizzare l'istruzione cout per richiedere all'utente di inserire il secondo numero.
Utilizzare l'istruzione cin per leggere il secondo numero e memorizzarlo in num2.
Utilizzare l'istruzione cout per richiedere all'utente di inserire il terzo numero.
Utilizzare l'istruzione cin per leggere e memorizzare il terzo numero in num3.
Calcola la somma dei tre numeri utilizzando l'operatore + e memorizzala nella variabile somma.
Utilizzare l'istruzione cout per stampare la somma dei tre numeri.
La funzione principale restituisce 0, che indica la corretta esecuzione del programma.

Complessità temporale: O(1)
Spazio ausiliario: O(1)

Un problema, tante soluzioni: La soluzione di un algoritmo può essere o non può essere più di una. Ciò significa che durante l'implementazione dell'algoritmo, può esserci più di un metodo per implementarlo. Ad esempio, nel problema precedente relativo alla somma di 3 numeri, la somma può essere calcolata in molti modi:

+ operatore
Operatori bit-a-bit
. . eccetera

Come analizzare un algoritmo?

Affinché un algoritmo standard sia valido, deve essere efficiente. Quindi l'efficienza di un algoritmo deve essere verificata e mantenuta. Può avvenire in due fasi:

1. Analisi a priori:

Priori significa prima. Quindi l'analisi a priori significa verificare l'algoritmo prima della sua implementazione. In questo caso, l'algoritmo viene controllato quando è scritto sotto forma di passaggi teorici. L'efficienza di un algoritmo viene misurata presupponendo che tutti gli altri fattori, ad esempio la velocità del processore, siano costanti e non abbiano alcun effetto sull'implementazione. Questo viene fatto solitamente dal progettista dell'algoritmo. Questa analisi è indipendente dal tipo di hardware e dal linguaggio del compilatore. Fornisce le risposte approssimative per la complessità del programma.

2. Analisi posteriore:

Posteriore significa dopo. Quindi l'analisi a posteriori significa controllare l'algoritmo dopo la sua implementazione. In questo, l'algoritmo viene controllato implementandolo in qualsiasi linguaggio di programmazione ed eseguendolo. Questa analisi aiuta a ottenere un rapporto di analisi effettivo e reale sulla correttezza (per ogni possibile input se mostra/restituisce un output corretto o meno), spazio richiesto, tempo consumato, ecc. Cioè, dipende dalla lingua del compilatore e il tipo di hardware utilizzato.

Cos'è la complessità dell'algoritmo e come trovarla?

Un algoritmo è definito complesso in base alla quantità di Spazio e Tempo che consuma. Quindi la complessità di un algoritmo si riferisce alla misura del tempo necessario per eseguire e ottenere l'output previsto, e allo spazio necessario per archiviare tutti i dati (input, dati temporanei e output). Quindi questi due fattori definiscono l’efficienza di un algoritmo.
I due fattori di complessità dell’algoritmo sono:

Fattore tempo : Il tempo viene misurato contando il numero di operazioni chiave come i confronti nell'algoritmo di ordinamento.
Fattore spaziale : Lo spazio viene misurato contando lo spazio di memoria massimo richiesto dall'algoritmo per l'esecuzione/esecuzione.

Quindi, il La complessità di un algoritmo può essere divisa in due tipi :

1. Complessità spaziale : La complessità spaziale di un algoritmo si riferisce alla quantità di memoria richiesta dall'algoritmo per memorizzare le variabili e ottenere il risultato. Può trattarsi di input, operazioni temporanee o output.

Come calcolare la complessità spaziale?
La complessità spaziale di un algoritmo viene calcolata determinando le seguenti 2 componenti:

Parte fissa: Questo si riferisce allo spazio richiesto dall'algoritmo. Ad esempio, variabili di input, variabili di output, dimensione del programma, ecc.
Parte variabile: Si riferisce allo spazio che può essere diverso in base all'implementazione dell'algoritmo. Ad esempio, variabili temporanee, allocazione dinamica della memoria, spazio nello stack di ricorsione, ecc.
Quindi complessità spaziale S(P) di qualsiasi algoritmo P è S(P) = C + SP(I) , dove C è la parte fissa e S(I) è la parte variabile dell'algoritmo, che dipende dalla caratteristica di istanza I.

Esempio: Considera l'algoritmo seguente per la ricerca lineare

Java genera un numero casuale

Passaggio 1: INIZIA
Passaggio 2: ottenere n elementi dell'array in arr e il numero da cercare in x
Passaggio 3: inizia dall'elemento più a sinistra di arr[] e uno per uno confronta x con ciascun elemento di arr[]
Passaggio 4: se x corrisponde a un elemento, stampa Vero.
Passaggio 5: se x non corrisponde a nessuno degli elementi, stampa False.
Passaggio 6: FINE
Qui, ci sono 2 variabili arr[] e x, dove arr[] è la parte variabile di n elementi e x è la parte fissa. Quindi S(P) = 1+n. Quindi, la complessità dello spazio dipende da n(numero di elementi). Ora, lo spazio dipende dai tipi di dati di determinate variabili e tipi costanti e verrà moltiplicato di conseguenza.

2. Complessità temporale : La complessità temporale di un algoritmo si riferisce alla quantità di tempo richiesta dall'algoritmo per essere eseguito e ottenere il risultato. Questo può essere per operazioni normali, istruzioni condizionali if-else, istruzioni loop, ecc.

Come calcolare , Complessità temporale?
La complessità temporale di un algoritmo viene calcolata anche determinando le seguenti 2 componenti:

Parte temporale costante: Qualsiasi istruzione eseguita una sola volta rientra in questa parte. Ad esempio, input, output, if-else, switch, operazioni aritmetiche, ecc.
Parte temporale variabile: Qualsiasi istruzione eseguita più di una volta, diciamo n volte, rientra in questa parte. Ad esempio, loop, ricorsione, ecc.
Quindi complessità del tempoT(P) di qualsiasi algoritmo P è T(P) = C + TP(I) , dove C è la parte temporale costante e TP(I) è la parte variabile dell'algoritmo, che dipende dalla caratteristica di istanza I.

Esempio: Nell'algoritmo di ricerca lineare sopra, la complessità temporale viene calcolata come segue:

Passaggio 1: –Tempo costante
Passo 2: — Tempo variabile (prendendo n input)
Passaggio 3: –Tempo variabile (fino alla lunghezza dell'array (n) o all'indice dell'elemento trovato)
Passaggio 4: –Tempo costante
Passaggio 5: –Tempo costante
Passaggio 6: –Tempo costante
Quindi, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, che può essere detto come T(n).

Come esprimere un algoritmo?

Linguaggio naturale:- Qui esprimiamo l'algoritmo nella lingua inglese naturale. È troppo difficile capirne l'algoritmo.
Diagramma di flusso :- Qui esprimiamo l'algoritmo creando a rappresentazione grafico/pittorica dello stesso. È più facile da capire rispetto al linguaggio naturale.
Pseudocodice :- Qui esprimiamo l'algoritmo sotto forma di annotazioni e testo informativo scritto in un inglese semplice che è molto simile al codice reale ma poiché non ha sintassi come nessuno dei linguaggi di programmazione, non può essere compilato o interpretato dal computer . È il modo migliore per esprimere un algoritmo perché può essere compreso anche da un profano con una conoscenza di livello scolastico.

TechCodeview

Cos'è l'algoritmo | Introduzione agli algoritmi