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

Введение в алгоритмы

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

Авторы

Иванников Виктор Петрович
Иванников Виктор Петрович
Доктор физико-математических наук, профессор, академик РАН, директор Института системного программирования РАН.
Чему я научусь?
  • Анализировать вычислимость задач с помощью формальных моделей.
  • Проектировать логику работы для различных машин Тьюринга.
  • Использовать нормальные алгоритмы Маркова для описания вычислений.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Понятие алгоритма и машина Тьюринга В лекции вводится понятие алгоритма, дается исторический экскурс, определяются множества и функции. Рассказывается о тезисе Тьюринга... В лекции вводится понятие алгоритма, дается исторический экскурс, определяются множества и функции. Рассказывается о тезисе Тьюринга и даются описание и пример машины Тьюринга. ещё
Понятие алгоритма и машина Тьюринга тест для курса Введение в алгоритмы 50 мин
2 Разновидности машины Тьюринга Рассматриваются задача на построение анализатора на основе машины Тьюринга и алгоритм решения задачи Марвина Мински. Приводятся... Рассматриваются задача на построение анализатора на основе машины Тьюринга и алгоритм решения задачи Марвина Мински. Приводятся разновидности машин Тьюринга, рассказывается о неразрешимых проблемах и проблеме мертвого кода. ещё
Разновидности машины Тьюринга тест для курса Введение в алгоритмы 60 мин
3 Нормальные марковские алгоритмы Вводятся нормальные марковские алгоритмы, даются их примеры, определяются их замыкание и композиция.
Нормальные марковские алгоритмы тест для курса Введение в алгоритмы 60 мин
4 Понятие языка Дается описание формальной системы Паскаль, рассказывается об алгоритме Евклида. Вводится понятие языка и типов данных.
Понятие языка тест для курса Введение в алгоритмы 60 мин
5 Язык программирования Паскаль Дается краткое введение в язык программирования Паскаль, приводятся основные понятия: операторы, операции, типы данных. Даются примеры.
Язык программирования Паскаль тест для курса Введение в алгоритмы 60 мин
6 Имена и функции в языке программирования Паскаль Вводятся понятия имен и функции, рассказывается о способах передачи параметров в функции, побочных эффектах функции, коллизиях... Вводятся понятия имен и функции, рассказывается о способах передачи параметров в функции, побочных эффектах функции, коллизиях имен, дается понятие отношения. ещё
Имена и функции в языке программирования Паскаль тест для курса Введение в алгоритмы 60 мин
7 Графы Дается определение графов, деревьев, стеков, очередей, кучи. Рассказывается о недостатках этих структур.
Графы тест для курса Введение в алгоритмы 60 мин
8 Работа со стеками, очередями и деревьями Даются примеры работы со стеком, очередью и списком, указываются особенности работы с ними. Рассказывается о двоичных... Даются примеры работы со стеком, очередью и списком, указываются особенности работы с ними. Рассказывается о двоичных деревьях. ещё
Работа со стеками, очередями и деревьями тест для курса Введение в алгоритмы 60 мин
9 Двоичные деревья Приводятся варианты обхода дерева c использованием циклов, рекурсий, стеков. Вводятся понятия первичного и вторичного ключа, даются... Приводятся варианты обхода дерева c использованием циклов, рекурсий, стеков. Вводятся понятия первичного и вторичного ключа, даются оценки алгоритмов. ещё
Двоичные деревья тест для курса Введение в алгоритмы 60 мин
10 Деревья сравнения списковой памяти Рассказывается о деревьях сравнения списковой памяти, операции удаления и вставки.
Деревья сравнения списковой памяти тест для курса Введение в алгоритмы 60 мин
11 АВЛ-деревья Рассказывается об АВЛ-деревьях, условиях их существования и построения, приводятся процедуры корректировки характеристик и частные случаи трансформации... Рассказывается об АВЛ-деревьях, условиях их существования и построения, приводятся процедуры корректировки характеристик и частные случаи трансформации деревьев. ещё
АВЛ-деревья тест для курса Введение в алгоритмы 60 мин
12 Цифровой поиск Приводится оценка вычислительной сложности АВЛ-деревьев, рассказывается о цифровом поиске, дается пример реализации программы.
Цифровой поиск тест для курса Введение в алгоритмы 60 мин
13 Методы обработки таблиц с вычисляемыми адресами Рассказывается о методах обработки таблиц с вычисляемыми адресами, реализуются необходимые процедуры.
Методы обработки таблиц с вычисляемыми адресами тест для курса Введение в алгоритмы 60 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

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

Сертификат

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

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

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

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

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