MaterStudiorum.ru - домашняя страничка студента.
Минимум рекламы - максимум информации.


Авиация и космонавтика
Административное право
Арбитражный процесс
Архитектура
Астрология
Астрономия
Банковское дело
Безопасность жизнедеятельности
Биографии
Биология
Биология и химия
Биржевое дело
Ботаника и сельское хоз-во
Бухгалтерский учет и аудит
Валютные отношения
Ветеринария
Военная кафедра
География
Геодезия
Геология
Геополитика
Государство и право
Гражданское право и процесс
Делопроизводство
Деньги и кредит
Естествознание
Журналистика
Зоология
Издательское дело и полиграфия
Инвестиции
Иностранный язык
Информатика
Информатика, программирование
Исторические личности
История
История техники
Кибернетика
Коммуникации и связь
Компьютерные науки
Косметология
Краткое содержание произведений
Криминалистика
Криминология
Криптология
Кулинария
Культура и искусство
Культурология
Литература и русский язык
Литература(зарубежная)
Логика
Логистика
Маркетинг
Математика
Медицина, здоровье
Медицинские науки
Международное публичное право
Международное частное право
Международные отношения
Менеджмент
Металлургия
Москвоведение
Музыка
Муниципальное право
Налоги, налогообложение
Наука и техника
Начертательная геометрия
Новейшая история, политология
Оккультизм и уфология
Остальные рефераты
Педагогика
Полиграфия
Политология
Право
Право, юриспруденция
Предпринимательство
Промышленность, производство
Психология
Психология, педагогика
Радиоэлектроника
Разное
Реклама
Религия и мифология
Риторика
Сексология
Социология
Статистика
Страхование
Строительные науки
Строительство
Схемотехника
Таможенная система
Теория государства и права
Теория организации
Теплотехника
Технология
Товароведение
Транспорт
Трудовое право
Туризм
Уголовное право и процесс
Управление
Управленческие науки
Физика
Физкультура и спорт
Философия
Финансовые науки
Финансы
Фотография
Химия
Хозяйственное право
Цифровые устройства
Экологическое право
Экология
Экономика
Экономико-математическое моделирование
Экономическая география
Экономическая теория
Эргономика
Этика
Юриспруденция
Языковедение
Языкознание, филология
    Начало -> Математика -> Конспекты лекций по математической логике

Название:Конспекты лекций по математической логике
Просмотров:115
Раздел:Математика
Ссылка:Скачать(282 KB)
Описание:Теория алгоритмов. Булевы функции. Логические исчисления. Предикаты и кванторы.

Часть полного текста документа:

Конспекты лекций по математической логике
    
    1. Теория алгоритмов
    1.1 Различные подходы к определению алгоритма:
    10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).
    20. Машина с неограниченными регистрами (МНР).
    30 Машина Тьюринга - Поста (МТ-П).
    40 Нормальные алгоритмы Маркова (НАМ).
    
    1.1.1 Машина с неограниченными регистрами (МНР).
    Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.
    Допустимые команды:
    Z(n) - обнуление регистра Rn.
    S(n) - увеличение числа в регистре Rn на 1.
    T(m,n) - копирует содержимое Rm в регистор Rn.
    I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет
    следующая.
    Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.
    
    Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.
    
    1.1.2 Машина Тьюринга - Поста.
    Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:
    Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).
    Допустимые команды:
    1) ,где .
    2) (остановка программы). Последовательность команд называется программой, если в этой последовательности не встречается команд с одинаковыми левыми частями. Машина останавливается если она не находит команды с левой частью подобной текущей.
    1.1.3 Нормальные алгоритмы Маркова.
    Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.
    Допустимые команды: (Для машин этого типа важна последовательность команд.)
    где Пример:
    Программа:
    
    1.1.4 Реализация функции натурального переменного.
    но мы допускаем не всюду определенную функцию.
    то это означает, что
    притом , если f не определена, то и программа не должна ничего выдавать.
    
    притом , если f не определена, то и программа не должна ничего выдавать.
    ( , а числа представляются в виде ,например .)
    1.2 Эквивалентность трех подходов к понятию алгоритм.
    1.2.1 Теорема об эквивалентности понятия вычислимой функции.
    вычислима: ()
    1) Если существует программа МНР, которая вычисляет эту функцию.
    2) Если существует программа МТ-П, которая вычисляет эту функцию.
    3) Если существует программа НАМ, которая вычисляет эту функцию.
    
    Использование НАМ:
    
    
    Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.
    Пусть которая вычисляется на МТ-П, вычислим её на НАМ.
    МТ-П:
    
    НАМ:
    Команда МТП: преобразуется по правилам:
    
    Команда МТП:
    
    2. ............




Нет комментариев.



Оставить комментарий:

Ваше Имя:
Email:
Антибот:  
Ваш комментарий:  



Похожие работы:

Название:Доказательства неравенств с помощью одномонотонных последовательностей
Просмотров:232
Описание: Муниципальное общеобразовательное учреждение Средняя общеобразовательная школа № 4 Секция: математика ИССЛЕДОВАТЕЛЬСКАЯ РАБОТА по темеДоказательства неравенств с помощью одномонотонных последо

Название:Содержание финансового и управленческого анализа и последовательность его проведения
Просмотров:78
Описание: КУРСОВАЯ РАБОТА по дисциплине "Комплексный экономический анализ хозяйственной деятельности" на тему: Содержание финансового и управленческого анализа и последовательность его про

Название:Предел последовательности. Теорема Штольца
Просмотров:240
Описание: Курсовая работа "Предел последовательности. Теорема Штольца" Содержание Введение Предел последовательности Свойства сходящихся последовательностей Приме

Название:Импульсные последовательности в магнитно-резонансных томографах
Просмотров:259
Описание: Импульсные последовательности в магнитно-резонансных томографах Импульсной последовательностью называется совокупность РЧ и градиентных импульсов, создава

Название:Исследование цепи переменного тока с последовательным соединением активного сопротивления, индуктивности и емкости
Просмотров:223
Описание: Министерство образования Российской Федерации Пермский Государственный Технический Университет Кафедра электротехники и электромеханики Лабораторная работа «Исследование цепи пер

 
     

Вечно с вами © MaterStudiorum.ru