Компьютерные науки

Алгоритмы и теория вычислений

В программе изучаются фундаментальные математические понятия вычислений и доказательств. Предусматривается знакомство с теорией алгоритмических моделей и аксиоматическим подходом к математической логике.
Студентов 2375 Выпускников 443 Для профессионалов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Программирование
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа посвящена глубоким теоретическим аспектам вычислений. В учебной программе детально изучаются алгоритмические модели, такие как машина Тьюринга, рекурсивные функции, формальные грамматики и сети Петри. Особое внимание уделено исчислению высказываний и предикатов. Внутри программы разобраны темы от базового понятия алгоритма до сложных формальных систем и метатеории. Теоретическое изложение чередуется с тестовыми заданиями для проверки понимания математической логики.
Цели
  • Дать фундаментальные знания по теории вычислений и алгоритмическим моделям.
  • Раскрыть суть аксиоматического подхода к математической логике.
  • Сформировать представление о разрешимых и перечисляемых множествах.
Чему я научусь?
  • Оперировать понятиями машины Тьюринга и рекурсивных функций.
  • Анализировать формальные системы и грамматики.
  • Использовать исчисление высказываний и предикатов для доказательств.

Авторы

Кузнецов Олег Петрович
Кузнецов Олег Петрович
Профессор, доктор технических наук.\n\n
Чему я научусь?
  • Оперировать понятиями машины Тьюринга и рекурсивных функций.
  • Анализировать формальные системы и грамматики.
  • Использовать исчисление высказываний и предикатов для доказательств.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Понятие алгоритма. Классификация алгоритмических моделей. Знакомство с машиной Тьюринга "В начале лекции рассказывается об истории возникновения математики, формировании понятий ""Доказательство"" и ""Вычисление"". Определяется понятие ""Алгоритм"",... "В начале лекции рассказывается об истории возникновения математики, формировании понятий ""Доказательство"" и ""Вычисление"". Определяется понятие ""Алгоритм"", приводятся основные требования, предъявляемые к алгоритму. Во второй половине лекции рассказывается о классификации алгоритмических моделей, начинается знакомство с машинами Тьюринга." ещё
2 Машина Тьюринга. Вычислимость. Примеры. Способы задания В начале лекции обсуждается понятие вычислимости. Далее приводится описание, способы задания, указываются особенности программирования машин Тьюринга... В начале лекции обсуждается понятие вычислимости. Далее приводится описание, способы задания, указываются особенности программирования машин Тьюринга (МТ). Рассматриваются основные операции над МТ, доказывается теорема о существовании универсальной МТ. ещё
3 Рекурсивные функции Лекция посвящена введению в теорию рекурсивных функций. Дается определение, рассматриваются примеры, способы задания рекурсивных функций, формулируются... Лекция посвящена введению в теорию рекурсивных функций. Дается определение, рассматриваются примеры, способы задания рекурсивных функций, формулируются и доказываются соответствующие теоремы. ещё
4 Разрешимые и перечисляемые множества. Введение в теорию конечных автоматов Лекция состоит из двух частей. В первой части обсуждаются вопросы разрешимости и перечислимости множеств, сходимости алгоритмов,... Лекция состоит из двух частей. В первой части обсуждаются вопросы разрешимости и перечислимости множеств, сходимости алгоритмов, приводится формулировка теоремы Райса. Вторая часть лекции посвящена введению в теорию конечных автоматов (КА). Дается формальное определение КА, рассматриваются способы задания, примеры. ещё
Разрешимые и перечисляемые множества. Введение в теорию конечных автоматов тест для курса Алгоритмы и теория вычислений 60 мин
5 Свойства и варианты конечных автоматов В лекции рассматриваются свойства и варианты конечных автоматов (КА). Дается определение, и приводятся примеры эквивалентных автоматов.
6 Алгоритмические возможности конечных автоматов. Сети Петри В лекции рассматривается понятие регулярного множества. Приводится формулировка теоремы Клини. Рассматривается блочное описание конечного автомата. Обсуждаются... В лекции рассматривается понятие регулярного множества. Приводится формулировка теоремы Клини. Рассматривается блочное описание конечного автомата. Обсуждаются понятия композиции и декомпозиции. В заключение рассматриваются сети Петри. ещё
Алгоритмические возможности конечных автоматов. Сети Петри тест для курса Алгоритмы и теория вычислений 60 мин
7 Формальные системы. Свойства, интерпретация, моделирование Лекция посвящена формальным системам (ФС). Дается строгое определение ФС, приводятся примеры, рассматриваются свойства ФС.
8 Формальные грамматики В лекции рассматриваются и строго определяются такие понятия как формальный язык, грамматика языка, язык грамматики. Приводится... В лекции рассматриваются и строго определяются такие понятия как формальный язык, грамматика языка, язык грамматики. Приводится классификация формальных грамматик по Хомскому. Рассматриваются примеры. ещё
Формальные грамматики тест для курса Алгоритмы и теория вычислений 60 мин
9 Логика. Исчисления высказываний и исчисление предикатов "В начале лекции рассказывается об истории возникновения понятия "" Логика"". Далее обсуждаются основные различия между исчислением... "В начале лекции рассказывается об истории возникновения понятия "" Логика"". Далее обсуждаются основные различия между исчислением высказываний и исчислением предикатов. Рассматриваются правила вывода Modus Ponens, приводятся примеры их использования." ещё
10 Метатеория. Введение в исчисление предикатов В первой половине лекции обсуждается понятие метатеории и метатеорем. Приводится теорема о дедукции, ее доказательство, обратная... В первой половине лекции обсуждается понятие метатеории и метатеорем. Приводится теорема о дедукции, ее доказательство, обратная теорема о дедукции. В завершение рассматривается пример. Вторая половина лекции посвящена введению в исчисление предикатов (ИП): рассматриваются основные определения и понятия, дается формальное определение ИП. ещё
11 Интерпретация и полнота исчисления предикатов В начале лекции кратко повторяются основные понятия и термины исчисления предикатов (ИП): алфавит, множество формул, множество... В начале лекции кратко повторяются основные понятия и термины исчисления предикатов (ИП): алфавит, множество формул, множество аксиом, множество правил вывода. Далее рассматриваются понятия интерпретации и полноты ИП. Приводится теорема Гёделя о полноте, теоремы о разрешимости ИП. ещё
12 Метод резолюций в исчислении высказываний и исчислении предикатов Лекция целиком посвящена методу резолюций в исчислении высказываний и исчислении предикатов. Подробно излагается идея и суть... Лекция целиком посвящена методу резолюций в исчислении высказываний и исчислении предикатов. Подробно излагается идея и суть метода, даются основные определения и понятия, на житейском примере разбирается алгоритм работы. В заключении рассматривается метод аналитических таблиц как альтернатива методу резолюций. ещё
Метод резолюций в исчислении высказываний и исчислении предикатов тест для курса Алгоритмы и теория вычислений 60 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

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

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^