30. Быстрое умножение Карацубы.
3.2. Список вопросов к зачетам и экзаменам
Вопросы для подготовки к экзамену (1 семестр)
1. Описать принцип измерения информации, понятие информационной неопределенности, единицы измерения информации в модели Шеннона.
2. Дать определение энтропии. Записать и объяснить формулы Хартли и Шеннона. Описать основные свойства энтропии.
3. Дать определение избыточности алфавита. Источники избыточности. Формула расчета избыточности. Положительные и отрицательные последствия избыточности.
4. Описать процесс кодирования сообщений, понятие кода, кодового слова. Дать определение равномерного и неравномерного кода, разрядности кода и средней длины кодового слова. Опишите понятия количества и объема информации в сообщении, соотношение между ними.
5. Как рассчитать минимальную разрядность равномерного кода для передачи сообщения в заданном алфавите?
6. В чем заключается избыточность кода и каковы ее источники? Как рассчитать среднюю длины кодового слова? Какова связь энтропии и минимальной средней длины кодового слова. Что такое коэффициент оптимальности кода, как он рассчитывается?
7. Какие коды называются неравномерными? В чем заключается принцип префиксности, каково его значение? Опишите алгоритмы построения оптимальных кодов (Шеннона- Фано и Хаффмана).
8. Какие коды называются помехоустойчивыми? Как используется избыточность для обеспечения помехоустойчивости? Понятие обнаруживающей способности кода. Пример помехоустойчивого кода.
9. Понятия криптографического кодирования: шифр, ключ шифра, шифрование. Основные принципы построения шифров – замена и перестановка. Шифр Цезаря, Шифр Вижинера.
10. Кодирование и сжатие информации. Сжатие без восстановления исходного сообщения. Принципы сжатия числовых массивов и последовательностей.
11. Общее представление о процессе передачи информации по каналам связи. Понятие канала связи. Техническая и информационная скорость передачи, единицы измерения. Понятие пропускной способности канала связи.
12. Представление числа в позиционных системах счисления. Алгоритмы преобразования чисел в разные системы счисления
13. Представление чисел в ЭВМ в разрядных сетках с фиксированной и плавающей запятой.
14. Записать диапазоны представимых чисел. Объяснить понятие машинного нуля и переполнения разрядной сетки.
15. Как выполняются операции над числами, представленными в разрядных сетках с фиксированной и плавающей запятой.
16. Понятие машинных кодов. представление чисел в прямом, обратном и дополнительном кодах.
17. Арифметические операции над числами, представленными в машинных кодах.
2.4 Вопросы для подготовки к зачету (2 семестр)
1. Объясните понятие множества и подмножества. Какое множество называется универсумом? Почему не используется понятие «множество всех множеств»?
2. Способы задания множеств: перечисление элементов, порождающая, разрешающая процедура – объяснить суть этих способов, привести примеры.
3. Объясните понятия «функция» и «операция». Какие функции называются взаимно-однозначными соответствиями? Приведите пример взаимно-однозначных соответствий.
4. Дайте определение основных свойств операций (ассоциативность, дистрибутивность, коммутативность). Приведите примеры операций, обладающих и не обладающих этими свойствами.
5. Дайте определение основных операций на множествах – запишите их в терминах теории множеств и проиллюстрируйте на кругах Эйлера.
6. Приведите примеры выражения одних теоретико-множественных операций через другие. Докажите, что разность и симметрическую разность нельзя выразить через объединение и пересечение.
7. Дайте определение равномощных множеств и объясните понятие мощности множеств. Как определяется мощность конечного множества? Докажите теорему о мощности множества всех подмножеств конечного множества.
8. Какие множества называются «счетными»? Докажите, множество всех целых чисел является счетным. Докажите, что множество всех пар целых чисел является счетным. Докажите, что множество всех рациональных чисел является счетным.
9. Докажите, что множество всех действительных чисел не является счетным (теореме Кантора). Как называется мощность множества всех действительных чисел?
10. В чем заключаются основные правила сложения и умножения в комбинаторике? Приведите примеры применения этих правил.
11. Дать определения размещений и сочетаний. Записать и объяснить формулы расчета числа этих объектов.
12. Дать определения размещения с повторениями и перестановок с повторениями. Записать и объяснить формулы расчета их числа.
13. Дать определение сочетания с повторениями. Записать и объяснить формулу расчета числа этих объектов.
14. Дать определение разбиений. Записать и объяснить формулу расчета числа этих объектов.
15. Доказать свойства сочетаний (симметричность, сумма всех сочетаний для заданного n-элементного множества, основное рекуррентное соотношение, бином Ньютона, треугольник Паскаля), перестановок с повторениями (полиномиальное разложение) .
16. Доказать формулу суммы всех сочетаний для заданного n-элементного множества.
17. Доказать основное рекуррентное соотношение для сочетаний.
18. Доказать формулу бинома Ньютона.
19. Обосновать алгоритм вычисления сочетаний на основе треугольника Паскаля .
20. Доказать формулу полиномиального разложения
21. Записать и объяснить формулу включений и исключений (для произвольного n). Пояснить на кругах Эйлера
22. Описать тип задач, которые могут решаться с использованием метода включений и исключений. Привести пример такой задачи.
23. Описать интерпретацию сочетаний с помощью траекторий на декартовой плоскости.
24. Дать определение рекуррентного уравнения в общем виде, линейного рекуррентного уравнения и привести примеры. Что называется общим и частным решением рекуррентного уравнения? Для чего нужны начальные условия и сколько их нужно?
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.