билеты по информатике

Билеты по информатике.

Билет 1

1. Понятие рекурсии. Достоинства и недостатки рекурсивных алгоритмов. Нахождение всех подмножеств заданного множества.

2. Решение комбинаторных задач при помощи динамического программирования

3. Задача

Билет 2

1. Переборные алгоритмы основанные на рекурсии. . Получение всех перестановок элементов множества. Получение всех упорядоченных подмножеств заданного множества.

2. Основные принципы, положенные в основу динамического программирования. Применение динамического программирования вместо перебора.

3. Задача

Билет 3

1. Основные типы переборных задач – задача коммивояжера, задача о составлении трубы. Поиск в глубину и в ширину. Отсечение при переборе.

2. Решение комбинаторных задач при помощи динамического программирования

3. Задача

Билет 4

1. Графы основные понятия и определения. Представление графов в памяти компьютера. Алгоритм нахождения компонент графа.

2. Применение переборных алгоритмов для решения игровых задач. Alpha Beta отсечение.

3. Задача

Билет 5

1. Применение переборных алгоритмов для решения игровых задач.

2. Понятие паросочетания. Алгоритм нахождения оптимального паросочетания.

3. Задача

Билет 6

1. Взвешенные графы. Алгоритм нахождения кратчайшего пути в графе.

2. Эйлеров путь и Эйлеров цикл в графе, алгоритм его нахождения. Теорема Эйлера о необходимом и достаточном условии существования Эйлерова цикла в графе.

3. Задача

Билет 7

1. Алгоритм нахождения минимального остовного дерева во взвешенном графе. Эйлеров путь в графе, алгоритм его нахождения.

2. Алгоритм нахождения оптимальной расстановки рабочих на конвейере. (задача об оптимальном назначении).

3. Задача

Билет 8

1. Алгоритм нахождения оптимальной расстановки рабочих (задача об оптимальном назначении).

2. Понятие рекурсии. Достоинства и недостатки рекурсивных алгоритмов. Замена рекурсии итерацией.

3. Задача.

Билет 9

1. Применение динамического программирования для решения игровых задач.

2. Переборные алгоритмы основанные на рекурсии. Нахождение всех подмножеств заданного множества. Получение всех перестановок элементов множества. Получение всех упорядоченных подмножеств заданного множества.

3. Задача

Билет 10

1. Понятие очереди сообщений. Организация взаимодействия объектов через очередь сообщений.

2. Решение комбинаторных задач при помощи динамического программирования

3. Задача

Билет 11

1. Алгоритм нахождения минимального остовного дерева во взвешенном графе. Эйлеров путь в графе, алгоритм его нахождения.

2. Решение комбинаторных задач при помощи динамического программирования.

3. Задача

Билет 12

1. Графы основные понятия и определения. Представление графов в памяти компьютера. Алгоритм нахождения компонент графа.

2. Основные принципы, положенные в основу динамического программирования. Применение динамического программирования вместо перебора.

3. Задача

Билет 13

1. Эйлеров путь и Эйлеров цикл в графе, алгоритм его нахождения.

Теорема Эйлера о необходимом и достаточном условии существования Эйлерова цикла в графе.

2. Взвешенные графы. Алгоритм нахождения кратчайшего пути в графе.

3. Задача

Билет 14

1. Определение потока в графе. Теорема о величине максимального потока. Алгоритм нахождения максимального потока.

2. Понятие паросочетания. Алгоритм нахождения оптимального паросочетания.

3. Задача

Билет 15

1. Переборные алгоритмы основанные на рекурсии. Нахождение всех подмножеств заданного множества. Получение всех перестановок элементов множества. Получение всех упорядоченных подмножеств заданного множества.

2. Алгоритм нахождения оптимальной расстановки рабочих (задача об оптимальном назначении).

3. Задача.

Билет 16

1. Основные принципы, положенные в основу динамического программирования. Применение динамического программирования вместо перебора.

2. Определение потока в графе. Теорема о величине максимального потока. Алгоритм нахождения максимального потока.

3. Задача

Билет 17

1. Основные типы переборных задач – задача коммивояжера, задача о составлении трубы. Поиск в глубину и в ширину. Отсечение при переборе.

2. Решение комбинаторных задач при помощи динамического программирования.

3. Задача.

Билет 18

1. Алгоритм нахождения минимального остовного дерева во взвешенном графе. Эйлеров путь в графе, алгоритм его нахождения.

2. Понятие паросочетания. Алгоритм нахождения оптимального паросочетания.

3. Задача

Билет 19

1. Определение потока в графе. Теорема о величине максимального потока. Алгоритм нахождения максимального потока.

2. Алгоритм нахождения оптимальной расстановки рабочих на конвейере. (задача об оптимальном назначении).

3. Задача

Билет 20

1. Применение переборных алгоритмов для решения игровых задач. Alpha Beta отсечение.

2. Основные принципы, положенные в основу динамического программирования. Применение динамического программирования вместо перебора.

3. Задача