Содержание базового курса информатики

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

Курс состоит из 4 семестров. В первом семестре студенты знакомятся с языком программирования C– изучают основные языковые конструкции, выделение памяти, ввод-вывод. Эти навыки используются при решении алгоритмических задач – студенты должны освоить различные сортировки (быструю, пирамидальную, слиянием, вставками, поразрядную), структуры данных (список, стек, очередь, очередь с приоритетами), жадные алгоритмы и динамическое программирование.

Второй семестр посвящен ООП в C++ (включая нововведения, появившиеся в С++11). Студенты начинают отрабатывать ООП на простых задачах – реализовать целочисленную длинную арифметику, работу с матрицами (быстрое умножение, обращение, вычисление детерминанта и т.д.). После этого идет блок, связанный с вычислительной геометрией. В начале даются задачи школьного уровня – пересечение отрезков, построение выпуклой оболочки (алгоритмы Джарвиса и Грэхема), пересечение всех отрезков (идея заметающей прямой). Затем студенты изучают более сложные алгоритмы для решения триангуляции Делоне и построения диаграмм Вороного. Следующий блок задач связан с графами – варианты представления графа, обходы в глубину и в ширину, топологическая сортировка, поиск сильносвязных компонент. Завершающий блок связан с поисковыми структурами данных – красно-черное дерево, хеш-таблицы, B-деревья и разными задачами на комплексное использование STL (например, коды Хаффмана или StringPool).

Третий семестр начинается с более глубокого знакомства с графами – изучаются алгоритмы Флойда, Дейкстры, Форда-Беллмана для поиска кратчайших путей, построение минимальных остовных деревьев с помощью алгоритмов Прима и Крускала. Для эффективной реализации алгоритмов студенты знакомятся с разными видами пирамид – фиббоначиевой, биномиальной. Также в этот набор входят эвристические алгоритмы (A*) и алгоритмы на потоки в сетях. Середина семестра посвящена декартовым деревьям, деревьям Фенвика, различным решениям задач RMQи LCA (включая сведение одного к другому). Заключительая часть семестра отведена для изучения алгоритмов для строк – алгоритмы Рабина-Карпа, Бойера-Мура, Кнута-Морриса-Пратта, Ахо-Корасика. Студенты изучают способьы использования и эффективное построение таких структур данных, как суффиксный массив суффиксное дерево.

Заключительный, четвертый, семестр базового курса обращает внимание слушателей на основы использования алгоритмов и структур данных в многопоточном коде. В этом семестре студенты пишут как структуры данных с внутренними локами, так и lock-free. Также студенты знакомятся с основными паттернами параллельных алгоритмов - Map, Reduce, Scan, Sort, Gather&Scatter.