Что нужно знать к зачету C'
- Сложность алгоритмов.
- Логические операции: AND, OR, NOT, XOR - таблицы значений.
- Битовые операции.
- Проверка на простоту, разложение на множители.
- НОД и НОК: алгоритм Евклида.
- Признак Паскаля.
- Линейный поиск.
- Квадратичные сортировки (выбор, вставки, пузырек).
- Сортировка подсчетом.
- Функции (и процедуры). Виды параметров. Передача массивов.
- Рекурсия: НОД, Ханойские башни, перебор с возвратом.
- Стек. Стек функций.
- Теория графов. Определения графа, основных элементов графов. Типы графов. Деревья: число вершин и висячих вершин.
- Представления графов в памяти: с помощью матрицы смежности и списка ребер. Оценка сложности для простейших операций.
- DFS и BFS. Алгоритм. Реализация для простейших представлений в памяти. Оценка сложности. Восстановление пути.
- Динамика на одномерных и двумерных массивах: количество способов, есть ли способ, лучший способ.
- Динамическое программирование с 2 параметрами - длина и последний элемент.
- НОП.
- Бинарный поиск. Инвариант, время работы.
- Быстрая сортировка Хоара. Время работы в среднем/худшем случае.
- Длинная арифметика. Сложение, вычитание, умножение на короткое/длинное число.