Алгоритми та структури даних. Лабораторна робота з Інформаційні технології. Робота № 527144

Перехід до торгівельного партнера Binance

Алгоритми та структури даних

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2012

Тип роботи:

Лабораторна робота

Предмет:

Інформаційні технології

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ МОЛОДІ ТА СПОРТУ УКРАЇНИ Технічний Коледж Національного університету «Львівська політехніка» Відділення Інформаційних Технологій та Комп’ютерної Техніки Лабораторна робота №5 З дисциплiни «Алгоритми та структури даних» Львів 2012 План 1.Тема 2.Мета 3.Основні теоретичні відомості 4.Розробка структурних даних 5.Розробка алгоритму 6.Текст робочої програми 7.Тестування 8.Висновок 1.Тема Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ). 2.Мета Ознайомлення зі способом подання алгоритму на прикладі машини Тьюрінга. Завдання: Виконати операцію додавання двох двійкових чисел: Z=(X+Y) Результат розташувати на місці вхідних даних, де X – день народження (дата) Y – номер варіанту Побудувати модель одно стрічкової детермінованої Машини Тьюринга, яка б виконувала ряд команд {A}x{Q}->{A}{L,R,S}{Q}, де L – зсув головки вліво R – зсув головки вправо S – Головка залишається на місці. Й мала б вигляд: M=<A,Q,q0,qr,a0,p>, де A – кінцева множина символів зовнішнього алфавіту, Q – кінцева множина символів внутрішнього алфавіту, q1 – початковий стан, q0 – кінцевий стан, q0, q1 Є Q, a0 – позначення нульової комірки стрічки. Зобразити роботу машини Тьюрінга до початку виконання програми та після всіх пройдених команд. Початковим станом МТ вважати крайнє праве положення головки на стрічці. 3.Основні теоретичні відомості Основним призначенням математичних ФАС є дослідження проблем розв’язності. Для цієї проблеми вимога елементарності кроку є необхідною. Оскільки ця вимога не може бути математично точно сформульована, вона інтерпретується як умова загальної зрозумілості. Математичні моделі ФАС ( вийнятки становлять рекурсивні функції) використовують елементарні операції типу розпізнавання символу, трасування, заміна або зміщення. Всі ці операції нагадують дитячу гру з кубиками, тому можуть вважатись загальнозрозумілими або елементарними. Прикладом ФАС є машина Тьюрінга. Маши́на Тю́ринга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюринга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюринга ввів американський математик Еміль Пост. Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку або пересунути голівку на одну комірку ліворуч або праворуч. 4.Розробка структурних даних Змінна Опис Тип Dn День народження Int Nv Номер варіанту int Sum Сума Int Dnd Д.Н. в двійковому форматі Int [3] Nvd Н.В. в двійковому форматі Int [5] Sumd Сума в двійковому форматі Int [5] Таблиця внутрішніх станів Q\A 0 1 + _ Q₁ Q₂1L Q11L Q₂ Q₂0L Q₂1L Q3_L Q₃ Q3_L Q3_L Q0__S 5.Розробка алгоритму Блок схема Граф схема Словесний алгоритм Підключення бібліотек Оголошення змінних Введення даних Додавання десяткових змінних Переведення змінних в двійковий масив Переведення суми в двійковий масив Виведення результату Завершення програми 6.Текст робочої програми #include "stdafx.h" #include <iostream> #include <stdio.h> #include <conio.h> #include <iomanip> #include <math.h> #include <string.h> using namespace std; int main () { int dn,nv,sum; static int dnd[3],nvd[5],sumd[5]; int i; cout<<"Vvedit datu narodzhennia, nomer variantu"<<endl; cin>>dn>>nv; sum=dn+nv; for (int i=0;i<3;i++) { dnd[3-i-1]=dn%2; dn=dn/2; } for (int i=0;i<5;i++) { nvd[5-i-1]=nv%2; nv=nv/2; } for (int i=0;i<5;i++) { sumd[5-i-1]=sum%2; sum=sum/2; } cout<<"\ndatu narodzhennia:\n"; for (i=0;i<3;i++)cout<<dnd[i]; cout<<"\nomer variantu:\n"; for (i=0;i<5;i++)cout<<nvd[i]; cout<<"\nsuma=\n"; for (i=0;i<5;i++)cout<<sumd[i]; getch(); return 0; } 7.Тестування Вхідні дані День народження=2 Номер варіанту=25 / Реалізація машини Тьюринга на основі результатів виконання програми 111+10111 q1 111+10111 q2 111+10111 q2 111+10011 q2 111+11011 q2 111_11011 q2 11__11011 q3 1___11011 q3 ____11011 q3 11011=27 8.Висновок На даній лабораторній роботі ми ознайомились зі способом подання алгоритму на прикладі машини Тьюрінга.

Лабораторна робота Інформаційні технології

777ZED777

27.05.2015 00:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись