Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Bloody_Mary
0 / 0 / 0
Регистрация: 02.06.2011
Сообщений: 2
1

Машина Тьюринга

05.06.2011, 19:43. Просмотров 437. Ответов 0
Метки нет (Все метки)

Люди спасите....ни у кого нет курсовой работы по вот такой вот задачке:

1.Задание
Тема 24. Машина Тьюринга для проверки достижимости в графе
А) Построить программу м. Т., которая по матрице смежности А ориентированного графа G = (V = {1,2,…,n},E) и двум вершинам i и j проверяет достижимость вершины j из вершины i. Квадратная матрица A=(aij),a_ij∈{0,1},1≤i,j≤n, представляется перечислением строк, разделенных символом *, I и j представляются в унарном кодировании и отделяются от матрицы и друг друга символом #.
Вход имеет вид: a11a12…a1n*a21a22…a2n*an1an2…ann#|i#|j.
Выход: 1, если в G вершина j достижима из вершины i, и 0 – в противном случае.
Б) Обосновать правильность построенной программы.
В) Привести протокол вычисления программы для матрицы смежности:
A=(■(0&1&0@0&1&1@1&1&0))
и вершин
i=1 и j=1;
i=1 и j=3.
Г) Оценить (по порядку) время работы программы как функцию от числа вершин n.



буду очень благодарна.....зарание спасибо
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2011, 19:43
Ответы с готовыми решениями:

Машина поста и машина тьюринга: необходимо написать алгоритм к данному изображению
нужно решение в виде команд МТ и МП

Сложение четырех целых без знака (Машина Поста), Троичное вычитание "-1" (Машина Тьюринга).
Здравствуйте! Можете пожалуйста помочь с задачками: Машина Поста: Сложение...

Машина Поста и Машина Тьюринга
Помогите решить задачу. На Машине Поста нужно написать программу Необходимо...

Машина Тьюринга
Здачка такая есть,дан Алфавит,состоящий из букв А,В,на ленточном механизме мб...

Машина Тьюринга
Помогите разобраться...хоть подсказку дайте... Постройте машину Тьюринга,...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2011, 19:43

Машина Тьюринга
Люди.. кто знает машины Тьюринга подскажите пожалуйста реализацию следующей...

Машина Тьюринга
1. A={a,b}. Удалить из слова Р его второй символ, если такой есть. 2....

машина Тьюринга
На ленте машины Тьюринга находится целое положительное число, записанное в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru