Реферат: Вопросы к теоретическому зачету группы с (sis ­­– 2003)

Вопросы к теоретическому зачету группы С (SIS ­­– 2003).


Графы: представление в компьютере, связность, обходы в ширину и глубину.

Графы: алгоритм Дейкстры поиска кратчайшего пути между вершиной и всеми остальными.

Графы: алгоритм Флойда поиска кратчайшего пути между всеми парами вершин.

Графы: алгоритм Форда-Беллмана поиска кратчайшего пути между вершиной и всеми остальными.

Графы: Циклы отрицательного веса в графе, существование.

Графы: Каркасы минимального веса: алгоритмы Прима и Краскала.

Длинная арифметика: хранение длинных чисел, ввод, вывод.

Длинная арифметика: сложение, вычитание, умножение.

Длинная арифметика: деление.

Геометрия: представление элементарных объектов (точка, прямая, отрезок). Уравнения прямой: общее, в отрезках, kx+b.

Геометрия: пересечение двух прямых, проверка на параллельность и совпадение.

Геометрия: пересечение двух отрезков, возможные случаи.

Геометрия: выпуклая оболочка множества точек, алгоритм Джарвиса построения выпуклой оболочки.

Комбинаторика: перестановки, получение перестановки по номеру, получение номера по перестановке, генерация следующей, количество.

Комбинаторика: сочетания, получение сочетания по номеру, получение номера по сочетанию, генерация следующего, количество.

Комбинаторика: сочетания с повторениями, получение сочетания по номеру, получение номера по сочетанию, генерация следующего, количество.

Комбинаторика: правильные скобочные последовательности, получение по номеру, получение номера по ней, генерация следующей, подсчет количества.

Структуры данных: стек, очередь, heap. Примеры использования – heap sort,

Модификация алгоритма Дейкстры с помощью структуры данных heap.

Динамическое программирование: примеры, классические задачи. Рекурсивная формула – сведение к динамическому программированию.


Вопросы к теоретическому зачету группы С (SIS ­­– 2003).


Графы: представление в компьютере, связность, обходы в ширину и глубину.

Графы: алгоритм Дейкстры поиска кратчайшего пути между вершиной и всеми остальными.

Графы: алгоритм Флойда поиска кратчайшего пути между всеми парами вершин.

Графы: алгоритм Форда-Беллмана поиска кратчайшего пути между вершиной и всеми остальными.

Графы: Циклы отрицательного веса в графе, существование.

Графы: Каркасы минимального веса: алгоритмы Прима и Краскала.

Длинная арифметика: хранение длинных чисел, ввод, вывод.

Длинная арифметика: сложение, вычитание, умножение.

Длинная арифметика: деление.

Геометрия: представление элементарных объектов (точка, прямая, отрезок). Уравнения прямой: общее, в отрезках, kx+b.

Геометрия: пересечение двух прямых, проверка на параллельность и совпадение.

Геометрия: пересечение двух отрезков, возможные случаи.

Геометрия: выпуклая оболочка множества точек, алгоритм Джарвиса построения выпуклой оболочки.

Комбинаторика: перестановки, получение перестановки по номеру, получение номера по перестановке, генерация следующей, количество.

Комбинаторика: сочетания, получение сочетания по номеру, получение номера по сочетанию, генерация следующего, количество.

Комбинаторика: сочетания с повторениями, получение сочетания по номеру, получение номера по сочетанию, генерация следующего, количество.

Комбинаторика: правильные скобочные последовательности, получение по номеру, получение номера по ней, генерация следующей, подсчет количества.

Структуры данных: стек, очередь, heap. Примеры использования – heap sort,

Модификация алгоритма Дейкстры с помощью структуры данных heap.

Динамическое программирование: примеры, классические задачи. Рекурсивная формула – сведение к динамическому программированию.