Вопросы по информатике




Скачать 47.44 Kb.
Дата14.07.2016
Размер47.44 Kb.
Вопросы по информатике

  1. Задача сортировки массива. Пример алгоритма, решающего эту задачу за O(N log(N)). Доказательство факта, что любой алгоритм сортировки в среднем тратит время не меньшее θ(N log(N)). Алгоритм Quick Sort, его сложность и оптимизации.

  2. Алгоритм Heap Sort: описание лежащих в основе структур данных, доказательство оценки сложности.

  3. Структура данных хеш-таблица: определение, интерфейс, сложность выполнения основных операций. Способы разрешения конфликтов. Пример реализации функции добавления нового элемента для открытой адресации.

  4. Структура данных красно-чёрное дерево. Что такое сбалансированность дерева и как её можно достигнуть. Сбалансированность красно-чёрных деревьев. Оценки времени поиска, добавления и удаления элементов. Пример реализации добавления элементов, включая вращения.

  5. Жадные алгоритмы. Пример жадного алгоритма с оценкой качества получаемого решения.

  6. Динамическое программирование. Общий метод и пример применения с оценкой сложности.

  7. Дискретная и непрерывная задачи о рюкзаке.

  8. Задача о наибольшей общей подпоследовательности (Longest Common Subsequence, LCS). Расстояние Левенштейна.

  9. Алгоритмы обхода графа в глубину и в ширину.

  10. Система непересекающихся множеств. Алгоритм Крускала.

  11. Алгоритмы Флойда и Дейкстры для поиска кратчайших путей в графе.

  12. Кучи. Бинарная, биномиальная, фибоначчиева. Алгоритмы для работы с кучей в STL. Очередь с приоритетами и реализация в STL.

  13. Поиск подстроки в тексте. Поиск общей подстроки максимальной длины двух текстов. Суффиксное дерево.

  14. Инфиксная и постфиксная формы записи выражений. Перевод из одной системы в другую.

  15. Средства объектно-ориентированного программирования в C++.

  16. Шаблоны в C++.

  17. Основные классы-контейнеры и алгоритмы стандартной библиотеки STL.

  18. Представление целых чисел(знаковых/беззнаковых) в памяти компьютера. Представление вещественных чисел.

  19. Логическая архитектура компьютера: фон Неймана, гарвардская.

  20. Средства распараллеливания/ускорения работы процессора: конвейер, кэш, суперскалярная архитектура.

  21. Задачи операционной системы: понятие вычислительной системы, управление физическими/логическими ресурсами, планирование. Типы операционных систем: пакетные, разделения времени, реального времени, сетевые.

  22. Понятие процесса, виды процессов.

  23. Базы данных. Классификация БД по модели данных. Реляционная теория. Атрибуты, кортежи, домены, отношения. Первичные и внешние ключи.

  24. Физическое устройство БД. Страницы данных. Индексы.

  25. Конкурентный доступ. Согласованность и изолированность. Виды изоляции.

  26. Средства объектно-ориентированного программирования в языке Java.

  27. Виртуальная машина Java. Управление памятью. Передача примитивных типов в функции. Передача ссылочных типов в функции. Проблема изменения ссылки внутри подпрограммы. Статические инициализаторы. Удаление неиспользуемых объектов и метод finalize. Проблема деструкторов для сложно устроенных объектов. Сборка мусора.

  28. Коллекции и массивы в Java.

  29. Моделирование при помощи UML. Статическое представление модели. Диаграммы классов. Виды отношений: ассоциация, зависимость, абстракция, реализация и другие. Ограничения. Экземпляры классов. Варианты использования (прецеденты). Выделение классов. Метод Аббота, карточки Класс-Контракт-Коллеги (CRC), диаграммы устойчивости.

  30. Паттерны проектирования. Структурные, создания и паттерны поведения. Примеры паттернов. Строитель. Посетитель. Шаблон метода. Фасад. Мост. Метрики качества объектно-ориентированной структуры. Эвристики GRASP.

Литература

  1. Винокуров Н.А. Ворожцов А.В. Практика и теория программирования. В 2-х книгах. – М.: Физматкнига, 2008.

  2. Эккель Б., Философия С++. Введение в стандартный С++. – СПб:Питер, 2004.

  3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. – М.: «Вильямс», 2006.

  4. Керниган Б.У., Ритчи Д.М. Язык программирования С, 2-е издание. – М.: «Вильямс», 2006.

  5. Мейерс С. Эффективное использование STL. – СПб.: Питер, 2002.

  6. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: «Вильямс», 2000.

  7. Бентли Дж. Жемчужины программирования, 2-е изд. – СПб.: Питер, 2002.

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

  9. Солтер Н.А., Клепер С.Д. С++ для профессионалов. М.: «Вильямс», 2006.

  10. Шилдт Г. Полный справочник по С++, 4-е изд. – М.: «Вильямс», 2006

  11. Седжвик Р. Фундаментальные алгоритмы на C++, 3-е изд. – СПб: ООО «ДиаСофт», 2002.

  12. Фаулер М. UML. Основы. Третье издание. (любой издатель)

  13. Ларман К. Применение UML 2.0 и шаблонов проектирования. Введение в объектно-ориентированный анализ, проектирование и итеративную разработку. М.: «Вильямс», 2009.-736 с.

  14. Гамма Э., Хелм Р., Джонсон Р. Приемы объектно-ориентированного проектирования. Паттерны проектирования, любое издание.

  15. Pressman R. Software Engineering: A Practitioner's Approach, 6th Ed. - McGraw Hill, 2005

  16. Орлов С.А. Технологии разработки программного обеспечения. Разработка сложных программных систем. Для студентов и преподавателей высших учебных заведений. – СПб: Питер, 2004. – 527 с.

  17. Басс Л., Клементс П., Кацман Р. Архитектура программного обеспечения на практике. 2-е изд. – СПб.: Питер, 2006, 576 с.

  18. Мейер Б. Объектно-ориентированное конструирование программных систем. – М.: Русская Редакция, 2005.

  19. Liskov B., Guttag J. Program Development in Java: Abstraction, Specification and Object-Oriented Design. - Addison-Wesley, 2000.

  20. Эккель Б. Философия Java. – СПб.: Питер, 2009.

  21. Робачевский А.М. Операционная система UNIX – СПб.:БХВ-Петербург, 2010.

  22. Карпов В.Е., Коньков К.А. Операционные системы – М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2005.

  23. Таненбаум Э.С. Современные Операционные системы, 2-е изд. – СПб.:Питер, 2002.

  24. Стивенс У.С. Разработка сетевых приложений. – СПб.:Питер, 2002.

  25. Стивенс У.С., Раго С.А. UNIX. Профессиональное программирование (Professional Programming UNIX environment). – СПб.: Символ-Плюс, 2007

  26. Дейт К. Дж Введение в системы баз данных. 8-е изд. М.: «Вильямс», 2005

  27. Сошников Д.В. Функциональное программирование — М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2010.

  28. Mark C. Paulk, Bill Curtis, Mary Beth Chrissis, Charles V. Weber. Capability Maturity Model (SM) for Software, Version 1.1., Software Engineering Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213 http://www.sei.cmu.edu/cmm/.

  29. Соммервилл И.. Инженерия программного обеспечения, 6-е издание. : Издательский дом «Вильямс», 2002.- 624 с. : ил.

  30. К.Вигерс. Разработка требований к программному обеспечению./ Пер. с англ. Издательско-торговый дом «Русская Редакция», 2004. —576с.: ил.


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница