Формальные языки и грамматики.
Естественные и формальные языки. Цепочки символов и операции над ними. Формальное определение языка. Способы задания языков. Синтаксис и семантика языка. Грамматика. Формальное определение грамматики. Форма Бэкуса-Наура. Запись правил грамматики с использованием метасимволов и в графическом виде. Классификация языков и грамматик. Четыре типа грамматик по Хомскому.
Литература
1. Советов Б.Я., Яковлев С.А. Моделирование систем. –М.: Высш.школа.2005.-343с.
2. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика. -М.: Академия, 2008. - 848 с
3. Острейковский В.А. Информатика: Учеб. для вузов. - М.: Высшая школа, 2009. –512 с.
4. Семененко М.Г. Введение в математическое моделирование.-М.,2002.-112с.
5. Васин А. А., Краснощеков П. С., Морозов В. В.. Исследование операций - М.: Академия, 2008. - 464 с.
6. Соболева Т.С. Дискретная математика - М.: Академия, 2006. - 256 с.
7. Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения. -М. Высшая.школа 2000. –266 с.
8. Вержбицкий В.М. Численные методы. Математический анализ. -М.Высшая.школа 2001.–382 с.
9. Новиков Ф.А. Дискретная математика для программистов - СПб.: Питер, 2008. - 384 с.
10. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. -М.: Лаборатория базовых знаний. 2001. - 288 с.
11. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. – М.:ФИЗМАТЛИТ.2002.-240 с.
12. Яблонский С.В. Введение в дискретную математику. -М.: Высшая школа. 2001. –384 с.
13. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. - М.: Вузовская книга, 2001. –280с.
14. Хохлов Г.И. Основы теории информации - М.: Академия, 2008. - 176 с.
15. Матросов В.Л., Горелик В.А. и др.Теоретические основы информатики - М.: Академия, 2009. - 352 с.
16. Баранов А.Н. Введение в прикладную лингвистику. Учебное пособие. -М.: Эдиториал УРСС. 2001. - 360 с.
17. Осовский С. Нейронные сети для обработки информации. –М.: Финансы и статистика. 2002. –344 с.
18. Ясницкий Л.Н. Введение в искусственный интеллект. Уч.пособие для студ.ВУЗов. –М.: «Академия». 2005. – 176 с.
19. Волков И.К., Загоруйко Е.А. Исследование операций. М.: Издательство МГТУ. 2002. – 436 с.
20. Жидков Е.Н. Вычислительная математика: учебное пособие. - М.: Академия, 2010. - 208 с.
21. Игошин В.И. Математическая логика и теория алгоритмов - М.: Академия, 2008. - 448 с.
22. Павловский Ю.Н. и др. Имитационное моделирование - М.: Академия, 2008. - 236 с.
23. Душин В.К. Теоретические основы информационных процессов и систем: учебник - М.: Дашков и К., 2006. - 348 с
24. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. –М.: Высшая школа. 2001. –208 с.
25. Письменный Д.Т. Конспект лекций по теории вероятностей, математической статистике и случайным процессам - М.: Айрис-пресс, 2007. - 288 с
26. Крупский В.Н. Теория алгоритмов - М.: Академия, 2009. - 208 с.
27. Тарасевич Ю.Ю. Математическое и компьютерное моделирование: Учебное пособие - М.: Едиториал, 2003. - 144с.
28. Гриненко Е.В., Емельянова М.В., Пушечкин Н.П. Численные методы (учебно-методическое пособие).- Славянск-на-Кубани. ч.1 ООО «Берегиня». 2003. –64 с. ч.2 Изд. СГПИ. 2005. –56 с.
III. Копьютерные сети, интернет и мультимедиа-технологии, архитектура ЭВМ, теоретические основы информатики
Представление информации в ЭВМ. Арифметические и логические основы ЭВМ.
Логические основы ЭВМ – логические операции и булевы функции. Построение таблиц истинности базовых логических операций. Логические элементы ЭВМ – конъюнкторы, дизъюнкторы, инверторы, сумматоры. Представление информации в ЭВМ – графическая, мультимедиа и числовая информация. Кодовая таблица ЭВМ. Представление чисел – целые и действительные числа. Прямой, обратный и дополнительный код. Представление чисел с плавающей запятой.
Системы счисления. Правила перевода чисел из одной системы в другую. Выполнение арифметических операций в различных системах счисления.
Позиционные и непозиционные системы счисления. Причины использования 2-ой, 8-ой, и 16-ой системы счисления в ЭВМ. Правила перевода чисел из одной системы в другую. Упрощенные правила перевода для 2, 8, 16-ых систем. Выполнение арифметических операций в различных системах счисления.
Основные задачи теории кодирования. Кодирование и декодирование. Теоремы Шеннона. Методы восстановления информации в канале с шумом. Коды Хэмминга. Понятие о компьютерной криптографии. Сложность алгоритма. Классы сложности алгоритмов. NP задачи.
Основные задачи теории кодирования: однозначное кодирование-декодирование, оптимальные коды и методы сжатия информации, самовосстанавливающиеся коды, криптографические задачи. Процессы кодирования и декодирования. Избыточность кодирования. Понятие о теоремах Шеннона (о существовании оптимального кода, о помехоустойчивых кодах). Восстановление потерянной информации в канале с шумом. Бит четности. Коды Хэмминга. Расстояние в коде Хэмминга. Понятие о компьютерной криптографии. Понятие сложности алгоритма. Оценка сложности алгоритма (асимптотические оценки О(n)). Классы сложности алгоритмов: полиномиальные и неполиномиальные алгоритмы. Не полиномиальные алгоритмы (NP задачи). Понятие о теореме полноты класса NP задач. Пример NP задачи (задача коммивояжера, задача разложения на простые сомножители и т.д.).
Информация и ее виды. Дискретная и непрерывная информация. Измерение информации. Вероятностный и объемный подход к измерению информации. Формулы Шеннона и Хартли. Сжатие информации. Основные алгоритмы сжатия информации.
Понятие информации и ее виды. Дискретная и непрерывная информация. Измерение информации. Вероятностный и объемный подход к измерению информации. Формулы Шеннона и Хартли вычисления объема информации. Сжатие информации. Основные алгоритмы сжатия информации (методы Шеннона-Фано, Хафмена и Лепел-Зива).