- •Билет 1. Концепция языка Си, его достоинства и недостатки
- •Билет 2. Представление целых чисел в эвм. Основные типы данных в Си и операции над ними. Особенности операций над вещественными числами.
- •Билет 3. Основные управляющие конструкции в Си. Понятие инварианта цикла и его применение.
- •Билет 4. Характеристика алгоритмов, программ, языков программирования и соответствия между ними.
- •Билет 5. Массивы и указатели в языке Си. Их представление, связь между ними.
- •Билет 6. Метод барьера и различные варианты его применения.
- •Билет 7. Процедуры и функции в Си. Формальные и фактические. Входные и выходные параметры, локальные и глобальные переменные.
- •Билет 8. Массивы и указатели в Си, связь между ними. Передача массивов и указателей как параметров процедур.
- •Билет 9. Представление строк и символов в Си. Операции над ними.
- •Билет 10. Понятие эффективности алгоритма, различные способы ее измерения.
- •Билет 11. Понятие рекурсии. Виды и характеристики.
- •Билет 12. Алгоритмы перебора с возвратом. Способы сокращения перебора.
- •Способы сокращения перебора
- •Билет 13. Алгоритмы оптимального поиска. Метод ветвей и границ.
- •Билет 14. Сортировка массивов. Простые методы.
- •Билет 15. Сортировка массивов. Усовершенствованные методы.
- •Билет 16. Алгоритм поиска подстроки в строке.
- •3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или
- •Билет 17. Алгоритм получения случайных чисел. Правильный выбор параметров линейного конгруэнтного генератора.
Билет 10. Понятие эффективности алгоритма, различные способы ее измерения.
Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область — быстрые алгоритмы. Необходимо анализировать конструируемый алгоритм. Такой анализ должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временнОй сложности процесса.
Эффективность алгоритма - заключается в том, что каждый шаг алгоритма должен быть выполнен точно и за конечное время. Так вот, эффективность алгоритма - это функция зависящая от размера входных данных. Чем больше входных данных, тем дольше будет выполняться алгоритм.
Основной способ оценки эффективности алгоритма - подсчет его операций. Быстродействие алгоритма связано с количеством выполняемых операций, поэтому оценить его эффективность можно путем их простого подсчета. Давая оценку быстродействия алгоритма, следует рассмотреть поведение вычислительного процесса в среднем и, отдельно, в экстремальных для него условиях, то есть - в худшем случае.
Для каждой конкретной задачи составляют некоторое число, которое называют ее размером. Время, которое тратит алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма О(n).Оно считается по тому, сколько операций произвела программа за все время работы.
Билет 11. Понятие рекурсии. Виды и характеристики.
Реку́рсия — процесс повторения чего-либо самоподобным способом. Например, вложенные отражения, производимые двумя точно параллельными друг другу зеркалами, являются одной из форм бесконечной рекурсии. Данный термин имеет более специальные значения в различных областях знаний — от лингвистики до логики.
Наиболее общее применение рекурсия находит в математике и информатике. Здесь она является методом определения функций, при котором определяемая функция применена в теле своего же собственного определения. При этом бесконечный набор случаев (значений функции) описывается с помощью конечного выражения, которое для некоторых случаев может ссылаться на другие случаи, если при этом не возникает циклов или бесконечной цепи ссылок. Фактически это способ определения множества объектов через самого себя с использованием ранее заданных частных определений.
Использующее рекурсию определение называется индуктивным. Одним из примеров подобного определения является аксиоматическое построение множества натуральных чисел.
Функции
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Любую рекурсивную функцию можно заменить циклом и стеком.
Пример Факториал с использованием рекурсии
int fact(int n)
{
int res = 1;
for (int i = 1; i <= n; ++i)
{
res *= i;
}
return res;
}