А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования, страница 2

Декодирование и дизассемблирование.II. Взаимосвязь языка Си, языка ассемблера и особенностейархитектуры IA321. Отображение операторов разыменования указателя и взятияадреса из языка Си в язык ассемблера. Одномерныемассивы, адресная арифметика. Размещение различныхтипов переменных языка Си в памяти компьютера.2. Реализация арифметических операций над 64-разряднымицелыми в архитектуре IA32. Знаковое и беззнаковоеумножение в языке Си и языке ассемблера.

Обоснованиереализации умножения 64-разрядных знаковых целых чиселна 32-разрядных регистрах.3. Условная передача данных: goto-форма представленияветвлений и циклов. Отображение операторов цикла языкаСи в язык ассемблера. Организация цикла с помощьюинструкции LOOP.4. Различные способы отображения оператора switch в языкассемблера: последовательность if-else, таблица переходов,дерево выбора.5.

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

Инструкции сдвига ивращения. Битовые поля структур.Соглашение о вызове функций cdecl. Распределение памятиво фрейме функции. Организация рекурсии. Реализацияразличных классов памяти языка Си.Возвращаемое значение в соглашении cdecl, возвратструктур из функции в компиляторе gcc. Выравниваниефреймов в стеке. Организация вызова функций стандартнойбиблиотеки языка Си из ассемблерного кода. Функции спеременным числом параметров.Ускорение вызова функций и возврата из них: реализациявызова функций без указателя фрейма, соглашение fastcall.Вызов функции по указателю.

Обратный вызов.Ассемблерные вставки в Си-программах.Формат инструкций архитектуры IA32. Префиксы:модификаторы размера операнда и адреса, префиксыповторения. Реализация операций над строками.Представление чисел с плавающей точкой. Стандарт IEEE754. Операции над числами с плавающей точкой.Округление чисел.Сопроцессор FPU x87. Аппаратный стек регистров.

Числа сплавающей точкой в языке Си: типы, доступ к результатамсравнения чисел, передача в качестве параметров функции,возвращаемое значение.III. Архитектура компьютера101. Организация аппаратного обеспечения компьютера.Логические вентили. Закон Мура. Закон Гроша.2. Устройство оперативной памяти. Статическая идинамическая память. Расслоение памяти.3. Организация ввода/вывода.

Шины, их характеристики,примеры шин: фронтальная шина, PCI, USB, SATA.4. Периферийные устройства: НЖМД. Устройство,организация доступа к хранимой информации, емкость,временные характеристики доступа. Организацияввода/вывода через пространство портов и через память.Прямой доступ к памяти периферийных устройств.Твердотельные диски.5. Тенденции в развитии запоминающих устройств.Локальность в программах. Иерархическая организацияпамяти, кэширование. Кэш-память процессора, способы ееорганизации: кэш прямого отображения, N-канальныйассоциативный кэш.

Метрики производительностикэш-памяти.6. Способы оценки производительности компьютеров ипрограмм. Аппаратные средства измерения времени.Синтетический тест: оценка производительности памятисовременного компьютера.7. Конвейерная обработка команд. Приостановка иопустошение конвейера. Суперскалярная архитектура. CISCи RISC архитектуры.8. Совместимость в программном и аппаратном обеспечении.Обратная совместимость процессоров.Включение/выключение линии A20.9. Многозадачная работа компьютера: требования каппаратуре, работа с памятью в защищенном режиме.Прерывания: программные, аппаратные, исключения.1110.

Сегментная и страничная организация памяти. Логические,линейные и физические адреса памяти.11. Режимы работы современного процессора архитектурыIntel64/AMD64: реальный, защищенный, «длинный», режимсовместимости, режим системного управления. Процессзагрузки компьютера.IV. Система программирования языка Си и ее связь сархитектурой компьютера1. Компиляция и интерпретация. Система программированияязыка Си. Программные инструменты, используемые приразработке Си-программ.2. Схема работы ассемблера. Статическая компоновкапрограммы.

Схема работы компоновщика: разрешениесимволов и перемещение кода. Типы объектных файлов(модулей). Формат ELF.3. Обработка компоновщиком нескольких символов содинаковыми именами: сильные и слабые символы.4. Организация многомодульной программы, рользаголовочных файлов. Автоматизация сборкимногомодульной программы: утилита make.5. Статические библиотеки. Компоновка со статическимибиблиотеками.

Загрузка исполняемого файла в память.V. Рекомендованная литература1. Рэндал Э. Брайант, Дэвид О’Халларон. Компьютерныесистемы: архитектура и программирование (ComputerSystems: A Programmer’s Perspective). БХВ-Петербург, 2005г. — 1186 стр.122. Кип Р. Ирвин. Язык ассемблера для процессоров Intel.4-е издание. Вильямс, 2005. — 912 стр.3.

Э. Таненбаум. Архитектура компьютера. 5-е изд.СПб.:Питер, 2007. — 844 стр.4. Барри Брэй. Микропроцессоры Intel: 8086/8088,80186/80188, 80286, 80386, 80486, Pentium, Pentium ProProcessor, Pentium 4. Архитектура, программирование иинтерфейсы. (The Intel Microprocessors 8086/8088,80186/80188, 80286, 80386, 80486, Pentium, Pentium ProProcessor, Pentium 4. Architecture, Programming,andInterfacing). БХВ-Петербург, 2005 г.

—1328 стр.5. Рудольф Марек. Ассемблер на примерах. Базовый курс.СПб: Наука и Техника, 2005. —231 стр.6. Юров Виктор Иванович. Assembler. 2-е изд. Питер, 2010 —640 стр.7. Юров Виктор Иванович. Assembler: Практикум. 2-е изд.Питер, 2007 год. —400 стр.8. Е.А. Кузьменкова, В.С. Махнычев, В.А. Падарян Семинарыпо курсу «Архитектура ЭВМ и язык ассемблера»(методическое пособие) Часть 1.

— М. Издательский отделфакультета ВМК МГУ, 2012.132.ВАРИАНТЫ ЭКЗАМЕНАЦИОННЫХРАБОТ И КОЛЛОКВИУМОВ2.1. ВАРИАНТ_1. 2012 г. ( “Алгоритмы иалгоритмические языки”)1. Составьте диаграмму машины Тьюринга (МТ), которая в непустомвходном слове над алфавитом А3={0, 1, 2} меняет местами символы впаре подряд стоящих символов (например, входное слово 02121преобразуется в слово 20211). Пары символов отсчитываются от левогокрая (первого символа) слова.

Лента МТ бесконечна только справа. Вначальном состоянии головка МТ обозревает пустую ячейку сразу послевходного слова, в конечном состоянии – пустую ячейку сразу послевыходного слова. Можно предполагать, что слева от входного слова наленте есть одна пустая ячейка. При построении можно использоватьэлементарные машины l, r, L, R, символ (сдвиг головки на одну ячейкувлево/вправо, сдвиг головки на одно слово влево/вправо, запись символа вячейку, соответственно).2.

Дано описание:struct list {int key; struct list *next;};Напишите функциюvoid move_elts_keys (struct list **src,struct list **dst),которая переносит из односвязного списка src в односвязный список dstвсе элементы с чётными ключами, удаляя их при этом из исходногосписка. Перенесенные элементы должны добавляться в начало списка dstв произвольном порядке. Относительный порядок изначальных элементовобоих списков должен остаться неизменным.

Считайте, что заголовочногоэлемента в обоих списках нет, списки могут быть пустыми.3. Пусть int x = 42; int y = -105;Для каждого из 6 отдельных независимых выражений указать егозначение и побочные эффекты (если они есть) либо “ошибка”, есливыражение ошибочно.141) y %= x / 52) x ^ ~y & 653) y <<= (--x || --y)4) (y = 1) && (y = 2)5) x++ + --y6) x += y, y = x - y, x -= y4. Что будет напечатано при выполнении программы:#include <stdio.h>int x = 2, y = 1;int a[3] = { 1, 2 };int f (int x, int **p) {static int c = 2;if (c--)**p += x;else++x;return (*p)++ - a - x;}int main (void) {int x = y, c = 0; int *p;p = &a[x];for (int y = 2; y >= c; --y, ++x)c = f (y, &p);printf ("%d %d %d %d %d\n",a[0], a[1], a[2], x, y);return 0;}5. Перепишите приведенный фрагмент программы с использованиемединственного оператора switch (дополнительные условные операторыиспользовать запрещено):if (i == -1)j = i;15else if (3 >= i && i >= 1)j = 10 - i;elseabort ();6.

С использованием единственного цикла for напишите фрагментпрограммы, который для массива int a[N] формирует в переменнойpairs количество пар соседних элементов, имеющих разную четность.Другие операторы циклов и операторы перехода использовать запрещено.7. Напишите функциюint scalar (void),которая считывает со стандартного потока ввода непустуюпоследовательность целых чисел, заканчивающуюся нулем (нуль невходит в последовательность, количество ненулевых элементов четно,элементы нумеруются с 1). Функция возвращает значение скалярногопроизведениядвухвекторов,составленныхизэлементовпоследовательности: первый вектор – из элементов с нечетныминомерами, второй вектор – из элементов с четными номерами. В решенииможно использовать не более одного оператора цикла.

Запрещаетсяиспользовать операторы перехода.8. Напишите функциюvoid erase (char *s, const char *w),на вход которой дается строка s и слово w. Слово – непустая строка излатинских букв. Строка s представляет собой последовательность слов,разделенных одним пробелом. Перед первым словом и после последнегопробелов нет. Функция должна удалить из строки s все слова, в которыеслово w входит как подстрока.