Joint Department with the RAS Institute for System Programming

Regular version of the site

Publications

Book

ECPPM 2021 – eWork and eBusiness in Architecture, Engineering and Construction

Edited by: Vitaly Semenov, R. J. Scherer.

CRC Press, 2021.

Article

Equivalence checking and intersection of deterministic timed finite state machines

Bresolin D., El-Fakih K., Villa T. et al.

Formal Methods in System Design. 2022.

Book chapter

City and building information modelling using IFC standard

Shutkin V., Morozkin N., Zolotov V. et al.

In bk.: ECPPM 2021 – eWork and eBusiness in Architecture, Engineering and Construction. CRC Press, 2021. P. 406-413.

Working paper

Preventive Model-based Verification and Repairing for SDN Requests

Burdonov I., Kossachev A., Nina Yevtushenko et al.

arxiv.org. Computer Science. Cornell University, 2020

All publications

Delivered by:: Joint Department with the RAS Institute for System Programming

Type:: Compulsory course

When:: 1 year, 1-3 module

Instructors

Aleinik, Vladislav

Белеванцев Андрей Андреевич

Егоров Данила Игоревич

Иконникова Мария Кирилловна

Малышев Никита Евгеньевич

Terlych, Nikita

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

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

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

2023/2024 учебный год 2 модуль
П = 0.4 х ЭКЗ + 0.3 х КР + 0.3 х ДЗ, если ЭКЗ >= 0.3 Если ЭКЗ < 0.3, то П = ЭКЗ Результат = Округление(П * 10)
2023/2024 учебный год 3 модуль
0.35 * С++. Семинарские занятия. Домашняя работа 1. + 0.35 * С++. Семинарские занятия. Домашняя работа 2. + 0.3 * С++. Экзамен

Contacts

Algorithms and Algorithmic Languages

Instructors

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

Аннотация

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

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

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

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

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

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

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

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