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

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

5
занятий

13:50:14
длительность

0
тестов


577

1. Понятие алгоритма. Длительность: 72 минут
1.1 Понятие алгоритма. Классификация алгоритмических моделей Видео
2. Машина Тьюринга. Длительность: 147 минут
2.1 Машина Тьюринга. Вычислимость. Примеры. Способы задания Видео
2.2 Рекурсивные функции Видео
3. Разрешимые и перечисляемые множества. Длительность: 207 минут
3.1 Введение в теорию конечных автоматов Видео
3.2 Свойства и варианты конечных автоматов Видео
3.3 Алгоритмические возможности конечных автоматов. Сети Петри Видео
4. Формальные системы. Длительность: 140 минут
4.1 Свойства, интерпретация, моделирование Видео
4.2 Формальные грамматики Видео
5. Логика Длительность: 265 минут
5.1 Исчисления высказываний и исчисление предикатов Видео
5.2 Метатеория. Введение в исчисление предикатов Видео
5.3 Интерпретация и полнота исчисления предикатов Видео
5.4 Метод резолюций в исчислении высказываний и исчислении предикатов Видео

Отзывы пользователей, который прошли этот курс

Будь первым, кто пройдет курс и оставит свой отзыв!

Пока в этом курсе не задано ни одного вопроса

Задать вопрос

Описание курса

Курс предлагает подборку видеоматериалов лекций, семинаров и конференций по интернет-технологиям и включает в себя следующие вопросы:

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

Что будет изучено

см. выше

Требования к обучаемому

Курс рассчитан на студентов ВУЗов, в учебном плане которых предусмотрена такая учебная дисциплина как "Менеджмент" и для пользователей широкого круга, изучающих секреты менеджмента для самообразования.