1.1. Понятие алгоритма и его уточнения. Рекурсивные функции. Машины Тьюринга-Поста. Тезисы Чёрча и Тьюринга. Понятие алгоритмической неразрешимости. Эффективный алгоритм.
1.2. Временная и ёмкостная сложность алгоритма. Классы P и NP.
1.3. Логика 1-го порядка. Выполнимость и общезначимость. Общая схема метода резолюций. Логическое программирование.
1.4. Теорема Поста о полноте систем функций в алгебре логики. Графы, деревья, планарные графы, их свойства.
Гуц А.К. Математическая логика и
теория алгоритмов. - Омск: "Наследие. Диалог-Сибирь", 2003. -
108 с.
Любимский Э. З., Мартынюк В. В., Трифонов Н. П. Программирование.
– М.: Наука,1980. – 608 с.
Кормен Т., Лейзерсон
Ч., Ривест Р. Алгоритмы: построение и анализ. –
М.: МЦНМО, 2000. – 960 с.
Чень Ч.,
Ли Р. Математическая логика и автоматическое доказательство теорем. –
М.: Наука, 1983. – 360 с.
Метакидес
Г., Нероуд А., Принципы логики и логического
программирования. – М.: «Факториал», 1998. – 288 с.
Яблонский
С. В. Введение в дискретную математику. – М.: «Высшая школа», 2003. –
384 с. ISBN
Корухова
Л. С., Шура-Бура М. Р. Введение в алгоритмы: Учебное пособие. – М.: Изд. отдел
ф-та ВМиК МГУ, 1997. – 28 с.
Ахо А., Хопкрофт
Дж., Ульман Дж. Построение и анализ вычислительных
алгоритмов. – М.: Мир, 1979. – 539 с.
Макконелл. Дж. Анализ алгоритмов.
Вводный курс. – М.: Техносфера, 2002. – 304 с.
Алексеев В. Б. Введение в теорию сложностей алгоритмов: Учебное пособие
для студентов. – М: Изд. отд. ф-та ВМиК МГУ,
2002. – 82 с.
Братко И.
Программирование на языке Пролог для искусственного интеллекта. – М.: Мир,
1990. – 559 с.
Братко И.
Алгоритмы искусственного интеллекта на языке PROLOG – М.: Издательский дом «Вильямс», 2004. – 640 с.
Алексеев В. Б.,
Ложкин С. А. Элементы теории графов и схем: Учебное пособие. –
М.: Изд. отд. ф-та ВМиК МГУ. 2000. – 58 с.
2.1. Основы архитектуры операционных систем. Базовые понятия – процесс, ресурс. Физические, виртуальные (логические) ресурсы. Структура ОС. Ядро. Системные вызовы. 2.2. Управление процессами. Определение процесса. Жизненный цикл, состояния процесса. Основные типы процессов: полновесные процессы, легковесные процессы (нити).
2.3. Взаимодействие процессов. Взаимодействие параллельных процессов и их синхронизация. Классификация средств межпроцессного взаимодействия. Разделяемые ресурсы и синхронизация доступа к ним.
2.4. Файловые системы. Файлы, структурная организация файлов. Атрибуты файлов. Типовые программные интерфейсы работы с файлами. Структура файловой системы, подходы в практической реализации.
2.5. Управление внешними устройствами. Общие концепции. Архитектура организации управления внешними устройствами. Драйверы физических и логических устройств, иерархия драйверов. Буферизация обмена. Модельная организация управления внешними устройствами на примере ОС Unix.
Столлингс В. Операционные системы. Внутреннее устройство и
принципы проектирования. 4 изд. – М.: Изд. дом «Вильямс», 2002. – 843 с. Таненбаум Э. Современные операционные системы. – СПб.:
Питер, 2002. – 1040 с.
Стивенс У. UNIX – взаимодействие процессов. – СПб.: Питер,
2002. – 576 с.
Вдовикина Н. В., Казунин А. В., Машечкин И. В., Терехин И. В. Системное программное обеспечение –
взаимодействие процессов. – М.: МГУ, 2002. – 184 с.
Вахалия Ю. Unix изнутри. –
СПб.: Питер, 2003. – 844 с.
Таненбаум Э., Стеен М. ван. Распределенные системы.
Принципы и парадигмы. –СПб.: Питер, 2003. – 887 с.
Соломон Д., Руссинович М. Внутреннее устройство MS Windows 2000. Мастер класс. – СПб.: Питер; М.:
Издательско-торговый дом «Русская Редакция», 2001. – 752 с.
Машечкин И. В.,
Петровский М. И., Скулачев П. Д.,
Терехин А. Н. Системное программное обеспечение: файловые системы ОС Unix и Windows NT. – М.:
Диалог-Москва, 1997. – 47 с.
3.1. Иерархическая организация компьютерных сетей (понятия протокола, иерархии протоколов, сервис и интерфейсы, архитектуры сети), классификация транспортных сред (способы коммутации данных, типы каналов, топология среды), классификация компьютерных сетей (локальные сети, городские сети, региональные сети). Требования, предъявляемые к современным компьютерным сетям (производительность, надежность, безопасность, расширяемость, масштабируемость, управляемость, совместимость).
3.2. Эталонная модель OSI ISO: понятие открытой системы, основные понятия модели, распределение функций сети между уровнями модели (физический, канальный, сетевой, транспортный, сессии, представления, приложений). Модель TCP/IP.
3.3. Теоретические основы передачи данных (данные, сигнал, передача; взаимосвязь пропускной способности канала и ширины его полосы пропускания [теорема Нийквиста-Котельникова, теорема Шеннона]). Основные виды физических сред передачи данных и их свойства (витая пара, коаксиальный кабель, оптоволокно); беспроводные каналы (радио сети, микроволновые сети, сотовые сети, спутниковые сети).
3.4. Основные проблемы, входящие в сферу обеспечения безопасности в сетях ЭВМ (конфиденциальность, целостность, идентификация подлинности), и способы их решения. Основные принципы шифрования. Алгоритмы шифрования с закрытым ключом. Алгоритмы шифрования с открытым ключом. Протоколы установления подлинности. Электронная подпись.
3.5. Принципы
организации и основные протоколы функционирования приложений: DNS, FTP, Электронная почта, SNMP протокол, WWW.
Смелянский
Р.Л. Сети ЭВМ и системы передачи данных (курс лекций) –http://www.lvk.cs.msu.su/cn.html.
Столлингс В. Современные компьютерные сети. 2-е изд. – СПб.:
Питер 2003. – 784 с.
Таненбаум Э. Компьютерные сети. 4-е изд. – СПб.: Питер 2003. –
992 с.
Столлингс В. Компьютерные системы передачи данных. 6-е изд. –
М.: Издательский дом «Вильямс», 2002. – 928 с.
4.1. Языки программирования. Понятие о парадигмах программирования. Процедурные, объектно-ориентированные и функциональные языки программирования.
4.2. Основные принципы объектно-ориентированного программирования. Понятие класса и его реализация в современных языках программирования. Объекты (основные свойства и отличительные признаки).
4.3. Машинно-ориентированные языки, язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации.
4.6. Системы программирования (СП). Состав, схема функционирования классической СП. Этапы жизненного цикла программного продукта. СП в рамках интегрированной среды разработки (ИСР). Типы трансляторов, особенности интерпретаторов и компиляторов. Основные функции редакторов текстов и отладчиков в рамках ИСР. Назначение и функционирование редактора связей и загрузчика. Основные типы библиотек. Основные методы распределения памяти и оптимизации программ.
Пратт Т.,
Зелковиц М. Языки программирования: разработка и
реализация. 4-е изд. – СПб.: Питер, 2002. – 688 с.
Себеста Роберт
У. Основные концепции языков программирования. 5-е изд. – М.: Издательский
дом «Вильямс», 2001. – 671 с.
Пильщиков В. Н.
Программирование на языке Ассемблера IBM PC. – М.: Диалог-МИФИ,
2003. – 288 с.
Гордеев А. В., Молчанов А. Ю. Системное
программное обеспечение. – СПб.: Питер, 2001. – 736 с.
Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков
программирования. – М.: МЗ-Пресс, 2003. – 345 с.
Ахо А., Сети А., Ульман Дж.
Компиляторы: принципы, технологии, инструменты. – М.: Изд. дом «Вильямс»,
2003. – 768 с.
5.1. Параллельная и конвейерная обработка данных. Параллелизм и конвейерность в архитектуре современных высокопроизводительных компьютеров.
5.2. Основные классы современных параллельных вычислительных
систем. Компьютеры с общей памятью, примеры, причины снижения
производительности на реальных программах. Вычислительные кластеры, примеры,
латентность и пропускная способность различных коммуникационных
технологий.
5.3.
Технологии параллельного программирования. Традиционные последовательные языки
и распараллеливающие компиляторы, проблемы.
Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ‑Петербург,
2002. – 608 с.
Королев Л. Н. Архитектура
процессоров электронных вычислительных машин. – М.: «Научный мир», 2005. –
272 с.
Корнеев В. В. Параллельные
вычислительные системы. – М.: Изд-во «Нолидж», 1999.
– 320 с.
6.1. Основные понятия структурной части реляционной модели данных. Тип данных, домен, заголовок отношения, кортеж, тело отношения, переменная отношения.
6.2. Обобщенная архитектура, компоненты и функции системы управления базой данных (СУБД). Структуры внешней памяти реляционных баз данных, способы организации индексов. Алгоритмы буферизации базы данных в основной памяти. Физическая и логическая целостность баз данных. Методы восстановления баз данных после сбоев, восстановление физически и логически целостного состояния базы данных. Авторизация доступа к базе данных, механизм привилегий.
6.5. Язык баз данных SQL. Типы данных. Средства определения, изменения определения и отмены определения доменов, базовых таблиц, представлений и ограничений целостности. Базовые средства выборки и обновления данных. Средства определения триггеров. Привилегии, передача привилегий, аннулирование привилегий.
Кузнецов С. Д. Основы баз данных. Курс лекций. – М.:
Интернет-университет информационных технологий, 2005 – 487 с.
Кузнецов С. Д. Основы современных баз данных. – ЦИТ. –http://www.citforum.ru/database/osbd/contents.shtml
Большакова Е. И., Мальковский М. Г., Пильщиков В. Н.
Искусственный интеллект: методы и алгоритмы эвристического поиска. – М.: Изд.
отд. ф-та ВМиК МГУ, 2002. – 81 с
Люгер Дж. Искусственный интеллект: стратегии и методы
решения сложных проблем. 4‑е издание. – М.:
Изд. дом «Вильямс», 2003. – 864 с.