logo

TechCodeview

Què és l'algoritme | Introducció als algorismes

Definició d'algoritme

La paraula Algorisme significa Conjunt de regles o instruccions finites que cal seguir en els càlculs o altres operacions de resolució de problemes
O
Un procediment per resoldre un problema matemàtic en un nombre finit de passos que sovint implica operacions recursives .

Per tant, algorisme es refereix a una seqüència de passos finits per resoldre un problema particular.

Què és l'algoritme

Ús dels algorismes:

Els algorismes tenen un paper crucial en diversos camps i tenen moltes aplicacions. Algunes de les àrees clau on s'utilitzen algorismes inclouen:



  1. Ciències de la Computació: Els algorismes constitueixen la base de la programació d'ordinadors i s'utilitzen per resoldre problemes que van des de la simple ordenació i cerca fins a tasques complexes com la intel·ligència artificial i l'aprenentatge automàtic.
  2. Matemàtiques: Els algorismes s'utilitzen per resoldre problemes matemàtics, com ara trobar la solució òptima a un sistema d'equacions lineals o trobar el camí més curt en un gràfic.
  3. Investigació operativa : Els algorismes s'utilitzen per optimitzar i prendre decisions en camps com el transport, la logística i l'assignació de recursos.
  4. Intel · ligència artificial: Els algorismes són la base de la intel·ligència artificial i l'aprenentatge automàtic, i s'utilitzen per desenvolupar sistemes intel·ligents que poden realitzar tasques com ara el reconeixement d'imatges, el processament del llenguatge natural i la presa de decisions.
  5. Ciència de dades: Els algorismes s'utilitzen per analitzar, processar i extreure coneixements de grans quantitats de dades en camps com ara màrqueting, finances i sanitat.

Aquests són només alguns exemples de les moltes aplicacions dels algorismes. L'ús d'algoritmes s'està expandint contínuament a mesura que sorgeixen noves tecnologies i camps, el que el converteix en un component vital de la societat moderna.

Els algorismes poden ser simples i complexos depenent del que es vulgui aconseguir.

Es pot entendre prenent l'exemple de cuinar una nova recepta. Per cuinar una nova recepta, un llegeix les instruccions i els passos i els executa un per un, en la seqüència donada. El resultat així obtingut és que el nou plat està cuinat perfectament. Cada vegada que utilitzeu el vostre telèfon, ordinador, ordinador portàtil o calculadora, feu servir algorismes. De la mateixa manera, els algorismes ajuden a fer una tasca de programació per obtenir la sortida esperada.

L'algorisme dissenyat és independent de l'idioma, és a dir, només són instruccions senzilles que es poden implementar en qualsevol idioma i, tanmateix, la sortida serà la mateixa, com s'esperava.

Quina és la necessitat dels algorismes?

  1. Els algorismes són necessaris per resoldre problemes complexos de manera eficient i eficaç.
  2. Ajuden a automatitzar els processos i els fan més fiables, ràpids i fàcils de dur a terme.
  3. Els algorismes també permeten als ordinadors realitzar tasques que els humans serien difícils o impossibles de fer manualment.
  4. S'utilitzen en diversos camps com ara les matemàtiques, la informàtica, l'enginyeria, les finances i molts altres per optimitzar processos, analitzar dades, fer prediccions i donar solucions a problemes.

Quines són les característiques d'un algorisme?

Característiques d'un algorisme

Com que no seguim cap instruccions escrites per cuinar la recepta, sinó només la estàndard. De la mateixa manera, no totes les instruccions escrites per a la programació són un algorisme. Perquè algunes instruccions siguin un algorisme, ha de tenir les característiques següents:

  • Clar i sense ambigüitats : L'algorisme hauria de ser inequívoc. Cadascun dels seus passos ha de ser clar en tots els aspectes i només ha de conduir a un significat.
  • Entrades ben definides : Si un algorisme diu que cal prendre entrades, haurien de ser entrades ben definides. Pot o no prendre entrada.
  • Sortides ben definides: L'algorisme ha de definir clarament quina sortida es produirà i també ha d'estar ben definit. Ha de produir almenys 1 sortida.
  • Finitud: L'algorisme ha de ser finit, és a dir, ha d'acabar després d'un temps finit.
  • Viable: L'algorisme ha de ser senzill, genèric i pràctic, de manera que es pugui executar amb els recursos disponibles. No ha de contenir cap tecnologia futura ni res.
  • Independent de la llengua: L'algoritme dissenyat ha de ser independent de l'idioma, és a dir, ha de ser només instruccions senzilles que es puguin implementar en qualsevol idioma i, tanmateix, la sortida serà la mateixa, com s'esperava.
  • Entrada : un algorisme té zero o més entrades. Cadascun que conté un operador fonamental ha d'acceptar zero o més entrades.
  • Sortida : un algorisme produeix almenys una sortida. Cada instrucció que conté un operador fonamental ha d'acceptar zero o més entrades.
  • Definició: Totes les instruccions d'un algorisme han de ser inequívoques, precises i fàcils d'interpretar. En fer referència a qualsevol de les instruccions d'un algorisme es pot entendre clarament què s'ha de fer. Cada operador fonamental de la instrucció s'ha de definir sense cap ambigüitat.
  • Finitud: Un algorisme ha d'acabar després d'un nombre finit de passos en tots els casos de prova. Tota instrucció que conté un operador fonamental s'ha d'acabar en un període de temps finit. Els bucles infinits o les funcions recursives sense condicions base no posseeixen finitud.
  • Eficàcia: Un algorisme s'ha de desenvolupar utilitzant operacions molt bàsiques, senzilles i factibles de manera que es pugui traçar amb només paper i llapis.

Propietats de l'algoritme:

  • Hauria d'acabar al cap d'un temps determinat.
  • Hauria de produir almenys una sortida.
  • Hauria de prendre zero o més entrada.
  • Hauria de ser determinista significa donar la mateixa sortida per al mateix cas d'entrada.
  • Cada pas de l'algorisme ha de ser efectiu, és a dir, cada pas hauria de funcionar.

Tipus d'algorismes:

Hi ha diversos tipus d'algoritmes disponibles. Alguns algorismes importants són:

1. Algorisme de força bruta :

És l'enfocament més senzill d'un problema. Un algorisme de força bruta és el primer enfocament que arriba a trobar quan veiem un problema.

2. Algorisme recursiu :

Es basa en un algorisme recursiu recursivitat . En aquest cas, un problema es divideix en diverses subparts i s'anomena la mateixa funció una vegada i una altra.

3. Algoritme de retrocés :

L'algoritme de retrocés crea la solució cercant entre totes les solucions possibles. Utilitzant aquest algorisme, continuem construint la solució seguint criteris. Sempre que una solució falla, ens remuntem al punt de fallada que es construeix a la següent solució i continuem aquest procés fins que trobem la solució o es cuiden totes les solucions possibles.

4. Algorisme de cerca :

Els algorismes de cerca són els que s'utilitzen per cercar elements o grups d'elements d'una estructura de dades determinada. Poden ser de diferents tipus segons el seu enfocament o l'estructura de dades en què s'ha de trobar l'element.

5. Algorisme d'ordenació :

Ordenar és organitzar un grup de dades d'una manera particular segons el requisit. Els algorismes que ajuden a realitzar aquesta funció s'anomenen algorismes d'ordenació. En general, els algorismes d'ordenació s'utilitzen per ordenar grups de dades de manera creixent o decreixent.

6. Algoritme hashing :

Els algorismes hash funcionen de manera similar a l'algorisme de cerca. Però contenen un índex amb un identificador de clau. En hash, s'assigna una clau a dades específiques.

ordre lexicogràfic

7. Algoritme Divideix i Conquista :

Aquest algorisme divideix un problema en subproblemes, resol un únic subproblema i fusiona les solucions per obtenir la solució final. Consta dels tres passos següents:

  • Dividiu
  • Resol
  • Combina

8. Algoritme Greedy :

En aquest tipus d'algorisme, la solució es construeix part per part. La solució per a la peça següent es construeix en funció del benefici immediat de la peça següent. La solució que ofereixi més beneficis serà escollida com a solució per a la part següent.

9. Algoritme de programació dinàmica :

Aquest algorisme utilitza el concepte d'utilitzar la solució ja trobada per evitar el càlcul repetitiu de la mateixa part del problema. Divideix el problema en subproblemes més petits que se superposen i els resol.

10. Algoritme aleatoritzat :

En l'algoritme aleatori, utilitzem un nombre aleatori perquè ofereix un benefici immediat. El nombre aleatori ajuda a decidir el resultat esperat.

Per obtenir més informació sobre els tipus d'algorismes, consulteu l'article sobre Tipus d'algorismes .

Avantatges dels algorismes:

  • És fàcil d'entendre.
  • Un algorisme és una representació pas a pas d'una solució a un problema donat.
  • En un algorisme, el problema es divideix en peces o passos més petits, per tant, és més fàcil per al programador convertir-lo en un programa real.

Inconvenients dels algorismes:

  • Escriure un algorisme triga molt de temps, de manera que requereix molt de temps.
  • Entendre la lògica complexa mitjançant algorismes pot ser molt difícil.
  • Les declaracions de ramificació i bucle són difícils de mostrar als algorismes (imp) .

Com dissenyar un algorisme?

Per escriure un algorisme, es necessiten les coses següents com a requisit previ:

  1. El problema això s'ha de resoldre amb aquest algorisme, és a dir, una definició clara del problema.
  2. El limitacions del problema s'ha de tenir en compte a l'hora de resoldre'l.
  3. El entrada a prendre per resoldre el problema.
  4. El sortida és d'esperar quan es resolgui el problema.
  5. El solució a aquest problema està dins de les limitacions donades.

A continuació, l'algorisme s'escriu amb l'ajuda dels paràmetres anteriors de manera que resolgui el problema.

Exemple: Considereu l'exemple per sumar tres nombres i imprimir la suma.

Pas 1: complir els requisits previs

Com s'ha comentat anteriorment, per escriure un algorisme, s'han de complir els seus requisits previs.

  1. El problema que s'ha de resoldre amb aquest algorisme : Sumeu 3 nombres i imprimiu la seva suma.
  2. Les limitacions del problema que s'han de tenir en compte per resoldre el problema : els números només han de contenir dígits i cap altre caràcter.
  3. L'entrada a prendre per resoldre el problema: Els tres nombres que cal sumar.
  4. La sortida que cal esperar quan es resolgui el problema: La suma dels tres nombres considerats com a entrada, és a dir, un únic valor enter.
  5. La solució a aquest problema, en les restriccions donades: La solució consisteix a sumar els 3 nombres. Es pot fer amb l'ajuda de l'operador ‘+’, per bits o qualsevol altre mètode.


Pas 2: Disseny de l'algorisme

Ara dissenyem l'algorisme amb l'ajuda dels requisits previs anteriors:

Algorisme per sumar 3 nombres i imprimir-ne la suma:

  1. COMENÇAR
  2. Declara 3 variables enteres num1, num2 i num3.
  3. Agafeu els tres nombres, que cal sumar, com a entrades a les variables num1, num2 i num3 respectivament.
  4. Declara una suma de variables enteres per emmagatzemar la suma resultant dels 3 nombres.
  5. Suma els 3 nombres i emmagatzema el resultat a la suma variable.
  6. Imprimeix el valor de la suma variable
  7. FINAL


Pas 3: prova l'algorisme implementant-lo.

Per provar l'algorisme, implementem-lo en llenguatge C.

Programa:

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>> núm1; cout<< ' ' << num1 << endl; cout << 'Enter the 2nd number: '; cin>> num2; 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 // 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; }>Java // 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*/>Python # 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# // 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>
Sortida

Introduïu el 1r número: 0 Introduïu el 2n número: 0 Introduïu el 3r número: -1577141152 La suma dels 3 nombres és: -1577141152

Aquí teniu l'algoritme pas a pas del codi:

  1. Declara tres variables num1, num2 i num3 per emmagatzemar els tres nombres que cal afegir.
  2. Declarar una suma variable per emmagatzemar la suma dels tres nombres.
  3. Utilitzeu la instrucció cout per demanar a l'usuari que introdueixi el primer número.
  4. Utilitzeu la instrucció cin per llegir el primer número i emmagatzemar-lo a num1.
  5. Utilitzeu la instrucció cout per demanar a l'usuari que introdueixi el segon número.
  6. Utilitzeu la instrucció cin per llegir el segon número i emmagatzemar-lo a num2.
  7. Utilitzeu la instrucció cout per demanar a l'usuari que introdueixi el tercer número.
  8. Utilitzeu la instrucció cin per llegir i emmagatzemar el tercer número a num3.
  9. Calcula la suma dels tres nombres amb l'operador + i emmagatzema-la a la variable suma.
  10. Utilitzeu la declaració cout per imprimir la suma dels tres nombres.
  11. La funció principal retorna 0, que indica l'execució correcta del programa.

Complexitat temporal: O(1)
Espai auxiliar: O(1)

Un problema, moltes solucions: La solució d'un algorisme pot ser o no pot ser més d'una. Vol dir que mentre s'implementa l'algorisme, pot haver-hi més d'un mètode per implementar-lo. Per exemple, en el problema anterior de sumar 3 nombres, la suma es pot calcular de moltes maneres:

  • + operador
  • Operadors de bits
  • . . etc

Com analitzar un algorisme?

Perquè un algorisme estàndard sigui bo, ha de ser eficient. Per tant, s'ha de comprovar i mantenir l'eficiència d'un algorisme. Pot ser en dues etapes:

1. Anàlisi a priori:

Priori vol dir abans. Per tant, l'anàlisi Priori significa comprovar l'algorisme abans de la seva implementació. En aquest, l'algorisme es verifica quan s'escriu en forma de passos teòrics. Aquesta eficiència d'un algorisme es mesura assumint que tots els altres factors, per exemple, la velocitat del processador, són constants i no tenen cap efecte en la implementació. Això ho fa normalment el dissenyador d'algoritmes. Aquesta anàlisi és independent del tipus de maquinari i llenguatge del compilador. Dóna les respostes aproximades per a la complexitat del programa.

2. Anàlisi posterior:

Posterior vol dir després. Per tant, l'anàlisi posterior significa comprovar l'algorisme després de la seva implementació. En aquest, es verifica l'algorisme implementant-lo en qualsevol llenguatge de programació i executant-lo. Aquesta anàlisi ajuda a obtenir l'informe d'anàlisi real i real sobre la correcció (per a cada entrada/s possible/s si mostra/retorna una sortida correcta o no), espai necessari, temps consumit, etc. És a dir, depèn de l'idioma del compilador i el tipus de maquinari utilitzat.

Què és la complexitat de l'algoritme i com trobar-la?

Un algorisme es defineix com a complex en funció de la quantitat d'espai i temps que consumeix. Per tant, la complexitat d'un algorisme fa referència a la mesura del temps que necessitarà per executar-se i obtenir la sortida esperada, i l'espai que necessitarà per emmagatzemar totes les dades (entrada, dades temporals i sortida). Per tant, aquests dos factors defineixen l'eficiència d'un algorisme.
Els dos factors de la complexitat de l'algoritme són:

  • Factor temps : el temps es mesura comptant el nombre d'operacions clau, com ara comparacions en l'algorisme d'ordenació.
  • Factor espacial : L'espai es mesura comptant l'espai de memòria màxim requerit per l'algorisme per executar/executar.

Per tant el La complexitat d'un algorisme es pot dividir en dos tipus :

1. Complexitat espacial : La complexitat espacial d'un algorisme fa referència a la quantitat de memòria requerida per l'algorisme per emmagatzemar les variables i obtenir el resultat. Això pot ser per a entrades, operacions temporals o sortides.

Com calcular la complexitat espacial?
La complexitat espacial d'un algorisme es calcula determinant els 2 components següents:

  • Part fixa: Això fa referència a l'espai que requereix l'algorisme. Per exemple, variables d'entrada, variables de sortida, mida del programa, etc.
  • Part variable: Això fa referència a l'espai que pot ser diferent en funció de la implementació de l'algorisme. Per exemple, variables temporals, assignació de memòria dinàmica, espai de pila de recursivitat, etc.
    Per tant, la complexitat espacial S(P) de qualsevol algorisme P és S(P) = C + SP(I) , on C és la part fixa i S(I) és la part variable de l'algorisme, que depèn de la característica de la instància I.

Exemple: Considereu l'algorisme següent per a la cerca lineal

Pas 1: COMENÇA
Pas 2: obteniu n elements de la matriu a arr i el nombre que cal cercar en x
Pas 3: comença des de l'element més a l'esquerra d'arr[] i un per un compare x amb cada element d'arr[]
Pas 4: si x coincideix amb un element, imprimiu True.
Pas 5: si x no coincideix amb cap dels elements, Imprimeix False.
Pas 6: FINALITZACIÓ
Aquí, hi ha 2 variables arr[] i x, on arr[] és la part variable de n elements i x és la part fixa. Per tant S(P) = 1+n. Per tant, la complexitat espacial depèn de n (nombre d'elements). Ara, l'espai depèn dels tipus de dades de les variables donades i dels tipus constants i es multiplicarà en conseqüència.

2. Complexitat temporal : La complexitat temporal d'un algorisme es refereix a la quantitat de temps que requereix l'algorisme per executar-se i obtenir el resultat. Això pot ser per a operacions normals, sentències condicionals if-else, sentències de bucle, etc.

Com calcular , Complexitat temporal?
La complexitat temporal d'un algorisme també es calcula determinant els dos components següents:

  • Part de temps constant: Qualsevol instrucció que s'executi només una vegada ve en aquesta part. Per exemple, entrada, sortida, if-else, commutació, operacions aritmètiques, etc.
  • Part de temps variable: Qualsevol instrucció que s'executi més d'una vegada, per exemple n vegades, ve en aquesta part. Per exemple, bucles, recursivitat, etc.
    Per tant, complexitat temporalT(P) de qualsevol algorisme P és T(P) = C + TP(I) , on C és la part constant del temps i TP(I) és la part variable de l'algorisme, que depèn de la característica d'instància I.

Exemple: A l'algorisme de cerca lineal anterior, la complexitat del temps es calcula de la següent manera:

Pas 1: -Temps constant
Pas 2: — Temps variable (agafa n entrades)
Pas 3: -Temps variable (fins a la longitud de la matriu (n) o l'índex de l'element trobat)
Pas 4: -Temps constant
Pas 5: -Temps constant
Pas 6: -Temps constant
Per tant, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, que es pot dir com a T(n).

Com expressar un algorisme?

  1. Llenguatge natural: - Aquí expressem l'algoritme en llengua anglesa natural. És massa difícil d'entendre l'algorisme a partir d'ell.
  2. Diagrama de flux :- Aquí expressem l'algoritme fent a representació gràfica/pictòrica del mateix. És més fàcil d'entendre que el llenguatge natural.
  3. Pseudocodi :- Aquí expressem l'algorisme en forma d'anotacions i text informatiu escrit en anglès senzill que és molt semblant al codi real però com que no té una sintaxi com cap dels llenguatges de programació, no pot ser compilat ni interpretat per l'ordinador. . És la millor manera d'expressar un algorisme perquè pot ser entès fins i tot per un profà amb alguns coneixements a nivell escolar.