Программирование на языке высокого уровня

Год

Системы счисления (с.с.)

Алгоритмы перевода действительных чисел из одной b-с.с. в другую:

- из произвольной b-c.с. в 10-с.с.;

- из 10-с.с. в произвольную b-с.с.;

- из произвольной b1-с.с в произвольную b2-с.с.;

- между кратными с.с.

Модели машинной арифметики с конечной разрядностью

2.1. Беззнаковые целые числа конечной разрядности, примеры их использования в Си. Формулы для min и max.

2.2. Знаковые целые числа конечной разрядности, примеры их использования в Си. Дополнительный код. Знаковый разряд. Формулы для мин и макс цеого числа со знаком.

2.3. Представление вещественных чисел с фиксированной точкой.

2.4. Представление вещественных чисел с плавающей точкой. Нормализованное представление вещественного числа. Мантисса и порядок, их вид. Разрядность мантиссы и порядка.

Вопросы по С

3.1. Базовые типы языка С. Представление значений базовых типов в памяти. Диапазоны значений базовых типов.

3.2. Базовые типы языка С. Операции над значениями базовых типов. Перенос и переполнение. Преобразования между базовыми типами языка С.

3.3. Массивы. Многомерные массивы. Индексация многомерных массивов. Распределение памяти в многомерных массивах. Связь понятия указателя и массива. Инициализаторы

массивов.

3.4. Понятие времени жизни и области видимости переменных. Глобальные и локальные переменные. Модификаторы области видимости и времени жизни.

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

3.6. Понятие типа/преобразование типов.

3.7. Синтаксис описания структур. Обращение к полям структур для объектов и к полям по указателю на объект типа структура. Инициализатор структур.

3.8. Функции. Описание функций. Возвращаемые значения. Передаваемые параметры. Порядок передачи параметров через стек.

3.9. Функции с переменным числом параметров. Получение переменных передаваемых после фиксированных параметров.

3.10. Функции printf, sprintf, fprintf, scanf, sscanf, fscanf. Форматная строка (целые знаковые и беззнаковые в десятичном и шестнадцатеричном виде, числа с плавающей запятой, буквы, строки). Возвращаемое значение.

3.11. Строки в языке С. Понятие длины строки. Инициализаторы строк. Функции работы со строками: определение длины строки, копирование строк, слияние строк.

3.12. Основные стандартные функции языка Си для работы с файлами. Текстовые и бинарные файлы.

3.13. Понятие указателя в С. Операции над указателями.

3.14. Препроцессор языка С. Включаемые файлы. Макроопределения и условная компиляция.

3.15. Выделение памяти под локальные переменные (класс памяти auto в языке С). Стек вызовов.

4. Управление памятью:

4.1. Классы памяти переменных в языке C. Cрок жизни переменных для каждого из классов памяти.

4.2. Динамическая память. Функции работы с ДП.

Элементы теорий вероятностей, информации и кодирования.

Метод Хаффмана построения кода типа А-{0,1}* с минимальной избыточностью. Реализация проекта по созданию архиватора.

Классические модели динамической памяти.

7.1. Список; как универсальная модель линейно упорядоченных структур данных последовательного доступа; разновидности списков: одно/двусвязные; циклические; иерархические

7.2. Операции над списками, алгоритмы поиска и включения для списков, анализ их эффективности, способы реализации списков (статика, динамика), реализация алгоритма топологической сортировки на иерархических списках.

7.3. Стек, преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.

7.4. Очередь, реализация обхода дерева методом в ширину.

7.5. Основные операции со стеком и очередью, способы реализации на различных базовых представлениях.

Абстрактные структуры данных.

8.1. Граф. Модели представления в ЭВМ: матрицы смежности и инцидентности, динамическая структура со списками дуг, табличное представление.

8.2. Дерево двоичного поиска, создание орфографического словаря по заданному набору слов. Алгоритмы включения и удаления, сравнение их эффективности с известными алгоритмами на массивах.

8.3. Сбалансированные (АВЛ) деревья. Алгоритм вставки элемента в АВЛ-дерево на уровне схемы.

8.4. Левое\правое скобочное представление деревьев.

8.5. Б-деревья. Алгоритмы поиска и включения элемента в Б-дерево.

Ватолин Д., Ратушпяк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.