Тьюринг машинасының формальді емес анықтамасы

Тьюринг машинасы автомат сияқты, екі жақты шексіз лентасы, басы (головкасы) және басқару құрылғысы бар. Басқару құрылғысы бір қалыпты болуы мүмкін, соңғы көпмүше жасайды Q = {q0, q1, ..., qn}. Көпмүше Q Тьюринг машинасының ішкі алфавиті деп аталады.

Тьюринг машинасының есептегіш машинадан принципті айырмашылығы мынада, оның еске сақтау құрылғысы шексіз лентадан тұрады, сондықтан ол шындыққа жанаспайтын қиялдағы машина болып қала береді. Лента ұяшықтарға бөлінген, әрқайсысына алфавиттің бір символы жазылған соңғы алфавит A={a0,a1,...,am}болады, ол Тьюринг машинасының енгізу алфавиті аталады. Тьюринг машинасы функциясын қолдану кезінде ұяшықтардың соңғы саны толтырылмаған болуы мүмкін. Есептегіш (считывающая) басы әр уақытта лентаның ұяшығына шолу, осы ұяшықтағы символға тәуелді және басқару құрылғысының қалпы ұяшыққа жаңа символ жазады немесе оны өзгертусіз қалдырады, ұяшық оңға немесе солға жылжиды немесе орнында қалады. Осыдан барып басқару құрылғысы жаңа күйге ауысады немесе бұрынғысында қалады. Бастапқы құрылғысының қалпы ортасында бастапқы қалып q₀ және соңғы қалып q_z болып бөлінеді.

Тьюринг машинасының бір тактісі бойынша символды санауға болады, оның орнына жаңасын жазып немесе оны өзгеріссіз қалдырамыз және басын бір ұяшық солға немесе оңға жылжытамыз немесе орнында қалдырамыз.

А алфавиті – кейбір соңғы көпмүше символдары.

Алфавит тізбегі деп осы алфавиттің символдарының тізбегін айтамыз. x тізбектің ұзындығы, ол сол тізбектегі символдар санын көрсетеді және | x | болып белгіленеді. Бос тізбек ұзындығы 0-ге тең.

Тізбек конкатенациясы деп х және у тізбегін айтады, қосылып жазылған символдардан алынған х тізбегінің оң жағындағы у тізбегі.

Тьюринг машинасына 7 түр енеді:

мұндағы

соңғы жиынның қалпы, басқару құрылғысы бар;

енгізу алфавиті;

көшу функциясы; мұндағы

жылжу бағыты;

бастапқы қалып; ;

соңғы қалып; ;

– бос ұяшықты көрсету символы ;

– арнайы символ - тізбекті лентаға бөлу ;

Тьюринг машинасының командасы деп функция элементінің көшуін айтамыз мұндағы және ; және . Әр команда Тьюринг машинасында жұмыстың бір тактісін көрсетеді.

Тьюринг машинасы конфигурациясы келесі әдістермен көрсетіледі: б мұндағы

С – есептегіш бастың сол жағында орналасқан тізбек.

В – Тьюринг машинасының басының оң жағында орналасқан тізбек.

Егер жаңа конфигурация енгізу конфигурациясының бір командасы қолдану нәтижесінде болса, онда конфигурациясы конфигурацияға қатысты көшеді. Бір конфигурациядан келесі конфигурацияға тікелей көшуді былайша көрсетеміз: .

Бастапқы қалып жағдайындағы конфигурацияны - бастапқы, соңғы қалып жағдайындағы конфигурацияны - соңғы деп аталады. Егер С тізбегіндегі конфигурация бос болса, онда бастапқы және соңғы конфигурация стандартты деп аталады.

Тьюринг машинасы х тізбегін у тізбегіне өңдейді, егер, лентада х тізбегі болып, бастапқы конфигурациямен әрекет етсе, Тьюринг машинасы лентада у тізбегі болып, соңғы конфигурацияға көшеді. Егер бастапқы және соңғы конфигурация стандартты болса, онда х-ті у-ке өңдеу процессі дұрыс өңдеу болып табылады.

Бекіту сұрақтары:

1. 
   Алгоритмнің құрылымына қарай нешеге бөлінеді? Атап бер.
   
2. 
   Сызықтық алгоритм деген не?
   
3. 
   Тармақтық алгоритм деген не?
   
4. 
   Циклдық алгоритм деген не?
   
5. 
   Циклдық құрылым неше түрге бөлінеді?
   
6. 
   Шарт алдынан берілген алгоритмге мысал келтір.
   
7. 
   Шарт соңынан берілген алгоритмге мысал келтір.
   
8. 
   Параметрлі циклге мысал келтір.
   
9. 
   Алгоритм деген не?
   
10. 
    Алгоритм термині қайдан шыққан?
    
11. 
    Алгоритмнің қасиеттерін ата?
    
12. 
    Компьютерде есеп шығару қадамдарын көрсет?
    
13. 
    Сөздік алгоритмге мысал келтір.
    
14. 
    Графиктік алгоритм деген не? Мысал келтір.
    
15. 
    Графиктік алгоритмнің шарт белгілерін көрсет.
    
16. 
    Тьюринг машинасы дегеніміз не?
    
17. 
    Тьюринг машинасының формальді емес анықтамасы;
    
18. 
    Тьюринг машинасының формальді анықтамасы.
    

• 
  Бағдарламалау тілдеріне шолу: бағдарламалау тілдерінің тарихы.
  
• 
  Бағдарламалаудың негізгі құрылғылары: жоғары деңгейлі бағдарламалу тілінің семантикасы мен синтаксисінің негіздері; айнымалылар, өрнектер және меншіктеу; қарапайым енгізу-шығару; тармақталу және интерактивті операторлар
  

• 
  Бағдарламалаудың парадигмдері.
  
• 
  Процедуралық бағдарламалау.
  
• 
  Модульдік және құрылымыдық бағдарламалау концепциялары. Объектіге –бағытталған бағдарламалау
  

Pentium типті процессорлардың орындайтын қарапайым әрекеттерінің саны мыңнан асады. Процессордың әрбір әрекеті үшін арнайы команда бар, олар 0-ден 255-ке дейінгі сандармен немесе сандар тобымен жазылады.

Pentium модельді процессорлардың әртүрлі буындарға жататын процессорлардың команда жүйесі бойынша сәйкестенбеуінен пайдаланушыларға қолайсыздық тумауы үшін «жоғарыдан төменге» сәйкестену принципі енгізілген. Мысалы, қазіргі заманғы Pentium ІІІ процессорлы компьютерлерде Pentium І процессорлы компьютерлерде жасалған программалар орындалуы керек. Ал керісінше ертеректегі буын компьютерлерінде қазіргі компьютерлерде жасалған программа әрдайым орындала бермейді.

Программаны машиналық кодта жазу. Процессордың барлық командалары 0-ден 255-ке дейінгі мәні бар сандармен немесе осындай сандар тобымен (байттармен) көрсетіледі. Тура осы сияқты оперативті жадыдағы сандық берілгендер мен ұяшық адрестері көрсетіледі. Егер біз процессордың программамен жұмыс істеуіне қарайтын болсақ, онда тек сандардың ұзын қатарын ғана көреміз. Олардың кейбірі - командалар, кейбірі - жады ұяшығының адресі, кейбірі – берілгендер: сандар, әріптер, дыбыстар, бейне т.с.с. Мысалы:

33, 0, 1, 34, 210, 15, 238 ...

Программаны жазудың мұндай формасы машиналық код деп аталады. Бұл жалғыз ғана процессорға түсінікті программаның жазылу түрі. Өкінішке орай ол адамдардың көпшілігіне түсініксіз.

Программаның бастапқы коды. Программаны программалау тілінде жазуды бастапқы код немесе программа мәтіні деп атайды.

Жоғарғы деңгейдегі программалау тілдеріне: Fortran, Cobol, Algol, Pascal, Basic, C(Си), C++, Java тілдері жатады.

Delphi ортасы мәлеметтер қорымен жұмыс істейтің программаларды құруда BDE (Borland DataBase Engine), механизмі қолданылады. Бұл механизм деректерде өңдеу үшін Паскаль тілінде жазылған программаны мәлеметтер қорының архетектурасынан тәуелсіз орындай алады. Мәлеметтер қоры файл-серверлік, клиент-серверлік архетектураның қайсысында құрылсада өңдеуге бірдей дәрежеде қатыса алады. Бұл механизм клиент программа мәлеметтер қоры арасында байланыс орнатады.

Жоғары деңгейлі программалау процедуралық, логикалық және обьектілі- бағдарлы болып 3 түрге бөлінеді. «Логика» термині logos (логос) деген грек сөзінен шыққан, ол «ойлау», «түсіну», «сана» деген ұғымды береді. Ойдың мазмұны және құрылымы: ой мазмұнына қарай құбылыстардың бекелі санасындағы дәлме –дәл бейнелеуін ақиқат дейді. Ал қарама-қарсы түрін жалған дейді. Логика ғылымы ретінде негізін қалаушы ежелгі грек философы Аристотель (384-322 ж.б.з.д). Ол ең алғаш дедукция теоремасын өңдеген. Математикалық дәлелделермен математикалық сұрақтарды зертейтін ғылым. Математикалық логика пәні- предикаттарды есептеу. Негізінде бірнеше көп тілді программалау логикалық предикаттар жатыр және алгоритм теоремасы: мысалы тілдің атауы Prolog қысқаша «логикалық программмалау » деп атайды.

ОБП тілінде прграммалалардың жұмысы оқиғалар тізбегінен және түрлі обьектілердің осы оқиғаларға жауабынан тұрады. Олар, әсіресе Delphi программалау тілі кез-келген қосымшаны дайындауға болатын жылдамдығы тез, қуатты тіл. Delphi -дің негізгі ерекшелігі- онда қосымша құруды компонентік және обьектілік тәсілдер пайдаланылады. Компонентік тәсілдің мәнісі жеңіл: қосымша арнайы іс-әрекеттерді орындайтын компонентерден жинақталады.

Ол жеткіліксіз болса, обьектіні өңдеуге арналған үстеме программа құралады. Компонентер визуалды кітапханасында (VCL- Visual Component library) жинақталған.

Компонентер панелінде түрлі класстарға тиісті стандартты компонентер өте көп пайдаланушы жаңа компонент дайындап, оны осы панелге қосуына да болады.

Delphi -де программа дайындау, программа мәзірін құру, анимация, мультимидия, процесстерін ұйымдастыру, OLE техналогияны пайдаланады, басқа офистік қосымшаларды шақыру, олармен жұмыс істеу және т.б іс-әрекететрді орындауға болады. Көптеген оператордың жазылуы Турбо Паскальдағы сияқты. Бірақ, мұнда программалауды үйрену үшін обьект, оқиға, әдіс, класс, қасиеті ұғымдарымен еркін танысып, компонентерді пайдаланып және түрлі командалардың жазылу түрлерін білу қажет.

Бекіту сұрақтары:

1. 
   Программаны машиналық код түрінде жазуды қалай түсінесің және ол қандай негізгі құрылғымен байланысты?
   
2. 
   Процессордың командалар жүйесі деген не?
   
3. 
   Pentium модельді процессорлардың командалар жүйесінің сәйкестенуі деген не?
   
4. 
   «Жоғарыдан төменге» сәйкестену принципі туралы айтып бер.
   
5. 
   Компьютерлік программа деген не?
   
6. 
   Транслятор – программа деген не?
   
7. 
   Трансляторлардың түрлері туралы айтып бер.
   
8. 
   Компилятор-программалар деген не?
   
9. 
   Интерпретатор-бағдарламалар деген не?
   
10. 
    Программалау тілдерінің деңгейлері ұғымын түсіндіріп бер.
    
11. 
    Төменгі деңгейдегі программалау тіліне қандай тіл жатады?
    
12. 
    Жоғарғы деңгейдегі программалау тілдеріне қандай тілдер жатады?
    
13. 
    Алгоритмдік (модульдік) программалау ұғымын түсіндіріп бер.
    
14. 
    Құрылымдық программалау ұғымын түсіндіріп бер.
    
15. 
    Ішкі программа деген не?
    

• 
  Қазіргі қолданбалы программамен қамтамасыз етуге шолу.
  
• 
  Операциялық жүйелердің негізгі концепциялары.
  
• 
  Операциялық жүйелердің даму тарихы.
  
• 
  Типтік операциялық жүйелердің жұмыс істеуі.
  
• 
  Операциялық жүйелердің декомпозициялау әдістері: монолитті, көп деңгейлі, модульді микроядролық модельдер.
  
• 
  Процесстерді басқару.
  
• 
  Жоспарлау және диспетчеризациялау.
  
• 
  Файлдық жүйелер.
  
• 
  Утилиттер.
  
• 
  Драйверлер.
  
• 
  Желілер мен телекоммуникациялар.
  
• 
  Желілік қауіпсіздік.
  
• 
  Web –клиент –сервер архитектурасының мысалы
  

Қазіргі компьютерлерде қолданбалы программаларды бірден орнатпайды, себебі әрбір пайдаланушы өзіне қажет қолданбалы программаларды өзі орнатады.

Ең төменгі деңгейдегі программаны орнатудың қажеті жоқ – олар компьютердің тұрақты есте сақтау құрылғысына (ПЗУ) бірден жазылып, компьютермен бірге келеді. Олар жүйелік және қызметтік программаларды орнату үшін жеткілікті. Ал жүйелік және қызметтік программалар көп болғандықтан оларды бір пакетке жинап, операциялық жүйе деп атаған. Сонымен, операциялық жүйе – жүйелік және қызметтік құралдар комплексі. Операциялық жүйе бір жағынан BIOS жүйесіне енетін компьютердің базалық қамсыздануына сүйенеді, екінші жағынан өзінен жоғары деңгейдегі қолданбалы программаларға тірек болады. Операциялық жүйе қосымшалары осы жүйенің басқаруымен жұмыс істеуге арналған программалар. ОЖ-нің негізгі функциялары:

1. 
   Пайдаланушы мен компьютердің программалық-аппараттық құралдарының арасында интерфейс орнату;
   
2. 
   Аппараттық қамсыздандыру мен программалық қамсыздандыру арасындағы интерфейс орнату;
   
3. 
   Программалық қамсыздандырудың әр түрінің арасында интерфейс орнату.
   

Барлық операциялық жүйелер пайдаланушылармен жұмыс істеудің пакеттік және диалогтық режимдерін қамсыздандырады.

Пакеттік режимде – операциялық жүйенің берілген командалар тізбегін автоматты түрде орындайды.

Диалогтық режимде – операциялық жүйе пайдаланушының командасын күтеді де, арнайы команда алған соң орындап, жауап қайтарады да, келесі команданы күтеді. Операциялық жүйе процессор үзілісі мен BIOS үзілісіне негізделген. ОЖ-нің жұмысты үзіп, әрекеттерге жауап бере алуын диалогтық режим деп атайды.

Пайдаланушы интерфейсі 2 түрге бөлінеді: графикалық және графикалық емес ОЖ.

Графикалық емес ОЖ-де командалық жол интерфейсі қолданылады. Мұнда негізгі басқару құрылғысы – пернетақта. Басқару командалары командалық жолдарға енгізіледі, мұнда командаларды редакторлеуге де болады. Команданың орындалуы Enter пернесін басқаннан кейін жүзеге асады. IBM PC компьютерінің командалық жол интерфейсін MS-DOS операциялық жүйесі атқарады.

Графикалық ОЖ-де интерфейстің күрделірек түрі жұмыс істейді. Мұнда басқару органы ретінде пернетақтадан басқа – тышқан манипуляторы бар. Графикалық ОЖ-нің жұмысы экранның басқару элементтерінің активті және пассивті түрлерінің өзара әрекеттесуіне негізделген.

Активті басқару элементі ретінде тышқанның меңзері болады.

Пассивті басқару элементі ретінде – қосымшаларды басқару элементтері (батырмалар, шарт белгілер, ауыстырғыштар, жалаушалар, ашылатын тізімдер, меню жолдары және т.б.) болады.

Барлық операциялық жүйелер автоматты түрде жүктеледі.

Дискіге жазылған мәліметтермен жұмыс істеуге қолайлы болу үшін оларды файлдарға орналастырады. Файл – дискіде ат қойылып, берілгендер сақталған облыс. Әдетте бір файлда бір типке жататын мәліметтер сақталады. Берілгендер типі – файл типін анықтайды. Файлдың толық аты – файл аты мен кеңейтілуінен тұрады. Аты мен кеңейтілуінің арасына нүкте қойылады. Файл атының кеңейтілуі оның қандай типке жататынын білдіреді. MS-DOS операциялық жүйесінде файл атына 8 символ, ал кеңейтілуіне 3 символ беріледі:символдар / \ : * « < > -нан басқа/, сандар және латын әріптері бола алады. Ал WINDOWS операциялық жүйесінде файл аты 256 символдан тұра алады. Файлмен барлық жүйеде жұмыс істей алу үшін қысқа атты пайдаланған дұрыс.

Файлды сипаттайтын параметрлер:

• 
  Файлдың толық аты;
  
• 
  Файлдың көлемі (байтпен);
  
• 
  Жасалу күні;
  
• 
  Жасалу уақыты;
  
• 
  Файлға қатынастың дәрежесін анықтайтын файл атрибуттар: R(Read only) – только для чтения, H(Hidden) – скрытый, S(System) – системный, A(Archive) – архивированный;