Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Дискретный анализ (3 семестр)

министерство образования российской федерации

Московский физико-технический институт

(государственный университет)

 

                                                                              УТВЕРЖДАЮ

                                                                Проректор по учебной работе

                                                               ______________Ю.А. Самарский

                                                               «____»_________________  2002

 

 

П Р О Г Р А М М А

 

по курсу                      ДИСКРЕТНЫЙ АНАЛИЗ                   

по направлению               511600                                    

факультет                               ФПМЭ                                    

кафедра           математических основ управления                 

курс                             II        

семестр                       3         

лекции             34 часа                                    экзамен               нет 

семинары        34 часа                        зачет с оценкой   3 сем.

лабораторные занятия           нет                          самостоятельная работа    2 часа в неделю

ВСЕГО ЧАСОВ    68              

 

Программу составили: академик РАН, проф. Ю.И. Журавлев

                                    д.ф.- м.н., проф.А.Ю. Флёров

                                    д.ф.- м.н., проф. В.К. Леонтьев

                                    к.ф.- м.н., доц.   Т.М. Дадашев

 

Программа обсуждена на заседании кафедры математических основ управления 16 мая 2002 г.

 

 

Заведующий кафедрой                     С.А. Гуз

I. Исчисление высказываний

1.       Метод формальных теорий. Основные понятия исчисления высказываний. Выражения, формулы и аксиомы. Схемы аксиом и правило вывода.

2.       Вывод в исчислении высказываний. Теорема дедукции. Теорема о полноте.

3.       Непротиворечивость исчисления высказываний и независимость его схем аксиом.

II. Исчисление предикатов

 1.       Основные понятия теорий первого порядка: кванторы, термы, формулы, свободные и связанные вхождения переменных в формулы.

2.       Интерпретации. Выполнимость и истинность. Модели. Логически общезначимые формулы.

3.       Схемы аксиом и правила вывода исчисления предикатов. Непротиворечивость исчисления предикатов.

4.       Теорема дедукции. Теорема Геделя о полноте (без доказательства).

III. Теория алгоритмов

1.       Необходимость уточнения понятия алгоритма. Примеры алгоритмов. Машины Тьюринга (МТ) и их основные свойства. Примеры МТ.

2.       Нумерация МТ. Операции над МТ.

3.       Понятие нормального алгоритма Маркова. Примеры. Марковские вычисления.

4.       Эквивалентность определений алгоритма по Тьюрингу и Маркову.

5.       Понятие вычислимости. Примитивно-рекурсивные функции. Тезис Чёрча.

6.       Алгоритмически неразрешимые проблемы: распознавание применимости, самоприменимости и переводимости.

7.       Проблема тождества слов в полугруппах. Разрешимые случаи. Примеры. Неразрешимость проблемы тождества слов в полугруппах.

Список литературы

1.       Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.

2.       Трахтенберг Б.А. Алгоритмы и вычислительные автоматы. М.: Сов. Радио, 1974.

3.       Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

4.       Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математический логике и теории алгоритмов. М.: Физматгиз, 1995.

5.       Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992.

6.       Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.

7.       Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965.

 

ЗАДАНИЕ

по курсу “Дискретный анализ”

для студентов ФПМЭ, II курс, III семестр ФПМЭ

 

1.       Доказать выводимость следующих формул языка  L1 :

а)  ( \bar{A} -> A) -> A ;

б)  (B -> C) -> ((A \/ D) -> (A \/ C)) ;

в)  (A & B) -> (B & A).

2.       Выяснить общезначимость и выводимость формул языка L2 , не пользуясь теоремой о полноте

3.       Доказать, что не существует нормального алгоритма Маркова в алфавите А , удваивающего любое слово в этом алфавите.

4.       Построить нормальный алгоритм Маркова над алфавитом А для удвоения любого слова в алфавите А .

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

6.       Построить нормальный алгоритм Маркова и машину Тьюринга, которые слова вида anbn (n >= 1) и только их преобразуют в слова a2nb2n .

7.       Доказать, что из функций

O(x) = O

n m (x1x2...xn)=xm ,    1<=m<=n

с помощью суперпозиций и схем примитивной рекурсии нельзя получить функции x + 1 и 2x.

8. Доказать примитивную рекурсивность функций

1) f(x1,x2)=x1x2 - x2 2

2) f(x1,x2,x3)=x1 2 + x3  (сумма по mod 2)

9. Пусть g1(y), g 2(x), g 3(x, y) примитивно рекурсивные функции. Доказать, что тогда примитивно рекурсивна и f(x, y), определяемая схемой

f(0, y) = g 1(y),

f(x+1, 0) = g 2(x),

f(x + 1, y + 1) = g 3(x, y)  при  x >= 0, y>=  0.

10.        Пусть \pi (x) – число простых чисел, не превосходящих х. Доказать, что  \pi (x)  - примитивно рекурсивная функция.

11. Показать, что если функция f(x) частично рекурсивна, то и всякая функция, отличающаяся от f(x) на конечном множестве значений аргумента, является частично рекурсивной.

12. Привести пример частично-рекурсивной функции, не являющейся примитивно-рекурсивной.

 

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика