Что нужно знать к зачету C'

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