Drupal | Information

Created: 17.03.2009 | Level: specialist | Access: free

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

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

Supplementary courses Graphs and Algorithms Introduction to Schemes, Automata and Algorithms Advanced Algorithms for Schoolchildren Basic and Advanced Algorithms for Schoolchildren Programming in Pascal Introduction to Cryptocurrencies and Blockchain Combinatorial Algorithms Distributed systems and algorithms Computational Mathematics and Structure Algorithms Introduction to Parallel Algorithms An Introduction to Programming and Algorithms Introduction to Algorithms Algorithms and Model Calculations Algorithms: Construction and Analysis Algorithms and Theory of Computation

Вам нравится? Нравится 29 students like this

| Share |

Поддержать

| Скачать видеокурс (mp4)

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

User login

Navigation

Who's online

Online users

Information

Introduction to Algorithms

Supplementary courses

План занятий