CO JE ALGORITMUS | ÚVOD DO ALGORITMŮ - TECHCODEVIEW.COM

Definice algoritmu

Slovo Algoritmus prostředek Sada konečných pravidel nebo pokynů, které se mají dodržovat při výpočtech nebo jiných operacích řešení problémů
Nebo
Postup pro řešení matematického problému v konečném počtu kroků, který často zahrnuje rekurzivní operace .

Algoritmus proto odkazuje na sekvenci konečných kroků k vyřešení konkrétního problému.

Použití algoritmů:

Algoritmy hrají klíčovou roli v různých oblastech a mají mnoho aplikací. Některé z klíčových oblastí, kde se používají algoritmy, zahrnují:

Počítačová věda: Algoritmy tvoří základ počítačového programování a používají se k řešení problémů od jednoduchého třídění a vyhledávání až po složité úkoly, jako je umělá inteligence a strojové učení.
Matematika: Algoritmy se používají k řešení matematických problémů, jako je hledání optimálního řešení soustavy lineárních rovnic nebo hledání nejkratší cesty v grafu.
Operační výzkum : Algoritmy se používají k optimalizaci a rozhodování v oblastech, jako je doprava, logistika a přidělování zdrojů.
Umělá inteligence: Algoritmy jsou základem umělé inteligence a strojového učení a používají se k vývoji inteligentních systémů, které mohou provádět úkoly, jako je rozpoznávání obrazu, zpracování přirozeného jazyka a rozhodování.
Data Science: Algoritmy se používají k analýze, zpracování a získávání poznatků z velkého množství dat v oblastech, jako je marketing, finance a zdravotnictví.

Toto je jen několik příkladů z mnoha aplikací algoritmů. Používání algoritmů se neustále rozšiřuje s tím, jak se objevují nové technologie a obory, což z nich činí životně důležitou součást moderní společnosti.

Algoritmy mohou být jednoduché a složité v závislosti na tom, čeho chcete dosáhnout.

Dá se to pochopit na příkladu vaření nového receptu. Chcete-li uvařit nový recept, přečtete si pokyny a kroky a provedete je jeden po druhém v daném pořadí. Výsledkem je, že nový pokrm je dokonale propečený. Pokaždé, když používáte telefon, počítač, notebook nebo kalkulačku, používáte algoritmy. Podobně algoritmy pomáhají při programování, aby se získal očekávaný výstup.

Navržený algoritmus je jazykově nezávislý, to znamená, že jde pouze o prosté instrukce, které lze implementovat v jakémkoli jazyce, a přesto bude výstup stejný, jak se očekávalo.

Co je potřeba pro algoritmy?

Algoritmy jsou nezbytné pro efektivní a efektivní řešení složitých problémů.
Pomáhají automatizovat procesy a činí je spolehlivějšími, rychlejšími a snadněji proveditelnými.
Algoritmy také umožňují počítačům provádět úkoly, které by pro člověka bylo obtížné nebo nemožné provádět ručně.
Používají se v různých oblastech, jako je matematika, informatika, strojírenství, finance a mnoho dalších, k optimalizaci procesů, analýze dat, předpovědi a poskytování řešení problémů.

Jaké jsou vlastnosti algoritmu?

Charakteristika algoritmu

Při vaření by se člověk neřídil žádnými písemnými pokyny, ale pouze standardními. Podobně ne všechny psané instrukce pro programování jsou algoritmy. Aby některé instrukce byly algoritmem, musí mít následující vlastnosti:

Jasné a jednoznačné : Algoritmus by měl být jednoznačný. Každý jeho krok by měl být po všech stránkách jasný a musí vést pouze k jednomu smyslu.
Dobře definované vstupy : Pokud algoritmus říká, že má přijímat vstupy, měly by to být dobře definované vstupy. Může nebo nemusí přijímat vstup.
Dobře definované výstupy: Algoritmus musí jasně definovat, jaký výstup bude generován, a měl by být také dobře definován. Měl by produkovat alespoň 1 výstup.
Konečnost: Algoritmus musí být konečný, tj. měl by skončit po konečném čase.
Proveditelný: Algoritmus musí být jednoduchý, obecný a praktický, aby jej bylo možné provést s dostupnými zdroji. Nesmí obsahovat nějakou budoucí technologii nebo tak něco.
Jazykově nezávislý: Navržený algoritmus musí být jazykově nezávislý, to znamená, že se musí jednat pouze o prosté instrukce, které lze implementovat v jakémkoli jazyce, a přesto bude výstup stejný, jak se očekávalo.
Vstup : Algoritmus má nula nebo více vstupů. Každý, který obsahuje základní operátor, musí přijmout nula nebo více vstupů.
Výstup : Algoritmus vytváří alespoň jeden výstup. Každá instrukce, která obsahuje základní operátor, musí přijmout nula nebo více vstupů.
Jednoznačnost: Všechny instrukce v algoritmu musí být jednoznačné, přesné a snadno interpretovatelné. Odkazem na kteroukoli z instrukcí v algoritmu lze jasně pochopit, co je třeba udělat. Každý základní operátor ve výuce musí být definován bez jakýchkoliv nejasností.
Konečnost: Algoritmus musí skončit po konečném počtu kroků ve všech testovacích případech. Každá instrukce, která obsahuje základní operátor, musí být ukončena v konečném čase. Nekonečné smyčky nebo rekurzivní funkce bez základních podmínek nemají konečnost.
Účinnost: Algoritmus musí být vyvinut pomocí velmi základních, jednoduchých a proveditelných operací, aby bylo možné jej vysledovat pouze pomocí papíru a tužky.

Vlastnosti algoritmu:

Mělo by to skončit po uplynutí určité doby.
Měl by produkovat alespoň jeden výstup.
Mělo by to trvat nula nebo více vstupů.
Mělo by to být deterministické prostředky poskytující stejný výstup pro stejný případ vstupu.
Každý krok v algoritmu musí být efektivní, to znamená, že každý krok by měl dělat nějakou práci.

Typy algoritmů:

K dispozici je několik typů algoritmů. Některé důležité algoritmy jsou:

1. Algoritmus hrubé síly :

Je to nejjednodušší přístup k problému. Algoritmus hrubé síly je první přístup k nalezení, když vidíme problém.

2. Rekurzivní algoritmus :

Rekurzivní algoritmus je založen na rekurze . V tomto případě je problém rozdělen do několika dílčích částí a znovu a znovu volána stejná funkce.

3. Algoritmus zpětného sledování :

Algoritmus backtracking vytváří řešení hledáním mezi všemi možnými řešeními. Pomocí tohoto algoritmu pokračujeme v budování řešení podle následujících kritérií. Kdykoli řešení selže, vysledujeme zpět k bodu selhání stavíme na dalším řešení a pokračujeme v tomto procesu, dokud nenajdeme řešení nebo se postaráme o všechna možná řešení.

4. Algoritmus hledání :

Vyhledávací algoritmy jsou ty, které se používají pro vyhledávání prvků nebo skupin prvků z konkrétní datové struktury. Mohou být různých typů na základě jejich přístupu nebo datové struktury, ve které by se měl prvek nacházet.

5. Algoritmus řazení :

Třídění je uspořádání skupiny dat určitým způsobem podle požadavku. Algoritmy, které pomáhají při provádění této funkce, se nazývají třídicí algoritmy. Obecně se třídicí algoritmy používají k třídění skupin dat rostoucím nebo klesajícím způsobem.

6. Hašovací algoritmus :

Hašovací algoritmy fungují podobně jako vyhledávací algoritmus. Obsahují ale index s ID klíče. Při hashování je klíč přiřazen ke konkrétním datům.

7. Algoritmus rozděl a panuj :

Tento algoritmus rozdělí problém na dílčí problémy, vyřeší jeden dílčí problém a sloučí řešení, aby získal konečné řešení. Skládá se z následujících tří kroků:

Rozdělit
Řešit
Kombajn

8. Chamtivý algoritmus :

V tomto typu algoritmu je řešení sestavováno část po části. Řešení pro další část je postaveno na základě okamžitého přínosu další části. Jedno řešení, které poskytuje největší užitek, bude vybráno jako řešení pro další část.

9. Algoritmus dynamického programování :

Tento algoritmus využívá koncept použití již nalezeného řešení, aby se zabránilo opakovanému výpočtu stejné části problému. Rozdělí problém na menší překrývající se podproblémy a ty řeší.

10. Randomizovaný algoritmus :

V randomizovaném algoritmu používáme náhodné číslo, takže poskytuje okamžitý užitek. Náhodné číslo pomáhá při rozhodování o očekávaném výsledku.

Další informace o typech algoritmů naleznete v článku o Typy algoritmů .

Výhody algoritmů:

Je snadné to pochopit.
Algoritmus je postupná reprezentace řešení daného problému.
V algoritmu je problém rozdělen na menší části nebo kroky, a proto je pro programátora snazší jej převést na skutečný program.

Nevýhody algoritmů :

Psaní algoritmu trvá dlouho, takže je časově náročné.
Pochopení složité logiky pomocí algoritmů může být velmi obtížné.
Příkazy větvení a smyčkování se v algoritmech obtížně zobrazují (imp) .

Jak navrhnout algoritmus?

K napsání algoritmu jsou nezbytné následující věci:

The problém to má být řešeno tímto algoritmem, tj. jasnou definicí problému.
The omezení problém je třeba vzít v úvahu při řešení problému.
The vstup být přijat k vyřešení problému.
The výstup lze očekávat, až bude problém vyřešen.
The řešení tento problém je v rámci daných omezení.

Poté je pomocí výše uvedených parametrů napsán algoritmus tak, aby problém vyřešil.

Příklad: Zvažte příklad sečíst tři čísla a vytisknout součet.

Krok 1: Splnění předpokladů

Jak bylo uvedeno výše, pro napsání algoritmu musí být splněny jeho předpoklady.

Problém, který má tento algoritmus vyřešit : Sečtěte 3 čísla a vytiskněte jejich součet.
Omezení problému, která je třeba vzít v úvahu při řešení problému : Čísla musí obsahovat pouze číslice a žádné další znaky.
Vstup, který má být použit k vyřešení problému: Tři čísla, která mají být přidána.
Výstup, který lze očekávat po vyřešení problému: Součet tří čísel braných jako vstup, tj. jedna celočíselná hodnota.
Řešení tohoto problému v daných omezeních: Řešení spočívá v sečtení 3 čísel. To lze provést pomocí operátoru „+“, nebo bitově nebo jakoukoli jinou metodou.

Krok 2: Návrh algoritmu

Nyní navrhneme algoritmus s pomocí výše uvedených předpokladů:

Algoritmus pro sečtení 3 čísel a vytištění jejich součtu:

START
Deklarujte 3 celočíselné proměnné num1, num2 a num3.
Vezměte tři čísla, která se mají přidat, jako vstupy do proměnných num1, num2 a num3.
Deklarujte součet celočíselných proměnných pro uložení výsledného součtu 3 čísel.
Sečtěte 3 čísla a výsledek uložte do proměnné součet.
Vytiskněte hodnotu proměnné součet
KONEC

Krok 3: Testování algoritmu jeho implementací.

Abychom otestovali algoritmus, implementujme jej v jazyce C.

Program:

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>> číslo1;  cout < < ' '  < < num1  < < endl;    cout  < < 'Enter the 2nd number: ';  cin>> číslo2;  cout < < ' '  < < num2  < < endl;    cout  < < 'Enter the 3rd number: ';  cin>> číslo 3;  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; }>

Jáva

 // 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*/>

Krajta

 # 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 >

Výstup

Zadejte 1. číslo: 0 Zadejte 2. číslo: 0 Zadejte 3. číslo: -1577141152 Součet 3 čísel je: -1577141152

Zde je krok za krokem algoritmus kódu:

Deklarujte tři proměnné num1, num2 a num3, abyste uložili tři čísla, která mají být přidána.
Deklarujte proměnný součet pro uložení součtu tří čísel.
Pomocí příkazu cout vyzvěte uživatele k zadání prvního čísla.
Použijte příkaz cin k přečtení prvního čísla a jeho uložení do num1.
Pomocí příkazu cout vyzvěte uživatele k zadání druhého čísla.
Pomocí příkazu cin načtěte druhé číslo a uložte jej do num2.
Pomocí příkazu cout vyzvěte uživatele k zadání třetího čísla.
Pomocí příkazu cin přečtete a uložíte třetí číslo v num3.
Vypočítejte součet tří čísel pomocí operátoru + a uložte jej do proměnné součtu.
Pomocí příkazu cout vytiskněte součet tří čísel.
Funkce main vrací 0, což znamená úspěšné provedení programu.

Časová složitost: O(1)
Pomocný prostor: O(1)

Jeden problém, mnoho řešení: Řešení algoritmu může nebo nemůže být více než jedno. To znamená, že při implementaci algoritmu může existovat více než jedna metoda k jeho implementaci. Například ve výše uvedeném problému sčítání 3 čísel lze součet vypočítat mnoha způsoby:

+ operátor
Bitové operátory
. . atd

Jak analyzovat algoritmus?

Aby byl standardní algoritmus dobrý, musí být efektivní. Proto musí být účinnost algoritmu kontrolována a udržována. Může být ve dvou fázích:

1. Priori analýza:

Priori znamená předtím. Priori analýza tedy znamená kontrolu algoritmu před jeho implementací. V tomto je algoritmus kontrolován, když je zapsán ve formě teoretických kroků. Tato účinnost algoritmu se měří za předpokladu, že všechny ostatní faktory, například rychlost procesoru, jsou konstantní a nemají žádný vliv na implementaci. To obvykle provádí návrhář algoritmu. Tato analýza je nezávislá na typu hardwaru a jazyku kompilátoru. Poskytuje přibližné odpovědi na složitost programu.

2. Zadní analýza:

Posterior znamená po. Posteriorní analýza tedy znamená kontrolu algoritmu po jeho implementaci. V tomto je algoritmus kontrolován jeho implementací v libovolném programovacím jazyce a jeho provedením. Tato analýza pomáhá získat aktuální a skutečnou zprávu o analýze o správnosti (pro každý možný vstup/y, zda ukazuje/vrací správný výstup nebo ne), požadovaném prostoru, spotřebovaném čase atd. To znamená, že je závislá na jazyce kompilátor a typ použitého hardwaru.

Co je to složitost algoritmu a jak ji najít?

Algoritmus je definován jako komplexní na základě množství prostoru a času, který spotřebuje. Složitost algoritmu se tedy týká míry času, který bude potřebovat k provedení a získání očekávaného výstupu, a prostoru, který bude potřebovat k uložení všech dat (vstup, dočasná data a výstup). Tyto dva faktory tedy definují účinnost algoritmu.
Dva faktory složitosti algoritmu jsou:

Časový faktor : Čas se měří počítáním počtu klíčových operací, jako jsou srovnání v algoritmu řazení.
Space Factor : Prostor se měří počítáním maximálního paměťového prostoru požadovaného algoritmem ke spuštění/provedení.

Proto Složitost algoritmu lze rozdělit na dva typy :

1. Vesmírná složitost : Prostorová složitost algoritmu se vztahuje k množství paměti požadované algoritmem k uložení proměnných a získání výsledku. To může být pro vstupy, dočasné operace nebo výstupy.

Jak vypočítat složitost prostoru?
Prostorová složitost algoritmu se vypočítá určením následujících 2 složek:

Pevná část: To se týká prostoru, který algoritmus vyžaduje. Například vstupní proměnné, výstupní proměnné, velikost programu atd.
Variabilní část: To se týká prostoru, který se může lišit v závislosti na implementaci algoritmu. Například dočasné proměnné, dynamická alokace paměti, rekurzní zásobník atd.
Proto vesmírná složitost S(P) libovolného algoritmu P je S(P) = C + SP(I) , kde C je pevná část a S(I) je proměnná část algoritmu, která závisí na instanční charakteristice I.

Příklad: Zvažte níže uvedený algoritmus pro lineární vyhledávání

Krok 1: START
Krok 2: Získejte n prvků pole v arr a číslo, které se má hledat v x
Krok 3: Začněte od levého prvku arr[] a jeden po druhém porovnejte x s každým prvkem arr[]
Krok 4: Pokud se x shoduje s prvkem, Print True.
Krok 5: Pokud x neodpovídá žádnému z prvků, Print False.
Krok 6: KONEC
Zde existují 2 proměnné arr[] a x, kde arr[] je proměnná část n prvků a x je pevná část. Proto S(P) = 1+n. Prostorová složitost tedy závisí na n (počtu prvků). Nyní prostor závisí na datových typech daných proměnných a konstantních typech a bude odpovídajícím způsobem vynásoben.

2. Časová složitost : Časová složitost algoritmu se týká množství času, které algoritmus potřebuje k provedení a získání výsledku. To může být pro normální operace, podmíněné příkazy if-else, příkazy smyčky atd.

Jak vypočítat , Časová složitost?
Časová složitost algoritmu se také vypočítá určením následujících 2 složek:

Konstantní časová část: Každá instrukce, která je provedena pouze jednou, přichází v této části. Například vstup, výstup, if-else, přepínač, aritmetické operace atd.
Variabilní časová část: Každá instrukce, která je provedena více než jednou, řekněme nkrát, přichází v této části. Například smyčky, rekurze atd.
Proto časová složitost T(P) libovolného algoritmu P je T(P) = C + TP(I) , kde C je konstantní časová část a TP(I) je proměnná část algoritmu, která závisí na instanční charakteristice I.

Příklad: Ve výše uvedeném algoritmu lineárního vyhledávání se časová složitost vypočítá takto:

Krok 1: – Konstantní čas
Krok 2: — Variabilní čas (s n vstupy)
Krok 3: – Variabilní čas (do délky pole (n) nebo indexu nalezeného prvku)
Krok 4: – Konstantní čas
Krok 5: – Konstantní čas
Krok 6: – Konstantní čas
Tedy T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, což lze říci jako T(n).

Jak vyjádřit algoritmus?

Přirozený jazyk:- Zde vyjadřujeme algoritmus v přirozeném anglickém jazyce. Z toho je příliš těžké pochopit algoritmus.
Vývojový diagram :- Zde vyjádříme algoritmus vytvořením a jeho grafické/obrázkové znázornění. Je srozumitelnější než přirozený jazyk.
Pseudo kód :- Zde vyjadřujeme algoritmus ve formě anotací a informativního textu napsaného v jednoduché angličtině, který je velmi podobný skutečnému kódu, ale protože nemá syntaxi jako kterýkoli z programovacích jazyků, nemůže být kompilován nebo interpretován počítačem. . Je to nejlepší způsob, jak vyjádřit algoritmus, protože mu může porozumět i laik s určitými školními znalostmi.