ВОПРОСЫ К ВСТУПИТЕЛЬНОМУ ЭКЗАМЕНУ
1.Задачи поиска: исчерпывающий поиск, быстрый поиск, использование деревьев в
задачах поиска.................................................................................................................................. |
5 |
1.1. Задачи поиска................................................................................................................................ |
5 |
1.2. Исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое |
|
программирование........................................................................................................................ |
5 |
1.3. Быстрый поиск: бинарный и последовательный поиски в массивах, хеширование................. |
7 |
1.4. Использование деревьев в задачах поиска: бинарные и случайные бинарные, |
|
оптимальные и сбалансированные деревья поиска................................................................... |
7 |
2.Уровни моделей и этапы проектирования баз данных Инфологическое
моделирование............................................................................................................................... |
10 |
|
1.1. |
Базы данных (БД) и системы управления базой данных (СУБД).......................................... |
10 |
1.2. |
Выбор системы управления базами данных............................................................................ |
12 |
1.3. |
Жизненный цикл базы данных................................................................................................... |
12 |
1.4. |
Уровни моделей и этапы проектирования БД......................................................................... |
13 |
1.5. |
Инфологическое моделирование................................................................................................ |
15 |
1.6. |
Языковые средства современных СУБД.................................................................................. |
16 |
1.7. |
Даталогическое моделирование................................................................................................ |
16 |
1.8. |
Проектирование на физическом уровне................................................................................... |
17 |
1.9. |
Средства и методы проектирование БД................................................................................. |
17 |
1.10. |
Ограничения целостности......................................................................................................... |
18 |
1.11. |
Технология оперативной обработки транзакции (OLTP-технология)................................. |
19 |
1.12. |
Информационные хранилища.................................................................................................... |
20 |
1.13. |
OLAP-технология ....................................................................................................................... |
20 |
3.Принципы построения и архитектура компьютерных сетей Протоколы, иерархия
протоколов и режимы их работы............................................................................................... |
22 |
|
1.1. |
Классификация современных компьютерных сетей .............................................................. |
22 |
1.2. |
Принципы построения и архитектура компьютерных сетей.............................................. |
24 |
1.3. |
Протоколы, иерархия протоколов и режимы их работы ..................................................... |
28 |
1.4. |
Соединение, передача данных, разъединение .......................................................................... |
30 |
1.5. |
Передача информации в компьютерных сетях....................................................................... |
30 |
1.6. |
Каналы связи, модемы................................................................................................................ |
31 |
1.7. |
Кодирование и защита от ошибок........................................................................................... |
32 |
1.8. |
Структура пакета..................................................................................................................... |
33 |
1.9. |
Методы коммутации каналов, сообщений, пакетов.............................................................. |
35 |
1.10. Маршрутизация.......................................................................................................................... |
40 |
|
1.11. Базовые средства передачи данных......................................................................................... |
40 |
|
1.12. Локальные вычислительные сети (ЛВС)................................................................................. |
41 |
|
1.13. Структура и принципы строения ЛВС.................................................................................... |
41 |
|
1.14. Конфигурация связей.................................................................................................................. |
42 |
|
1.15. Стандарты, соглашения и рекомендации ............................................................................... |
44 |
|
1.16. Программное обеспечение компьютерных сетей................................................................... |
46 |
|
4. Назначение и основные функции операционных систем...................................................... |
48 |
|
4.1. Назначение и основные функции операционных систем (ОС)............................................... |
48 |
|
4.2. Способы построения современных операционных систем и операционных оболочек....... |
56 |
|
4.3. |
Организация и управление памятью, распределение ресурсов, сервисные службы |
|
|
операционных систем, организация сохранности и зашиты программных систем.......... |
59 |
5. Языки и системы программирования Модели языков программирования..................... |
62 |
|
5.1. Языки и системы программирования....................................................................................... |
62 |
|
5.2. |
Компиляторы и интерпретаторы........................................................................................... |
64 |
5.3. |
Объектно-ориентированное программирование.................................................................... |
65 |
6. Модели и этапы разработки программного обеспечения ..................................................... |
67 |
|
6.1. Программные средства и программные продукты................................................................ |
71 |
|
6.2. Коммерческое, условно-бесплатное и свободно распространяемое программное |
|
|
|
обеспечение.................................................................................................................................. |
72 |
|
3 |
|
6.3. |
Теория схем программ................................................................................................................ |
74 |
6.4. |
Семантическая теория программ............................................................................................ |
75 |
6.5. Модели вычислительных процессов: Модель графов распределения ресурсов.................... |
76 |
|
6.6. |
Вычислительные схемы ............................................................................................................. |
79 |
7.РеляционныесистемыуправлениябазамиданныхОбъектно-ориентированныебазы
данных ............................................................................................................................................. |
80 |
|
7.1. |
Реляционные СУБД..................................................................................................................... |
80 |
7.2. |
СУБД на инвертированных файлах.......................................................................................... |
83 |
7.3. |
Гипертекстовые и мультимедийные БД................................................................................. |
84 |
7.4. |
XML-серверы............................................................................................................................... |
85 |
7.5. |
Объектно-ориентированные базы данных.............................................................................. |
85 |
7.6. |
Организация процессов обработки данных в БД .................................................................... |
89 |
8. Архитектуры вычислительных систем Архитектура системы команд............................ |
92 |
|
8.1. |
Классификация современных вычислительных систем ......................................................... |
95 |
8.2. |
Способы организации и типы ВС............................................................................................. |
95 |
8.3. |
Параллельная обработка информации: уровни и способы организации .............................. |
96 |
8.4. |
Реализация в многомашинных и многопроцессорных ВС....................................................... |
97 |
8.5. |
Операционные контейнеры....................................................................................................... |
97 |
8.6. |
Векторные, матричные, ассоциативные системы................................................................ |
98 |
8.7. |
Однородные системы и среды: RISC-архитектуры .............................................................. |
99 |
8.8. |
Развитие архитектур, ориентированных на языковые средства и среду |
|
|
программирования...................................................................................................................... |
99 |
8.9. |
Основы метрической теории ВС............................................................................................ |
100 |
8.10. Технология распределенной обработки данных.................................................................... |
102 |
|
9. Задачи сортировки Анализ сложности и эффективности алгоритмов сортировки ...... |
104 |
|
9.1. |
Задачи сортировки................................................................................................................... |
104 |
9.2. |
Внутренняя и внешняя сортировки........................................................................................ |
104 |
9.3. |
Алгоритмы сортировки........................................................................................................... |
104 |
9.4. |
Анализ сложности и эффективности алгоритмов поиска и сортировки......................... |
106 |
10. Современные технологии разработки программного обеспечения Управление |
|
|
версиями Документирование.................................................................................................... |
108 |
|
10.1. Современные технологии разработки программного обеспечения, постановка задачи, |
|
|
|
оценка осуществимости.......................................................................................................... |
108 |
10.2. Планирование, тестирование, обеспечение оценки качества............................................. |
110 |
|
10.3. Групповая разработка, управление версиями, организация коллектива разработчиков, |
|
|
|
документирование.................................................................................................................... |
111 |
10.4. Структурное проектирование, CASE-средства, реинжиниринг программных систем.. |
115 |
|
4
МАТЕРИАЛ ДЛЯ ПОДГОТОВКИ
Задача данного действия заключается в нахождении одного или нескольких элементов в множестве, причем искомые элементы должны обладать определенным свойством. Это свойство может быть абсолютным или относительным. Относительное свойство характеризует элемент по отношению к другим элементам: например, минимальный элемент в множестве чисел. Абсолютное свойство - поиск элемента, ключ которого равен заданному «аргументу поиска» x.
Таким образом, в задаче поиска имеются следующие шаги:
1)вычисление свойства элемента;
2)сравнение свойства элемента с эталонным свойством (для абсолютных свойств) или сравнение свойств двух элементов (для относительных свойств);
3)перебор элементов множества.
Исчерпывающий поиск – это процесс нахождения в некотором множестве всех возможных вариантов, среди которых имеется решение конкретной задачи.
Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом (backtracking) и его естественное логическое дополнение - метод решета.
Основная идея поиска с возвратом: построение решения по одному компоненту и выяснение, может ли дальнейшие построение привести к решению. Если да – решение продолжается путем выбора первого допустимого варианта для следующего компонента. Если таких вариантов нет, то такие варианты для всех оставшихся компонентов не рассматриваются. Алгоритм в этой ситуации возвращается к последнему построенному компоненту и заменяет его следующим допустимым компонентом этого уровня.
Общий алгоритм перебора с возвратом на псевдокоде:
do { выбора варианта (n): if (подходит) { запись варианта ( ); if (решение неполное) { try (n+-…)
if ( ! удача) стирание варианта ( );} } } while ( !удача || нет вариантов);
Способы сокращения перебора
1.Отбрасывание заведомо неверных вариантов.
2.Применение эвристик.
3.Метод ветвей и границ.
Эвристика в программировании – это решение задачи при помощи разбора частных случаев, так как каждая ветвь эвристического алгоритма эффективнее, чем общее решение. Таким образом эвристическийалгоритм не решает задачу в общем виде, а работает только в определенных случаях, но это и хорошо, так как некоторые задачи не имеют общего решения и они решаются только при помощи эвристики. Применяется тогда, когда мы ищем одно из возможных решений, а не все. Таким образом эвристика позволяет выбрать из всех вариантов самый вероятный.
Перебор с возвратом (backtracking) – это один из методов организации исчерпывающего поиска, который строится конструктивно последовательным расширением частичного решения.
Метод решета – это один из методов организации исчерпывающего поиска, при котором из множества возможных вариантов исключаются все элементы, не являющиеся решениями.
Незначительные модификации метода перебора с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д.