Az algoritmus egy olyan matematikai fogalom, illetve eljárás, ami vagy konstrukciót vagy egy függvény kiszámítását teszi lehetővé, paraméterektől függetlenül és amely mechanikusan, gondolkodás nélkül láncszerüen hajtja végre szisztematikusan a feladatot. Egy programozási nyelven írt számítógépi program átgondolt algoritmus alapján fut le. A matematikai gépek valamilyen bemenetből valamilyen kimenetre jutunk. A matematikai gépek csak elméletben léteznek, mert végtelen bővíthető memóriát adunk hozzá.Egy probléma végtelen sok példányból áll, amelyek aztán tetszőlegesen nagy méretűek, ezért elméletben idealizáljuk a hardver hátteret. Az utóbbi megközelítésnek az az előnye, hogy nincsenek korlátok. A lényege egy központi rész (CPU), amely korlátos mert a bemenettől független, és egy végtelen tárolót egy lineális tömböt használ memóriának. Pontosabban, a memória egy végtelen, egydimenziós cellákból álló tömb. A vezérlés egy véges automata, amely képes tetszőleges lokális változtatásokat végrehajtani a szkennelt memóriacellán, és fokozatosan változtatni a szkennelt pozíciót. Számítógépek modelljei alapján minden olyan számítás elvégezhető, amelyet bármely más matematikai gépmodellen el lehetne végezni. Ezt a gépfogalmat főként elméleti vizsgálatokban használjuk. Kevésbé alkalmas konkrét algoritmusok definiálására, mivel a leírása nehézkes, és főleg azért, mert számos fontos szempontból eltér a meglévő számítógépektől. Az adattároláskor a RAM egyetlen lépésben elérhet egy tetszőleges memóriacellát. A valós világ számítógépeinek egyszerűsített modelljének tekinthető, azzal az absztrakcióval együtt, hogy korlátlan memóriával rendelkezik, és képes tetszőlegesen nagy egész számokat tárolni minden egyes memóriacellájában. A RAM tetszőleges programozási nyelven programozható. Az algoritmusok leírásához célszerű a RAM-ot használni, mivel ez áll a legközelebb a valódi programozáshoz. De látni fogjuk, hogy a RAM sok szempontból ekvivalens; ami a legfontosabb, ugyanazok a függvények számíthatók ki a RAM-on. Látszólagos elméleti korlátaik ellenére a logikai áramköröket is a számítás modelljének tekintjük. Egy adott logikai áramkör csak adott bemeneti méretet engedélyez. Ily módon csak véges számú problémát tud megoldani; nyilvánvaló lesz azonban, hogy rögzített bemeneti méret esetén minden függvény kiszámítható egy logikai áramkörrel. Ha azonban korlátozzuk a számítási időt, akkor a logikai áramkörökre és a RAM-ra vonatkozó problémák közötti különbség nem lesz olyan lényeges. Mivel a logikai áramkörök szerkezete és működése a legátláthatóbb és legkönnyebben kezelhető, nagyon fontos szerepet játszanak az elméleti vizsgálatokban (különösen a bonyolultság alsó korlátainak bizonyításában). Ha egy logikai áramkörhöz órajel- és memóriaregisztereket adunk, akkor megkapjuk az összekapcsolt véges automatákat. A végtelen gépek egyik legegyszerűbb modellje, ha végtelen számú hasonló automatát kapcsolunk össze egy tömbbe. Így egy komplex egy cellás automatát kapunk. Azt mondjuk, hogy az M gép szimulálja az N gépet, ha az N belső állapotai és átmenetei az M gép által nyomon követhetők olyan módon, hogy ugyanazokból a bemenetekből M ugyanazokat a kimeneteket számítja ki, mint N. Egy véges automata egy nagyon egyszerű és nagyon általános számítástechnikai eszköz. Csak azt feltételezzük, hogy ha bemenetet kap, akkor megváltoztatja belső állapotát és kimenetet ad ki. Ha végtelen állapotot engedélyeznénk, szinte bármit modellezhetnénk véges automataként. Olyan automaták érdekelnek minket, ahol az állapotok száma sokkal kisebb - általában feltételezzük, hogy korlátos marad, míg a bemenet mérete korlátlan. Egynyelvet regulárisnak nevezünk, ha létezik olyan automata, amely pontosan az általunk preferált bemeneteket fogadja el, tehát minden véges automata leírható egy irányított gráffal. Tehát; az algoritmus egy mechanikus, lépésről lépésre haladó eljárás, a Turing-gép pedig egy elméleti számítási modell, amely a végtelen memóriája miatt korlátok nélkül működik. A szöveged jól mutatja be a matematikai alapokat, de pontosítani kell néhány fogalmat: a végtelen memóriás modell a Turing-gép, míg a véletlen elérésű RAM-modell áll közelebb a mai számítógépekhez.Az algoritmusok és gépek alapjaiAlgoritmus: pontos, gépies és véges lépéssorozat egy feladat megoldására.Turing-gép: elméleti modell egy központi vezérléssel és egy végtelen szalag memóriával.RAM-modell: a valós gépekhez jobban hasonlító modell, amely közvetlenül eléri a memóriacellákat.A Church–Turing tézis lényege a különböző elméleti számítási modell, ami mint a Turing-gép és a RAM-modellnél is ugyanazt a halmazát tudja kiszámítani a függvényeknek.univerzalitás: amit az egyik modell meg tud oldani, azt a többi is képes kiszámítani. A Turing-gép és a RAM-modell egyaránt elméleti számítási modell, amelyek ekvivalensek a kiszámíthatóság szempontjából, de a RAM-modell közvetlenebbül tükrözi a modern számítógépek címzéses memóriakezelését, míg a Turing-gép a szalagon történő szekenciális lépegetést használja. Mindkét eszköz alapvető fontosságú az algoritmusok és a számítási komplexitás elméleti vizsgálatában. Főbb különbségekMemóriakezelés: A Turing-gépnél a szalag lépésről lépésre járható be, míg a RAM-modellben a memóriacímek közvetlenül elérhetők (mint a modern memóriákban).Hatékonyság és komplexitás: A RAM-modell sokkal élethűbben modellezi a valódi algoritmusok futási idejét (pl. egy tömb eleminek elérését), mert a közvetlen címzést egy lépésnek tekinti, míg ugyanez egy Turing-gépen sok lépesbe (szalagon való utazásba) telhet.Matematikai kezelhetőség: A Turing-gép rendkívül egyszerű felépítése miatt könnyebb formálisan bizonyítani matematikai tételeket, a RAM-modell pedig a gyakorlati programozási nyelvekhez és algoritmusokhoz (pl. pointerek, tömbök) közelít jobban. A Turing-gép úgynevezett absztrakt automata: a valóságos digitális számítógépek nagyon leegyszerűsített modellje, elméleti munkákhoz. A Turing-gép aktuális konfigurációja, a gép működése során egy véges vagy végtelen, megszámlálható tagú konfigurációsorozat jön létre. Míg a Turing-gép, azaz egy algoritmus a Turing-gépek elméletében matematikailag egy formális elemnyolcas, addig a gép működése, vagyis egy-egy számítási eljárása, azaz az algoritmus egy konkrét megvalósulása semmi más, mint ez a megszámlálható tagú konfigurációsorozat. A Turing-algoritmusok megszámlálhatóak és felsorolhatóak. A Turing gépek izomorfok, mert olyan struktúrákat vagy rendszereket használnak, amelyek szerkezetileg megegyeznek, még akkor is, ha az elemeik különböznek. Kölcsönösen egyértelmű megfeleltetés (bijekció) áll fenn közöttük, ami megőrzi a belső tulajdonságokat.A fogalommal leggyakrabban az alábbi területeken találkozhatsz. A matematikai struktúrák (pl. csoportok, testek) közötti olyan leképezés, amely az összes műveleti szabályt és relációt megtartja. Az izomorf (görög eredetű szó: iszosz = azonos, morphé = alak) kifejezés olyan struktúrákra vagy rendszerekre utal, amelyek szerkezetileg megegyeznek, még akkor is, ha az elemeik különböznek, de a különböző adatszerkezetek logikai felépítésének egyezése állandó.
Abstract
The essence of the algorithm is a mathematical concept or procedure that allows either a construction or the calculation of a function, regardless of parameters and that mechanically, without thinking, systematically performs the task in a chain-like manner. A computer program written in a programming language runs based on a well-thought-out algorithm. Mathematical machines get some output from some input. Mathematical machines only exist in theory because we add infinitely expandable memory. A problem consists of an infinite number of instances, which are then arbitrarily large, so in theory we idealize the hardware background. The advantage of the latter approach is that there are no limits. Its essence is a central part (CPU), which is limited because it is independent of the input, and uses an infinite storage or a linear array as memory. More precisely, memory is an infinite, one-dimensional array of cells. The control is a finite automaton that can make arbitrary local changes to the scanned memory cell and gradually change the scanned position. Based on computer models, any calculation that could be performed on any other mathematical machine model can be performed. This machine concept is mainly used in theoretical studies. It is less suitable for defining concrete algorithms, because its description is cumbersome, and mainly because it differs from existing computers in several important respects. When storing data, RAM can access any memory cell in a single step. It can be considered a simplified model of real-world computers, with the abstraction that it has unlimited memory and can store arbitrarily large integers in each of its memory cells. RAM can be programmed in any programming language. It is convenient to use RAM to describe algorithms, since it is the closest to real programming. But we will see that RAM is equivalent in many respects; most importantly, the same functions can be computed on RAM. Despite their apparent theoretical limitations, logic circuits are also considered models of computation. A given logic circuit only allows a given input size. In this way, it can solve only a finite number of problems; however, it will be obvious that for a fixed input size, any function can be computed with a logic circuit. However, if we limit the computation time, the difference between problems involving logic circuits and problems involving RAM will not be so significant. Since the structure and operation of logic circuits are the most transparent and easy to handle, they play a very important role in theoretical investigations (especially in proving lower bounds on complexity). If we add clock and memory registers to a logic circuit, we get connected finite automata. One of the simplest models of infinite machines is to connect an infinite number of similar automata into an array. Thus, we get a complex one-cell automata. We say that machine M simulates machine N if the internal states and transitions of machine N can be traced by machine M in such a way that, given the same inputs, M computes the same outputs as N. A finite automaton is a very simple and very general computational device. We simply assume that when it receives an input, it changes its internal state and outputs an output. If we were to allow infinite states, we could model almost anything as a finite automaton. We are interested in automatons where the number of states is much smaller - we usually assume that it remains bounded, while the size of the input is unbounded. A monolanguage is called regular if there exists an automaton that accepts exactly the inputs we prefer, so that every finite automaton can be described by a directed graph. So; an algorithm is a mechanical, step-by-step procedure, and a Turing machine is a theoretical computational model that operates without limits due to its infinite memory. Your text presents the mathematical basics well, but some concepts need to be clarified: the infinite memory model is the Turing machine, while the random access RAM model is closer to today's computers. Fundamentals of algorithms and machines Algorithm: a precise, mechanical and finite sequence of steps to solve a problem. Turing machine: a theoretical model with a central control and an infinite tape memory. RAM model: a model that is more similar to real machines, which directly accesses memory cells. The essence of the Church–Turing thesis is the different theoretical computational models, which, like the Turing machine and the RAM model, can calculate the same set of functions. Universality: what one model can solve, the others can also calculate. The Turing machine and the RAM model are both theoretical computational models, which are equivalent in terms of computability, but the RAM model more directly reflects the addressed memory management of modern computers, while the Turing machine.




