A programozás alapstruktúrái (algoritmustípusok). Az algoritmus fogalma. Programozás Programozási algoritmusok

Különböző komplexitású alkalmazások írásához először ismereteket kell szereznie arról, hogyan történik. És kívánatos az algoritmizálás és a programozás alapjairól kiindulni. Erről fogunk beszélni a cikkben.

Ez egy komplex műszaki tudomány elnevezése, melynek feladata az adatok létrehozásának, feldolgozásának, továbbításának, tárolásának, reprodukálásának módszereinek rendszerezése, valamint a cél elérését segítő működési elvek és kezelési módszerek rendszerezése. Maga a "számítástechnika" kifejezés francia eredetű, és az "információ" és az "automatizálás" szavak hibridje. Az adatok gyűjtésének, feldolgozásának és továbbításának új technológiáinak fejlesztése és elterjedése miatt alakult ki, amelyek a gépi adathordozókon való rögzítésükhöz kapcsolódnak. Ez az informatika eredete. Az algoritmizálás és programozás alapjai ennek a tudománynak az egyik legfontosabb területe.

Mit csinál?

Az informatika a következő feladatokkal néz szembe:

1. Számítástechnika hardveres és szoftveres támogatása.
2. Az ember és a számítógép-alkatrészek egymás közötti kölcsönhatásának biztosításának eszközei.

Az "interfész" kifejezést gyakran használják a műszaki részre. Itt van egy ingyenes programunk. Az algoritmizálás és a programozás alapjait mindig alkalmazzák a tömeges terjesztésű termékek létrehozásakor, amelyeknek széles közönséget "kell" megnyerniük. Végül is a népszerűség érdekében a kifejlesztett alkalmazásnak működnie kell és optimálisnak kell lennie.

Algoritmusok bemutatása

Nagyon sokféleképpen írhatók. A legnépszerűbbek a következők:

1. Verbális-képlet leírás. Ez azt jelenti, hogy olyan szöveget kell elhelyezni, amely minden egyedi esetben megmagyarázza az interakció jellemzőit.
2. Blokk diagramm. A grafikus szimbólumok jelenléte feltételezhető, amelyek lehetővé teszik a program önmagán belüli és más alkalmazásokkal vagy a számítógép hardverkomponensével való interakciójának jellemzőit. Mindegyikük külön funkcióért, eljárásért vagy képletért felelős.
3. Ez magában foglalja a konkrét esetekre külön leírási módszerek létrehozását, amelyek bemutatják a feladatok jellemzőit és sorrendjét.
4. Üzemeltetői sémák. Ez magában foglalja egy prototípus létrehozását - megmutatja az interakciót azon utak alapján, amelyeken az egyes operandusok keresztülmennek.

Pszeudokód. A program gerincének vázlata.

Algoritmus írása

Hogyan kezdjük el egy program, funkció vagy eljárás prototípusának elkészítését? Ehhez elegendő a következő általános ajánlásokat használni:

1. Minden algoritmusnak saját névvel kell rendelkeznie, amely megmagyarázza a jelentését.
2. Ügyeljen a kezdet és a vég jelenlétére.
3. A bemeneti és kimeneti adatokat le kell írni.
4. Meg kell adni azokat a parancsokat, amelyek segítségével bizonyos műveletek végrehajtásra kerülnek az adott információn.

Rögzítési módszerek

Az algoritmusnak akár öt reprezentációja is lehet. De csak kétféleképpen írhatunk:

1. Formálisan verbális. Jellemzője, hogy a leírás főleg képletek és szavak felhasználásával készül. A tartalom, valamint az algoritmus lépéseinek végrehajtási sorrendje ebben az esetben természetes szakmai nyelven, tetszőleges formában kerül rögzítésre.
2. Grafikus. A leggyakrabban. Blokkszimbólumokat vagy algoritmussémákat használnak hozzá. A köztük lévő kapcsolatot speciális vonalak segítségével mutatjuk be.

Programstruktúrát alakítunk ki

Három fő típusa van:

1. Lineáris. Ezzel a struktúrával az összes műveletet egymás után, prioritási sorrendben hajtják végre, és csak egyszer. A séma úgy néz ki, mint egy blokkok sorozata, felülről lefelé elrendezve, a végrehajtás sorrendjétől függően. A kapott elsődleges és köztes adatok nem befolyásolhatják a számítási folyamat irányát.
2. Elágazó. Széleskörű alkalmazásra talált a gyakorlatban, összetett problémák megoldásában. Tehát, ha figyelembe kell venni a kezdeti feltételeket vagy a közbenső eredményeket, akkor ezeknek megfelelően elvégzik a szükséges számításokat, és a számítási folyamat iránya a kapott eredmény függvényében változhat.

Ciklikus. A sok feladat megkönnyítése érdekében érdemes többször megismételni a programkód egyes szakaszait. Annak érdekében, hogy ne írják elő, hányszor és mit kell tenni, ciklikus szerkezetet használnak. Parancsok sorozatát írja elő, amelyek addig ismétlődnek, amíg egy adott feltétel teljesül. A hurkok használata lehetővé teszi a programírás bonyolultságának nagymértékben történő csökkentését.

Programozás

Fontos, hogy mely programok készülnek. Meg kell jegyezni, hogy sok közülük bizonyos munkakörülményekre „szabott” (például böngészőben). Általában a programozási nyelvek két csoportra oszthatók:

1. Funkcionális.
2. Operátor:

Nem eljárási;

eljárási.

Kitalálod, melyiket használják a leggyakrabban? Üzemeltetői-eljárási – ez a válasz. Lehetnek géporientáltak vagy függetlenek. Az előbbiek közé tartoznak az assemblerek, az autokódok, a szimbolikus kódolás. A függetleneket irányultságuk alapján osztják fel:

• eljárási;
• problematikus;
• tárgy.

Mindegyiknek megvan a maga hatóköre. De a programok (hasznos alkalmazások vagy játékok) írásához leggyakrabban objektum-orientált nyelveket használnak. Természetesen másokat is használhat, de tény, hogy ezek a legfejlettebbek a tömegek számára készült végső fogyasztói termékek létrehozására. Igen, és ha még nincs pontos elképzelése arról, hogy hol kezdje, javaslom, hogy fordítson figyelmet az algoritmizálás és az objektum-orientált programozás alapjaira. Most ez egy nagyon népszerű terület, ahol sok oktatási anyagot találhat. Általánosságban elmondható, hogy az algoritmizálás és a programozási nyelvek alapjaira most azért van szükség, mert hiányoznak a képzett fejlesztők, és ezek jelentősége a jövőben csak nőni fog.

Következtetés

Az algoritmusokkal (és ezt követően a programokkal) végzett munka során törekedni kell arra, hogy minden részletet a legkisebbre gondoljon. Ezt követően a kód minden kidolgozatlan szakaszának azonosítása csak többletmunkát, a fejlesztési költségek és a feladat időzítésének növekedését eredményezi. Az összes árnyalat gondos tervezése és kidolgozása jelentősen időt, erőfeszítést és pénzt takarít meg. Nos, most már azt mondhatják, hogy a cikk elolvasása után van egy elképzelése az algoritmizálás és programozás alapjairól. Már csak ezt a tudást kell alkalmazni. Ha van vágy a téma részletesebb tanulmányozására, tanácsot adhatok az "Algoritmizálás és programozás alapjai" (Semakin, Shestakov) 2012 című könyvben.

Az algoritmus fogalma a számítástechnika egyik alapfogalma. Tekintsük az algoritmus fogalmához kapcsolódó alapfogalmakat.

Amikor egy algoritmusról van szó, mindig feltételezik, hogy létezik valamilyen végrehajtó, amelyre az algoritmust szánják.

Végrehajtó - egy személy vagy egy automata (például számítógép), amely egy bizonyos véges műveletsort képes végrehajtani.

recept - parancs a meghatározott véges halmazból történő műveletek végrehajtására.

Vényköteles rendszer - elfogadható végzések halmaza.

Program - az utasítások végső sorrendje végrehajtásuk sorrendjének megjelölésével.

Abban az esetben, ha a végrehajtó számítógép, az előírást lehívják csapat , és a rendelési rendszer ún számítógépes parancsrendszer . A különböző számítógépek, eszközüktől függően, eltérő parancsrendszerrel rendelkezhetnek.

Programozás - a probléma megoldásához szükséges parancssor összeállítása.

A program elkészítését egy algoritmus kidolgozása előzi meg.

Algoritmus - ez egy pontos és érthető utasítás az előadó számára egy meghatározott cél elérését vagy egy kitűzött feladat megoldását célzó végső műveletsor végrehajtására.

Bármely algoritmus a következő tulajdonságokkal rendelkezik:

• 1. diszkrétség. Az algoritmus végrehajtása elemi műveletek sorozatára - lépésekre oszlik. A végrehajtónak minden műveletet végre kell hajtania, mielőtt a következő műveletre léphet. Az egyes műveletek végrehajtásához a végrehajtó egy speciális utasítást ír elő az algoritmus rekordban, amelyet parancsnak neveznek.
• 2. Pontosság vagy determinizmus. Az algoritmus rekordjának olyannak kell lennie, hogy a következő parancs végrehajtása után az végrehajtó pontosan tudja, melyik parancsot kell legközelebb végrehajtani.
• 3. Világosság. Minden algoritmus egy konkrét végrehajtó szem előtt tartásával épül fel, akinek képesnek kell lennie az algoritmus minden egyes parancsának végrehajtására a céljuknak megfelelően.
• 4. Hatékonyság. Az algoritmus összes előírásának pontos végrehajtásával a folyamatot véges számú lépésben kell végrehajtani, és ezzel egyidejűleg valamilyen választ kell kapni a feladatra. Az egyik lehetséges megoldás annak megállapítása lehet, hogy a problémának nincs megoldása
• 5. Tömegjelleg. ugyanazt az algoritmust használva megoldhatja ugyanazt a típusú problémát, és megismételheti. A tömegkarakter tulajdonsága jelentősen növeli az algoritmusok gyakorlati értékét.

Az algoritmusok nagy értéke abban rejlik, hogy az előadó nem mélyedhet el annak értelmében, amit csinál, és ugyanakkor több tudást kap, mint az előadótól.

A legegyszerűbb műveletek, amelyekre a problémamegoldási folyamat megszakad, egy speciálisan az algoritmus egyes parancsainak meghatározott sorrendben történő végrehajtására kialakított automata eszközzel valósítható meg. Ha sikerül egy probléma megoldására algoritmust szerezni, akkor lehetségessé válik egy olyan gép létrehozása, amely automatizálná a megoldását.

Mindegyik algoritmus feltételezi bizonyos kezdeti adatok jelenlétét. Például egy orvosi felírásnál (algoritmusnál) a kiindulási adatok a gyógyszerek, az eredmény pedig egy fiola kész gyógyszerrel. Az összeadási algoritmusnál a bemeneti adat egy tagpár, az eredmény pedig ezek összege. Minden algoritmushoz tartozik az objektumok egy osztálya, amely elfogadható bemeneti adatként. A kezdeti adatok néha anyagi objektumok, néha pedig számok.

Az algoritmus szabály, ezért valamilyen nyelven kell megfogalmazni. A bemeneti adatokat és a kívánt eredményeket is le kell írni valamilyen nyelven, amely esetleg eltér attól a nyelvtől, amelyen az algoritmust leírják.

Így minden algoritmus két nyelvhez kapcsolódik: az egyikben önmagában fogalmazódik meg, a másik mondatai a kiindulási adatok érvényes változatai számára.

A probléma megoldására szolgáló algoritmus kidolgozását algoritmizálásnak nevezzük. Az algoritmizálás folyamatában a feladat egy bizonyos sorrendben elrendezett lépéssorozat felépítésére redukálódik.

Nincs egyértelmű különbség az algoritmusok és a programok között. A programot általában problémamegoldó algoritmusnak nevezik, amelyet úgy terveztek, hogy számítógéppel lehessen végrehajtani, és a használt programozási nyelv mondataival írják meg.

Algoritmikus szerkezet egy szabványos módja az algoritmus egyes lépéseinek összekapcsolásának egy tipikus műveletsorozat végrehajtása érdekében.

Az algoritmusok elméletében bebizonyosodott, hogy bármely algoritmus ábrázolható három algoritmikus struktúra kombinációjaként: sorozat, villa és ciklus.

Ez a műveletek egymás utáni végrehajtása (12. ábra).

Rizs. 12.

Abban az esetben használjuk, ha valamilyen logikai feltétel igazságától függően egy vagy másik műveletet kell végrehajtani (13. ábra).

Rizs. 13.

Az 1. és 2. művelet viszont más algoritmikus struktúrákat is tartalmazhat.

Ciklus . Akkor használatos, ha valamilyen műveletet többször kell végrehajtani. Kétféle ciklus létezik.

Akkor használatos, ha bizonyos műveleteket addig kell ismételni, amíg egy bizonyos feltétel hamis lesz (14. ábra).

Rizs. 14. Ciklus Előtt.

Kezdő hozzárendelések alatt a ciklusban használt változókhoz kezdeti értékek hozzárendelésének műveleteit értjük. Az ismétlődő műveletek sorozatát a hurok törzsének nevezzük.

Akkor használatos, amikor néhány műveletet meg kell ismételni, amíg egy bizonyos feltétel nem válik valóra (15. ábra).

Rizs. 15. Ciklus Viszlát.

A kurzus megismerteti a hallgatókkal az alapvető adatstruktúrákat és algoritmusokat, amelyek ismerete szükséges a különböző programozási problémák hatékony megoldásához. A kurzus készítői informatikában és programozásban tehetséges hallgatók, iskolások felkutatásával, képzésével foglalkoznak. Irányításuk alatt a diákcsapatok többször is Oroszország bajnokai lettek a programozásban, világ- és Európa-bajnokok.

A tanfolyamról

A kurzus olyan alapvető algoritmusok és adatstruktúrák tanulmányozására irányul, amelyek ismerete szükséges a különböző programozási problémák hatékony megoldásához. Különféle rendezési algoritmusok, lineáris adatszerkezetek, például sorok és listák, algoritmusok és adatstruktúrák az információk hatékony kereséséhez és tárolásához – kiegyensúlyozott keresési fák és hash-ek, valamint részstring keresési algoritmusok is számításba jönnek.

A tantárgy célja alapvető ismeretek elsajátítása az információk tárolására és lekérésére használt alapvető algoritmusokról, adatstruktúrákról.

A kurzus elvégzése után a hallgatók elsajátítják az alapvető programozási algoritmusok és adatstruktúrák elemzésének és megvalósításának, valamint az alkalmazott információs technológiák megvalósításához szükséges eszközök tervezésének és fejlesztésének készségeit.

A "Programozási algoritmusok és adatstruktúrák" kurzus teljesítése jelentősen növeli a szoftverfejlesztésben részt vevő hallgatók termelékenységét és versenyképességét.

Formátum

A tanfolyam videó előadásokat, előadási anyagokon alapuló felméréseket és gyakorlati programozási feladatokat tartalmaz, amelyek magukban foglalják a kurzusban tanult algoritmusok és adatstruktúrák önmegvalósítását a javasolt modern programozási nyelvek egyikén. A tanfolyam tíz hétig tart. Az egy tanulóra jutó átlagos heti terhelés 14 óra. A kurzus teljes komplexitása négy kreditegység.

Információs források

A tanfolyam elvégzéséhez és az összes javasolt feladat elvégzéséhez elegendő videós előadásanyag. A vizsgált témával kapcsolatos ismeretek elmélyítéséhez azonban használhatja a következő további forrásokat:

1. Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmusok: konstrukció és elemzés. - M.: Williams, 2012.
2. Aho A., Hopcroft D., Ulman D. Adatstruktúrák és algoritmusok. - M.: Williams, 2007.
3. Online jegyzetek a diszkrét matematikáról, algoritmusokról és adatstruktúrákról az ITMO Egyetem Számítástechnikai Tanszékén.

Követelmények

A tanfolyam sikeres elsajátításához ismerni kell a diszkrét matematika alapjait, közepes méretű programok objektum-orientált programozási nyelven való írásának képességét.

A kurzushoz az alábbi programozási nyelvek valamelyikének nyilvános fordítójára van szükség:

• Java: 8-as verzió (letöltési hivatkozás az Oracle webhelyén)
• C, C++: MinGW 5.1-es verzió (Linux esetén hasonló verziójú GCC használható), valamint Microsoft Visual Studio C++ 2013 (letöltheti a Visual Studio Express-t).
• C#: Microsoft Visual Studio C# 2013 (letöltheti a Visual Studio Express-t).
• Python: 3.5-ös verzió (letöltési link a python.org webhelyről)
• Scala: 2.11-es verzió (letöltési hivatkozás a scala-lang.org oldalról)
• Kotlin: 1.0-s verzió (hivatkozások a fordító telepítéséhez, az IntelliJ IDEA és az Eclipse bővítményeihez).

Tanfolyami program

A tanfolyam a következő témákat öleli fel:

1. Algoritmusok futási idejének becslése
2. Összehasonlításon alapuló rendezési algoritmusok (egyesítési rendezés, gyors rendezés, alsó korlát a rendezési algoritmusok idejére)
3. Lineáris idejű rendezési algoritmusok (számláló rendezés, numerikus rendezés, zsebre rendezés)
4. Elemi adatstruktúrák (verem, sor, csatolt listák)
5. Bináris kupac alapú algoritmusok (halom rendezés, prioritási sor)
6. Bevezetés a keresési algoritmusokba (bináris keresés rendezett tömbben, bináris keresési fa)
7. Kiegyensúlyozott keresési fák (a kiegyensúlyozott fák áttekintése, AVL fa, Splay fa)
8. Kivonatolás (zárt és nyitott címzésű hash táblák)
9. Bevezetés a karakterlánc-keresésbe (a legegyszerűbb részkarakterlánc-kereső algoritmus, Rabin-Karp algoritmus)
10. Részkarakterlánc-keresés (Knuth-Morris-Pratt algoritmus, Z-függvény, Boyer-Moore algoritmus)

Minden téma egy hét tanulást foglal magában. Hetente jelennek meg a programozási feladatok, amelyek a kurzusban tanult algoritmusok és adatstruktúrák önálló megvalósítását jelentik.

A kurzusnak kétféle határidője van (az értékelési tevékenységek elvégzésének határideje):
– puha határidő, amelyben az aktuális hét összes értékelési tevékenységét annak befejezése előtt el kell végezni;
– kemény határidő, amelyben további két hetet szánnak az értékelési tevékenységek végrehajtására a puha határidő után, amely után a vonatkozó tevékenységekhez való hozzáférés megszűnik.

Tanulási eredmények

• Képes alapvető programozási algoritmusok és adatstruktúrák elemzésére és megvalósítására
• Alkalmazott információs technológiák megvalósításának eszközeinek tervezésében és fejlesztésében való jártasság
• Algoritmusok kidolgozásának készsége az informatika területén végzett kísérleti kutatásokhoz

Kialakult kompetenciák

• 09.03.02 Információs rendszerek és technológiák
  1. Képes alapvető és alkalmazott információs technológiák tervezésére (PC-11)
  2. Képes információs technológiák (algoritmikus) megvalósítási eszközeinek fejlesztésére (PC-12)
  3. Részvételi hajlandóság kísérleti vizsgálatok megfogalmazásában és lefolytatásában (PC-23)

1. Az algoritmus fogalma

Algoritmus - ez egy pontos és érthető utasítás az előadó számára a feladat megoldását célzó műveletsor végrehajtására. Név " algoritmus" a közép-ázsiai matematikus, al-Khwarizmi nevének latin alakjából származik - Algorithmi.

Algoritmus végrehajtó- ez valamilyen absztrakt vagy valós (műszaki, biológiai vagy biotechnikai) rendszer, amely képes végrehajtani az algoritmus által előírt műveleteket. Az előadót a következők jellemzik: környezet, elemi cselekvések, parancsrendszer, hibák. szerda(vagy környezet) az előadó "élőhelye". . Minden végrehajtó csak bizonyos szigorúan meghatározott listából tud parancsokat végrehajtani - parancsrendszerek előadó. Minden parancshoz meg kell adni az alkalmazhatósági feltételeket (mely környezeti állapotokban lehet a parancsot végrehajtani), és le kell írni a parancs végrehajtásának eredményét. A parancs hívása után a végrehajtó végrehajtja a megfelelőt elemi cselekvés. Kudarcok végrehajtó hibák akkor fordulnak elő, ha egy parancsot akkor hívnak meg, amikor a környezet állapota érvénytelen.

A számítástechnikában az algoritmusok univerzális végrehajtója a számítógép.

2. Algoritmusok tulajdonságai

A következőket lehet megkülönböztetni Az algoritmusok alapvető tulajdonságai:

1) Világosság az előadó számára - i.e. Az algoritmus végrehajtójának tudnia kell, hogyan kell végrehajtani.

2) diszkrétség(szakadás, szétválás) - i.e. az algoritmusnak a probléma megoldásának folyamatát egyszerű vagy korábban meghatározott lépések egymás utáni végrehajtásaként kell ábrázolnia.

3) Bizonyosság- azaz az algoritmus minden szabályának világosnak, egyértelműnek kell lennie, és nem hagyhat helyet az eltéréseknek.

4) Hatékonyság(vagy végtag). Ez a tulajdonság az, hogy az algoritmusnak véges számú lépésben kell a feladat megoldásához vezetnie.

5) tömegjelleg- azt jelenti, hogy a probléma megoldásának algoritmusát általános formában dolgozzák ki, pl. egy bizonyos problémaosztályra kell alkalmazni, amelyek csak a kezdeti adatokban különböznek egymástól. Ebben az esetben a kiindulási adatok egy bizonyos területről választhatók ki, amelyet ún az algoritmus hatóköre.

3. Algoritmusok ábrázolási formái

A leggyakrabban algoritmusok reprezentációs formái a következők: verbális, grafikus, pszeudokód és szoftver.

1) Szóalak a rekord az adatfeldolgozás egymást követő szakaszainak leírása természetes nyelven (például oroszul).

Példa.Írjon fel egy algoritmust két természetes szám legnagyobb közös osztójának (GCD) megkeresésére.

Algoritmus: 1) állítson be két számot; 2) ha a számok egyenlőek, akkor vegye fel bármelyiket válaszként, és hagyja abba, ellenkező esetben folytassa az algoritmust; 3) határozza meg a nagyobb számokat; 4) cserélje ki a nagyobb számok közül a nagyobb és a kisebb közötti különbséget; 5) ismételje meg az algoritmust a 2. lépéstől.

A leírt algoritmus bármely természetes számra alkalmazható, és véges számú lépésben kell a feladat megoldásához vezetnie.

A verbális módszert nem használják széles körben, mivel az ilyen leírások:

a) szigorúan nem formalizálhatók;

b) szenvednek az iratok bőbeszédűségétől;

c) lehetővé teszi az egyes előírások félreérthető értelmezését.

2) Grafikus mód Az algoritmusok reprezentációja tömörebb és vizuálisabb a verbálishoz képest. A grafikus végrehajtás során az algoritmust összekapcsolt funkcionális blokkok sorozataként ábrázolják, amelyek mindegyike egy-egy művelet végrehajtásának felel meg. Az ilyen grafikus ábrázolást algoritmusdiagramnak, ill blokk diagramm . A folyamatábrán minden egyes művelettípus egy geometriai alakzatnak felel meg, az úgynevezett blokk szimbólum. A blokk szimbólumok összekapcsolódnak átmeneti vonalak amelyek meghatározzák a műveletek végrehajtásának sorrendjét.

Erről bővebben lent...

3) Pszeudokód egy jelölések és szabályok rendszere, amelyet az algoritmusok egységes rögzítésére terveztek. Köztes helyet foglal el a természetes és formális nyelvek között.

Egyrészt közel áll a hétköznapi természetes nyelvhez, így az algoritmusok sima szövegként írhatók és olvashatók benne. Másrészt a pszeudokód használ hivatalos szavakés a matematikai szimbolizmus, amely az algoritmus jelölését közelebb hozza az általánosan elfogadott matematikai jelöléshez. A funkcionális szavak a nyomtatott szövegben félkövérrel, a kézzel írt szövegben pedig alá vannak húzva, hogy meg lehessen különböztetni őket a szöveg többi részétől.

Példa. 1) állítson be két x és y számot; 2) HA x=y, AKKOR GCD=x és VÉGE; 3) HA x>y, AKKOR x=x-y, MÁS y=y-x; 4) Ugorjon a 2. pontra.

4) Program űrlap különböző programozási nyelveken írt programok szövege.

Az alábbiakban a blokkdiagramokon található grafikus szimbólumok láthatók.

Az ábrákon a SERIES egy vagy több operátort jelent; A FELTÉTEL egy logikai kifejezés (LP) (ha értéke IGAZ, az átmenet az IGEN ág mentén történik, egyébként - a NEM mentén). A paraméterrel ellátott ciklusdiagramon a következő jelöléseket használjuk: PC - ciklusparaméter, NC - ciklusparaméter kezdeti értéke, KZ - ciklusparaméter végső értéke, Ш - ciklusparaméter módosításának lépése.

A blokkdiagramokon az algoritmus kezdetét és végét ovális jelzi, a bemeneti és kimeneti változókat paralelogrammában írjuk fel.

). Az ilyen programozási rendszert használó program fejlesztése két szakaszból áll: 1) a program grafikus felületének elemeinek vizuális módban történő létrehozása; 2) programkód fejlesztése. Ez a megközelítés nagyban megkönnyíti a programok létrehozását, mivel a grafikus felület manuális (eljárási nyelveken) fejlesztése összetett és időigényes folyamat.

Az algoritmusok tanulmányozásának és megismerésének fontosságának megértéséhez az első lépés az, hogy pontosan meghatározzuk, mit is kell érteni egy algoritmuson. A programozásban egy algoritmus az világos és pontos műveletsor, programozási nyelven írva.Az Algorithms: Construction and Analysis című népszerű könyv (Kormen, Leyzerson, Rivest, Stein) szerint "algoritmus (algoritmus) bármely jól definiált számítási eljárás, amelynek bemenetét (bemenetét) táplálják valamilyen érték vagy értékkészlet, és amelynek eredménye egy kimeneti érték vagy értékkészlet." Más szóval, az algoritmusok olyanok, mint egy jól meghatározott cél eléréséhez vezető útiterv. A Fibonacci-sorozat feltételeinek kiszámítására szolgáló kód egy meghatározott algoritmus megvalósítása. Még a két szám összeadásának egyszerű függvénye is egy algoritmus, bár egyszerű.

Algoritmus (program) létrehozásához tudnia kell:

a feladat kezdeti adatainak teljes készlete (az objektum kezdeti állapota);

az algoritmus létrehozásának célja (az objektum végső állapota);

a végrehajtó parancsrendszere (vagyis a végrehajtó által megértett és végrehajtható parancsok halmaza).

Az eredményül kapott algoritmusnak (programnak) a következő tulajdonságokkal kell rendelkeznie:

diszkrétség(az algoritmus külön lépésekre oszlik - parancsokra);

egyediség(minden parancs meghatározza az előadó egyetlen lehetséges műveletét);

érthetőség(az algoritmus összes parancsa benne van a végrehajtó parancsrendszerében);

hatékonyság(az előadónak véges számú lépésben kell megoldania a feladatot).

A legtöbb algoritmusnak is megvan a tulajdonsága tömegjelleg(ugyanazt az algoritmust használva sok azonos típusú problémát megoldhat).

Egyes algoritmusok, például a Fibonacci-szekvencia kiszámítására, intuitívak, és a logikus gondolkodás és problémamegoldás veleszületett készségeihez tartoznak. Legtöbbünknek azonban hasznára válik az összetett algoritmusok elsajátítása is, így a jövőben építőelemként használhatjuk őket a logikai problémák hatékonyabb megoldásához. Valójában meglepődhet, ha megtudja, mennyi összetett algoritmust használnak az emberek e-mailek ellenőrzése vagy zenehallgatás során. Ez a cikk az algoritmuselemzés néhány alapötletét mutatja be gyakorlati példákkal, amelyek szemléltetik az algoritmusok tanulásának fontosságát.

A programozási nyelv az algoritmikus struktúrák és adatok írásához szükséges szabályok összessége.

Az algoritmus végrehajtási idejének elemzése

Az algoritmusok egyik legfontosabb szempontja a sebesség. Gyakran könnyű olyan algoritmust találni, amely megold egy problémát, de ha az algoritmus túl lassú, akkor visszaküldik felülvizsgálatra. Mivel az algoritmus pontos sebessége az algoritmus futtatásának helyétől, valamint a megvalósítás részleteitől függ, az informatikusok általában a bemeneti adatokhoz viszonyított végrehajtási időről beszélnek. Például, ha a bemenet N egész számból áll, akkor az algoritmusnak N 2 -vel arányos futási ideje lehet, amelyet O(N 2 )-ként ábrázolunk. Ez azt jelenti, hogy ha az algoritmus megvalósítását egy N méretű bemenettel rendelkező számítógépen futtatja, akkor C*N 2 másodpercet vesz igénybe, ahol C valamilyen állandó, amely nem változik a bemenet méretével.

Számos összetett algoritmus végrehajtási ideje azonban nemcsak a bemeneti adatok méretétől függ, hanem sok más tényezőtől is. Például egy egész számok halmazának rendezésére szolgáló algoritmus sokkal gyorsabban futhat, ha a halmaz már rendezve van. Szokás a legrosszabb eset teljesítményéről és az átlagos esetteljesítményről beszélni. A legrosszabb eset végrehajtási ideje az a maximális idő, ameddig egy algoritmus a „legrosszabb” bemeneten futhat. Az átlagos végrehajtási eset az algoritmus átlagos futási ideje az összes lehetséges bemeneten. E két futásidejű típus közül a legrosszabb esetet a legkönnyebb megindokolni, ezért gyakrabban használják viszonyítási alapként egy adott algoritmushoz. Egy algoritmus legrosszabb és átlagos futási idejének meghatározása meglehetősen bonyolult lehet, hiszen általában nem lehet minden lehetséges bemenetre futtatni az algoritmust.

Fentebb megjegyeztük, hogy ugyanaz az algoritmus többféleképpen írható. Írhatsz egy algoritmust természetes nyelv. Ebben a formában recepteket, utasításokat stb. Formális végrehajtóknak szánt algoritmusok írásához speciális programozási nyelvek. Bármely algoritmus leírható grafikusan blokkdiagram formában. Ehhez egy speciális jelölési rendszert fejlesztettek ki:

Adjunk példát két mennyiség összegzésére szolgáló algoritmus leírására blokkdiagram formájában:

Az algoritmus leírásának ez a módja a legvilágosabb és legérthetőbb az ember számára. Ezért a formális végrehajtó algoritmusokat általában először blokkdiagram formájában fejlesztik ki, és csak azután készítenek programot az egyiken.

Válogatás

A rendezés jó példa a programozók által gyakran használt algoritmusra. Az elemcsoportok rendezésének legegyszerűbb módja, ha először eltávolítja a legkisebb elemet a csoportból, és ezt helyezi előtérbe. Ezután a második legnagyobb elemet eltávolítjuk, és második helyre helyezzük, és így tovább. Sajnos ennek az algoritmusnak a futási ideje O(N 2), ami azt jelenti, hogy az elemek számának négyzetével arányos időbe telik. Ha több milliárd elemet kellene rendeznünk, akkor ehhez az algoritmushoz 10 18 műveletre lenne szükség. Ha feltételezzük, hogy a tipikus asztali számítógépek körülbelül 10 9 műveletet végeznek másodpercenként, akkor évekbe telhet ennek a milliárdos elemnek a rendezése.

Szerencsére számos jobb algoritmus létezik, mint például a gyors rendezés (quicksort), a kupac rendezés (heapsort) és az egyesítő rendezés (mergesort). Ezeknek az algoritmusoknak a futási ideje O(N * Log(N)). Így a tételek milliárdjainak rendezéséhez szükséges műveletek száma olyan ésszerű határokra csökken, hogy még a legolcsóbb asztali számítógép is képes rendezni. A milliárdos négyzetes műveletek (10 18) helyett ezek az algoritmusok mindössze 10 milliárd műveletet (10 10) igényelnek, i.e. 100 milliószor gyorsabb.

A legrövidebb út

Az egyik pontból a másikba vezető legrövidebb út megtalálására szolgáló algoritmusokat évek óta kutatják. Számos példa van ezen algoritmusok alkalmazására, azonban a bemutatás egyszerűsége érdekében ragaszkodunk a következő megállapításhoz: meg kell találni a legrövidebb utat A pontból B pontba egy több utcával és kereszteződéssel rendelkező városban. Számos különböző algoritmus létezik a probléma megoldására, mindegyiknek megvannak a maga előnyei és hátrányai. Mielőtt elmélyülnénk bennük, nézzük meg egy egyszerű brute-force algoritmus végrehajtási idejét. Ha az algoritmus figyelembe vesz minden lehetséges utat A-tól B-ig (ami nem alkot ciklusokat), akkor nem valószínű, hogy életünk során véget ér, még akkor sem, ha A és B egy kisvárosban van. Ennek az algoritmusnak a futási ideje exponenciális, amelyet néhány C esetén O(C N)-ként jelölünk. Még kis C érték esetén is C N csillagászati ​​számmá válik, amikor N mérsékelten nagy értéket vesz fel.

A probléma megoldására szolgáló egyik leggyorsabb algoritmus futási ideje O(E+V*Log(V)), ahol E az útszakaszok száma, V pedig a kereszteződések száma. Az algoritmus körülbelül 2 másodpercet vesz igénybe, hogy megtalálja a legrövidebb utat egy 10 000 kereszteződésből és 20 000 útszakaszból álló városban (általában körülbelül 2 útszakasz van kereszteződésenként). Ez az algoritmus Dijkstra algoritmusaként ismert, és meglehetősen összetett, és prioritási soradat-struktúra használatát igényli. Azonban bizonyos esetekben még ez a végrehajtási idő is túl lassú (vegyük például a legrövidebb út megtalálását New Yorkból San Franciscoba - az USA-ban milliónyi kereszteződés van), ilyenkor a programozók a végrehajtási időt próbálják javítani a segítséggel. az úgynevezett heurisztikából. A heurisztika valaminek a közelítése, ami egy probléma szempontjából releváns. Például egy legrövidebb út probléma esetén hasznos lehet tudni, hogy egy pont milyen messze van a céltól. Ennek ismeretében lehetőség nyílik egy gyorsabb algoritmus kidolgozására (például az A* keresési algoritmus bizonyos esetekben sokkal gyorsabban működik, mint a Dijkstra-féle algoritmus). Ez a megközelítés a legrosszabb esetben sem mindig javítja az algoritmus végrehajtási idejét, de a legtöbb valós alkalmazásban az algoritmus gyorsabban kezd futni.

Hozzávetőleges algoritmusok

Néha még a legfejlettebb, legfejlettebb heurisztikával rendelkező algoritmus is túl lassú a leggyorsabb számítógépen. Ilyen esetekben csökkenteni kell a végeredmény pontosságát. Ahelyett, hogy a legrövidebb utat keresné, korlátozhatja magát egy olyan útra, amely például 10%-kal nagyobb, mint a legrövidebb út.

Valójában jó néhány olyan fontos probléma van, amelyre a jelenleg ismert algoritmusok túl lassan adják az optimális eredményt. E problémák leghíresebb csoportja az NP (nem determinisztikus polinom). Ha egy problémát NP-teljesnek vagy NP-nehéznek neveznek, az azt jelenti, hogy senki sem tud elég jó módszert az optimális megoldás megtalálására. Továbbá, ha kifejlesztünk egy hatékony algoritmust egy NP-nehéz probléma megoldására, akkor ez az algoritmus minden NP-nehéz feladatra alkalmazható.

Az NP-nehéz probléma jó példája az utazó eladó probléma. Az eladó N várost szeretne meglátogatni, és tudja, mennyi ideig tart eljutni egyik városból a másikba. A kérdés az, hogy milyen gyorsan tudja bejárni az összes várost? A probléma megoldására szolgáló leggyorsabb ismert algoritmus túl lassú – és sokan azt hiszik, hogy mindig is az lesz –, ezért a programozók olyan algoritmusokat keresnek, amelyek elég gyorsak ahhoz, hogy jó megoldást adjanak, de gyakran nem optimálisak.

Véletlenszerű algoritmusok

Néhány probléma megoldásának másik módja az algoritmus véletlenszerűvé tétele. Ez a megközelítés a legrosszabb esetben nem javítja az algoritmus idejét, középesetben azonban gyakran jól működik. A gyorsrendezési algoritmus jó példa a véletlenszerűsítés alkalmazására. A legrosszabb esetben a Quicksort algoritmus O(N 2) elemcsoportot rendez, ahol N az elemek száma. Ha ebben az algoritmusban véletlenszerűsítést alkalmazunk, akkor a legrosszabb eset esélyei marginálisan kicsivé válnak, és átlagosan a gyorsrendezési algoritmus O(N*Log(N)) idő alatt fut le. Más algoritmusok még a legrosszabb esetben is garantálják az O(N*Log(N)) értéket, de átlagos esetben lassabbak. Míg mindkét algoritmus futási ideje N*Log(N) arányos, a gyorsrendezés algoritmusának kisebb a konstans tényezője – pl. ehhez C*N*Log(N) szükséges, míg más algoritmusok több mint 2*C*N*Log(N) műveletet igényelnek.

Egy másik algoritmus, amely véletlen számokat használ, egy számcsoport mediánját keresi, és átlagos futásideje O(N). Ez sokkal gyorsabb, mint az az algoritmus, amely rendezi a számokat és kiválasztja az átlagot, és O(N*Log(N)) függvényben fut. Vannak determinisztikus (nem véletlenszerű) algoritmusok, amelyek meg tudják találni a mediánt O(N) idő alatt, de a véletlenszerű algoritmus könnyebben érthető és gyakran gyorsabb, mint ezek a determinisztikus algoritmusok.

A medián keresési algoritmus fő ötlete az, hogy a számok közül véletlenszerű számot válasszunk, és kiszámoljuk, hogy a csoportban hány szám kisebb, mint a kiválasztott szám. Tegyük fel, hogy N szám van, ezek közül K kisebb vagy egyenlő, mint a kiválasztott szám. Ha K kisebb, mint fele N, akkor tudjuk, hogy a medián az (N/2-K)-edik szám, amely nagyobb, mint a véletlenszám, ezért a véletlenszámnál kisebb vagy azzal egyenlő K számot elvetjük. Tegyük fel, hogy a medián helyett az (N/2-K)-ik legkisebb számot szeretnénk megtalálni. Az algoritmus ugyanaz, csak véletlenszerűen választunk ki egy számot, és ismételjük meg a leírt lépéseket.

Tömörítés

Az algoritmusok másik osztálya adattömörítésre készült. Ez az algoritmus nem a várt eredménnyel jár (mint például a rendezési algoritmus), hanem bizonyos kritériumok szerint történik az optimalizálás. Adattömörítés esetén egy algoritmus (pl. LZW) megpróbálja elérni, hogy az adatok minél kevesebb bájtot vegyenek fel, de ugyanakkor úgy, hogy az eredeti formájukra kibontható legyen. Bizonyos esetekben az ilyen típusú algoritmusok ugyanazokat a módszereket használják, mint a többi algoritmus, ami jó eredményt ad, de nem optimális. Például a JPG és MP3 úgy tömöríti az adatokat, hogy a végeredmény gyengébb minőségű legyen, mint az eredeti, de a méret kisebb. Az MP3-tömörítés nem őrzi meg az eredeti hangfájl minden funkcióját, de igyekszik megőrizni a kellő részletet, hogy elfogadható minőséget biztosítson, miközben jelentősen csökkenti a fájlméretet. A JPG formátum ugyanazt az elvet követi, de a részletek jelentősen eltérnek, mert a cél a kép tömörítése, nem a hang.

Miért kell ismerned mindenféle algoritmust

Az algoritmusok megfelelő használatához fontos ismerni az összes említett algoritmustípust. Ha fontos szoftvert kell fejlesztenie, akkor képesnek kell lennie arra, hogy értékelje az algoritmus sebességét. A becslés pontossága attól függ, hogy mennyit tud az algoritmusok végrehajtási idejének elemzéséről. Ezenkívül ismernie kell az algoritmusok részleteit, amelyek lehetővé teszik olyan speciális esetek előrejelzését, amelyekben a program nem működik gyorsan, vagy elfogadhatatlan eredményeket ad.

Természetesen előfordul, hogy korábban feltáratlan problémákba ütközik. Ilyen esetekben új algoritmust kell kidolgozni, vagy a régi algoritmust új módon kell alkalmazni. Minél többet tud az algoritmusokról, annál valószínűbb, hogy jó megoldást talál egy problémára. Sok esetben az új probléma könnyen redukálható a régire, de ehhez a régi problémák alapvető megértése szükséges.

Példaként tekintse meg a hálózati kapcsolók működését. A kapcsolóhoz N kábel van csatlakoztatva, és az ezeken a kábeleken keresztül érkező adatcsomagokat fogadja. A kapcsolónak először elemeznie kell a csomagokat, majd vissza kell küldenie a megfelelő kábelen keresztül. A kapcsoló, mint egy számítógép, diszkrét módban működik - a csomagok diszkrét időközönként kerülnek elküldésre, nem folyamatosan. Egy gyors kapcsoló minden intervallumban igyekszik minél több csomagot elküldeni, különben felhalmozódnak és a kapcsoló "leesik". Az algoritmus célja, hogy az egyes intervallumok során a lehető legtöbb csomagot küldje el, és az is, hogy a többinél korábban érkezett csomagok is korábban kerüljenek elküldésre, mint mások. Ebben az esetben kiderül, hogy egy "stabil illesztés" néven ismert algoritmus alkalmas a probléma megoldására, bár ez első pillantásra nem biztos, hogy nyilvánvaló. A probléma és a megoldás közötti ilyen összefüggéseket csak a már meglévő algoritmikus ismeretek segítségével lehet felfedezni.

Valós Példák

Rengeteg példa van a valódi problémák megoldására, amelyekhez a legújabb algoritmusok szükségesek. Szinte minden, amit számítógépen csinál, olyan algoritmusokon múlik, amelyeket valaki nagyon régóta fejleszt. Még a legegyszerűbb programok sem léteznének az algoritmusok nélkül, amelyek a színfalak mögött dolgoznak a memória kezelésére és az adatok betöltésére a merevlemezről.

Több tucat példa van az összetett algoritmusok használatára, de két olyan problémát fogunk megvitatni, amelyek ugyanolyan készségeket igényelnek, mint néhány probléma megoldása a TopCoder-en. Az első probléma a maximális áramlási probléma néven ismert, a második pedig a dinamikus programozáshoz kapcsolódik, egy olyan technikához, amely gyakran lehetővé teszi a problémák megoldását lehetetlennek tűnő villámgyorsan.

Algoritmus a maximális áramlás meghatározásához

A maximális áramlás megtalálásának feladata, hogy a rendelkezésre álló hálózatot a legjobb módon használjuk arra, hogy valamit egyik helyről a másikra mozgassunk. Konkrétan, ilyen probléma először az 1950-es években merült fel a Szovjetunió vasúti sínjeivel kapcsolatban. Az USA tudni akarta, hogy a Szovjetunió milyen gyorsan tud anyagokat szállítani a kelet-európai műholdállamokba vasúti hálózatán keresztül.

Ezenkívül az USA tudni akarta, hogy a sínek melyik részét lehet a legkönnyebben megsemmisíteni, hogy elvághassák a műholdas államokat a Szovjetunió többi részétől. Kiderült, hogy a két probléma szorosan összefügg, és a maximális áramlási probléma megoldása megoldotta a minimális vágási problémát is, amely végül feltárja a legolcsóbb módot a Szovjetunió elvágására a műholdaktól.

Az első hatékony algoritmust a maximális áramlás meghatározására Ford és Fulkerson tudósok találták fel. Az algoritmust később Ford-Fulkerson algoritmusnak nevezték el, és a számítástechnika egyik legismertebb algoritmusa. Az elmúlt 50 évben az algoritmus számos fejlesztésen ment keresztül, amelyek gyorsabbá tették (bár e fejlesztések némelyike ​​bonyolultságában félelmetes).

Mivel a probléma egyértelműen meghatározásra került, sok különböző alkalmazást fedeztek fel. Az algoritmus közvetlenül kapcsolódik az internethez, ahol fontos, hogy a lehető legtöbb adatot szállítsák egyik pontból a másikba. A feladat számos üzleti folyamatban is előfordul, és az operációkutatás fontos részét képezi. Például, ha van N alkalmazott és N feladatot kell elvégezni, de nem minden alkalmazott tudja kezelni az egyes feladatokat, akkor a maximális áramlás keresése megoldást ad arra, hogyan rendeljünk N alkalmazottat a feladatokhoz úgy, hogy minden feladat befejeződött. , feltéve, hogy a Lehet. A TopCoder SRM 200 Graduation problémája jó példa a maximális áramlási problémára.

Sorozatok összehasonlítása

Sok kódolónak egész pályafutása során soha nem kellett dinamikus programozást használó algoritmust megvalósítania. A dinamikus programozást azonban számos fontos algoritmus alkalmazza. Az egyik algoritmus az, hogy különbségeket keresünk két szekvencia között, amit valószínűleg a legtöbb programozó használt, bár valószínűleg nem értette. Ez az algoritmus kiszámítja az A szekvencia B szekvenciává konvertálásához szükséges beszúrások, törlések és szerkesztések minimális számát.

Vegyük például az „AABAA” és „AAAB” sorozatokat. Az első szekvencia második szekvenciává alakításához a legegyszerűbb eltávolítani a B-t a közepén, és az utolsó A-t B-re cserélni. Ennek az algoritmusnak számos alkalmazása van, beleértve néhány DNS- és plágiumészlelési feladatot is. Sok programozó azonban főleg ugyanazon fájl verzióinak forráskóddal való összehasonlítására használja. Ha a sorozat elemei sorok a fájlban, akkor ez az algoritmus lehetővé teszi, hogy megtudja, mely sorokat kell törölni, beilleszteni, módosítani a fájl egyik verziójának a másikra való konvertálásához.

Dinamikus programozás nélkül exponenciális számú transzformáción kell keresztülmennie, hogy egyik sorozatból a másikba kerüljön. A dinamikus programozás azonban az algoritmus végrehajtási idejét O(N*M-re) csökkenti, ahol N és M a két sorozat elemeinek száma.

Következtetés

Hány különböző probléma létezik, annyi különböző algoritmus létezik a megoldásukra. Jó eséllyel azonban a megoldani kívánt probléma valamilyen módon hasonló egy másik problémához. Az algoritmusok széles skálájának mélyreható megértésével képes lesz kiválasztani a megfelelő algoritmust, és alkalmazni tudja egy problémára. Ezenkívül a TopCoder versenyeken való problémák megoldása segít fejleszteni tudását ezen a területen. E feladatok közül sok mesterségesnek és irreálisnak tűnik, de ugyanazt az algoritmikus tudáskészletet követeli meg, mint a való világban minden nap.