1. АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ 1. Предмет, объекты и составные части информатики. Физические и математические аспекты информации. 2.
2 1. АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ 1. Предмет, объекты и составные части информатики. Физические и математические аспекты информации. 2. Математические основы информатики. Языки как способы описания объектов и процессов. 3. Алгоритмы. Реализация и эмпирический анализ. 4. Принципы анализа алгоритмов. Рост функций. О - нотация. 5. Простейшие рекурсии. 6. Примеры анализа алгоритмов. Основные программно - эффективные схемы вычислений. 7. Типы и структуры данных. Фундаментальные типы данных. 8. Представление массивов, записей и множеств. 9. Последовательности. Информационные структуры. Линейные списки. 10. Стеки, очереди, деки. 11. Последовательное распределение. Связанное распределение. 12. Списки. Циклические списки. Ортогональное списки. 13. Указатели. Деревья. Представления деревьев. 14. Многосвязные структуры. 15. Динамическое выделение памяти. 16. Алгоритмы внутренней сортировки: сортировка включением, сортировка выбором. 17. Анализ двоичного включения. Анализ алгоритмов сортировки обменом. 18. Алгоритмы внутренней сортировки: шейкерная сортировка, сортировка разделением. 19. Нахождение медианы. Анализ алгоритмов внешней сортировки. Альтернативные методы сортировки. 20. Линейный поиск. Двоичный поиск. Поиск в строке. 21. Алгоритм Кнута-Мориса-Пратта. Алгоритм Боуера-Мура. 22. Алгоритмы обработки строк. 23. Алгоритм Рабина. 24. Рекурсивные алгоритмы. 25. Алгоритмы с возвратом. 26. Фундаментальные методы программирования. 27. Технология разработки программ и их реализация. 28. Оптимизация вычислений. Методы отладки и тестирования программ. 29. Основные принципы модульного программирования. 30. Технологии структурного программирования.
3 2. ТЕОРИЯ БАЗ ДАННЫХ 1. История развития и основные понятия теории баз данных, классификация. 2. Основные компоненты систем баз данных: СУБД, Банки данных. Назначение и классификация. 3. Обзор современных СУБД. Функции, классификация, типовая организация СУБД. Процесс обработки пользовательского запроса. 4. Уровни представления баз данных. Структуры данных: динамические, статические. Логическая, физическая структура данных. Структура хранения данных. 5. Понятие схемы и подсхемы. Понятие модели данных. Класификация. 6. Иерархическая модель данных. 7. Сетевая модель данных. 8. Реляционная модель данных. 9. Основные понятия реляционной БД, свойства, операции. 10. Схема отношения. Виды связей. 11. Язык манипулирования данными для реляционной модели. Реляционная алгебра. Реляционное исчисление. 12. Язык SQL. История, структура, функции, основные возможности, типы данных и операторы. Создание запроса. Пример. 13. Основные методы проектирования. 14. Проектирование инфологической модели базы данных. Системный анализ предметной области. 15. Функциональные зависимости. Декомпозиция отношений. Транзитивные зависимости. 16. Нормализация отношения. Нормальные формы. 17. Проектирование с использованием метода «сущность связь» (ER - диаграмма). 18. Выбор современных СУБД. Одиночные, групповые и корпоративные СУБД. 19. Создание и модификация базы данных. 20. Поиск, сортировка, индексирование БД. Поиск по дереву, хеширование. Индексы. 21. Запрос в СУБД. 22. Создание форм и отчетов в СУБД. 23. Физическая организация баз данных. 24. Хешированные, индексированные файлы. 25. Защита баз данных. Методы защиты информации в СУБД. Аутентификация. Управление доступом. Уровни привилегий. 26. Целостность и сохранность баз данных. Виды угроз СУБД. 27. Управление транзакциями, журнализация, сериализация транзакции. 28. Перспектива развития баз данных и СУБД. 29. Постреляционные БД: дедуктивные, основанные на правилах, темпоральные, исторические. 30. Объектно ориентированные СУБД.
4 3. ТЕОРИЯ ЯЗЫКОВ И АВТОМАТОВ 1. Алфавиты, цепочки и языки. Представление языков. Проблемы формализации. 2. Основные понятия формальных грамматик. Терминальные и нетерминальные символы. Правила вывода. 3. Классификация грамматик: регулярные грамматики, контекстно-свободные грамматики, контекстно-зависимые грамматики, грамматики общего вида, атрибутные грамматики, программные грамматики. 4. Иерархия Хомского формальных языков. 5. Алгоритмические проблемы: проблема пустоты, проблема идентификации, проблема эквивалентности языков. 6. Детерминированные конечные автоматы. Диаграммы Мура (Системы переходов). 7. Эквивалентность конечных автоматов. Теорема Мура. Автоматы Мили и Мура. 8. Алгебраическая структурная теория конечных автоматов. 9. Кодирование внутренних состояний конечного автомата. 10. Последовательная и параллельная декомпозиция конечных автоматов. 11. Классификация автоматов: конечные автоматы, автоматы с магазинной памятью, двухсторонние автоматы, машины Тьюринга, детерминированные и недетерминированные автоматы, автоматы фон Неймана. 12. Построение недетерминированного конечного автомата по регулярному выражению. 13. Построение детерминированного конечного автомата по недетерминированному автомату. 14. Нечеткие грамматики, автоматы и языки. 15. Распознавание символов. Программирование лексического анализа. 16. Конструктор лексических анализаторов LEX. 17. Нисходящий синтаксический анализ. LL(1) - грамматики. Рекурсивный спуск. 18. Нисходящий синтаксический анализ. Преобразования КС-грамматик. Удаление левой рекурсии. Левая факторизация. Достоинства и недостатки LL(1) анализа. 19. Восходящий синтаксический анализ. Разбор снизу-вверх типа сдвиг-свертка. LR(1)-анализаторы. 20. Восходящий синтаксический анализ. Создание и использование таблицы синтаксического анализа 21. Особенности LR - анализа. Варианты LR- анализаторов. 22. Формализация семантики языков программирования. Языки спецификации. 23. Не контекстно - свободные характеристики языка. Организация таблиц символов. Таблицы идентификаторов. 24. Таблицы расстановки. Таблицы расстановки со списками. Функции расстановки. 25. Таблицы на деревьях. Реализация блочной структуры. 26. Организация памяти. Статическая и динамическая память. 27. Адреса времени компиляции. Куча. Генерация кода. 28. Создание промежуточного кода. Трехадресный код. Р - код. Байт - код. 29. Создание машинного кода. Выбор инструкции. Распределение регистров. 30. Оптимизация объектного кода. В экзаменационные билеты дополнительно будут включены задачи по указанным дисциплинам
5 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ 1. Альфред В. Ахо. Структуры данных и алгоритмы.: Пер. с англ./ Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. М.: Изд. Дом «Вильямс», с. 2. Дүйсембаев А.Ә. Информатика. Деректер құрылымы, сұрыптау және іздеу. Оқу құралы. Астана, 2005ж 3. Вирт Н. Алгоритмы + структуры данных = программы. М., Мир, Ахо, А, Ульман, Дж, Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция. М.:Мир, с. 5. Буза М.К., Дубков В.П., Рябый В.В. Структуры данных и методы трансляции. Ч.2. Лабораторный практикум по математическому обеспечению ЭВМ. [Учебное пособие для вузов] Мн.: Вышэйшая школа, Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. М., Радио и связь, Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. 7-е изд. М.: «Вильямс», с. (Глава стр) 8. А.Ә.Шәріпбай. Тілдер мен автоматтар теориясы:оқулық/ Астана: Л.Н.Гумилев атындағы ЕҰУ, б. 9. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. М.: Издательский дом «Вильямс», С Богаченко Н.Ф., Файзуллин Р.Т. Автоматтар, грамматикалар, алгоритмдер. Оқу құралы. Омбы. Диалог-Сибирь с.
АЛГОРИТМДЕР ЖӘНЕ ДЕРЕКТЕР ҚҰРЫЛЫМЫ 1. Информатика пәні объектілері және оны құрайтын бөлімдері. Ақпараттың физикалық және математикалық аспектілері.1. АЛГОРИТМДЕР ЖӘНЕ ДЕРЕКТЕР ҚҰРЫЛЫМЫ 1. Информатика пәні объектілері және оны құрайтын бөлімдері. Ақпараттың физикалық және математикалық аспектілері. 2. Информатиканың математикалық негіздері. Тілдер