1 формальные теории 1 Основные положения



страница8/17
Дата15.01.2013
Размер1.67 Mb.
ТипДокументы
1   ...   4   5   6   7   8   9   10   11   ...   17

2.5 Задачи и упражнения


  1. Если значения примитивно-рекурсивной, общерекурсивной или частично рекурсивной функции изменить лишь на конечном множестве точек, то будет ли новая функция снова соответственно примитивно-рекурсивной или частично рекурсивной?

  2. Покажите, что примитивно-рекурсивна каждая

а) конечная совокупность чисел;

б) совокупность чисел вида a * n + b, n = 0, 1, 2, ...;

в) совокупность чисел вида a * bn, n = 0, 1, 2, ... .

  1. Составьте программу машины Тьюринга, складывающей любые два натуральных числа n1 и n2 , представленные на ленте двумя сериями из n1 + 1 и n2 + 1 единиц, разделенных ячейкой, в которой записан символ 0. (Результатом вычисления считается число единиц в выражении, написанном на ленте после окончания вычисления.) В начальном состоянии головка считывает первый символ 1.

  2. Составьте программу машины Тьюринга, проверяющей истинность равенства x = 0.

  3. Составьте программу машины Тьюринга, сдвигающей головку влево на следующий массив чисел.

  4. Составьте программу машины Тьюринга, уменьшающей данное число на единицу.

  5. Используя понятие композиции машин Тьюринга и программы машин, решающих задачи 5 и 6, постройте программу машины, сдвигающей головку влево на следующий массив единиц, изображающий некоторое число, и уменьшающей это число на единицу.

  6. Постройте нормальные алгорифмы Маркова для вычисления простейших числовых функций: функции - константы, функции тождества.



  • 3 ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА


Целый ряд математических моделей процессов управления представляет собой дискретные модели комбинаторного типа. Так, например, комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции и т.д. Исследование таких моделей и методов их решения относится к области комбинаторного анализа.

Что же изучают в комбинаторном анализе и какие типы задач решают? Рассмотрим для начала несколько задач.

  1. Поступающий в ТУСУР должен сдать три экзамена при пятибальной системе оценок. Для поступления достаточно набрать 13 баллов. Сколькими способами он может сдать экзамены (разумеется, не получив ни одной двойки)?

  2. Как отыскать кратчайший путь для почтальона, обязанного обслуживать заданное число населенных пунктов? Расстояние между каждой парой пунктов известно.


  3. Сколько ферзей или других шахматных фигур достаточно, чтобы они держали под боем все клетки шахматной доски? Сколькими способами они могут быть расставлены?

  4. На сколько частей делят пространство плоскостей, из которых никакие четыре не проходят через одну и ту же точку, никакие три не проходят через одну и ту же прямую и никакие две не параллельны, а любые три плоскости имеют общую точку?

Общим во всех этих задачах является то, что в них рассматриваются дискретные (составленные из отдельных, обособленных элементов) множества. Эти множества в большинстве случаев конечны, но могут быть и бесконечными, составленными из неограниченно большого числа элементов.

Задачи комбинаторного анализа можно разбить на три класса:

а) задачи о количестве решений, то есть о числе дискретных построений, удовлетворяющих поставленным условиям, или перечислительные задачи;

б) задачи, решающие вопрос о существовании или несуществовании конфигурации, удовлетворяющей условиям, то есть о наличии или отсутствии решения;

в) задачи отыскания алгоритма получения конфигурации, а также выделения из заданной совокупности конфигураций таких, которые обладали бы избранным свойством в наибольшей или наименьшей степени, или задачи оптимизации.

Элементы комбинаторных суждений появились еще в глубокой древности, на заре формирования математической науки. В ходе истории они развивались совместно с другими разделами математики, Нетрудно увидеть, что в ряде областей современной математики: теории чисел, алгебре, геометрии, математической логике и др. многие основные понятия и методы имеют дискретную природу и обладают устойчивыми связями. Это позволяет рассматривать задачи комбинаторного анализа в различных интерпретациях, исследовать проблемы различной природы с единой точки зрения, В наше время в связи с развитием вычислительной техники возможности дискретных методов исследования и их значение резко возросли. Наряду с исторически сложившейся комбинаторной теорией (комбинаторным анализом) в современной математике существуют: теория графов, геометрия чисел, дискретный и конечный анализы, исследование операций.
1   ...   4   5   6   7   8   9   10   11   ...   17

Похожие:

1 формальные теории 1 Основные положения iconОсновные положения теории электролитической диссоциации
Закрепить умение записывать процесс диссоциации при помощи химических знаков и формул, сформулировать основные положения теории электролитической...
1 формальные теории 1 Основные положения iconПрограмма курса «Числовые системы»
Формальные и неформальные аксиоматические теории. Схема построения неформальной аксиоматической теории. Интерпретация и модель аксиоматической...
1 формальные теории 1 Основные положения iconПарапсихология и психофизика. 1999. №1. С. 155-158. Принципы теории вакуумных экранов
Настоящая работа является логическим продолжением работы [1]. Введены основные положения теории каналов, проведены некоторые расчеты...
1 формальные теории 1 Основные положения iconЗачет по «теории и истории языкознания»
Повое время: сенсуализм. Основные положения о языке в теории сенсуалистов (Ф. Бэкон. Т. Гоббс, Дж. Локк, Э. Б. де Кондильяк)
1 формальные теории 1 Основные положения icon«Основные положения молекулярно-кинетической теории»
«Сформировать представления о структуре и содержании новой физической теории, организовать усвоение основных положений мкт»
1 формальные теории 1 Основные положения iconФормальные языки и грамматики
Основные положения иллюстрируются примерами различных формальных языков, в том числе языка программирования "Паскаль". Каждому студенту...
1 формальные теории 1 Основные положения iconО некоторых особенностях семантизаций тематически связанных слов в психолингвистическом эксперименте
В таком союзе теории и практики семантика сформировала основные положения своей теории, а лексикографию ознаменовал выпуск замечательных...
1 формальные теории 1 Основные положения icon-
Указаны основные положения теории Э. Дюркгейма об обществе. Даны основные типы солидарности. Описан процесс разделения труда, с точки...
1 формальные теории 1 Основные положения iconОсновные положения синтетической теории эволюции
Термин «синтетическая» идет от названия книги известного английского эволюциониста Дж. Хаксли «Эволюция: современный синтез» (1942)....
1 формальные теории 1 Основные положения icon«мкт. Основы термодинамики»
Основные положения молекулярно-кинетической теории газов и её опытные обоснования
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org