НОУ ИНТУИТ | Повышение квалификации

Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней

Темы: Языки и системы программирования, Программирование, Алгоритмы и дискретные структуры, Дискретные структуры, Алгоритмы

В курсе дается введение в теорию алгоритмов. Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль, а также основные структуры данных и алгоритмы.

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

Вам нравится? Нравится 1 студенту

| Поделиться |

Поддержать

Занятие	Заголовок <<	Дата изучения
	Экзамен экстерном	-
Лекция 1	Понятие алгоритма и машина Тьюринга В лекции вводится понятие алгоритма, дается исторический экскурс, определяются множества и функции. Рассказывается о тезисе Тьюринга и даются описание и пример машины Тьюринга. Оглавление Введение Возникновение понятия алгоритма Пример простого алгоритма и его свойств Алгоритм Евклида Компоненты и свойства алгоритма Первые исследования алгоритма и способов его формального определения Множества и функции Определение функции Понятия алфавита и слова Тезис Тьюринга Машина Тьюринга Описание машины Тьюринга Пример работы машины Тьюринга	-
Тест 1 30 минут	10 заданий	-
Лекция 2	Разновидности машины Тьюринга Рассматриваются задача на построение анализатора на основе машины Тьюринга и алгоритм решения задачи Марвина Мински. Приводятся разновидности машин Тьюринга, рассказывается о неразрешимых проблемах и проблеме мертвого кода. Оглавление Введение Задача на построение анализатора на основе машины Тьюринга Алгоритм решения задачи Марвина Мински Введение в алгоритм Состояния машины Тьюринга Мертвый код Задание начальных значений Разновидности машин Тьюринга Лента бесконечная в одном направлении Алфавит ленты = (0,1) Универсальные машины Тьюринга Введение в универсальные машины Тьюринга Создание универсальной машины Тьюринга на машине Тьюринга Ввод дополнительного символа Композиции машин Тьюринга Мониторы Хора Неразрешимые проблемы Постановка неразрешимых проблем Проблема останова Парадокс Рассела Ввод в доказательство псевдоанализатора E* Возврат к проблеме мертвого кода Создание анализатора мертвого кода на машине Тьюринга Примеры случаев мертвого кода	-
Тест 2 36 минут	12 заданий	-
Лекция 3	Нормальные марковские алгоритмы Вводятся нормальные марковские алгоритмы, даются их примеры, определяются их замыкание и композиция. Оглавление Введение Нормальные марковские алгоритмы Определение Основной и вспомогательный алфавиты Три альтернативы процесса работы исполнителя Пример с алгоритмом сложения чисел Альтернативный алгоритм сложения чисел Замыкание алгоритма Композиция Получения строки бета Явное задание пустышки Неразрешимые проблемы	-
Тест 3 36 минут	12 заданий	-
Лекция 4	Понятие языка Дается описание формальной системы Паскаль, рассказывается об алгоритме Евклида. Вводится понятие языка и типов данных. Оглавление Введение Подведение итогов Формализация понятия Алгоритма Универсальная Машина Тюринга Неразрешимые проблемы Композиция частей Характеристики Формальная система Паскаль Описание системы Экскурс в историю Алгоритм Евклида НОД (док-во) Алгоритм Евклида на Паскале Понятие языка Синтаксис и семантика Правила и интерпретация Способы описания правил грамматик Типы данных Вещественные числа Вещественное число Мантисса Пример	-
Тест 4 36 минут	12 заданий	-
Лекция 5	Язык программирования Паскаль Дается краткое введение в язык программирования Паскаль, приводятся основные понятия: операторы, операции, типы данных. Даются примеры. Оглавление Введение Суммирование ряда из трех членов Пример Пример на вещественной оси Эволюция машин Язык программирования Паскаль Оператор присваивания Исключение Операции OR, AND и NOT Символы Перечислимый тип Диапазонный тип Правила описания типа Пример описания переменных Оператор GOTO Пустой оператор Составные операторы Оператор выбора Операторы цикла Составной оператор begin...end Пример описания факториала Задача о кроликах Оператор for Пример на вычисление суммы членов гармонического ряда	-
Тест 5 36 минут	12 заданий	-
Лекция 6	Имена и функции в языке программирования Паскаль Вводятся понятия имен и функции, рассказывается о способах передачи параметров в функции, побочных эффектах функции, коллизиях имен, дается понятие отношения. Оглавление Введение Имена и функции в языке программирования Паскаль Понятие имени Функции Способы передачи параметров в функции Передача по значению Передача по ссылке Передача по имени Пример программы Побочный эффект функции Понятие побочного эффекта Пример побочного эффекта Коллизии имён Введение в динамическую память Литература по структурам данных Отношения Понятие отношений Свойства отношений Виды отношений	-
Тест 6 36 минут	12 заданий	-
Лекция 7	Графы Дается определение графов, деревьев, стеков, очередей, кучи. Рассказывается о недостатках этих структур. Оглавление Графы Введение Определение Деревья Стек в линейной памяти (векторной) Операции над стеком Очередь в линейной памяти Недостатки рассмотренных структур Операции в куче	-
Тест 7 36 минут	12 заданий	-
Лекция 8	Работа со стеками, очередями и деревьями Даются примеры работы со стеком, очередью и списком, указываются особенности работы с ними. Рассказывается о двоичных деревьях. Оглавление Введение Процедура Вытолкнуть из стека Формула Наглядное объяснение Вытолкнуть единственный элемент Дополнительное объяснение Недостатки процедуры в Pascal Очередь в списковой памяти Схема списка очереди Взятие из списка Запись в список Список с обратным ходом Особенности списковой памяти Связывание указателей Операция get Операция put Предельный случай put Предельный случай get Реализация очереди в списковой памяти с фиктивным элементом В чем проблема списков? Пустая очередь Увеличение ошибок вследствие использования if Операция put Дополнительный пример операции put Операция get Дополнительный пример операции get Пример программы Типы Инициализация очереди Функция check Процедура put Наглядное объяснение процедуры put Процедура get Наглядное объяснение процедуры get Двоичные деревья Определение Задача полного обхода всех вершин Определение высоты дерева Обход дерева в ширину Обход дерева в глубину Что будет в следующий раз	-
Тест 8 36 минут	12 заданий	-
Лекция 9	Двоичные деревья Приводятся варианты обхода дерева c использованием циклов, рекурсий, стеков. Вводятся понятия первичного и вторичного ключа, даются оценки алгоритмов. Оглавление Введение Алгоритмы обхода двоичных деревьев Полный обход дерева Варианты обхода 1-й вариант обхода дерева c использованием циклов (итеративный) Ситуация 1 (вход) Ситуация 2 (вверх) Ситуация 3 (влево) Ситуация 4 (вправо) Типы и переменные для варианта №1 Процедура разметки для варианта №1 Реализация ситуации 1 (вход) Определение case(повторение) Реализация ситуации 2 (вверх) Реализация ситуации 3 (влево) Реализация ситуации 4 (вправо) 2-й вариант обхода дерева(рекурсивный) Общие сведения Описание типов данных Особенность объявления (отсутствие родительского указателя) Рекурсивная процедура Рекурсивное дерево (повторение) Обобщение алгоритма 3-й вариант обхода дерева с использованием стеков(рекурсивно-итеративный) Общие сведения Описание типов данных Рекурсивная процедура со стеками Применение стека в алгоритме Случай №1 в рекурсивной процедуре со стеками Случай №1 в рекурсивной процедуре со стеками (пояснения) Случай №2 в рекурсивной процедуре со стеками Особенность вариантов - отсутствие указателя на родительский узел Замечания об использовании рекурсии Сравнение алгоритмов обхода бинарных деревьев Внутренние таблицы Понятие (n)-арного отношения Понятие первичного ключа и его использование при поиске Понятие вторичного ключа Внутренние и внешние таблицы (общность методов поиска) Оценка алгоритма при работе с неотсортированным массивом Оценка алгоритма при работе с отсортированным массивом Набор операций для поиска Описание типов данных Описание функции fetch (функции выборки) Идея дихотомического метода поиска (метод деления пополам)	-
Тест 9 36 минут	12 заданий	-
Лекция 10	Деревья сравнения списковой памяти Рассказывается о деревьях сравнения списковой памяти, операции удаления и вставки. Оглавление Введение Деревья сравнения списковой памяти Операция Delete Операция Insert Дерево сравнения Деревья сравнения списковой памяти Функция fetch Вспомогательная функция Deletemin Трансформация дерева сравнения	-
Тест 10 36 минут	12 заданий	-
Лекция 11	АВЛ-деревья Рассказывается об АВЛ-деревьях, условиях их существования и построения, приводятся процедуры корректировки характеристик и частные случаи трансформации деревьев. Оглавление Введение Основные условия существование АВЛ-деревьев Частный случай АВЛ-дерева. Дерево Фибоначчи Построение АВЛ-деревьев Условия построения АВЛ-деревьев Процедуры корректировки характеристик Процедура FETCH Процедура INSERT Частные случаи трансформации деревьев Процедура DELETE Анонс следующей лекции	-
Тест 11 36 минут	12 заданий	-
Лекция 12	Цифровой поиск Приводится оценка вычислительной сложности АВЛ-деревьев, рассказывается о цифровом поиске, дается пример реализации программы. Оглавление Введение Оценка вычислительной сложности АВЛ-деревьев Цифровой поиск Написание программы Пример реализации программы Функция fetch Пояснения Анонс следующей лекции	-
Тест 12 36 минут	12 заданий	-
Лекция 13	Методы обработки таблиц с вычисляемыми адресами Рассказывается о методах обработки таблиц с вычисляемыми адресами, реализуются необходимые процедуры. Оглавление Введение Методы обработки таблиц с вычисляемыми адресами Описание констант, переменных Процедура FETCH Процедура DELETE Процедура INSERT CASE EMPTY Варианты реорганизации таблиц. Функция совершенного хэширования Выводы Решение переборочных задач. Метод динамического программирования	-
Тест 13 36 минут	12 заданий	-
5 часов	Экзамен	-

Авторизоваться

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

План занятий