English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

Детерминированные и ограниченно-детерминированные функции

 

 

1.1. Является ли детерминированной функция φ: {0,1}* → {0,1}*

1) Слово x(1)x(2)… отображается в слово 00…0, если существует t, при котором x(t)=0, в противном случае =11….1

2) s-я буква y(s) в слове φ(x(1)x(2)…) равна 0, если при некотором t ≤ s выполняется неравенство x(t)<x(t+1)+x(t+2), в противном случае y(s)=1

 

1.2. Частичная функция φ: {0,1}* → {0,1}* не определена только на словах вида 00…0. Можно ли доопределить ее до детерминированной?

1) φ (xω) = xω, если в каждом префиксе слова xω число нулей не меньше числа единиц, иначе φ (xω) =1ω

2) φ (xω) = y(1)y(2)… где y(t)=0, если для некоторого s ≤ t x(s)=1, иначе y(t)=1

 

1.3. Является ли φ1 остаточным оператором функции φ?

1) φ: y(1)=0, y(t)=x(t)+y(t-1)+1, φ1: y(1)=1, y(t)=y(t-1)+1

2) φ: y(1)=1, y(t)=y(t-1)+1, φ1: y(1)=0, y(t)=y(t-1)+1

 

1.4. Является ли φ ОД-функцией? Если да, найти ее вес:

1) y(1)=y(2)=1, y(t)=x(t-2) при t ≥ 3

2) y(2t)=x(t+1), y(2t-1)=x(t)+1

3) y(1)=1, y(2t-1)=x(2t-1)+y(2t-3), y(2t)=x(2t-1)

 

1.5. Частичная функция φ: {0,1}* → {0,1}* определена только на словах вида 0ω и 1ω. Доопределить ее до ОД-функции с минимально возможным весом:

1) φ(0ω) = 0101[100]ω, φ(1ω) = 11[10]ω

2) φ(0ω) = 01[011]ω, φ(1ω) = 1010010001000010…

 

 

Список задач по автоматам

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru