Промышленное программирование и структуры данных: часть 1, язык С

научить современным методам программирования и разработки программных систем на языках С и С++, привить навыки надежного, промышленного программирования, работы в команде, подготовить их для участия в тематических проектах других курсов Технотрека. Как показывает практика, студенты с олимпиадным прошлым привыкли работать не над проектами, а над отдельными задачами, и таких навыков, как правило, не имеют. :)
15 занятий, 64 ак.часа
Хочу учиться
Что дает курс

Результатом согласованной работы лектора, семинариста и студентов должно стать не только изучение теоретического материала и отработка его на практических задачах, но и формирование современной методологии разработки программ и профессиональной системы ценностей у студентов, что позволит им как успешно разрабатывать системные программные продукты, так и участвовать в дальнейших курсах Технотрека.

Неформально говоря, до прохождения этого курса студенты обычно имеют навыки написания небольших задач, автоматически тестирующихся, не обладающих избыточной надежностью, не связанных с другими частями проекта, уже разработанными или планирующимися к разработке, не предназначенных для использования коллегами в компании, не предназначенные для прочтения и изменения коллегами, не предназначенных для работы в таких средах, о которых автор в момент написания не имел даже никакого понятия. :)

После прохождения этого курса студенты должны получить все эти навыки. И начать их оттачивать месяцами и годами, "правило десяти тысяч часов" никто не отменял. Но профессиональные качества программиста зависит от того, как именно провести эти десять тысяч часов.

Какие знания нужны

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

Как проходят занятия

Автор курса ставит целью концентрированно передать не только свои академические знания, но прежде всего свой опыт разработчика-профессионала.

Ранее этот курс читался в рамках известного проекта Ilab ("Айлаб", образовательной лаборатории МФТИ-Intel) и был доступен только для студентов ФРТК. Теперь он доступен для всех физтехов.

Несколько замечаний:

Те, кто уже занимался Си, Си++ и их потомками - Java, C# и т.п. - найдут много нового в нюансах языков, но главное - в том, как языковые средства применять грамотно.

Те, кто считают, что Си - уже мертвый язык, а в Си++ "легко выстрелить себе в ногу", возможно, в чем-то правы, но "гарантированно не выстрелить себе в ногу" можно только на языке, которым никто не пользуется. А языки семейства С/С++ и их потомки - абсолютные лидеры по применению. К сожалению, на любом языке можно писать плохо и выстрелить в эту самую ногу. Наша цель - научиться не делать так.

Те, кто активно занимался алгоритмами и олимпиадами, могут заметить, что алгоритмически курс не супер-нагружен. Это сделано специально, чтобы сфокусироваться на том, что в олимпиадах вообще не рассматривается. А не рассматривается там процентов 90 от необходимых навыков профессионального программиста, так как олимпиады - это лишь только спорт, и большинство навыков программиста-профессионала там просто не нужны. А в профессии - нужны.

Курсов, посвященным только алгоритмам очень много, как и литературы по ним в Интернете. Наш курс фокусируется на том, как грамотно реализовать алгоритмы и структуры данных и соединить их вместе в надежно работающий объемный проект, "чтобы не было мучительно стыдно" за бесцельно потраченное время, нервы коллег и свои собственные. История, увы, обычная для каждого олимпиадника, пытающегося прикоснуться к профессии. А вот об этом уже нет курсов, мало книг и немного систематизированной информации в сети.

Важно: этот курс не рассчитан на обучение "с нуля", он предполагает знание какого-либо языка программирования и алгоритмический опыт, олимпиадный или проектный.

Собираясь на этот курс, имейте в виду, что он потребует значительного времени на практику, что абсолютно честно отражено в оценках времени самостоятельной работы. Однако там указаны оценки максимального времени, так честнее.

Lifehack: Материал этого курса автор читает в своих академических группах МФТИ для первого курса, поэтому те, кто в этих группах учатся, могут получить за эту работу еще и зачет в зачетку. :)

May the Source be with you! :)

Первая часть курса (5-6 занятий) – быстрое практическое введение в Си через разбор и решение небольших задач, но с упором на принципы промышленного программирования.

Вторая часть курса (11-12 занятий) – введение в структуры данных и алгоритмы, практическая часть которой содержит меньшее число задач, но большего объема. Задачи второй части подобраны по большей части таким образом, что в конце курса каждый студент самостоятельно реализует примитивную модель вычислительной системы, инструментальные средства низкоуровневой разработки для него, а также небольшой высокоуровневый транслятор в байт-код, совместимый с трансляторами других студентов на уровне AST. Это дает возможность использовать кросс-компиляцию программ одного студента для виртуальной машины другого и затем на ней, а также перевод в исходный текст в формате языка другого студента. Студентам предстоит разработать общие стандарты взаимодействия компонентов системы.

Третья часть курса (второй семестр, 6-10 занятий) представляет собой введение в язык С++ в терминах различий С и С++, методом рефакторинга ряда решений на языке С, рассматривавшихся в осеннем семестре.

Четвертая часть курса (второй семестр, 6-10 занятий) посвящена технологии применения С++ (ООД, ООП, компо-нентное программирование) в многомодульном проекте, использующем программный код группы разработчиков в виде динамически подключаемых библиотек. Здесь, используя материал курса языка Ассемблера кафедры информатики МФТИ, появляется возможность устроить продолжение тематики второй части курса в виде реализации простейшего JIT-компилятора.

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

Как поступить?

Регистрация
Заполни заявку и регистрируйся на курс до 10:00 13-го сентября
Тестирование
Ссылка на тест придет на почту 14-го сентября. Пройди тест до 10:00 16-го сентября
Зачисление
Письмо о зачислении придет на почту каждому студенту 16-го сентября
Начало обучения
Обучение начнется на неделе с 17-го сентября согласно расписанию

Вопросы по обучению

Отборочный тест

 

Требования к поступающим

Поступить могут студенты и аспиранты всех курсов и факультетов МФТИ, знающие какой-либо язык программирования.

Оборудование для обучения

Компьютер, возможность подключиться к беспроводной сети для выхода в сеть Internet.

Нагрузка в неделю

4 ак. часа в неделю без учета времени на выполнение домашнего задания.

Место проведения

МФТИ.

Стоимость обучения

Обучение бесплатно.

Моего вопроса тут нет :(

Другие вопросы можно посмотреть здесь.

Программа

Лекция № 1. Введение в язык С. Краткая история и особенности возникновения языка. Трансляция и построение программы. Принципы промышленного программирования.

Причины, вызвавшие бурное развитие Си и появления его многочисленных потомков. Язык Си и ОС Unix. Ключевая роль Си в программировании, ори-ентированном на производительность и проблемы, проистекающие из этого.

Введение в язык Си на примере программы, решающей квадратное уравнение, вначале на примерах и способах, знакомых начинающим слушателям по школьным и олимпиадным курсам. «Традиционный школьный» подход: одна функция, минимум проверок, максимум неявных условий корректного использования программы. Реализация программы квадратного уравнения на языке Си. Структура и синтаксис простейшей программы на языке Си. Раздел включаемых заголовочных файлов, главная программа. Объявление переменных, типы данных (на примере int и double). Ввод и вывод информации, функции printf и scanf. Работа функции scanf, необходимость передавать ей местоположение (машинный адрес) переменной. Оператор взятия адреса переменной. Арифметические выражения, операторы сложения, вычитания, умножения и деления, оператор присваивания. Функция вычисления квадратного корня. Условный оператор. Возвращаемое значение главной функции программы. Разбор традиционных очевидных проблем, понятных знакомым со школьным и олимпиадным подходом: учет области определения функции квадратного корня, особенности сравнения действительных чисел, учет сводимости квадратного уравнения к линейному. Доработка программы с устранением этих проблем и доведением качества алгоритма (не кода) до «олимпиадного». Функция fabs для вычисления модуля действительного числа.

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

Реализация повторного использования кода в программе квадратного уравнения. Рефакторинг с выделением функции решения квадратного уравнения. Понятие определения функции, ее заголовка и тела. Качество имени функции, стили его образования (pascal case, camel case). Формальные параметры функции квадратного уравнения (коэффициенты), синтаксис их объявления. Понятие и синтаксис вызова функции. Понятие прототипа функции, его необходимость для контроля вызова, синтаксис. Понятие архитектурного рефакторинга, программа как система из взаимодействующих функций, модульный принцип построения программ. Роль архитектуры кода в обеспечении масштабируемости и командной работы. Критический анализ получившейся функции, ее недостатки (печать результатов внутри функции). Анализ и классификация результатов функции (количество корней, их величины). Способы передачи данных из функции. Передача данных через оператор return. Анализ возвращаемого значения в main, оператор switch, его синтаксис. Проблема передачи информации о бесконечном количестве корней. Использование «магических чисел» и именованных констант для обозначения бесконечного количества корней. Синтаксис определения именованной константы. Указатели, передача данных через параметр-указатель. Входные и выходные параметры функции. Опасности работы с указательными параметрами, примеры их неверного использования. Необходимость проверки параметров вызываемой стороной. Макрос assert, его применение для проверки указательных параметров, информативность для программиста при отладке. Понятие контрактного программирования. Принципы контрактного программирования на примере взаимодействия функции квадратного уравнения и функции main (проверка параметров в функции решения уравнения и проверка возвращаемого значения в main. Синтаксис метки default). Рекомендации по количеству строк кода функции. Использование и проектирование функций, метод проектирования «сверху вниз», как минимизирующий проблему деком-позиции. Заключительный обзор стратегий, примененных при рефакторинге: основной – «разделяй и властвуй», его следствия – функциональная декомпозиция (модульный принцип, структурное разделение), контрактное программирование (разделение ответственности). Общая стратегия работы инженера: мечтатель – реалист – критик (У. Дисней).

Смешанное занятие № 1. Принципы промышленного программирования (продолжение). Разбор различных инженерных решений.

Комментирование кода. Задачи комментария в коде, его правильное и неправильное применение. Тривиальные, неясные, устаревшие и неверные комментарии. Использование комментариев только для того, что нельзя непосредственно выразить через текст программы. Примеры: комментарии «о хаках», комментарии-TODO. Блочные комментарии файла и функции. Документирование текста программы. Системы автоматического документирования. Система документирования doxygen. Документирующие комментарии doxygen, основные теги doxygen (file, mainpage, author, version, date, note, warning, par, param, param[out], return, see, code/endcode). Постфиксные документирующие комментарии. Порождение выходных форматов, пример создания документации. Выработка привычки создавать документацию и считать недокументированный исходный текст неполноценным.

Динамическая верификация кода (assert). Препроцессор языка C. Соотношение фаз работы компилятора и препроцессора. Директивы препроцессора. Директива include для стандартных заголовочных файлов и файлов из произвольных директорий. Опасность путаницы включаемых файлов с одинаковыми названиями. Использование одинаковых названий для реализации особенностей компиляции (#include “config.h”). Директива define. Использование директивы для задания констант, ее отличия от конструкции с const. Директива define с параметрами. Границы имени и определения в случае макроопределения с параметрами. Особенности и побочные эффекты в случае макроопределения с параметрами, ее отличие от функций. Классические примеры построения макроопределения с параметрами с демонстрацией побочных эффектов и защитой параметров скобками. Продолжение макроопределения на следующие строки с помощью символа обратной косой черты. Опасности применения этого символа (конструкция \ с пробелом после него, продолжение комментария с помощью \). Типичные ошибки построения макроопределения: лишние точки с запятой, несинтаксические макроопределения, не похожие на вызов функции, отсутствие скобочной защиты параметров и всего макроопределения. Ошибки применения define: использование аргументов с побочным эффектом (инкремент/декремент переменных, вызовы функций, работающих с потоками и т.п.) Временные переменные в определениях, опасность смешения и сокрытия имен разных областей видимости, передача имени типа в качестве параметра, ключевое слово auto в С++ 0x11. Директива undef. «Ситуационные» «локальные» макроопределения. Стратегия применения макроопределений: они хуже всего остального, что есть в языке Си, но лучше прямого копирования текста программы. Построение макроопределения assert. Стандартные макроопределения __FILE__, __LINE__, __DATE__, __TIME__. Макроопределения __PRETTY_FUNCTION__, __FUNC__ и им подобные, константа __func в С++. Макрооператор #. Понятие о макрооператоре ##. Необходимость управления статусом проверок в макроопределении assert, роль макроопределения NDEBUG, его правильное применение. Разбор механизма влияния NDEBUG на assert, условная компиляция. Директивы #ifdef, #ifndef, #if (и синтаксис допустимых в нем конструкций), #else, #elif, #endif. Построение собственного полноценного улучшенного макроопределения ASSERT. Задача о подавлении вывода отладочной информации. Построение макроопределения, блокирующего (регулирующего) вывод отладочной информации в зависимости от компиляции на клиентской или серверной стороне тестирующей системы (DBG_PRINTF и т.п.). Использование этого макроопределения для работы над единой версией текста программы, предназначенного как для автоматического тестирования, так и для взаимодействия с пользователем. Тонкие вещи в макроопределениях: фазы раскрытия макроопределений, раскрытие макроопределений, являющихся параметрами других макроопределений. Пример с автоматическим «закавычиванием» автоматически подставляемого номера строки. Другие директивы препроцессора: error, warning, pragma. Примеры использования этих директив.

Разбор и сдача работ.

Смешанное занятие № 2. Массивы и указатели. Динамическая память.

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

Массивы в языке Си. Использование массивов для хранения серий данных. Объявление и инициализация массива. Ограничения массивов в Си (нумерация, единство типа данных, ограниченный размер). Хранение массивов в оперативной памяти. Адресация к массиву. Имя массива как адрес (указатель) его начального элемента. Типичные ошибки при работе с массивами (выход за границы массива). Отсутствие автоматической проверки выхода за границы массива в Си, причины этого отсутствия. Возможные последствия выхода за границы массива по чтению и по записи. Важность хорошо аннотированных диаграмм для разбора вопросов, связанных с адресацией и массивами. Проверка допустимости индексации с помощью assert. Надежный способ написания двойных неравенств в Си («почти как в математике»). Внешние программные средства отслеживания ошибок адресации во время выполнения программы (GNU valgrind, MicroFocus (NuMega) Bounds Checker). Проблема дублирования размера массива в разных частях программы, решение ее с помощью именованных констант. Оператор sizeof. Вычисление длины массива в его элементах с помощью sizeof, макрос на основе этого подхода, границы его применимости (только при наличии в текущей области видимости полного описания с указанием размера). Особенности работы с массивами с размером, не являющимся константой времени компиляции. Передача массива в функцию, проблемы, с ней связанные (волатильность из-за отсутствия передачи по значению, потеря атрибута размера массива). Решение проблемы волатильности с помощью модификатора const. «Неверная» работа sizeof в случае передачи массива в функцию, решение этой проблемы с помощью явной передачи размера массива. Экономия на передаче длины массива: использование стоп-значений, удобство и опасности такого подхода. «Паскальный» подход (хранение длины массива в его начальном элементе), его ограничения.

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

Разбор и сдача работ.

Смешанное занятие № 3. Многомерные массивы. Строки.

Многомерные массивы, их объявление, инициализация, адресация в них. Проблема передачи многомерного массива в функцию. Вычисление адреса элемента в многомерном массиве. Необходимость передавать раз-меры многомерного массива в функцию. Самостоятельное вычисление смещения относительно начала массива и адреса нужного элемента массива, преимущества и недостатки такого подхода. Функции или макросы для адресации к массивам в случае использования самостоятельно вычисленных смещений. Реализация непрямоугольных массивов с регулярной структурой на примере «треугольного» массива. Реализация многомерных массивов в динамической памяти, доступ к таким массивам.

Массивы указателей. Синтаксис объявления и использования массивов указателей. Трактовка операции индексации в случае массивов указателей. Реализация многомерных массивов через массивы указателей, преимущества и недостатки по сравнению с традиционными многомерными массивами. Решение вопроса о хранении массива с «рваным правым краем» (неодинаковым размером строк). Использование разных блоков для хранения разных строк массива, возможность реаллокации для изменения длин строк. Использование одного блока динамической памяти для хранения данных массива в случае, если изменения длин строк не предполагается. Использование единственного блока динамической памяти для хранения массива указателей и данных. Реаллокация динамических многомерных массивов, реализованных как массивы указателей, необходимость пересчета указателей.

Строки. Реализация строк в языке Си, «смысловая» и «свободная» зоны строки, преимущества и недостатки такого подхода, сравнение с другими реализациями (паскальные строки, структуры с явным хранением длины). Нулевой символ. Понятие пустой строки. Задачи о копировании и сравнении строк, задача о сжатии пробелов в строке «на месте». Концепция «текущего символа». Проблемы «маляра Шлемиля (Шлемиэля)», их характерные проявления и устранение. Возможности строковой библиотеки языка Си. Массивы строк. Реализация массива строк с «рваным правым краем», и его формирование при чтении текста из файла. Задача о сортировке строк, сравнение эффективности ее реализаций для различных реализаций обмена строк. Различные критерии сортировки строк. Функция сортировки строк по различным фиксированным критериям. Обобщение алгоритмов сравнения строк. Указатели на функции. Использование указателей на функции для построения универсальной функции сортировки строк. Библиотечная функция qsort и работа с ней.

Работа с файлами. Функции открытия и закрытия файла. Текстовые файлы, посимвольное и построчное считывание. Состояние «конец файла», константа EOF. Опасность переполнения буфера при чтении. Форма-тированный текстовый ввод и вывод, опасности, с ним связанные. Символы преобразования данных и форматирования. Буферизация, ее виды. Блочные чтение и запись. Бинарные файлы. Отличия в обработке текстовых и бинарных файлов в Windows. Представление данных в бинарных файлах для разных типов данных. Форматы хранения целых чисел. Перемещение по файлу. Буферизация средствами операционных систем, работа с сетевыми файлами и файлами на медленных носителях. Отображение файлов в память, особенности работы с такими файлами, удобства и «подводные камни».

Разбор и сдача работ.


Смешанное занятие № 4. Структуры данных на языке Си

Структуры. Сравнительный анализ структур и массивов, мотивированный выбор для представления данных в виде структур или массивов. Операции доступа к структурам. Построение структур, размер структуры, выравнивание полей. Передача структур в функцию, способы ее ускорения (через указатель) и защиты доступа (через указатель на константные данные). Структура как одно из объектно-ориентрованных понятий в языке Си. Про-блемы и примеры логичного и нелогичного построения структур. Связь структуры с семейством функций для ее «обслуживания». Реализация «методов класса» средствами языка Си.

Понятие абстрактных структур данных. Примеры работы структур данных в различных алгоритмах. Структура данных «стек». Функции для работы со стеком. Проблема допустимости значений и согласованности переменных в структуре данных, связанные с ней опасности и решения. Функции конструирования, уничтожения, верификации и технической распечатки (дампа). Построение функции верификации как предиката. Пример реализации функции дампа. Реализация верифицируемой функции для работы со структурой данных. Понятие о предусловии, постусловии и инварианте алгоритма. Реализация предусловий с помощью функции верификации и дампа. Тактика двойной верификации с предусловием и постусловием для функций, работающих с неконстантным объектом. Понятие ошибочного объекта. Введение объекта в фатальное ошибочное состояние, понятие «яда», его использование для предотвращения работы с уже уничтоженным объектом. Понятие о нефатальной ошибке, способы ее реализации в языке Си (возврат кодов ошибок, создание переменных, хранящих коды ошибок, написание функции-обработчика ошибок, хранение указателя на функцию-обработчик ошибок).

Использование стека. Задача о вычислении выражений. Вычисление выражений, заданных обратной польской записью. Понятие стекового вычислителя (процессора). Реализация структуры стекового вычислите-ля и связанных с ней функций. Реализация арифметических команд для стекового вычислителя. Примеры работы стекового вычислителя. Интерактивный режим работы программы вычисления выражений. Задача о построении таблицы значений функции или ее графика. Пример про-граммы в обратной польской записи (Р-программы) для вычисления значения функции в каждой заданной точке. Пример фрагмента про-граммы на языке Си для запуска стековых вычислений функции для каждого заданного значения ее аргумента. Необходимость использования аргумента функции (абсциссы) в обратной польской записи, проблема его хранения в вычислителе. Понятие регистра вычислителя (процессора), введение регистра абсциссы (АХ) в стековый вычислитель. Функция на языке Си для загрузки значения абсциссы в вычислитель (mov_ax).

Разбор и сдача работ.


Смешанное занятие № 5. Развитие стекового вычислителя

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

Расширение круга задач для стекового вычислителя. Обобщение постановки задачи для построения таблиц значений (графиков) функций с необходимостью единственного исполнения программы и организации перебора значений аргумента в Р-программе. Пример возможной Р-программы для построения таблиц значений (графика) функции. Необходимость команд текстового или графического вывода данных (out), команд условного и безусловного переходов (j*, jmp) для организации цикла в Р-программе. Проблема аргумента в командах переходов. Реализация команд переходов с помощью вручную рассчитанных адресов пе-реходов, недостатки такого подхода. Задача автоматического расчета адресов переходов. Понятие меток как синонимов адресов. Задача сканирования меток и сопоставления им адресов. Методы сопоставления (патчинг кода и многопроходная трансляция). Реализация программы много-проходного (двухпроходного) транслятора в Р-код с использованием нумерованных меток. Именованные метки и их преимущество перед нумерованными. Обсуждение типичных ошибок в реализации команд переходов.

Реализация вызова функций в стековом вычислителе. Сравнение работы команд вызова функции и безусловного перехода. Понятие возврата из функции. Необходимость в регистре, хранящем адрес возврата из функции, или стеке адресов возвратов для поддержки рекурсии. Реализация команд вызова функции с аргументом в виде метки и возврата из функции с помощью отдельного стека для хранения адресов возврата.
Выполнение задач на стековом вычислителе в виде написания самостоятельно разработанных Р-программ (решение квадратных уравнений с разбором всех частных случаев, выдачей количества и величин их корней, вычисления факториала чисел и чисел Фибоначчи итеративным и рекурсивным способами). Расширение количества регистров (добавление регистров bx, cx, dx), системы команд (добавления команды ввода с клавиатуры in).

Разбор и сдача работ.

Смешанное занятие № 6. Структура данных "Список" и ее реализации. Хеш-таблицы.

Структура данных «список». Использование списков. Односвязные и двусвязные списки. Реализация списков с хранением в массиве и с хранени-м в виде отдельных узлов. Сравнительная характеристика этих реализаций. Списки как потоковая структура данных. Неэффективность операции индексации для списков (еще один пример «алгоритма маляра Шлемиля»). Кольцевые списки, их реализация через линейные и наоборот. Задача о проверке зацикленности списка. Хранение длины списка в явном виде, достоинства и недостатки этого подхода. Проблема дублирования (кэширования) данных и необходимость верификации дубликатов. Проверка валидности спи-ска, уровни глубины этой проверки. Разработка юнит-тестов для списков.

Структура данных «хеш-таблица». Задачи, приводящие к хеш-таблицам. Хеш-функции, их примеры (от простейших и бесполезных к реальным) и свойства, качество хеширования. Характерные размеры хеш-таблиц. Использование хеш-таблиц. Юнит-тестирование хеш-таблиц. Качественное сравнение качества хеширования с помощью гистограммы заполнения хеш-таблицы. Использование хеш-таблиц для эффективного поиска перевода слов в словаре. Генерация файла HTML с подстрочным переводом текста. Программа «Подстрочный перевод».

Разбор и сдача работ

Семинар № 1. Структура данных "Список" и ее реализации. Хеш-таблицы.

Разбор и сдача работ

Смешанное занятие № 7. Структура данных «дерево» и алгоритмы синтаксического разбора

Структура данных «дерево». Примеры различного использование деревьев. Деревья поиска. Перечисление узлов дерева, виды обходов дерева. Верификация деревьев и ее ограниченность (или необходимость добавления дублирующихся данных). Дамп деревьев. Задачи, использующие деревья.
Структура арифметических выражений. Инфиксная форма записи выражений, ее соответствие порядку действий и дереву вычислений. Задача о грамматическом разборе выражений. Необходимость задания структуры выражений. Понятие языка и грамматики. Способы построения дерева разбора. Алгоритм распознавания языка методом рекурсивного спуска. Итеративное построение грамматики языка программирования и кода распознавателя, использующего рекурсивный спуск. Решение вопроса о приоритете операторов и задачи о подвыражениях в скобках. Достоинства метода рекурсивного спуска, его проблемы и ограничения. Различные обходы деревьев выражений, восстановление линейной инфиксной записи и генерация различных видов польских записей (префиксной, постфиксной). Транслятор инфиксных выражений в ассемблер стекового процессора. Лексический анализ как предварительная фаза перед синтаксическим, его роль в повышении эффективности трансляции и ее упрощении. Понятие лексемы, ее реализация. Рефакторинг транслятора с применением лексического анализа. Автоматизация по-строения трансляторов. Понятие о промышленных системах построения трансляторов, примеры их использования.

Семинар № 2. Структура данных «дерево» и алгоритмы синтаксического разбора

Разбор и сдача работ

Смешанное занятие № 8. Архитектура nGCC. Front-end, middle-end и back-endFront-end, middle-end и back-end.

Архитектура nGCC. Front-end, middle-end и back-end. Достоинства модульного принципа и общего внутреннего формата. Задача о групповой реализации nGCC для n модельных входных языков высокого уровня и m вычислителей с разными системами команд (в данном случае n = m = k, где k – количество студентов в группе). Разработка общего внутригруппового стандарта промежуточного файла с AST, поддерживающего дополнительные данные (имена переменных и т.п.). Рефакторинг транслятора инфиксных выражений с использованием архитектуры nGCC. Реализация визуализатора AST. Реализация программы для запуска частей транслятора (драйвера). Реализация обратного преобразования (из AST в код модельного высокоуровневого языка).

Работа с переменными в модельных высокоуровневых языках. Модель оперативной памяти высокоуровневого языка. Использование таблиц имен для переменных и других именованных сущностей. Реализация операторов присваивания. Реализация условных операторов, операторов цикла, вызова функции.

Семинар № 3. Архитектура и реализация nGCC.

Разработка и реализация стандарта для обмена данными

Семинар № 4. Архитектура и реализация nGCC.

Разбор и сдача работ

Рубежный контроль № 1. Архитектура и реализация nGCC.

Разбор и сдача работ

Рубежный контроль № 2. Архитектура и реализация nGCC.

Разбор и сдача работ