Вопросы по специальности 05.13.11 для собеседования

1. Математические основы программирования.

  1. Понятие алгоритма, понятие об алгоритмической неразрешимости.
  2. Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач. Примеры NP-полных задач.
  3. Автоматы. Эксперименты с автоматами.
  4. Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка.  
  5. Формальные языки и способы их описания. Классификация формальных грамматик.
  6. Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения.
  7. Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Системы шифрования с открытым ключом (RSA). Цифровая подпись.

 

 2. Вычислительные машины, системы и сети.

  1. Многопроцессорные и многомашинные комплексы. Вычислительные кластеры.
  2. Методы и средства передачи данных в ИВС, протоколы передачи данных.
  3. Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI).
  4. Сеть Internet, доменная организация, семейство протоколов TCP/IP.

 

 3. Языки и системы программирования. Технологий разработки программного обеспечения.

  1. Распределенное программирование. Процессы и их синхронизация. Объектно-ориентированное распределенное программирование. Параллельное программирование над общей памятью.
  2. Основы построения трансляторов. Структура оптимизирующего транслятора. Промежуточные представления программы. Уровни промежуточного представления.
  3. Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции.
  4. Оптимизация программ при их компиляции. Оптимизация базовых блоков, чистка циклов. Анализ графов потока управления и потока данных.
  5. Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации. Модули, взаимодействие между модулями, иерархические структуры программ.
  6. Модули, взаимодействие между модулями, иерархические структуры программ.
  7. Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов. Системы генерации тестов.
  8. Методы спецификации программ. Схемное, структурное, визуальное программирование. Разработка пользовательского интерфейса, мультимедийные среды интерфейсного взаимодействия.

 

 4. Операционные системы.

  1. Виды процессов и управления ими в современных ОС. Представление процессов, их контексты, иерархии порождения, состояния и взаимодействие. Многозадачный (многопрограммный) режим работы. Команды управления процессами. Средства взаимодействия процессов.
  2. Параллельные процессы, схемы порождения и управления. Организация взаимодействия между параллельными и асинхронными процессами: обмен сообщениями, организация почтовых ящиков.
  3. Операционные средства управления процессами при их реализации на параллельных и распределенных вычислительных системах и сетях: стандарты и программные средства PVM, MPI, OpenMP, POSIX .
  4. Одноуровневые и многоуровневые дисциплины циклического обслуживания процессов на центральном процессоре, выбор кванта.
  5. Оптимизация многозадачной работы компьютеров. Операционные системы Windows, Unix, Linux. Особенности организации, предоставляемые услуги пользовательского взаимодействия.
  6. Операционные средства управления сетями. Эталонная модель взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками данных в сети. Сетевые ОС.
  7. Удаленный доступ к ресурсам сети. Организация электронной почты, телеконференций. Протоколы передачи файлов FTP и HTTP, язык разметки гипертекста HTML, разработка WEB-страниц, WWW-серверы.

 

 5. Методы хранения данных и доступа к ним. Организация баз данных и знаний.

  1. Теоретические основы реляционной модели данных (РДМ). Реляционная алгебра, реляционное исчисление. Функциональные зависимости и нормализация отношений.
  2. CASE-средства и их использование при проектировании базы данных (БД).
  3. Организация и проектирование физического уровня БД. Методы индексирования.
  4. Стандарты языков SQL. Интерактивный, встроенный, динамический SQL.
  5. Информационно-поисковые системы. Классификация. Методы реализации и ускорения поиска.
  6. Методы представления знаний: процедурные представления, логические представления, семантические сети, фреймы, системы продукций. Интегрированные методы представления знаний. Языки представления знаний. Базы знаний.
  7. Экспертные системы (ЭС). Архитектура ЭС. Механизмы вывода, подсистемы объяснения, общения, приобретения знаний ЭС. Жизненный цикл экспертной системы.

 

 6. Защита данных и программных систем.

  1. Аппаратные и программные методы защиты данных и программ. Защита данных и программ с помощью шифрования.
  2. Защита от несанкционированного доступа в OC Windows NT. Система безопасности и разграничения доступа к ресурсам в Windows NT.
  3. Защита от несанкционированного копирования. Методы простановки некопируемых меток, настройка устанавливаемой программы на конкретный компьютер, настройка на конфигурацию оборудования.
  4. Защита от разрушающих программных воздействий. Вредоносные программы и их классификация. Загрузочные и файловые вирусы, программы-закладки. Методы обнаружения и удаления вирусов, восстановления программного обеспечения.
  5. Защита информации в вычислительных сетях Novell Netware, Windows NT и др.: методы и средства защиты.

 

 Список литература:

1.      Ахо, Сети Р., Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. М., 2001.

2.      Введение в криптографию / Под ред. В.В. Ященко. СПб.: МЦНМО, 2001.

3.      Дейт К.Дж. Введение в системы баз данных. М.: Вильямс, 1999.

4.      Дейтел Г. Введение в операционные системы. М.: Мир, 1987.

5.      Кнут Д. Искусство программирования. Т. 1 – 3. М., СПб., Киев: ИД «Вильямс», 2000.

6.      Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002.

7.      Компьютерные сети. Учебный курс Microsoft Corporation, 1997.

8.      Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. М.: МЦНМО, 2000.

9.      Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991.

10. Матфик С. Механизмы защиты в сетях ЭВМ. М.: Мир, 1993.

11. Мельников В.В. Защита информации в компьютерных системах. М.: Финансы и статистика, 1997.

12. Яблонский С.В. Введение в дискретную математику. М.: Наука, 2001.

13. Керниган Б., Пайк П. UNIX – универсальная среда программирования. М.: Финансы и статистика, 1992.

14. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.

15. Королёв Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1980.

16. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000. СПб.: Питер, 2001.