14. Послед. И бинарный поиск

Задача поиска. Пусть заданы лин. списки: список эл-ов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для кажд. зн-ия Vi из V найти мн-во всех совпадающих с ним эл-ов из В. Чаще всего встречается ситуация когда V содержит один эл-т, а в В имеется не более одного такого эл-та.

Эфф-сть некот-го алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} кол-вами сравнений, необх-х для нахожд-я эл-та V в В. Если Pi – относ. частота исп-я эл-та Кi в В, а Si - кол-во сравнений, необх-ое для его поиска, то

Max{А} = max{ Si, i=1,n } ; Avg{А} = .

Последовательный поиск предусматривает последовательный просмотр всех эл-ов списка В в порядке их распол-я, пока не найдется эл-т, = V. Оч-но, что Max последовательного поиска равен N. Если частота исп-я каждого эл-та списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При разл. частоте исп-я эл-ов Avg можно улучшить, если поместить часто встречаемые эл-ты в начало списка.

Для упорядоченных лин-х списков сущ-ют более эфф. алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск сост. в том, что ключ V сравнивается со средним эл-ом списка. Если эти знач-ия окажутся равными, то искомый эл-т найден, в противном случае поиск продолжается в одной из половин списка.

Нахожд-ие эл-та бинарным поиском осущ-ся очень быстро. Max бинарного поиска равен log₂(N), и при один. частоте исп-я каждого эл-та Avg бинарного поиска =log₂(N). Недостаток бинарного поиска заключ-ся в необх-сти последовательного хранения списка, что усложняет операции добавления и исключения эл-ов.

Пример: {1, 2, 3, 4, 5, 6}. Используя определение бинарного поиска, найти элемент 4. (Сначала попадем на 3, затем на 5, затем на 4).

15. Операционные системы (ос)

ОС - это комплекс взаимосвяз. системных программ, назнач-е — организовать взаимодействие польз-ля с комп-ом и вып-е всех др. программ. ОС вып-ет роль связующего звена между аппаратурой комп-а и выполняемыми программами, а также польз-лем. ОС обычно хранится во внешней памяти комп-а — на диске. При включении комп-а она считывается с дисковой памяти и размещается в ОЗУ (операт. запомин. устройство). Этот процесс наз-ся загрузкой ОС.

В ф-ии ОС входит: осущ-е диалога с польз-лем; ввод-вывод и упр-е данными; планир-е и орг-ия процесса обработки программ; распред-е ресурсов (опер. памяти и кэша, процессора, внеш. устройств); запуск программ на вып-е; всевозможные вспом. операции обслуживания; передача инф-ии между разл. внутр. устр-вами; программная поддержка работы периферийных устр-в (дисплея, клавиатуры, дисковых накопителей, принтера и др.).

ОС для ПК, ориентированного на професс. применение, д. содержать след. осн. компоненты: программы упр-я вводом/выводом; программы, управляющие файл. системой и планирующие задания для комп-а; процессор командного языка, который принимает, анализирует и вып-ет команды, адресованные ОС.

Каждая ОС имеет свой командный язык, кот. позволяет польз-лю вып-ть те или иные действия: обращаться к каталогу; вып-ть разметку внеш. носителей; запускать прогр.и др. действ.

Для упр-я внеш. устр-вами комп-а исп-ся спец. сист. программы — драйверы. Драйверы станд. устр-в образуют в совок-сти базовую систему ввода-вывода (BIOS), которая обычно заносится в пост. ЗУ комп-а.

Файл — это место пост. хранения инф-ии: программ, данных для их работы, текстов, закодированных изобр-ий, звуков и др.

Файл. система — это ср-во для орг-ии хранения файлов на к.-либо носителе.

Файлы физически реализ-ся как участки памяти на внеш. носителях — магнитных дисках или CD-ROM.

Обслуживает файлы спец. модуль ОС, называемый драйвером файл. системы. Каждый файл имеет имя, зарегистрированное в каталоге — оглавлении файлов.

Каталог (иногда наз-ся директорией или папкой) доступен польз-лю ч/з командный язык ОС.

Каталог может иметь собств. имя и хран-ся в др. каталоге с обыч. файлами: так образ-ся иерархич. файл. структуры.

Драйвер файл. системы обеспечивает доступ к инф-ии, записанной на магнитный диск, по имени файла и распределяет простр-во на магнитном диске между файлами.

Для вып-я этих ф-ий драйвер файл. системы хранит на диске не только инф-ю польз-ля, но и свою собств. служ. инф-ию. В служ. областях диска хранится список всех файлов и каталогов, а также разл. допол. справ. таблицы, служащие для повышения скорости работы драйвера файл. системы.

Утилиты – сервисные программы (форматирование дисков, восстановление данных, коррекция логических и физических ошибок дисковых данных, дефрагментация, антивирусные программы, архиваторы и др.)

Наиболее распространенной ОС является Windows. В этой ОС используется интерфейс командной строки. Интерфейс командной строки  — разновидность текстового интерфейса между человеком и компьютером, в котором инструкции компьютеру даются в основном путём ввода с клавиатуры текстовых строк (команд), в UNIX-системах возможно применение мыши. Также известен под названием консоль. Рассмотрим некоторые команды: CD - Вывод имени либо смена текущей папки; COPY - Копирование одного или нескольких файлов в другое место; DEL - Удаление одного или нескольких файлов; DIR - Вывод списка файлов и подпапок из указанной папки; EXIT - Завершение работы программы CMD.EXE (интерпретатора командных строк); FIND - Поиск текстовой строки в одном или нескольких файлах; HELP - Выводит справочную информацию о командах Windows; PRINT - Вывод на печать содержимого текстовых файлов. REN - Переименование файлов и папок; TIME - Вывод и установка системного времени.