Материалы 2019-2020 учебного года
Составной тип --- объединения, его назначение. Определение и инициализация, обращение к отдельным элементам. Частичная инициализация. Расположение в памяти, операция sizeof. Варианты использования объединений.
Стадии трансляции программы на Си: предобработка, компиляция и компоновка. Объявления и определения. Области видимости. Пространства имен. Доступ к переменным и функциям из других файлов, ключевые слова extern и static, внешнее и внутреннее связывание. Заголовочные файлы в Си, проблема повторного включения и её решение. Классы памяти для размещения локальных переменных, ключевые слова auto, register и static.
Керниган, Б. Практика программирования. / Б. Керниган, Р. Пайк. --- Вильямс, 2016. --- 288 с.
Макконнелл, С. Совершенный код. / С. Макконнелл. --- Русская Редакция, Microsoft Press, 2017. --- 896 с.
Ван Тассел, Д. Стиль, разработка, эффективность, отладка и испытание программ. / Д. Ван Тассел. --- М.: Мир, 1985. --- 334 с.
Тэллес, М. Наука отладки. / М. Тэллес, Ю. Хсих --- КУДИЦ-Образ, 2003. --- 560 с.
Программирование как искусство и как профессия: различные подходы, различные требования к квалификации. Профессиональный подход. Отличие коммерческих продуктов от студенческих лабораторных работ. Составляющие процесса разработки, жизненный цикл ПО вкратце (анализ, проектирование, кодирование, тестирование, отладка, оптимизация, документирование, сопровождение). Прибыль компании, оптимизация качественных и количественных характеристик.
Программирование как искусство (есть локальная копия для сохранности)
Программы пишутся не только для машины, но и для человека. Необходимость повышения читаемости программ: совместная разработка, отладка, модификация, повторное использование, поддержка, развитие. Правило №1 при редактировании кода. Визуальные составляющие стиля: форматирование кода, именование идентификаторов, комментирование. Смысловые составляющие стиля: паттерны (шаблоны) для решения стандартных задач. Соглашение об именовании: передача назначения объекта и дополнительных сведений. Способы объединения нескольких слов. Регистр букв, префиксы и суффиксы для передачи мета-информации (тип, вид, область видимости идентификаторов). Комментарий как конструкция языка для внедрения дополнительной информации в исходный код. Зачем? Почему? Как? Что? Краткое изложение кода, объяснение сложных конструкций, алгоритмов, намерений программиста. PDL (Program Design Language) и программирование "сверху вниз". Комментарии как метаданные для инструментария разработки, автодокументация.
Google style guides (C++, JavaScript, Objective C, Python, R, XML)
Независимые компоненты большой системы. Изоляция частей программы, уменьшение точек соприкосновения: упрощение понимания, уменьшение числа ошибок. Возможность независимого изменения и подмены. Модульность на уровне блоков, функций, файлов. Поддержка модульности в Си.
Понятия абстрактного типа данных (АТД) и структуры данных (СД). Техника использования непрозрачных (opaque) типов данных в Си. АТД "стек" и "очередь", интерфейс на языке Си и возможная реализация на массиве.
Ошибки времени выполнения и их неизбежность. Поведение в случае нескольких модулей, с точки зрения библиотеки функций. Обнаружение и уведомление "пользователя" модуля. Способы уведомления по инициативе пользователя и по инициативе библиотеки: глобальный статус, возвращаемое значение или функция-обработчик.
Причина ошибок. Статический анализ кода, программа lint и ее аналоги. Семантические проверки во время выполнения: assertions (утверждения) как проверка предположений программиста. Их назначение, стандартные реализации, синтаксис при использовании. Примеры применения, design by contract. Отладочная и финальная конфигурации проекта. Compile-time (static) assertions как проверка предположений во время компиляции программы. Их назначение, стандартная реализация, синтаксис при использовании.
Возможные собственные реализации ассертов: макрос и функция регистрации сообщения. Возможные собственные реализации статических ассертов: ошибки компиляции.
_
Классификация видов тестирования по действующему лицу, по виду ошибок, по целевой части программы. Модульное тестирование. Понятие нестабильности и примеры, процесс отладки. Интерактивный отладчик и его возможности. Библиотека crtdbg в Visual Studio.
_
Память и время. Доступные средства замера времени. Разрешающая способность таймеров, абсолютная и относительная погрешность на примере сортировки чисел. Способы уменьшения погрешности. Специализированный инструментарий.
Кормен, Т. Алгоритмы. Построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн ---
Вильямс, 2016. --- 1328 с.
Пределы оптимизации кода и оптимизация алгоритма. Время и пространство. Понятие сложности задачи и алгоритма. Сравнение типичных зависимостей на графике и в реальных числах, возможное увеличение задачи при росте вычислительной мощности. Область влияния констант.
_
Пример: возведение в целую степень, его модификация с рекурсией. Пространственная (емкостная) сложность приведенных алгоритмов, нерекурсивная реализация возведения в степень.
Поиск минимального и максимального элемента. Поиск заданного элемента. Упорядоченные массивы.
_
Задача сортировки. Свойства и метрики алгоритмов. Сортировка перебором. Сортировка выбором (selection sort) и вариации. Сортировка вставками (insertion sort) и вариации. Сортировка пузырьком (bubble sort) и вариации.
_
Сортировка Шелла (Shell sort) и вариации. Сортировка прочесыванием (гребнем, comb sort). Библиотечная сортировка*** (library sort).
Сортировка слиянием (merge sort) и вариации. Быстрая сортировка (Хоара, quicksort) и вариации. Пирамидальная сортировка (кучей, heapsort) и вариации. Случайные перестановки и их роль в сортировке.
_
Сортировка подсчетом (counting sort). Поразрядная сортировка (цифровая, radix sort). Сортировка вычерпыванием (черпаком, bucket sort).
_
Структура данных "связный список". Линейный односвязный список, основные операции и их вычислительная сложность. Альтернативная реализация интерфейса стека и очереди на связных списках. Другие динамически связные структуры: двусвязные списки, бинарные деревья и деревья с произвольным числом детей. Совпадение структур Си для разных структур данных.
_
Общее понятие рекурсии. Прямая и косвенная рекурсия в математике, пример с факториалом и числами Фибоначчи. Поддержка в языках программирования, возможная реализация, стек вызовов. Достоинства и недостатки рекурсии. Особый вид - хвостовая рекурсия.
Язык программирования и исполнитель. Рейтинги языков программирования, востребованные языки. Любимые языки. Интересные языки. Полиглот, квайн, уроборос.
Программно-аппаратная среда выполнения программ. Компоновка объектного кода в исполняемую программу. Статические и динамические библиотеки. Проблемы совместимости. Преобразование имен, порядок вызова функций и передачи параметров. Типы данных, различия в представлении массивов и строк.
_
_
Виртуальная машина языка Forth. Базовые слова управления стеком. Определение новых слов. Управляющие структуры.
Объявления и определения. Области видимости объявлений. Пространства имен. Время и место жизни объектов. Спецификаторы и модификаторы классов памяти.
Системы контроля версий...
_