наверх

Алгоритмы программирования и структуры данных

 width=
  • 10 недель

    длительность курса

  • 4 зачётных единицы

    для зачета в своем вузе

Курс знакомит слушателей с базовыми структурами данных и алгоритмами, знание которых необходимо для эффективного решения разнообразных задач программирования. Авторы курса занимаются поиском и подготовкой одаренных в области информатики и программирования студентов и школьников. Под их руководством студенческие команды многократно становились чемпионами России по программированию, чемпионами мира и Европы.

О курсе

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

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

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

Прохождение курса «Алгоритмы программирования и структуры данных» позволит существенно повысить продуктивность и конкурентоспособность слушателей при разработке программного обеспечения.

Формат

В состав курса входят видеолекции, опросы по материалам лекций и практические задания по программированию, предполагающие самостоятельную реализацию изучаемых в курсе алгоритмов и структур данных на одном из предложенных современных языков программирования. Курс рассчитан на десять недель. Средняя недельная нагрузка на обучающегося - 14 часов. Общая трудоемкость курса составляет четыре зачетных единицы.

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

  1. Кормен T., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2012.
  2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М. : Вильямс, 2007.
  3. Онлайн-конспекты лекций по дискретной математике, алгоритмам и структурам данных, читаемых на кафедре компьютерных технологий Университета ИТМО.

Требования

Для успешного освоения курса необходимы знание основ дискретной математики, умение писать программы среднего размера на объектно-ориентированном языке программирования.

Для прохождения курса требуется любой общедоступный компилятор одного из следующих языков программирования:

  • Java: версия 8 (ссылка для скачивания на сайте Oracle)
  • C, C++: MinGW версии 5.1 (для Windows, для Linux можно использовать GCC аналогичной версии), а также Microsoft Visual Studio C++ 2013 (скачать Visual Studio Express можно здесь).
  • C#: Microsoft Visual Studio C# 2013 (скачать Visual Studio Express можно здесь).
  • Python: версия 3.5 (ссылка для скачивания на сайте python.org)
  • Scala: версия 2.11 (ссылка для скачивания на сайте scala-lang.org)
  • Kotlin: версия 1.0 (ссылки на инструкции по установке компилятора, плагинов в IntelliJ IDEA и в Eclipse).

Программа курса

В курсе рассматриваются следующие темы:

  1. Оценка времени работы алгоритмов
  2. Алгоритмы сортировки, основанные на сравнении (сортировка слиянием, быстрая сортировка, нижняя оценка на время работы алгоритмов сортировки)
  3. Алгоритмы сортировки с линейным временем выполнения (сортировка подсчетом, цифровая сортировка, карманная сортировка)
  4. Элементарные структуры данных (стек, очередь, связанные списки)
  5. Алгоритмы, основанные на двоичной куче (сортировка кучей, очередь с приоритетами)
  6. Введение в алгоритмы поиска (двоичный поиск в отсортированном массиве, двоичное дерево поиска)
  7. Сбалансированные деревья поиска (обзор сбалансированных деревьев, АВЛ-дерево, Splay-дерево)
  8. Хеширование (хеш-таблицы с закрытой и открытой адресацией)
  9. Введение в поиск подстрок (простейший алгоритм поиска подстрок, алгоритм Рабина-Карпа)
  10. Поиск подстрок (алгоритм Кнута-Морриса-Пратта, Z-функция, алгоритм Бойера-Мура)

Каждая тема предполагает изучение в течение одной недели. На каждой неделе выдаются задания по программированию, предполагающие самостоятельную реализацию изучаемых в курсе алгоритмов и структур данных.

В курсе имеется два типа дедлайна (предельного срока выполнения оценивающих мероприятий):
– мягкий дедлайн, при котором необходимо выполнить все оценивающие мероприятия текущей недели до ее завершения;
– жесткий дедлайн, при котором на выполнение оценивающих мероприятий после мягкого дедлайна дополнительно выделяется еще две недели, по окончании которых доступ к соответствующим мероприятиям закрывается.

Результаты обучения

  • Умение анализировать и реализовывать базовые алгоритмы программирования и структуры данных
  • Навыки проектирования и разработки средств реализации прикладных информационных технологий
  • Навыки разработки алгоритмов для проведения экспериментальных исследований в области информатики

Формируемые компетенции

  • 09.03.02 Информационные системы и технологии
    1. Способность к проектированию базовых и прикладных информационных технологий (ПК-11)
    2. Способность разрабатывать средства реализации информационных технологий (алгоритмические) (ПК-12)
    3. Готовность участвовать в постановке и проведении экспериментальных исследований (ПК-23)

Сертификат

Сертификат будет выдан слушателям, выполнившим следующие условия:

  1. В срок до 23 октября 2016 года включительно получение не менее 12 баллов в сумме за выполнение следующих задач:
    • Неделя 1 - "Задача «a+b»";
    • Неделя 1 - "Задача «a+b2»";
    • Неделя 1 - "Простая сортировка";
    • Неделя 1 - "Знакомство с жителями Сортлэнда";

    • Неделя 2 - "Сортировка";
    • Неделя 2 - "Соревнования по бегу";
    • Неделя 2 - "Число инверсий";
    • Неделя 2 - "Анти-quick sort";
    • Неделя 2 - "K-ая порядковая статистика";

    • Неделя 3 - "Цифровая сортировка";
    • Неделя 3 - "Сортировка пугалом".
  2. Оплата в срок до 28 октября 2016 года включительно. К оплате допускаются только слушатели, выполнившие пункт 1.
  3. Достижение до жесткого дедлайна не менее 60% от максимального количества баллов по следующим задачам:
    • Неделя 4 - "Постфиксная запись";
    • Неделя 6 - "Проверка корректности";
    • Неделя 9 - "Быстрый поиск подстроки".
    Во время решения указанных задач должны быть выполнены условия проведения промежуточной и итоговой аттестации с идентификацией личности, которые описаны здесь. Невыполнение этих условий влечет за собой потерю возможности получения сертификата. Максимальная длительность каждой аттестации составляет 2 часа.
  4. Достижение в срок до 11 декабря 2016 года включительно не менее 60% от максимального количества баллов по курсу.

Буздалов Максим Викторович

Кандидат технических наук
Должность: доцент кафедры компьютерных технологий

Станкевич Андрей Сергеевич

Кандидат технических наук
Должность: доцент кафедры компьютерных технологий

Маврин Павел Юрьевич


Должность: тьютор кафедры компьютерных технологий

Буздалова Арина Сергеевна


Должность: тьютор кафедры компьютерных технологий

Нигматуллин Нияз Габдуллазянович


Должность: тьютор кафедры компьютерных технологий

Петрова Ирина Анатольевна


Должность: тьютор кафедры компьютерных технологий

сертификат об окончании курса

Сертификат

Похожие курсы