- •1. Понятие инф-ии.
- •2. Алгоритм
- •3. Оо анализ, проект-ие и программ-е.
- •4. Система программ-я.
- •5. Интерфейсные объекты
- •6. Данные.
- •7. Структурированные типы данных
- •8. Операторы передачи упр-я в языках программ-я. Turbo Pascal
- •Visual Basic
- •9. Операторы орг-ии циклов в языках программ-я. Turbo Pascal
- •Visual Basic
- •10. Процедуры в языках программ-я.
- •Visual Basic
- •Visual Basic
- •12. Граф. Процедуры и функции. Граф. Объекты.
- •13. Алгоритмы сортировки
- •Сортировка Хоара
- •14. Послед. И бинарный поиск
- •15. Операционные системы (ос)
- •16. Прикладное программное обеспечение общего назначения. Системы обработки текстов. Системы машинной графики.
- •Свои параметры форматирования имеют символы текста (шрифт): Формат – Шрифт.
- •17. Электронные таблицы
- •Можно описать процессы: создание рабочей книги, открытие рабочей книги, сохранение рабочей книги, закрытие рабочей книги, завершение работы с Microsoft Excel.
- •Операции с листами рабочих книг: переименование, копирование перемещение, перемещение листа, удаление, вставка.
- •21. Понятие архитектуры и основные типы архитектуры эвм. Типовая схема эвм. Оперативная память, центральный процессор эвм.
- •22. Периферийные устройства пк
- •18. Прикладные инструментальные пакеты для решения задач на эвм.
- •19. Антивирусные программы. Архиваторы. Программы обслуживания дисков.
- •20. Понятие "модель". Виды моделирования. Компьютерная модель. Математические модели.
- •23. Компьютерные сети.
- •24. Интернет (сеть). Электронная почта. Обмен файлами (ftp). Технология www. Поиск информации в Интернет.
- •25. Язык html как средство создания информационных ресурсов Интернет.
- •26. Понятие мультимедиа. Создание мультимедийных приложений.
- •27. Основные направления исследований в области искусственного интеллекта. Представление знаний в иис. Понятие об экспертной системе.
- •29. Информационные модели данных: реляционные, иерархические, сетевые. Последовательность создания информационной модели. Взаимосвязи в модели.
- •30. Базы данных. Определение взаимосвязи между элементами бд. Ключи атрибутов. Нормальные формы.
13. Алгоритмы сортировки
Массив - это упорядоч. структура однотипных данных, хранящая их послед-но. Доступ к эл-ту массива осущ-ся через его индекс.
Для зад-я массива в Visual Basic служит команда:
Dim ИмяМассива As Тип (Dim A(1 to 20) As Integer)
Границы могут задаваться одним числом N, тогда границы массива будут от 0 до N. Динамический массив задается:
Dim Massiv() As Integer ….
ReDim Massiv(First To Last)
или при сохр-ии знач-ий эл-та массива
ReDim Preserve Massiv(First To Last)
Для освоб-я памяти, занятой динам массивом:EraseMassiv
Сущ-ют разл. методы сортировки. Рассм. каждый метод на примере задачи сорт-ки по возр-ю массива из N цел.чисел.
Сортировка выбором Идея метода заключ-ся в том, что находится макс. эл-т массива и меняется местами с послед. эл-ом (с номером N). Затем, максимум ищется среди эл-ов с первого до предпоследнего и ставится на N-1 место, и т.д. Необх-мо найти N-1 максимум. Можно искать не макс., а минимум и ставить его на 1-е, 2-е и т. д. Также применяют модификацию этого метода с одноврем. поиском максимума и минимума. В этом случае кол-во шагов внешнего цикла N div 2. Вычисл. сложность сортировки выбором - величина порядка N*N, что обычно записывают как O(N*N). Это объясняется тем, что кол-во сравнений при поиске 1-го максимума равно N-1. Затем N-2, N-3, и т.д. до 1, итого: N*(N-1)/2.
Сортировка обменом (методом "пузырька")
Идея метода заключ-ся в том, что посл-но сравниваются пары соседних эл-ов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется макс. эл-т ("всплыл" первый "пузырек"). Следующий проход должен рассматривать эл-ты до предпоследнего и т.д. Всего требуется N-1 проход. Вычисл. сложность сортировки обменом O(N*N).
Сортировка Хоара
Эту сортировку также наз-ют быстрой сортировкой. Знач-ие какого-нибудь эл-та, обычно центр-го, запис-ся в перем-ую X. Просматриваются эл-ты массива. При движ-и слева-направо ищем эл-т > или = X. А при движ-и справа-налево ищем эл-т < или = X. Найден. эл-ты меняются местами и продолжается встречный поиск. После этого массив окажется разделенным на две части. В 1-ой нах-ся эл-ты < либо =X, а справа - > либо=X. Можно заменить исх.задачу о сортировке массива A на 2 подзадачи о сортировке получ.частей массива. Вычисл. сложность 1 вызова данного рекурсивного алгоритма пропорц-на кол-ву эл-ов сортируемого фрагмента массива. В лучшем случае деление на части произв-ся пополам, поэтому вычисл. сложность всего алгоритма быстрой сортировки сост-ет вел-ну порядка N*Log2N. Вычисл. сложность в среднем того же порядка.
4 |
3 |
12 |
7 |
21 |
j→ |
|
|
i |
|
7 |
3 |
12 |
4 |
21 |
i |
|
|
|
←j |
7 |
3 |
12 |
4 |
21 |
i |
|
|
j |
|
4 |
3 |
12 |
7 |
21 |
|
|
j |
i |
|
4 |
3 |
7 |
12 |
21 |
|
|
i j |
|
|
4 |
3 |
7 |
12 |
21 |
|
|
i |
j |
|
4 |
3 |
|
12 |
21 |