Бакалавриат 2024/2025

Алгоритмы и алгоритмические языки

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Базовая кафедра «Системное программирование» Института системного программирования им. В.П. Иванникова РАН (ИСП РАН)

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Алейник Владислав Владимирович, Афонин Сергей Александрович, Белеванцев Андрей Андреевич, Егоров Данила Игоревич, Иконникова Мария Кирилловна, Кармацких Ирина Вадимовна, Лебедев Сергей Аркадьевич, Лобанов Глеб Игоревич, Малышев Никита Евгеньевич, Морген Матвей Владиславович, Сокунов Дмитрий Антонович

Язык: русский

Кредиты: 7

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• ● Знать базовые понятия теории алгоритмов
• ● Знать основы языка С, в том числе утилиты сборки – компилятор, компоновщик
• ● Знать базовые алгоритмы и структуры данных
• ● Научиться писать и отлаживать программы на С, понимать, какие структуры данных использовать, какова сложность работы с ними
• Знать основы языка С++, базовые типы данных, основные понятия объектно-ориентированного программирования и их реализацию в С++: пространства имен, классы, методы, конструкторы и деструкторы, механизмы наследования.

Планируемые результаты обучения

• Знания основы языка С
• Знать основы языка С++

Содержание учебной дисциплины

• Цели и задачи курса. Характеристика разделов курса.
• Структура программного файла. Системные библиотеки и их использование. Описание Си-машины. Типы данных языка Си.
• Приведение типов при вычислении выражений (явное и неявное). Операторы: выражение-оператор, составный оператор, условный оператор, оператор выбора, циклы, оператор перехода.
• Обработка строк. Операция sizeof. Указатели. Адресная арифметика.
• Возврат из функции. Рекурсия. Хвостовая рекурсия. Встраивание функций. Указатели на функцию.
• Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора. Динамическое выделение и освобождение памяти.
• Инструменты поиска ошибок с динамической памятью. Представление данных с плавающей точкой. Стандарт IEEE 754.
• Организация типа данных «стек» на динамической памяти. Реализация стека как библиотеки. Использование стека для построения обратной польской записи.
• Простейшие алгоритмы сортировки (выбором, вставками, обменами). Оценка сложности алгоритмов сортировки.
• "Прошитое" двоичное дерево и его обход. Двоичные деревья поиска и операции над ними.
• Красно-черные деревья, их высота и вставка в красно-черное дерево.
• Хеширование. Хеширование цепочками.
• C++. Сборка бинарных файлов
• С++. Типы данных
• C++. Процедуры
• С++. Объектно-ориентированное программирование.

Элементы контроля

• С++. Экзамен
• Домашние задания
  По три домашних задания в 1-м и 2-м модулях.
• Контрольная работа
  Одна контрольная работа в 1-м модуле. Две контрольные работы во 2-м модуле.
• С++. Семинарские занятия. Домашняя работа 2.
  Реализация проекта на С++ Большое домашнее задание №2
• Экзамен по 1/2 модулям
  Экзамен состоит из нескольких задач (обычно между 8 и 12). Каждая задача оценивается в некоторое количество баллов. Оценка за экзамен вычисляется как сумма баллов по всем решенным задачам, поделенная на сумму баллов по всем задачам.
• Самостоятельная работа
  Две самостоятельные работы в модуле.
• С++. Семинарские занятия. Домашняя работа 1.
  Реализация проекта на С++ Большое домашнее задание №1
• А
  активность на семинарах (ответы на вопросы, решение задач)

Промежуточная аттестация

• 2024/2025 2nd module
  П = 0.4 х ЭКЗ + 0.3 х КР + 0.3 х ДЗ, если ЭКЗ >= 0.3 Если ЭКЗ < 0.3, то П = ЭКЗ Результат = Округление(П * 10)
• 2024/2025 3rd module
  Итог за 3 модуль = 0,1 * А + 0,5 * (0,45 * ДЗ1 + 0,55 * ДЗ2) + 0,4 * ЭКЗ

Список литературы

Рекомендуемая основная литература

• Керниган, Б. В. Язык программирования C : учебник / Б. В. Керниган, Д. М. Ричи. — 2-е изд. — Москва : ИНТУИТ, 2016. — 313 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100543 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Рекомендуемая дополнительная литература

• Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012

Авторы

• Буцкая Евгения Александровна
• Белеванцев Андрей Андреевич