1. Структура цом, представлення цом як конечного автомата
| Вид материала | Документы |
- Вторая, 374.07kb.
- «Автоматы: модель конечного автомата, распознаватели и преобразователи. Анализаторы, 150.22kb.
- Гражданское право (часть II) в вопросах и ответах батычко Вик. Т., 2008, 1556.04kb.
- Комарова Т. С, 299.71kb.
- Алконос) в русских средневековых легендах райская птица с человеческим лицом (часто, 251.62kb.
- Учебно-тематический план проведения пятидневных учебных сборов с обучающимися образовательных, 107.75kb.
- Урок обж в 10 классе по теме «Назначение и боевые свойства автомата Калашникова», 49.98kb.
- Структура програми Практична робота: «Робота у середовищі програмування», 56.69kb.
- Устройство автомата ак-74, обращение с ним, уход и сбережение Общие сведения Назначение, 10.05kb.
- 3 Последовательность синтеза автоматов с памятью лгоритм работы автомата с памятью, 144.1kb.
1. Структура ЦОМ, представлення ЦОМ як конечного автомата
ЦОМ – цифрові обчислювальні машини або обчислювальні машини дискретної
дії – працюють з інформацією, представленою в дискретній, а точніше в
цифровій формі.
Кінцевий(конечний) автомат - в теорії алгоритмів математична абстракція, що дозволяє описувати шляхи зміни стану об'єкта в залежності від його поточного стану і вхідних даних, за умови, що загальна можлива кількість станів скінченна. Кінцевий автомат є окремим випадком абстрактного автомата.
2. Модель фон Неймана.
Модель фон Неймана (von Neumann) служила базовою моделлю при проектуванні всіх сучасних комп'ютерних систем
Модель складається з чотирьох ключових компонентів:
- Система пам'яті, яка зберігає як команди, так і дані. Відома як система з програмою, яка зберігається. Доступ до цієї пам'яті здійснюється за допомогою регістра адреса (memory address register, MAR), куди підсистема пам'яті поміщає адрес елементу пам'яті, і регістра даних (memory data register, MDR), куди вона поміщає дані з осередку з вказаною адресою. Детальніше підсистема пам'яті обговорюється в розділі 4.
- Принаймні один блок обробки даних, найбільш відомий як арифметико-логічний пристрій (ALU). Ці блоки частіше називають центральними процесорами (CPU) .1 Цей блок відповідає за виконання всіх команд. Процесор також має невеликий об'єм пам'яті, званий набором регістрів. Обговорення процесорів буде докладніше.
- Блок управління, яке відповідає за операції між компонентами моделі. Включає лічильник команд, який містить наступну команду для завантаження, і регістр команд, в якому знаходиться поточна команда. Особливості моделі управління виходять за рамки цієї книги.
Системі необхідний незалежний спосіб зберігання дані, а також видачі їх користувачеві і ухвалення вхідних даних. Це прерогатива підсистеми введення-виводу (I/O). головним чином стосується дискових накопичувачів як механізмів для введення-виводу.
3. представлення інформації в цифрових автоматах
Інформація на зовнішньому світі представляється в безперервному або дискретному вигляді. Усередині ЕОМ інформація завжди представляється у вигляді чисел, записаних в тій або іншій системі числення. Якщо ж йдеться про текстовій інформації, то зазвичай вона кодується також за допомогою чисел. Питання про вибір системи числення для цифрового автомата — одне з найважливіших питань проектування як алгоритмів функціонування окремих пристроїв, так і розрахунок технічних характеристик цього автомата Система числення — сукупність прийомів і правил для запису чисел цифровими знаками. Найбільш відома десяткова система числення, в якій для запису чисел використовуються цифри О, 1, ..., 9. Будь-яка призначена для практичного використання система числення повинна забезпечувати: можливість представлення будь-якого числа в даному діапазоні величин; єдність предствлення (кожній комбінації символів повинна відповідати одна і лише одна величина); простоту операції числами. Всі системи представлення чисел ділять на позиційних і непозиційних.
Непозиційна система числення — система, для якої значення символу не залежить від його положення в числі. Принципи побудови таких систем не складні. Для їх освіти використовують в основному операції складання і віднімання.
Позиційна система числення — система, що задовольняє рівності (3.2). Природна позиційна система числення має місце, якщо q — ціле, позитивне число. У позиційній системі числення значення цифри визначається її положенням в числі: один і той же знак приймає різне значення. Наприклад, в десятковому числі 222 перша цифра справа означає дві одиниці, сусідня з нею — два десятки, а ліва — дві сотні.
Поняття про алфавіт
5 поняття про системи числення
Сукупність прийомів та правил найменування й позначення чисел називається системою числення. Звичайною для нас і загальноприйнятою є позиційна десяткова система числення. Як умовні знаки для запису чисел вживаються цифри. Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюється, називається непозиційною. Система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа, називається позиційною. Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел.
Добре відомим прикладом непозиційної системи числення є римська система, в якій роль цифр відіграють букви алфавіту: І - один, V - п'ять, Х - десять, С - сто, Z - п'ятдесят, D -п'ятсот, М - тисяча. Наприклад, 324 = СССХХІV. У непозиційній системі числення незручно й складно виконувати арифметичні операції.
7. Форми представлення чисел с фіксованою та плаваючими точками
Представлення чисел з фіксованою комою (точкою). Природна форма подання числа в цифровому автоматі характеризується тим, що положення його розрядів у автоматному зображенні залишається завжди постійним незалежно від величини самого числа. Існує також інша назва цієї форми запису чисел - представлення чисел з фіксованою комою (точкою).
Щоб спростити функціонування цифрового автомата, необхідно обмежити вхідну інформацію якоюсь однією областю чисел (на вхід автомата бажано подавати або цілі числа, або правильні дроби, або будь-які числа), що дозволить визначити значення масштабного коефіцієнта КА - Наприклад, якщо на вхід цифрового автомата надходять тільки правильні дроби, то
-1<[A]Ф<1, (1)
де [A] ф - машинне зображення числа для форми подання з фіксованою комою.
Тоді число А буде представлено у вигляді А— [А]фКа- Величина масштабного коефіцієнта КА, що задовольняє умові (1), визначає той факт, що в машинному зображенні кома завжди стоїть після цілої частини дробу, тобто перед її старшим розрядом. Отже, можна зберігати тільки дробову частина числа (цифрову частина), а в розряді цілої частини писати додаткову інформацію.
Представлення чисел в формі фіксованої точки.Подання чисел у формі з плаваючою комою. У нормальній формі
Ан =mApA
де тА - мантиса числа А; pA - порядок числа А (характеристика числа).
Як видно з раніше викладеного, таке подання чисел не однозначно; для визначеності звичайно вводять деякі обмеження. Найбільш поширене і зручно для представлення в ЕОМ обмеження виду
q-1≤│mA│<1 (2)
де q — основні системи числення.
Нормалізована форма представлення чисел - форма представлення чисел, для якої справедливо умова (2).
Оскільки в цьому випадку абсолютне значення мантиси лежить в межах від q - 1 до 1 – q - n де п - кількість розрядів для зображення мантиси без знака, положення розрядів числа в його автоматному зображенні не постійно. Тому таку форму подання чисел називають також формою подання з плаваючою комою. Формат машинного зображення числа з плаваючою комою повинен містити знакові частини та поля для мантиси і «порядку» (мал. 2, а). Виділяються спеціальні розряди для зображення знака числа (мантиси) і знака порядку або характеристики (мал. 2, а, б). Кодування знаків залишається таким же, як було з фіксованою комою.
Поскольку в этом случае абсолютное значение мантиссы лежит в пределах от q - 1 до 1 – q - n где п — количество разрядов для изображения мантиссы без знака, положение разрядов числа в его автоматном изображении не постоянно. Поэтому такую форму представления чисел называют также формой представления с плавающей запятой. Формат машинного изображения числа с плавающей запятой должен содержать знаковые части и поля для мантиссы и порядка (рис. 3.3, а). Выделяются специальные разряды для изображения знака числа (мантиссы) и знака порядка или характеристики (рис. 3.3, а, б). Кодирование знаков остается таким же, как было с фиксированной запятой.
Рис 2. Представлення чисел в формі з плаваючою точкою.
8. Точність представлення чисел в ЦОМ. Погрішності виконання арифметичних операщй.
Представлення числової інформації в цифровому автоматі, як правило, спричиняє за собою появу погрішностей (помилок), величина яких залежить ось форми представлення чисел і ось довжини розрядної сітки автомата.
Абсолютна погрішність уявлення — різниця між дійсним значенням вхідної величини Л і її значенням, отриманим з машинного зображення Ам, тобто А [Л] = А — Ам.
Відносна погрішність уявлення — величина
8[А]=А[А]/АК. (3.30)
Вхідні величини незалежно ось кількості значущих цифр можуть містити грубі помилки, що виникають із-за друкарських помилок, помилкових відліків показаний яких-небудь приладів, некоректною, постановки завдання або відсутності повнішої і точнішої інформації. Наприклад, часто приймають я =3,14. Проте ця величина може бути отримана з вищою точністю (800 знаків і більш). Якщо прийняти, що точне значення л= 3,14159265, то абсолютна погрішність рівна А [я] =0,00159265.
Часто деяка величина в одній системі числення має кінцеве значення, а в іншій системі числення стає нескінченною величиною, наприклад, дріб '/ю має кінцеве десяткове уявлення, але, будучи переведена в двійкову систему числення, стає нескінченним дробом 0,0001100110011...
Отже, при перекладі чисел з однієї системи числення в іншу неминуче виникають погрішності, оцінити які нескрутно, якщо відомі дійсні значення вхідних чисел.
Відповідно до (3.19) числа зображаються в машині у вигляді Ач—[а~\ Кл, де масштабний коефіцієнт Кл вибирають так, щоб абсолютне значення машинного зображення числа А в системі числення з підставою ц = 2 було завжди менше 1: Ач = Кл [а.q~x + а_2q2 + - + a-nq-n + ...].
Оскільки довжина розрядної сітки автомата рівна п двійкових розрядів після коми, і абсолютна погрішність перекладу десяткової інформації в систему з підставою q буде
А [Л] = а(n+1) q-(n+1)+. + а-(n+s) q-(n+s)+ ...=_ alql. (З.31)
Максимальна погрішність перекладу десяткової інформації в двійкову не перевищуватиме одиниці молодшого розряду розрядної сітки автомата. Мінімальна погрішність перекладу рівна нулю.
Усереднена абсолютна погрішність перекладу чисел в двійкову систему числення А [Л] = (0 + 2~")/2 = 0,5 • 2гп.
Для представлення чисел у формі з фіксованою комою абсолютне значення машинного зображення числа
2-n<|[A]ф|<1-2-n. (3.33)
Следовательно, относительные погрешности представления для минимального значения числа
Для ЭВМ, как правило, п =16÷64, поэтому 1>>2-n, откуда 
Аналогічно, для максимального значення:
З (3.34) видно, що погрішності представлення малих чисел у формі з фіксованою комою можуть бути дуже значними.
Для представлення чисел у формі з плаваючою комою абсолютне значення мантиси
Погрішність (3.32) — погрішність мантиси. Для знаходження погрішності представлення числа у формі з плаваючою комою величину цієї погрішності треба помножить на величину порядку числа рл:
9 .Основні положення алгебри логіки
Основне поняття алгебри логіки — вислів. Вислів — деяка пропозиція, про яку можна стверджувати, що воно достеменне або лвжно. Наприклад, вислів «Земля — це планета Сонячної системи» істинно, а про вислів «на вулиці йде дбждь» можна сказати, істинно воно або помилково, якщо вказані додаткові відомості про погоду в даний момент. Будь-який вислів можна позначити символом х і вважати, що х=1, якщо вислів достеменний, а х = О— якщо вислів помилковий. Логічна функція (функція алгебри логіки) — функція 1(х\, Х2 ???, хп), що набуває значення, рівного нулю або одиниці на наборі логічних змінних х\, хч ..., хп. Логічні функції від однієї змінної представлені в таблиці. 10.1.
Відповідно до введених визначень функція }\(х) є абсолютно достеменною (константа одиниці), а функція И*) — абсолютно помилковою функцією (константа нуля). Функція /з(х), що повторює значення логічної змінної, — тотожна функція (}3(х)= х), а функція /ч(*)> що набуває значень, зворотних значенням х, — логичеськбе_ заперечення, або функція НЕ ((х) =~1д: = х).
