ВОПРОСЫ ЭКЗАМЕН АЛГОРИТМЫ

Перечень вопросов, вынесенных на экзамен по курсу
«Алгоритмы и анализ сложности»

Раздел 1
Основы архитектуры вычислительных средств

1.1 Классическая архитектура и её параллельные версии.
1.2 Архитектура потока данных.
1.3 Редукционная машина и непроцедурные стили программирования.
1.4 Архитектура самоопределяемых данных


Раздел 2
Основы теории алгоритмов

2.1 Машина Поста и машина Тьюринга.
2.2 Основные положения теории автоматов.
2.3 Рекурсивные функции.
2.4 Основные положения теории формальных грамматик



Раздел 3
Основные алгоритмы обработки информации

3.1 Алгоритмы последовательного и бинарного поиска;
3.2 Алгоритмы сортировки сложности O(N*N) и O(N*logN);
3.3 Хеш-функции и методы исключения коллизий;
3.4 Деревья бинарного поиска; поиск в глубину и поиск в ширину;
3.5 Алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда);
3.6 Алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала);


Раздел 4
Основы анализа алгоритмов

4.1 Асимптотический анализ верхней и средней оценок сложности алгоритмов; 4.2 сравнение наилучших, средних и наихудших оценок;
4.3 O-, o-,
·- и
·-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов;
4.4 Накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов
Раздел 5
Стратегии алгоритмов

5.1 Полный перебор; метод «разделяй и властвуй»;
5.2 «Жадные» алгоритмы; бэктрекинг (перебор с возвратами);
5.3 Метод ветвей и границ; эвристический поиск;
5.4 Поиск по образцу, алгоритмы обработки строк;
5.5 Генетические алгоритмы;


Раздел 6
Распределённые алгоритмы

6.1 Модель параллельного выполнения программы с общей памятью и модель с разделённой памятью.
6.2 Модель потока данных.
6.3 Модель самоопределяемых данных;
6.4 Основы программирования в технологии CUDA;





Билеты к экзамену по курсу «Алгоритмы и анализ сложности»

БИЛЕТ № 1

1 Классическая архитектура и её параллельные версии
2 Алгоритмы последовательного и бинарного поиска
3 Полный перебор; метод «разделяй и властвуй»;

БИЛЕТ № 2

1 Архитектура потока данных.
2 Алгоритмы сортировки сложности O(N*N) и O(N*logN);
3«Жадные» алгоритмы; бэктрекинг (перебор с возвратами);

БИЛЕТ № 3

1 Редукционная машина и непроцедурные стили программирования
2 Хеш-функции и методы исключения коллизий
3 Метод ветвей и границ; эвристический поиск;

БИЛЕТ № 4

1 Редукционная машина и непроцедурные стили программирования
2 Деревья бинарного поиска; поиск в глубину и поиск в ширину
3 Поиск по образцу, алгоритмы обработки строк

БИЛЕТ № 5

1 Архитектура самоопределяемых данных
2 Алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда
3 Генетические алгоритмы;


БИЛЕТ № 6

1 Машина Поста и машина Тьюринга
2 Алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала);
3 Модель параллельного выполнения программы с общей памятью и модель с 2 разделённой памятью.


БИЛЕТ № 7

1 Основные положения теории автоматов
2 Асимптотический анализ верхней и средней оценок сложности алгоритмов
3 Модель потока данных.


БИЛЕТ № 8

1 Рекурсивные функции.
2 сравнение наилучших, средних и наихудших оценок;
3 Модель самоопределяемых данных;



БИЛЕТ № 9

1 Основные положения теории формальных грамматик
2 O-, o-,
·- и
·-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов;
3 Основы программирования в технологии CUDA
БИЛЕТ № 10

1 Классическая архитектура и её параллельные версии
2 Накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов
3 Модель самоопределяемых данных


БИЛЕТ № 11

1 Архитектура потока данных
2 Алгоритмы последовательного и бинарного поиска
3 Основы программирования в технологии CUDA;


БИЛЕТ № 12

1 Редукционная машина и непроцедурные стили программирования
2 Алгоритмы сортировки сложности O(N*N) и O(N*logN);
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 Основы программирования в технологии CUDA


БИЛЕТ №19

1 Рекурсивные функции
2 O-, o-,
·- и
·-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов;
3 Генетические алгоритмы;


БИЛЕТ № 20

1 Основные положения теории формальных грамматик
2 Накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов
3 Модель потока данных







Заголовок 1 Заголовок 2 Заголовок 315

Приложенные файлы

  • doc 7790358
    Размер файла: 53 kB Загрузок: 0

Добавить комментарий