Программирование на C. Алгоритмы и структуры данных

Магистратура 2025/2026

Статус: Курс обязательный (Аппаратно-программные комплексы искусственного интеллекта)

Кто читает: Департамент электронной инженерии

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

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

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

Преподаватели: Петряйкин Федор Алексеевич

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

Кредиты: 6

Дополнительные материалы в LMS Задать вопрос

Аннотация

Данный курс посвящен изучению (или повторению) основных аспектов программирования на языке C и является подготовительным к изучению языка C++. В ходе прохождения курса будут разобраны модель памяти C, система типов языка, вопросы сборки программы и другие. Будут затронуты темы взаимодействия программы с ОС и аппаратными компонентами компьютера.Как пример применения языка C будут рассматриваться реализации алгоритмов - как стандартных из библиотеки STL, так и частных, возникавших в реальных практических задачах авторов курса. В ходе курса слушатели познакомяться с процессами, применяемыми в промышленном программировании, - юнит-тестированием, инструментированием, code review и другими.Курс является базовым в блоке курсов по С/С++ и базируется на знаниях, полученных студентами в курсе “Архитектура вычислительных систем и нейроускорителей”

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

Изучение основ программирования на языке C++, включая изучение синтаксиса, базовых конструкций языка, работу с памятью, файлами, алгоритмами и другими ключевыми концепциями

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

Знать принципы построения unix-подобных систем
Знать принципы организации файловых систем в linux, основные команды shell и утилиты linux, в т.ч. ssh
Уметь выполнять простые операции над файлами и их содержимым, пользователями и процессами в linux с помощью командной строки
Уметь автоматизировать команды с помощью shell-скриптов
Уметь использовать ssh для подключения к серверам с помощью паролей и ключей, уметь разбирать простые ошибки по логу ssh
Знать этапы компиляции C++ программы
Знать значение директив препроцессора
Уметь собирать C++ программу из файлов исходного кода с различными флагами компиляции
Уметь исправлять простые ошибки компиляции
Знать основные синтаксические конструкции С++ : базовые типы, циклы, условные конструкции, объявление переменных
Уметь применять полученные знания для решения простейших алгоритмических задач, выбирая при этом оптимальную конструкцию
Знать что такое функции в С++, как задаются ее параметры
Знать организацию ввода-вывода в языке С
Знать арифметику адресов и указателей
Знать о-нотацию, простейшие алгоритмы сортировки: "наиваня", подсчетом, слиянием, пузырьковая
Знать алгоритм бинарного поиска
Знать различные способы поиска ошибок времени исполнения и "узких мест" в программах
Уметь реализовывать алгоритмы, описанные в (1)
Уметь использовать инструментирование, утилиту perf для нахождения "узких мест"
Уметь использовать gdb для отладки
Знать базовое устройство виртуальной памяти, стека вызовов и кеша процессора
Знать устройство массивов
Знать использование указателей при работе с массивами
Знать встроенные функции для работы со строками
Знать принципы обработки аргументов командной строки
Уметь писать простые алгоритмы с использованием массивов и адресной арифметики
Уметь использовать стандартные функции для работы со строками
Уметь корректно обрабатывать аргументы командной строки
Знать базовое устройство файловой системы в unix-like операционных системах
Знать принципы текстового и бинарного доступа в файл
Знать подходы для обработки консольного ввода
Уметь читать/писать в файлы
Уметь использовать файлы как дополнительную "медленную память".
Уметь писать программы с различными подходами консольного ввода
Знать базовое устройство динамической и статической памяти, области их использования и отличия
Знать что такое строки и массивы, их представление и способы взаимодействия с ними
Уметь использовать статическую и динамическую память
Уметь работать со строками и массивами
Знать базовое устройство типа данных 'структура' в С/С++
Знать устройство ключевого слова typedef
Понимать устройство указателей на функции
Уметь использовать структуру в коде
Уметь использовать ключевое слово typedef в коде
Уметь эксплуатировать указатели на функции под свои нужды
Знать устройство раздельной компиляции и причины её использования
Знать устройство процесса компоновки
Знать, что скрывает под собой команда make и ее назначение
Уметь использовать команду make
Уметь организовывать программный код под взаимодействие с командой make
Знать основные алгоритмы на графах (dfs, bfs, алгоритм дейкстры и т.д.)
Уметь реализовывать изученные алгоритмы на языках с и си++, применять их для решения простых алгоритмических задач
Знать простейшие методы оптимизации (градиентный спуск) и поиска корней уравнения (метод ньютона, мпи и др.)
Уметь реализовывать данные методы на языках С и С++
Знать основные принципы тестирования
Знать пирамиду тестирования
Знать подходы при написании unit-тестов и интеграционных тестов
Уметь покрывать свой код тестами и соблюдать баланс между разными типами тестов
Уметь работать с gtest, использовать линтеры и чекеры, а также asan флаги компилятора
Знать основные принципы и подходы для построения ci-пайплайнов
Уметь строить ci-пайплайны с артефактами, секретами и публикацией результатов тестирования

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

Введение. Операционная система LINUX. Устройство файловых систем. Оболочка. Файлы. Исполняемые файлы. ssh, ssh-agent и ssh-ключи
Первая программа на С. Препроцессор. Компиляция. Запуск. HELLO WORLD
Основные синтаксические конструкции C. Система типов. Переменные. Условные конструкции. Циклы
Функции. Параметры функций. Указатели (1). Scanf
Указатели (2). Массивы. Строки. Разбор аргументов командной строки
Работа с файлами и консольным вводом
Динамическая и статическая память. Алгоритмы на строках и массивах (задание)
Алгоритмы на строках и массивах (2). Замеры скорости. Отладка
Структуры. Typedef. Указатели на функции
Раздельная компиляция. Компоновка. Make
Алгоритмы на графах
Алгоритмы оптимизации и решения уравнений (простейшие)
Юнит и интеграционное тестирование
Запуск тестов в Ci. Git lab

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

Домашние задания
Практические задания
Экзамен

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

2025/2026 2nd module
Итоговая оценка формируется как сумма оценок за отдельные элементы контроля. Баллы, полученные за практические задания на семинарах, суммируются с баллами, полученными за экзамен (и в сумме могут быть не более 30), но при этом для получения зачёта необходимо сдать экзамен минимум на 15 баллов. Формула расчета итоговой оценки: SUM_7_ДОМАШНИЙ ЗАДАНИЙ + (SUM_14_ПРАКТИЧЕСКИХ ЗАДАНИЙ НА СЕМИНАРЕ + ЭКЗАМЕН) ГДЕ (SUM_14_ПРАКТИЧЕСКИХ ЗАДАНИЙ НА СЕМИНАРЕ + ЭКЗАМЕН) ≤ 30 БАЛЛОВ

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

Авторы

Манохин Александр Иванович
Нефедов Сергей Игоревич

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