НОУ ИНТУИТ | Повышение квалификации | Программирование и знакомство с алгоритмами

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

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

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

Рассказывается о стиле программирования и сложности алгоритмов, алгоритмах поиска, функциях и процедурах, рекурсии и динамическом программировании. Даются основные алгоритмы сортировки, поиска в глубину и ширину. Рассматриваются элементы теории графов и кодирование информации.

Вам нравится?

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

Поддержать

Занятие	Заголовок <<	Дата изучения
	Экзамен экстерном	-
Лекция 1	Стиль программирования и сложность алгоритмов. Логические операции и их свойства В лекции рассказывается о правильном стиле программирования, даются начальные сведения о сложности алгоритмов и эффективности программ. Дается информация о логических операциях и их свойствах. Оглавление Введение О стиле программирования Имена переменных Константы Тип Отступы в программе Конструкция begin-end Дополнение к стилю программирования Конструкция обнуления массива Сложность алгоритмов Недостатки готовой программы Оценка эффективности программы Подсчет времени Максимальное и среднее количество операций Пример подсчета количества операций Формула сложности алгоритма Таблица соотношений n,c,c' Обозначения, для времени работы алгоритма Вопрос по теме Деление (виды) алгоритмов Задача на определение сложности алгоритма Пояснение к задаче Определение log N Заключение Логические операции и их свойства Введение Приоретет операций Свойство операции AND Свойство операции OR Свойство операций в математическом понимании Битовые операции Сдвиги Пример применения AND Пример применения OR Пример применения XOR Пример применения NOT Приоретет битовых операций относительно логических Примеры	-
Тест 1 36 минут	12 заданий	-
Лекция 2	Поиск в массиве и двумерные массивы Приводятся алгоритмы линейного и бинарного поиска элементов в массиве, рассказывается о задании двумерного массива и поиске в нем. Оглавление Введение Линейный поиск в массиве Алгоритм линейного поиска в массиве Прием барьерный элемент Поиск второго максимума в массиве Поиск отсутствующего в массиве числа Бинарный поиск в массиве Алгоритм бинарного поиска в массиве Применение бинарного поиска Двумерный массив Задание двумерного массива Поиск в двумерном массиве	-
Тест 2 36 минут	12 заданий	-
Лекция 3	Функции и процедуры Рассказывается об использовании функций и процедур, их преимуществах и недостатках, неправильном использовании имени функции. Оглавление Введение Функции Определение функции Описание функции Типы результата Примеры описаний Использование функций Преимущества Недостатки Локальные (внутренние) переменные функции Параметры-значения Параметры-переменные Задача 1 Задача 2 Задача 3 Задача 4 Процедуры Описание процедуры Определение процедуры Примеры описаний Передача массива в параметре Команда EXIT Опережающее описание Модули Назначение модулей Описание модулей Interface часть Implementation часть Раздел инициализации Неправильное использование имени функции Рекурсия Вступление Определение рекурсии Пример Определение терминального условия Теорема о взаимозаменяемости цикла и рекурсии	-
Тест 3 36 минут	12 заданий	-
Лекция 4	Рекурсия В лекции рассказывается о рекурсии и ее использовании, приводится большое количество задач. Оглавление Введение Рекурсия Задача "Ханойские башни" Алгоритм решения задачи Написание процедуры на паскале Определение рекурсии Основная программа Анализ процедуры Процесс выполнения рекурсии в компьютере Глубина рекурсии Определение стека процедуры функции Схема стека Задачи на рекурсию Найти a в степени n Вопросы к задаче НОД 2-х чисел Определение НОД Алгоритм Евклида Формула НОД Доказательство Полная формула вычисления НОД Написание функции расчета НОД Понятие терминального условия Вопросы к задаче НОД 3-х чисел Определение НОК Формула НОК через НОД Проблемы, возникающие при решении задачи Задача вывода чисел без циклов Задача запоминания чисел без массива	-
Тест 4 36 минут	12 заданий	-
Лекция 5	Рекурсия и динамическое программирование Лекция продолжает тему рекурсии на примере задач. Рассказывается о динамическом программировании и приводятся различные примеры. Оглавление Введение Рекурсия Использование forward в Pascal Вычисление числа Фибоначчи Перебор. Заполнение матрицы Перебор. Расстановки ладей Разбор арифметического выражения Динамическое программирование Вступление Пример 1: Фишка и клетки (задача о полоске) Понятие барьерного элемента Пример 2: Задача о хромом короле Пример 3: Черепашка (максимум и путь) Пример 4: Задача о ранце. Вариант 1 Определение динамической задачи Пример 4: Задача о ранце. Вариант 2 Пример 5: Задача о разложении числа	-
Тест 5 36 минут	12 заданий	-
Лекция 6	Динамическое программирование В лекции рассказывается о динамическом программировании на примерах различных задач. Оглавление Введение Динамическое программирование Динамическое программирование и рекурсия Задача о ранце с ограничениями Переборное решение Динамическое решение Вывод формулы Редакционные растояния Определение редакционных растояний Пример Алгоритм расчета редакционных расстояний Вывод формулы Пример Продолжение вывода формулы Пример и окончание вывода формулы Ответы на вопросы	-
Тест 6 36 минут	12 заданий	-
Лекция 7	Сортировка В лекции приводятся различные методы сортировки: сортировка выбором, вставками, пузырьком, слиянием и быстрая сортировка. Оглавление Введение Сортировка выбором Идея алгоритма Код Оценка времени работы Сортировка вставками Идея алгоритма Код Оценка времени работы Сортировка пузырьком Идея алгоритма Код Оценка времени работы Метод "Разделяй и властвуй" как основа быстрых сортировок Быстрая сортировка Идея алгоритма Разбор примера у доски Выбор среднего элемента и оценка времени работы Код Обсуждение Сортировка слиянием Идея слияния двух массивов Код процедуры сортировки Код процедуры слияния Оценка времени работы Обсуждение быстрых сортировок	-
Тест 7 36 минут	12 заданий	-
Лекция 8	Множества, деление с остатком и взятие по модулю В лекции рассказывается о множествах и операциях в них. Рассматриваются операции деления с остатком и взятия по модулю. Приводятся примеры программ. Оглавление Введение Множества Понятие и примеры множества чисел Операции со множествами Фанторы Деление с остатком Определение Доказательство существования Доказательство единственности Примеры операции взятия по модулю Свойства операции взятия по модулю Теорема 1 Теорема 2 Теорема 3 Применение свойств взятия по модулю Задача 1 Задача 2 Метод Паскаля.Признак делимости числа Пример применения метода Паскаля Взятие по модулю на языке Паскаль Пример написания программы	-
Тест 8 36 минут	12 заданий	-
Лекция 9	Поиск пути, алгоритмы поиска в глубину и ширину Рассказывается об алгоритмах поиска пути выхода из лабиринта, объясняются алгоритмы поиска в глубину и ширину. Оглавление Введение Алгоритм поиска пути выхода из лабиринта Постановка задачи Способы хранения лабиринта в памяти Способы выхода из лабиринта Реализация алгоритма пути выхода в виде процедуры DFS Вид основной программы Оптимизация процедуры DFS Сокращение числа условных операций в DFS Преобразование процедуры в функцию Depth-First Search - алгоритм поиска в глубину Понятие Поиск произвольного пути выхода с помощью DFS Breadth-First Search - алгоритм поиска в ширину Понятие Нахождение кратчайшего пути выхода с помощью BFS Три способа записи кратчайшего пути в правильном порядке	-
Тест 9 18 минут	6 заданий	-
Лекция 10	Графы В лекции рассказывается о графах, даются основные понятия теории графов и их представления в компьютерных программах. Оглавление Введение Графы. Определения и понятия Формальное определение графа Компоненты связности Изолированные вершины Висячие вершины Степень вершин Кратные ребра Петли Простой граф Максимальное количество ребер в простом графе Путь в графе Простой путь Цикл в графе Связный граф Минимальное количество ребер в простом связном графе (обсуждение) Ориентированный граф Представление графа в компьютере Общие рассуждения Список ребер Матрица смежности Упорядоченный список ребер Списки смежных вершин Ответы на вопросы	-
Тест 10 36 минут	12 заданий	-
Лекция 11	Графы. Кодирование информации В лекции заканчивается рассказ о графах. Вводится понятие кодирования, рассказывается о коде Шеннона-Фано, проверке и исправлении ошибок, алгоритмах шифрования с открытым ключом. Оглавление Введение Представление графов в памяти компьютера Список рёбер Матрица смежности Сравнение способов задания графов Списки смежных вершин Выбор способа задания графов Хранение ориентированных графов Кодирование информации. Определение Цели кодирования Сжатие Код Шеннона-Фано Преффиксность Проверка ошибок Бит четности Контрольная сумма Проверка циклической избыточности Исправление ошибок Рефлективный код Грея.Кодовое расстояние Пример Секретность. Подлинность Алгоритм шифрования с открытым ключём Пример	-
Тест 11 36 минут	12 заданий	-
Лекция 12	Длинные числа В лекции рассказывается о длинных числах, вариантах их представления в программе и работе с ними. Приводятся программы для основных операций с длинными числами. Оглавление Введение Операции с длинными числами Варианты хранения длинных чисел	-
Тест 12 36 минут	12 заданий	-
5 часов	Экзамен	-

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

Программирование и знакомство с алгоритмами

План занятий