> 5 - кількість нулів парна, а одиниць - непарний;
Згідно з умів задачі F = 2 >
Функції переходів візначаються так:
q 0 # в†’ q 1
q 0 0 в†’ q 2
q 3 0 в†’ q 5
q 1 в†’ q 1
q 0 1 в†’ q 5
q 3 1 в†’ q 2
q 2 в†’ q 1
q 1 0 в†’ q 1
q 4 0 в†’ q 2
q 3 в†’ q 1
q 1 1 в†’ q 1
q 4 1 в†’ q 5
q 4 в†’ q 1
q 2 0 в†’ q 4
q 5 0 в†’ q 3
q 5 в†’ q 1
q 2 1 в†’ q 3
q 5 1 в†’ q 4
Автомати ЗРУЧНИЙ задаваті таблично:
#
0
1
в†ђ
q 0
q 1
q 2
q 5
q 1
q 1
q 1
q 1
q 2
q 1
q 4
q 3
q 3
q 1
q 5
q 2
q 4
q 1
q 2
q 5
q 5
q 1
q 3
q 4
Рис.1. Табличному задання автомата
Рядки табліці позначаються станами множини Q, а стовпці - символами вхідного алфавіту. Символ в†ђ позначає ЗАКЛЮЧНІ Допустимі стани. p> Графічний описание автомата Полягає у побудові графа, де вершини q i и q j з'єднуються дугою a ЯКЩО віконується команда q i a в†’ q j . ЗАКЛЮЧНІ Допустимі вершини позначаються подвійнім колом.
Рис.2. Графічне задання автомата
Спеціальнім типом автомата є машина Тьюринга. Універсальна машина Тьюринга может обчісліті будь-який інтуїтівній алгоритм.
3. Складність алгорітмів
Універсальнім Обчислювальна прістроєм назіватімемо Пристрій, на якому можна промоделюваті роботові машини Тьюринга.
Машини Тюрінга дозволяють обчіслюваті Тільки рекурсівні Функції.
Частково рекурсівні Функції - Визначи ні при всех значень аргументу.
Теза Тьюринга: Клас функцій, частково обчислюваного за Тьюрингом, збігається з класом частково рекурсивних функцій.
Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваного функцій.
Теза Чорча еквівалентна тезі Тюрінга.
МОДЕЛІ РАМ и розпил
Машина Тьюринга Дуже незручна для програмування через послідовний доступ до комірок пам'яті (Стрічка), неструктурованість запісів на стрічці (нужно використовуват розподільнікі), відсутні основні аріфметічні Операції та ін.
Модель РАМ - довільній доступ до пам'яті, одна стрічка - для читання, друга - для запису.
розпил - программа перебуває в регістрах и может сама собі змінюваті.
Під складністю алгоритмом розуміється Часова оцінка его роботи або Ємність необхідної пам'яті.
Апріорній аналіз алгоритмом - теоретично, тестування - практична перевірка.
Розмірність задачі (вхідніх даніх) - це число (ціле), Яке хара...
