border=0

Algemiene oanpak fan 'e beskriuwing fan apparaten foar it ferwurkjen fan diskrete ynformaasje

Meastal is in automatysk in apparaat dat útfierd wurdt, sûnder de direkte yndieling fan in persoan, in bepaalde folchoarder fan operaasjes, as gefolch dêr't de transformaasje fan materiaal objekten, enerzjy of ynformaasje plakfine. As it seit "sûnder minske yntervinsje", betsjut it in mislearjen fan eksplisite kontrôle troch de persoan by de útfiering fan operaasjes. It feitlik is lykwols de kontrôle útoefene, mar yndirekt troch in programma dat foarskreaun is troch de man en yn it apparaat ynboud. Yn 'e takomst beheine wy ​​ússels om allinich de apparaten te ûntwikkeljen dy't ûntwurpen binne om automatysk ynformaasje te feroarjen dy't yn diskrete foarm presintearre is.

Omdat it apparaat mei de eksterne omjouwing kommunisearret, moat it fansels in ynfierkanaal hawwe, troch hokker ynformaasje yndield, en ek in útfierkanaal wêrby't it resultaat fan 'e konverzje útfierd is. Dêrneist kin it apparaat in ûnthâld hawwe dat syn aktuele steat fêst is ; It resultaat fan de ferwurking wurdt algemien bepaald troch de ynfier effekten en de ynterne steat fan it apparaat. Wy sizze dat in inkelde alfabet X (ynfier alfabet) brûkt wurdt om de ynput ynformaasje te fertsjintwurdigjen , en it definitive alfabet Y (output alphabet) wurdt brûkt om de útfier ynformaasje te fertsjinjen . As earder oanjûn is de easken foar de finiteness fan alfabetten in gefolch fan 'e klearens fan' e ferwurkingstiid. De ynterne steaten fan it apparaat foarmje ek in diskrete set, dy't as ynterne alfabetysk beskôge wurde kin - wy bepale it troch Q. As it tal ferskillende ynterne steaten, meitsje wy gjin annulearrings oer har.

Wy ferjilde ek dat de ynput fan symboalen ynfier en it skeakeljen fan apparaatstatus kontinuaasjoneel komme, mar op bepaalde punten yn 'e tiid, d. diskret. As de rigels fan momintwillekeurigens binne, prate wy oer de asynchrone organisaasje fan 'e operaasje fan' e eleminten fan it apparaat, bygelyks, it dialjen fan in tillefoannûmer of slúskoade. Yn komplekse apparaten is lykwols synchronike organisaasje faak brûkt, wêrby't de mominten fan komst en ôfslach fan sinjalen lykas it skeakjen fan ynterne staaten elkoar folgje troch itselde fêste tiidpunt Δt = konst , takt. Dizze mominten wurde ynsteld mei in spesjale apparaat - in klokgenerator (of in generator fan klokpulsen). It oantal klokpulsen per ienheid fan 'e tiid hjit de klokfrekwinsje - it is ien fan' e wichtichste faktueren dy't de snelheid fan it apparaat bepaalt. Jo kinne de tiid t 0 , t 1 , t 2 , yngean , ..., markearje de grinzen fan teken (t 0 komt oerien mei de start fan it wurk). Yn dit gefal kinne wy ​​útskriuwe dat de eveneminten relatearre binne mei de fysyk i - oankomst fan it ynfiersymboal, feroaring fan de ynterne steat, generaasje en útfier fan it útfiersymboal - foarkomme instantaneel op it momint t i .

Devices dy't diskrete sets fan ynterne steat, ynfier- en útfieringsignalen hawwe, en in set fan punten yn 'e tiid wêryn't inputsignalen komme, ynterne steatwizigingen en útfieringsignalen wurde útjûn, wurde diskreet neamd .

Foarbylden fan diskrêftige apparaten binne in dial-uptelefon, in kombinaasjebalke, in kalkulator, elektroanysk scoreboards en, fansels, in komputer. Op ôfspraak kinne apparaten kombinearje yn trije groepen:

Informatie - referinsautomaat, elektroanysk skorpions, ferkearsljochten, alarmgerjochten, etc .;

Managers - kodearre slûs, loftkontrôle-apparaat, programma-kontrolearre masines, kamera-mikroproesjers, fideo, ensfh .;

Computing - in mikrôlekalker, mikroproesters fan kompjûters.

Der binne apparaten dy't de aktiviteiten útfiere fan alle trije soarten, bygelyks in komputer, in autopilot, ensfh.

Foar ús redenen is it essensjele dat de útfiersymboalen en de ynterne steaten fan sa'n apparatuer útdwaan binne fan diskrete funksjes fan de ynputsymboalen en operaasje-fiksnûmers. Wy stelle it begryp fan ' e transysjefunksje Y , dy't de ynterne steat fan' e apparaat oan 'e neikommende fyts te ferieniget mei de steat en it ynfiersymbool op' e aktuele sesje:

Mei oare wurden, de transysjefunksje lit de steat fan it diskreet appartemint fan alle mooglike Q sjen , as it yn 'e state q i wie , en it ynfiersymboal x waard ûntfongen.

Op deselde wize ynfiere wy de funksje fan 'e útfieringen Q, dy't de ynterne steat fan it apparaat en it ynfiersymboal by de hjoeddeiske klok te ferbinen mei it útfieringssignaal by deselde klok:

Dêrom bepale de funksje fan 'e útfieringen hokker symboal by de útfier foarme wurdt, as it ynfiersymboal en de steat fan' e apparaat op dizze kloksyklus bepaald wurde.

It wurdt bepaald dat de fiif fan 'e komponinten <X, Y, Q, Ψ, Θ> in automaton setten dy't de transformaasje soargje neffens guon regels fan de folchoarder fan tekens fan it ynfier alfabet yn' e útfieringsekst. Ja, as wy de earste betingst q 1 akseptearje = q 0 , dan bepale de werhelling fan relaasjes (9.1) en (9.2) de opdracht fan konversaasje fan 'e definitive seker fan ynputsymbols x 0 , x 1 ..., x n yn guon folchoarder fan outputsymbols fan deselde lingte y 0 , y 1 , ... y n ; Yn dit gefal sil in bepaalde folchoarder fan ynterne steat q 1 , q 2 , ... ûntsteane. Dit is it funksjonearjen fan 'e masine. It útfiersymboal dat troch de automaton ûntstien is by in bepaalde cycle , hinget net allinich op it ynfier symboal dat op itselde takt beoardiele is, mar ek op 'e letters dy't earder ûntfongen binne - binne fêstlein yn' e automaton troch de ynterne steat te feroarjen. Yn dit sin is de ynset fan ynterne steat fan 'e automaton syn ynterne ûnthâld. Ofhinklik fan de grutte fan dit ûnthâld binne de neikommende typen fan automaten oanwêzich:

Sûnder ûnthâld;

Mei ultime ûnthâld;

· Mei unike ûnthâld.

It rinnen fan in lyts foarút, bepale wy dat de automaton mei definitive ûnthâld de finite automaton hjit. Notysje ek dat de funksjes fan oergongs en útgongs de algemiene namme automatonfunksjes hawwe.

Wat foar diskrete apparatuer mei ûnbegryplike ûnthâld is dit in gewoan model teoretyske fertsjintwurdiging, om't gjin echte apparaat in folslein ûnthâld hat. In foarbyld fan in automaton mei ûnbegryplike ûnthâld is de Turing-masine, wêrby't, as yn sesje 7.3.3 oanjûn, de rol fan ûnthâld wurdt spile troch in ûneinige (of, as nedich, útstelbere) papierklep yn beide rjochtingen. Sa kinne wy ​​útskriuwe dat de automaton mei ûnfinich ûnthâld in algoritme is presintearre yn 'e foarm fan in Turing-masine. Sûnt saken dy't relatearre binne oan de wurking fan Turingmasines binne al earder beskôge, sille se net yn dit haadstik besprutsen wurde.

Yn echte diskrete apparatuer kinne sinjalen en har transaasjes in oare fysike natuer hawwe (elektrysk, meganyske, pneumatyske, ensfh.). Dochs kinne jo fan dizze aard ôfbrekke en allinich de algemiene wetten fan 'e bou fan automaten en de regels beskiede dy't de transformaasje fan ynformaasje bepale troch harren. Sokke automaten wurde abstrakt neamd . Yn 'e teory fan abstrakte automaten wurde ferskate groepen fan problemen behannele:

earst, it docht bliken út hokfoar transformaasjes mooglik binne yn 'e automaton, hoe't se se beskriuwe, hoe't de transformaasje útfierd binne ferbûn mei it oantal steaten (d.i. kompleksiteit) fan' e automaton, oft der problemen binne ûnbetrouber troch de automaton;

Tsjintwurdich wurde lykwichtige transformaasjes fan automaten ûndersocht; it probleem fan lykweardige transformaasje bestiet út it bouwen fan in automaton lykweardich oan in opjaan, mar it hat in oar oantal steaten (meastentiids in lytsere);

Tredde, wurdt in spesjale fraachstikken beskôge as de struktuer fan in automaton bepaald is troch de natuer en ferhâlding fan ynfier- en útfieringsignalen (automaton - "black box") - dit is in wichtige tapastlike opjefte fan technyske diagnostika fan apparaten, sûnder dat har praktyske operaasje ûnmooglik is;

fjirde wurde de struktureel eleminten fan 'e automaten markearre en de regels foar it bouwen fan komplekse apparaten út harren binne definiearre (de opdracht fan automata-synteze) - de ûntwikkeling fan nije automaten, benammen komputer, is dêrby ferbûn.

In wichtich gefal foar praktyk is de automaten dêr't alle ynformaasje fertsjintwurdige wurdt mei in binêre koade, d. De alfabetten X, Y, en Q binne binêre - soksoarte automaten wurde binary of logysk neamd. De lêste namme is troch it feit dat as in teory sjen lit mei binêre kodearring kin elke finiteatermasine fertsjintwurdige wurde as in kombinaasje fan in bepaalde tal fan eleminten dy't oandreaun wurde, en, of logyske operaasjes, lykas gedachteeleminten (ferlies en trigger). Kombineare eleminten wurde in logyske circuit. Twa omstannichheden binne wichtich: earst kin de operaasje fan logyske sirkels beskreaun wurde troch de wetten en regels fan wiskundige logika (dat is it resultaat fan 'e operaasje fan' e logyske circuit omfettet ta de berekkening fan 'e wearde fan' e logyske útdrukking; Tsjintwurdich kin elke finitenmateriaal fan dizze lytsere set fan eleminten oanlein wurde.





Sjoch ek:

Foarbyld 5.4

Besykje fragen en taken

Foarbyld 2.2

Utjefte fan it kodierprobleem, Shannon's earste teorem

Foarbyld 9.4

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ edudocs.fun