Реферат: Структура программы. Часть Структуры данных. 24. Классификация структур данных. Операции над структурами данных. 25. Простые структуры данных. Числовые типы. Машинное представление

Вопросы вступительного экзамена в магистратуру

по специальности

«6М011100 – Информатика»


Часть 1. Алгоритмы.

Алгоритмы. Основные свойства алгоритмов.

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

3. Диаграммы Тьюринга. Примеры машин Тьюринга.

4. Варианты машин Тьюринга.

5. Машины Тьюринга. Неразрешимость проблемы останова.

6. Машина Маркова. Тезис Маркова. Примеры машин Маркова.

7. Композиция машин Маркова.

8. Машины Маркова. Неразрешимость свойства самоприменимости


Часть 2. Алгоритмические языки.

9. Синтаксис и семантика языка. Синтаксические диаграммы. Примеры.

10. Типы и числа.

11. Простые типы данных.

12. Перечислимые и ограниченные типы данных.

13. Регулярный, комбинированный и множественный типы данных.

14. Файловый тип данных.

15. Операторы: составной, выбирающий, цикла, присоединения.

16. Массивы. Одномерные и многомерные массивы.

17. Записи. Организация записей.

18. Рекуррентные соотношения и итерации.

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

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

21. Модули. Стандартные модули.

22. Ссылочный тип данных.

23. Структура программы.


Часть 3. Структуры данных.

24. Классификация структур данных. Операции над структурами данных.

25. Простые структуры данных. Числовые типы. Машинное представление.

Вещественные типы. Битовые типы. Логический тип. Символьный тип.

Указатели.

26. Статические структуры данных. Векторы. Массивы. Множества.

Записи. Основные операции.

27. Полустатические структуры данных. Стеки. Очереди. Строки.

Основные операции.

28. Динамические структуры данных. Связное представление данных.

Линейные списки

29. Нелинейные структуры. Графы. Машинное представление. Деревья.

Бинарные деревья. Основные операции: обход, поиск. Основные

алгоритмы на графах.


Часть 4. Модели данных и передача данных в сети.

30. Модели данных. Иерархическая, сетевая, реляционная, постреляционная,

многомерная, объектно-ориентированная модели данных.

31. Современные системы управления базами данных.

32. Реляционная алгебра.

33. Информационные системы в сетях.

34. Архитектура файл-сервер. Архитектура клиент-сервер.

36. Проектирование баз данных. Проблемы проектирования.

37. Метод нормальных форм.

38. Обеспечение целостности.

39. Администрирование. Защита данных.

40. Сети. Классификация.

41. Виды сетей.

42. Архитектура сети.


Часть 5. Формальные системы и языки

43. Формальные грамматики и их классификация.

44. Распознаватели и их классификация.

45. Исчисление высказываний.

46. Исчисление предикатов.

47. Теория моделей и теория доказательств.

48. Языки первого и высшего порядков.


Литература:

Минский М. Вычисления и автоматы. -М.: МИР, 1971.

Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. -М.: Наука, 1988.

Йенсен К., Вирт Н.. Паскаль. Руководство для пользователя. -М.: Финансы и статистика, 1989.

Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. Т.2. Сортировка и поиск.

Холл. Вычислительные структуры. Введение в нечисленное программирование. –М.:МИР, 1978.

Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. –М.:Наука, 1980.

Вирт Н. Алгоритмы + структура данных = программа. –М.:Мир, 1985. -406с.

Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных. –Санкт-Петербург: КОРОНА принт, 2004. -736с.

Кейт К.Дж.. Введение в системы баз данных. – М., 2002. - 1070 с.

Марко Кэнту. Delphi 7. – М., Санкт-Петербург: ПИТЕР, 2005. - 1100 с.

Агафонов В.Н. Типы и абстракция данных в языках программирования.- М.: Мир, 1982.

Ахо А., Холкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгортимов. - М.:Мир, 1979. - 536с.

Баррон Д. Введение в языки программирования. - М.:Мир, 1980. - 190с.

Брукс Ф.П. Как проектируются и создаются программные комплексы. М.: Наука, 1979.

Виноградов М.М. Модели данных и отображения моделей данных : алгебраический подход // Теория и приложения систем баз данных.- М.: ЦЭМИ АП СССР, 1984. с.26-40.

Вирт Н. Систематическое программирование. Введение - М.:Мир, 1977.- 184с.

Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1989.- 360с.

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.:Мир, 1981. - 368с.

Данные в языках программирования. Под ред. В.Н.Агафонова. - М.:Мир, 1982. - 328с.

Дрибас В.П. Реляционные модели баз данных.- Минск : Изд.БГУ, 1982.- 192с.

Зайцев В.Ф. Кодирование информации в ЕС ЭВМ. - М.: Радио и связь, 1986.- 102с.

Замулин А.В. Типы данных в языках программирования и базах данных.-Новосибирск : Наука, 1987.- 150с.

Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. - М.:Мир, 1976. - 735с.

Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.:Мир, 1976. - 797с.

Костин Е.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах.- М.: Высш. школа, 1987.- 242с.

Леман Д., Смит М. Типы данных // Данные в языках программирования.- М.: Мир, 1982. с.196-213.

Ленгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ.- М.: Мир, 1989. 568с.

Макаровский Б.Н. Информационные системы и структуры данных. Учебное пособие вузов.- М.: Статистика, 1980.- 190с.

Морс С.П., Альберт Д.Д. Архитектура микропроцессора 80286.- М.: Радио и связь, 1990.- 300с.

Нагао М., Катаяма Т., Уэмура. Структуры и базы данных.- М.: Мир, 1984.

Флорес И. Структуры и управление данными.- М.: Радио и связь, 1982.- 118с.

Фостер Дж. Обработка списков. - М.:Мир, 1974. - 72с.

Малибекова М.С., Базикова К.М. Программирование на SQL. –Караганды, 2008. – 264с.