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