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

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. Динамическая память. Функции работы с ДП.

 

Алгоритмы: перестановки, поиск, сортировки

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

5.2. Основные методы программирования: повторение, ветвление и рекурсия. Рекурсивный переход, правила выхода, ветвящаяся и хвостовая рекурсия. Примеры использования для каждого метода.

5.3. Перестановки набора. Подсчет числа перестановок.

- Инверсии. Число инверсий, как мера сложности упорядочения набора; таблицы инверсий; алгоритм восстановления перестановки по таблице инверсий;

- Таблица инверсий как число в особой с.с.; итерационный алгоритм генерации всех таблиц инверсий.

- Алгоритмы перебора перестановок: рекурсивный, итерационный с лексикографическим упорядочением (Дейкстры).

5.4. Постановка задач поиска (П) и сортировки (С) записей в произвольном наборе данных. Внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора).

- Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности.

- Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура, Рабина-Карпа, оценки сложности.

- Методы сортировки массива:

метод простых вставок;

метод бинарных вставок;

метод простого выбора;

метод "пузырька";

шейкер-сортировка;

метод Шелла;

быстрая сортировка Хоара;

пирамидальная сортировка;

сортировка слиянием;

оценки сложности.

5.5. Cортировка файлов простым двухпутевым слиянием

 

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

 

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