Вопросы к экзамену (1100145)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Вопросы к экзамену по курсу

Алгоритмы и структуры данных

(1994-95г.)

1. Понятие алгоритма, его основные свойства.

2. Понятия Вычислительного процесса и исполнителя. Их

взаимосвязь с понятием алгоритма.

3. Алгоритм и вычислительный процесс как конструктивные

объекты и их основные свойства.

4. Понятия потенциальной осуществимости алгоритма и

потенциальной разрешимости проблем (на примерах).

Представление о сложности алгоритма.

5. Представление о данных и действиях в алгоритме. Понятие

применимости алгоритма.

6. Основные понятия теории алгоритмов: область

применимости, вычислимая функция, перечислимое множество,

разрешимое множество. Понятие конструктивного объекта.

7. Понятие алгоритмической системы и ее основные

параметры.

8. Машины Тьюринга, как уточнение понятия алгоритма:

определение, примеры, композиция МТ, сложность алгоритмов.

Тезис Тьюринга.

9. Нормальные алгоритмы Маркова, как уточнение понятия

алгоритма: определение, примеры, композиция НАМ, сложность

алгоритмов. Тезис Маркова.

10. Построение алгоритмов из алгоритмов: основные правила

композиции и их свойства; формулировка основной теоремы.

11. Существование универсальных вычислителей: на примере

универсальной машины Тьюринга.

12. Понятие Алгоритмической проблемы и представление об

алгоритмической разрешимости; доказательство существования

алгоритмически неразрешимых проблем.

13. Взаимосвязь алгоритмически равносильных Алгоритмических

систем; зависимость разрешимости алгоритмической проблемы от

алгоритмической системы.

14. Представление о языке программирования. Понятие

синтаксиса и способы его описания. Представление о

семантике.

15. Концепция данных в языке Pascal.

16. Синтаксис и семантика Выражения в языке Pascal.

17. Оператор присваивания и составной оператор.

18. Операторы выбора.

19. Операторы цикла.

20. Тип INTEGER: основные свойства и операции.

21. Тип REAL: основные свойства и операции.

22. Тип BOOLEAN: основные свойства и операции.

23. Тип CHAR: основные свойства и операции.

24. Перечислимый и ограниченный типы данных: основные

свойства и операции.

25. Регулярный типы данных: основные свойства и операции.

26. Тип множество и комбинированный типы данных: основные

свойства и операции.

27. Понятие процедуры и ее назначение в языках

программирования. Синтаксис и семантика определения

процедуры в языке Pascal.

28. Понятие процедуры и ее назначение в языках

программирования. Синтаксис и семантика оператора

процедуры, способы передачи параметров в процедуру в языке

Pascal.

29. Понятие функции и ее назначение в языках

программирования. Синтаксис и семантика определения

функции в языке Pascal. Понятие побочного эффекта.

30. Понятие функции и ее назначение в языках

программирования. Синтаксис и семантика оператора функции.

Способы передачи параметров функции.

31. Представление о рекурсии, применение рекурсии в

определении процедуры. Применение рекурсии в алгоритмах с

возвратом (на примере задачи о ходе коня).

32. Представление о рекурсии. Косвенная рекурсия.

Взаимосвязь итерации и рекурсии.

33. Тип файл. Операции над файлами. Операции ввода/вывода

в Pascal’е.

34. Концепция имени в языке программирования Pascal.

35. Основные этапы разработки программ: на примере

разработки программы поиска пути в лабиринте (задача об

Ариадне и Тезее).

36. Ссылочный тип данных. Основные свойства и операции.

37. Абстрактные Структуры Данных: дерево, бинарное

дерево, сбалансированное дерево, граф -

определение, способы представления, операции над ними.

38. Абстрактные Структуры Данных : Строка, Стек,

Очередь, Таблица - определения, способы представления,

операции.

39. Понятие Структуры Данных Хранения (СДХ).

Проблема отображения АСД на СДХ. Представление АСД-строка,

АСД-дерево, АСД-таблица в векторной памяти.

40. Проблема отображение АСД на СДХ. Представление АСД-строка

и АСД-стек с помощью списковых структур.

41. Проблема отображения АСД на СДХ. Представление АСД-граф с

помощью списковых структур.

42. Последовательные неупорядоченные таблицы

(векторное представление) и операции над ними. Реализация и

оценка сложности операций вставки и поиска.

43. Последовательные неупорядоченные таблицы

(списковое представление) и операции над ними. Реализация

и оценка сложности операций вставки и поиска.

44. Таблицы как деревья сравнений (векторное

представление) и операции над ними. Реализация и оценка

сложности операций вставки и поиска.

45. Таблицы как деревья сравнений (списковое

представление) и операции над ними. Оценка сложности

операций вставки и поиска. Теорема Хиббарда о средней

длине поиска. Случай сбалансированного дерева:

понятия балансировки и разбалансировки деревьев.

46. Таблицы как деревья сравнений (списковое

представление) и операции над ними. Реализация и оценка

сложности операций вставки и поиска. Представление о

балансировке и разбалансировке деревьев.

47. Таблицы с прямым доступом. Применение

функции перемешивания при работе с таблицами. Методы

разрешения коллизий - функции повторного перемешивания.

Требования к функции перемешивания. Оценка числа

сравнений при поиске и включении.

48. Таблицы с прямым доступом. Применение

функции перемешивания при работе с таблицами. Методы

разрешения коллизий - метод сцепления. Требования

к функции перемешивания. Оценка числа сравнений при

поиске и включении.

49. Сортировка - постановка задачи. Характеристики

методов сортировки. Сортировки линейным выбором, линейным

выбором с обменом: метод, реализация и оценка сложности.

50. Сортировки обменом - стандартный обмен, просеивание:

метод, реализация и оценка сложности.

51. Сортировки обменом - сортировка Шелла: метод,

реализация и оценка сложности.

52. Использование структуры в сортировке: турнирная

не минимальная по памяти сортировка - метод, реализация и

оценка сложности.

53. Использование структуры в сортировке: турнирная,

минимальная по памяти сортировка Флойда

- метод, реализация и оценка сложности.

54. [вырезано цензурой]

55. Быстрая сортировка: метод, реализация и оценка

сложности.

56. Сортировка методом больших степеней: метод и

оценка сложности. Сортировка методом слияния: метод,

реализация и оценка сложности.

ЛИТЕРАТУРА:

1. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова “Введение в Паскаль” М.Наука,1988.

2. П.Холл “Вычислительные структуры. Введение в нечисленное программирование” Мир,1978.

3. Г.Лорин “Сортировки и системы сортировки” Мир,1978.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов вопросов/заданий