Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Принципы Неймана. Пр-пы Фон Неймана: 1)команды и данные д. кодироваться двоичн. числами; осн. память д.иметь произв-й доступ, т.е. проц-у в любой момент времени д.б. доступна любая ячейка памяти и время доступа д.б. одинаково. 2)ЭВМ управ-ся прог-ой. Она вып-ся послед-но. В осн-й памяти д.храниться как данные, так и прог-а; инф-ция в осн-й памяти не имеет признаков принадл. к опред-ому типу. 3)память ЭВМ д.б. орг-на иерархически: быстрая и небольшая по объему осн-ая память и медленная – внеш.
ЭВМ явл. универс. устр-во для обраб., передачи и хранения инф-ции.
Из пр-пов вытекает, что структура ЭВМ:
Проц-р сост. из АЛУ и УУ. АЛУ- арифметико-логическое устройство, произв. арифм-ие и лог-ие операции. УУ- устр-во упр-ния, отдает команды различн-м устр-вам ЭВМ на вып-ие. Внутр. память делится на ПЗУ и ОЗУ. ОЗУ-операт. запомин-е устр-во, энергозав., быстрый доступ. ПЗУ- Пост-е.ЗУ, энергонез. Внеш. память использ. для долговрем. хранения инф-ции (различ. диски и т.п.). Они энергонез. и медлен. УСТР. ВВОДА - для ввода инф-ции в ЭВМ (клавиатура, СD, сканер) УСТР. ВЫВОДА - для вывода рез-тов (дисплей, принтер, модем, графопост-ль). УВВ осущ-ет связь с пом-ю шин (шина данных, адресов, управления).
3. Представление о вероятности. Энтропия опыта. В реальной жизни мы часто имеем дело с явл-ми или событ-ми, точн. рез-тат кот-х заранее не предсказуем. Этим заним-ся теория вер-сти. В каждом опыте колич. и хар-р рез-тов опыта (исходы) точно определены. Пример: подбрасыв. монеты (2 исхода), кубика (6) или вытаск-ие шаров. Выберем опыт с шарами. Пусть в урне лежат 2 шара (белый и черный). С провед-м опыта связана некот. неопред-сть. Осущ-ние опыта, снимают ее. Чем>изнач-ая неопр-сть исхода, тем>инф-ии о его фактическом наступл. (колич. мера инф-ии). Если связать колич. меру инф-ции с колич. мерой неопр-сти, то колич. мер. неопр-сти станет пропорц. кол-ву возм. исходов. В случае когда нельзя отдать предпочтение, исходы назыв. равновер-ми. Т.о. в опыте где n-число равновер-ых исходов, вер-сть каждого из них 1/n (рассмотреть > сложный пример: n=10, 1-белый, 9 черных. Тогда вер-сть вынуть белый шар Р(А)=1/10, где А-исход-вынуть белый шар, Р(В)=9/10). Вер-сть – отн-ние числа благопр-х исходов опыта к колич. возм-х. Она нах-ся в промежутке [0;1]. В кач-ве меры вер-сти м.б. взять само число n, но при n=1 неопр-сть отсутствует, т.е. д.б.=0. Это соображение приводит к опр-ию энтропии опыта (численная мера неопр-сти рассм-го опыта):
Н=log n. Величина Н - это мера колич. инф-ции, связ. с осущ-м опыта. (n – колич. возм-х вариантов сообщений). Мера одного исхода=(1/n)* log n.
5. Позиционные сист. счисления (СС). Алгоритмы перевода чисел из одной сист. в другую. Под СС понимается способ представления любого числа посредством некоторого алфавита символов. Сущ-т различ. СС. В зависимости от способа изображения цифр СС подразд-ся на позиционные и непозиционные. В непоз. СС цифры не меняют своего колич-го значения при изм-ии расп-ия их в числе (римская и вавилонская), при поз. СС - меняют (т.е. цифра имеет различ. знач-я, в завис-ти от занимаемой позиции). Классы СС: 1)анатомического происхождения (пятеричная, 10, 20); 2)алфавитная (древнерусская); 3)машинные (2,8,16). Основание СС – количество символов, используемых для записи любого числа. Общая запись числа –
am-1am-2…aoa-1a-2…a-s= m-количество цифр=
am-1pm-1+…+ao po+…+a-s p-s p-основание СС.
Алгоритмы перевода необходимо было выучить!
7. Понятие алгоритма (Алг). Исполнитель (Исп). Свойства алгоритма. Уровни определения алгоритма. Алг-послед-сть шагов ведущих от данных к рез-тату. Т.е. цель выполнения Алг: получение рез-тата. Слово Алг произошло от имени восточного ученого аль-Хорезми (9 век).
Для пояснения этого понятия важное значение имеет понятие исполнитель алгоритма. Алг формул-ся в расчете на конкретного Исп (человек, животное, особая машина и т.д.). Алг явл. руководством к действию для Исп. Необх. чтобы Алг был понятен Исп, т.к. каждый Исп снабжен своим огранич-м набором действий (система команд). Т.е при формулировке необх. учитывать возм-сти и особ-сти Исп, на которого рассчитан Алг. Свойства Алг: 1)массовость. Алг д. решать любую задачу из опред-го круга задач; 2)конечность. Вып-ие Алг заканч-ся после вып-ия конкретного числа шагов; 3)точность. На каждом шаге Исп д. понимать команду и каждый шаг д.б. четко и недвусмысленно определен и не д. допускать произв. трактовки Исп-ю; 4)результативность. На каждом шаге Исп-ю известен рез-тат шага; 5)дискретность. Алг представлен в виде конеч. послед-сти шагов, т.е. Алг имеет дискретную стр-ру, след-но его испол-ие расчленяется на вып-ие отдельных шагов.
Алг на интуитивном уровне определяется как единый метод решения определенного класса однотипных задач, обладающий указанными свойствами и работающий с конструктивными объектами. Осн. алгоритмических конструкции: линйейная, разветвляющаяся, циклическая. Способы записи Алг: словесный (ориентирован на человека), алгоритмический язык, блок-схема, ЯП.
9. Рекурсивные процедуры и функции. Стековый механизм передачи параметров при обращении. Рекурсия это метод, сводящий общую задачу к некоторым задачам более узкого, простого типа. Рекурс-й алг-м – это алг-м, кот-й в процессе своей работы обращается сам к себе.
Суть заключается в том, что при каждом вызове создается новая копия со своими переменными, но как только она заканчивает свою работу, то память, занятая этими локал-ми перем-ми, освоб-ся, а полученные рез-таты передаются в точку вызова. Т.е. реализ-ся стековый мех-зм передачи параметров при обращении. Понятие стека – стек – тип структуры данных, организ-й по принципу «последний пришел - первый ушел». В стеке доступен только один элемент, называемый вершиной стека. При выборке из стека выбир-ся элемент из его вершины, а все ост-ые эл-ты при изм-нии порядка сдвиг-ся вверх, так что в вершину попадает в эл-нт, пост-ший в стек предпоследний.
Задачи, решаемый этим методом, можно разбить на 4 вида. 1)Задачи с рекурсивной формулировкой (вычисления факториала натурального числа); 2)Задачи, из постановки которых можно извлечь рекурсию (перевод натурального числа из одной СС в другую); 3)Задачи, которые можно решить как частный случай обобщенной (если нельзя решить задачу рекурсивным способом, то можно расширить задачу, обобщить ее и решить; 4)Задачи, в которых можно использовать характеристику или свойства функции.
11. Кодирование: постановка задачи, оптимальные коды, коды, исправляющие ошибки. Постановка задачи: инф-ция требует умелой передачи на расстоянии. Инф-ция от источн. поступает в кодир-ее устр-во, оно затем по каналу связи – в декод-щее устр-во (передаваемая по каналу связи инф-ция наз-ся сообщением) и затем – к получателю сообщения. Правило, сопост-щее каждому передав-му сигналу некоторую комб-цию, наз. кодом. Операция перевода сообщ-я в послед-сть сигналов наз-ся кодированием. Треб-я: 1)эффективность. Чем короче кодовое слово, тем выгоднее код; 2)надежность; 3)однозначность декодир-ия.
Задача кодирования в общем виде. Есть сообщение; необх. закод-ть его, при этом нужно осущ-ть кодир-ие более рац-ым способом. Код Морзе. Явился первым ориентированным кодиров-м. В коде букве и цифре сопост-ся кратковрем-я и длинноврем-я подача тока (точка-тире), разделяемых кратковрем-ми паузами (пробел между буквами – одно тире, между словами - два). Код Бодо. Исп-ся в телеф-х аппаратах. Это двоичное кодир-е. Он допускает (как и код Морзе) однозначное декодир-е. Условием однозначности декод-ния явл-ся то, что никакое обозначение не д.совпадать с началом другого, более длинного слова. Код Шеннона-Фано. Идея кодир-ия: разбить все буквы на две группы так, чтобы вероя-сть принадлежать каждой из этих групп была как можно близки одна к другой. Осн-й принцип декодир-я: при выборе каждой цифры кода нужно стараться, чтобы содерж-ся в ней кол-во инф-ции было наибольшим. Т.е. независимо от знач-я всех предыд-х цифр эта цифра принимала оба возм-х значения (0-1) по возм-сти с равной вероятностью. Код Хафтмана. Идея: преобр-е алфавита А из n-символов в n-1 символов. И делать будем так, пока не получим два числа. Оптимальные коды. ОК называется код, у которого число элем-ых сигналов, приход-хся на одну букву, мин-но. Свойства ОК. 1)В ОК менее вероятное сообщение не д. кодир-ся > коротким словом; 2)если код опт-ый, то всегда м. так перенумеровать сообщение и соотв-щее кодовое слово, что будет вып-ся условие:
p1>=p2>=p3>=…>=pn, l1<=l2<=l3<=…<=ln, где p-вер-сть, l-число знаков; 3)в опт-м двоичном коде по крайней мере два слова – наиб-й длины, отлич-ся друг от друга только последним символом. Пример: блоковые коды (кодировка не отдельных букв, а целых блоков). Коды, испр-щие ошибки: код с повторением - каждый разряд замен-ся блоком, т.е. повт-ся неск-ко раз (пример: 1 заменяем 11111, 0 - 00000). Увелич. n м. убедиться, что передача сообщений будет безошибочн., но при этом уменьш-ся скорость передачи. Код хорошо испр-т ошибки, но неэффект-н. Код Хемминга. Добавление k битов четности, соотв-щим расп-ем среди битов n-разрядного слова можно построить n+k-разрядный код, позв-щий обнаружить и исправлять место ошибки.
13. Алгоритмы поиска и их сравнение.
Осн-й вопрос задачи поиска: где в заданной совокупн. данных находится элемент, обладающий заданым св-вом. Большинство задач поиска сводится к простейшей – поиск в таблице эл-та с заданным значением.
Алгоритмы поиска. 1)Линейный поиск. Продолжает поиск до обнаружения искомого эл-та или до конца массива, последов-но перебирая все эл-ты; 2)Линейный поиск с использ-ем барьера. В массив на n+1 место записываем искомый эл-т X, который будет являться барьерным. Если эл-т будет найден только при i=n+1, значит, интересующего эл-та в массиве нет; 3)Бинарный поиск. Это один из методов непослед-го поиска, назыв-ый также методом половинного деления. При его использ-и на каждом шаге область поиска сокращ-ся в 2 раза. Массив при этом д.б. отсортирован; Анализ: Линейный поиск: число сравнений зависит от того, где располагается искомая запись. Если она окажется первой, выполняется только одно сравнение, если последней – n сравнений. Следовательно, успешный поиск требует в среднем (n+1)/2 сравнений. Неуспешный потребует п+1 сравнений с учетом барьерного эл-та. Бинарный поиск: каждое сравнение уменьшает число кандидатов в 2 раза, однако, поиск применяется только в отсортированном массиве, тогда как последовательный поиск может работать в любом массиве. Поэтому, если необходимо произвести однократный поиск, лчуше воспользоваться линейным поиском. 4)Поиск подстроки в строке. Прямой поиск. Сводится к послед-ым сравнениям отд-х символов. Поиск прод-ся до тех пор, пока не обнаруж-ся сравнение; 5)Поиск подстроки в строке. Алгоритм Бойера-Мура. Поиск ведется от начала строки, но с конца искомой подстроки, для которой форм-ся таблица, размерн-ть кот-й-256. Эле-ми таблицы явл-ся расстояния от последнего символа искомой подстроки до ее каждого символа. Когда очередной символ подстроки не совпадает с очередным символов строки для последнего из таблицы расстояний опред-ся соотв-щее расстояние, после чего конец искомой подстроки сдвиг-ся вправо на соотв-щее число позиций, тем самым ряд позиций пропускается, сокращая время поиска; 6)Поиск подстроки в строке. Алгоритм Кнута-Мориса-Пратта. Требует только n сравнений даже в самом плохом случае, где n-длина строки. Сравнение нач-ся с первого символа строки S.
15. Операционные системы (обзор) и инструментальные оболочки. ОС входит в состав базового программного оборудования. БПО-это набор прогр.средств, обеспечивающих работу компа. ОС прендназначена для управления (выполнения) программ пользователя, для планирования и управления вычислительными ресурсами ЭВМ. ОС делятся на: 1)одно- и многозадачные (зависит от числа параллельно выполняемых прикладных процессов) 2)одно- и многопользовательские (зависит от числа пользователей одновременно работающих с ОС) 3) непереносимые и переносимые на др. типы комп-ов 4)несетевые и сетевые, обеспечивающие работу в локальной сети ЭВМ. Наиболее распространные ОС: OS/2, MSDOS, WindowsNT, Unix.
Иструментальные оболочки: задача – максимально упростить диалог пользователя с компьютером. Входят: операционные оболочки-спец.программы, прендназначенные для облегчения общения пользователя с командами ОС. Имеют текстовый и графический варианты интерфейса.(Нортон Командер, Дос Навигатор- текстовые, Windows- граф.); ЯП- средства перевода на язык машины; Трансляторы – это программы перевода в машинные коды. Виды: интерпритатор(Бейсик- построчно), компелятор (Паскаль- перводит целиком).
17. Отсечение отрезка прямоугольным окном
Постановка задачи. Дано окно прямоуг.АBСD с координатами вершин и отрезок MN. Изобразить только видимую часть в окне. Алг. Коэна-Созерленда. Вся область границами окна разбивается на 9 частей. Каждая часть кодируется b3 b2 b1 b0 (b3 = х < x(min) b2 = х >x(max) b1 = y <y(min) b0 = y > y(max)). Коды концов логически перемножаем. Если результат =0 и коды=0, то отрезок видим полностью. Если результат = 0 и хотя бы один код не равен нулю, то видим частично, а может быть не видим вообще. Если результат не=0 и коды содержат единицу, то полностью не видим. Далее находим точки пересечения с окном. Способы: метод половинного деления, решение систем уравнений отрезков и т.д. Алг.Кируса-Бека. Эффективен для любого окна. Идея: Для определения местоположения отрезка относительно окна используется вектор внутренней нормали. Рассматриваем отрезок P1P2 и для определенности границу окна AD. (См.рисунок на обороте) На стороне окна AD выберем точку F. Уравнение отрезка P1P2 P(t)= t-параметр [0;1]Проецируем на оси: x=x1+(x2-x1)t и y=y1+(y2-y1)t. Возможно три случая (скалярное произведение) и в зависимости от Cos угла 1)<0, то направлен вне от границы 2)=0, на границу; 3)>0, внутрь от границы. Если выполняется условие 2, то P – точка пересечения отрезка P1P2 и указанной границы окна. Теперь необходимо найти параметр t. Для используют формулы:
Из последней формулы находим t. Если вектор P1P2=0, то P1 и P2 совпадают. Если <0, то не рисуем, а если >0, то прямая лежит правее. При этом считаем значение t. Если он принадлежит [0; 1], то рисуем. Если нет, то проверяем знак числителя(i=номер стороны окна). Этот Алг.работает для любого выпук.окна
4.Информация. Количество информации. Формула Хартли и Шенона. Единицы инф-и.
Информация - содержание сообщения, сигнала, памяти, а также сведения, содержащиеся в сообщении, сигнале, памяти. Информационные процессы (процессы передачи, хранения, переработки информации) всегда играли важную роль в жизни общества. В интуитивном уровне мы понимаем под И. совокупность интересующих нас сведений, знаний, набор используемых данных и т.п. при этом подразумевается, что существует источник информации и ее потребитель. От источника к потребителю информация передается путем сообщения. Способ передачи сообщения (физический процесс, с помощью которого осуществляется такая передача) определяет канал связи между источником и потребителем. Информация, являющаяся значительной и ценной для одного человека, может не представлять никакого интереса для другого. Количество информации, извлекаемой человеком из некоторого сообщения, существенно зависит от уровня понимания этой информации и субъективно оцениваемой полезности. Вместе с тем технические проблемы развития разнообразных средств связи потребовали ввести количественную меру информации, независимую от субъективного человеческого восприятия. В 1948 г. К. Шеннон - специалист в области средств связи ввел математическое понятие количества информации, положив тем самым начало теории информации как технической и математической дисциплине.
Н=log n. (Хартли) Величина Н - это и мера количества информации, связанной с осуществлением опыта. (n - количество возможных вариантов сообщений). Т.к. опыт имеет n равновероятных исходов, то можно считать, что на долю каждого исхода приходится одна n-ая часть общей неопределенности опыта: 1/n*log n. Обозначим вероятность i-го исхода опыта через Рi (i =1,2,...n). Pi=1/n, тогда формула для численной меры неопределенности (формула количества информации) имеет вид (Шенон): Обычно в качестве основания логарифма в полученной формуле берут число 2. Легко сосчитать, что при этом условии и при n =2 мы получаем Н=1. Формулу можно использовать и в тех случаях, когда возможные результаты опыта не являются равновероятными. Пусть в урне 10 шаров (1 черный и 9 белых). Р1=1/10, Р2=9/10, тогда количество информации Н=0,469 (бит). Мы видим, что количество информации оказалось меньшим, чем для опыта с 2-мя равновероятными исходами (Н=1). Таким образом, в качестве единицы принимается количество информации, связанной с опытом, состоящим в выборе одного из двух равновероятных исходов. Такая единица количества информации получила название «бит».
Алфавит из 2-х символов называют двоичным и говорят о двоичном представлении информации. при таком представлении буквы, цифры изображаются двоичными словами - последовательностями из нолей и единиц. Если считать, что с нулем и единицей в двоичном алфавите связаны одинаковые вероятности их появления (Р1=Р2=1/2), то количество информации при двоичном кодировании будет равно:Н=log22=1бит. Т.о. количество информации (в битах) заключенной в двоичном слове, = длине слова (числу двоичных знаков в нем). Бит в переводе - двоичный знак. Для удобства использования введены крупные единицы количества информации. Восьмиразрядное двоичное слово называют байт. В одном байте можно закодировать значение одного из 256 символов (28). Объем информации в 1024 байта носит название килобайт (Кбайт); Мегабайт = 1024 Кбайт; Гигабайт = 1024 Мбайт.
Возможность измерить количество информации весьма важна с теоретической и практической точки зрения. Особое значение приобретает количественная оценка объемов обрабатываемой информации в связи с массовым применением ЭВМ.
2. Логические элементы ЭВМ. Орг-я памяти ЭВМ. Регистры и тригеры.
Логика- савкуп-ть правил, кот. подчин-ся процесс мыщления чел. (понятия, сужд., умозаключ.). Чтобы достичь истины, еужно следовать законам логики (формальн. и мате-кой(Лейбниц)). Мате-кая логика легла в основу всех схеи и устр-в ЭВМ. Она не рассматрив. содерж. высказ-я, а интерес-я только фактом истинности (1 и 0). Выдел. три основные операц. И, ИЛИ, НЕ.
Логические элементы. Первый был Шенон. Проектирование без логики невозможно. Логические эл-ты Инвертор, Коньюктор, Дизьюнктор. (рис. и табл. истинности).
|
X |
Y |
NOT X |
XANDY |
X OR Y |
|
1100 |
1010 |
0 0 1 1 |
1 0 0 0 |
1 1 1 0 |
С помощью этих лог. элем-в реализет. любая логич. функция и схема.
Регистры и тригерры. Тригерр- устр-во которое м. запоминать 0 и 1, демонстрировать их, и забывать. Делятся на тригеры с 1 входом и с 2 входами. 1) На вход 1, то на выходе меняется местами, если 0 то нехуя. 2) Делятся на асинхронный (нет синхр. сигнала) и синхронизированный (если информ. заносится одновременно синхрониз. сигналом). Синхротригеры делятся на однотактные(R=0, S=0 то нехуя. R=0, S=1 то тригер в 1. R=1, S=0 то тригер в 0) и двухтактные, который состоит из двух однотактных тригеров. Занесение информации в тригер происходит после того как, текущее состояние занесено во 2 тригер. На вход поступает 1 инфо. в 1 тр., при этом 2 тр. не меняет своего значения, т.к. на него поступает инверсное значение синхро импульса. После окончания синхроимпульса при подаче 0 на 1 тр. на 2 тр. подается 1, а 1 тр. переходит в состоян. хран.
Qt+1=S+Qt(таблица истинности нахуярить по формуле) R=1 S=1 запрещено. Регистры. Несколько тригеров можно объеденить в группу - регистр. Оперативная память представлена в виде регистров. Как прафило один регистр образует одну ячейку памяти, каждая ячейка в ОЗУ имеет адрес. 6. Представление инф-ции в ЭВМ.
Инф-ция в ЭВМ представляется в двоично-кодированном виде. Кодированием называется процесс построения данных элементов конечного множества (кодового набора) по установленным правилам. Кодом называется система, образуемая кодовым набором и правилами, по которым из элементов этого кодового набора строят данное при кодировании. Различают внутреннее представление инф-ции (на уровне машинного языка) и внешнее на носителях инф-ции применяемых в устройствах ввода-вывода, а также при обмене инф-цией с пользователем ЭВМ и передачи по каналам связи.
Виды инф-ции.
1) числовая - вещественная; целая 2) символы 3) строки 4) графическая 5) логическая 6) музыка 7) массивы 8) запись 9) файлы 10) сама программа 1,2,3,5 - фундаментальные виды инф-ции.
1) целые числа - записываются в 2-х машинных словах (2 байта или 16 бит), (знак + представляется нулем, знак - единица) в машине представляются всегда точно. Значения лежат в интервале -32768х32767; (215) вещественные числа а) одинарная точность: четыре машинных слова (4 байта) 26=64; Р- порядок. 10Р; -64Р63; m-мантиса m6 десятичных бит б) двойная: 8 машинных слов m14 десятичных бит.
Для представления чисел в ЭВМ применяются следующие системы счисления: представление чисел с фиксированной точкой, естественное, представление с плавающей точкой. Первые два представления являются позиционными системами счисления с фиксированныём основанием. В представлении с фиксированной точкой положение от делителя дробной части числа закреплено в последовательности разрядов, но сам отделитель явно не кодируется.
В естественном представлении отделитель дроби (. или ,) кодируются явно.
Представление с плавающей точкой - это система счисления, в которой число представлено мантиссой и порядком и определяется выражением M*aP, М - число представляющее мантиссу, а - основание числа, Р - число называемое порядком представления числа с плавающей точкой. Для однозначного кодирования числа используют поля мантиссы (без незначащих нулей), принято выбирать такой порядок числа, чтобы мантисса находилась в заданной границе, например, ее значение было меньше 1, но 10-1. Такое представление называется н-лизированной формой числа. Точность и диапазон представления числа определяется разрядностью отведенного ему поля. Точность представления числа с плавающей точкой определяется разрядностью мантиссы. Диапазон определяется разрядностью порядка и основанием системы счисления. Закодированные буквы и цифры, граф. знаки занимают в памяти ЭВМ по 1-му байту. Закодированные числа - 2 соседних байта - машинное полуслово, 4 байта - слово, 8 байт - двойное слово.
2) символ - каждому символу приписывается целое число в диапазоне от 0 до 255. Для кодировки используется код ASCII.
3) логические значения (boolean)
Прямой, обратный и дополнительный код.
Для хранения двоичного числа в памяти машины каждый бит заноситься в один разряд в ячейку фиксир. размера (8, 16, 32). Это прямой код. Для записи отриц. чисел используется дополнительный код (инвертировать и +1). Старший разряд является знаковым (1 - отриц.).
8. Анализ алгоритма и его сложность.
Для чего анализируются алгоритмы: 1) необходимость получения верхних оценок для объма памяти и времени работы необход. для успешной обработки вход. данных. Надо избегать алгоритмов,которые за определеное время не дают результат. 2) Необходимо заранее оценить время и объем памяти нужное составенному алг. для работы. Пусть А - алг. решающий пост. задачу. n- размер отдельно взятых данных для обработки (дл. строки, массив). Время алг. А - Можно определить две функции: ВремяА(n) - временная сложность. Память алг. А- памятьА(n) - емкостная сложность. Время. Максимальная граница времени для работы А с входными данными длиной n эта функции определяет максимальное число простых операций, которое должен выполнить алгоритм А(n). ПамятьА(n) - дает верхнюю границу для максимального числа одновремено существующих скалярных значений при вводе n. Критерий качества - скорость роста его сложности в зависимости от увеличения n.
Пример: с n2 (с-const) время обработки входных данных, то временная сложность имеет порядок n2. О(n2) - временная сложность А
Надо иметь в виду, что порядок сложности А является определенным только при обработке данных большого размера. А для задач с малым размером входных данных надо учитывать конст. при сравнениях алг. В общем случае: повышение скорости работы А может потребовать увелечение необход. ему памяти, в то же время верно и обратное: за счет увелечение временной сложности можно понизить его емкостную сложность. Более эффективный алг. приводит к программам большего размера и требуют больших усилий на его разработку.
Пример (пузырек). n размер массива, С - кол-во сравнений, М-кол-во обменов. Сортирока n-1 просмотр. На i-ом просмотре выполняется n-i сревнений.
Это значение не зависит от начального расположения элементов в массиве. Число обменов зависит от расположения элементов. Ммин=0 (упорядоченное) Ммах=3*С (см. формулу), Мср= (Ммин+Ммах)/2
Значить временная сложность О(n2).
10. Вспомогательные алгоритмы. Реал-ция вспом-х алг. на Паскале. Механизм передачи параметров.
Âñï. àëã - ýòî ïîâòîðÿþùàÿñÿ ãðóïïà îïðåòîðîâ îôîðìëåííàÿ â âèäå ñàìîñòîÿòåëüíîé ïðîãàìíîé åäиíèöû.
 ÿçûêå Ïàñêàëü èìååòñÿ äâå pàçíî-òè ïîäïpîãpàìì - ïpîöåäópû è ôóíêöèè.
Ïîäïpîãp.-ïpîöåäópà ïpåäíàçíà÷. äëÿ âûïîëíåíèÿ êàêîé-òî çàêîí÷åííîé ïîñëåäîâàòåëüíîñòè äåéñòâèé. Ëþáàÿ ïpî öåäópà ñîñòîèò èç çàãîëîâêà:
procedure <èìÿ ïpîöåäópû>(<ñïèñîê ôîpìàëíûõ ïàpàìåòpîâ>);
<pàçäåë îïèñàíèé>;
begin <òåëî ïpîöåäópû> end;
Çà çàãîëîâêîì èäóò òå æå pàçäåëû, ÷òî è â îñíîâíîé ïpîãpàììå.
Функции. Ïîäïpîãp.-ôóíêöèÿ ïpåäíàçíà÷. äëÿ âû÷èñëåíèÿ êàêîãî-ëèáî çíà÷åíèÿ.
Îïèñàíèå:
function <èìÿ ôóíêöèè>(<ñïèñîк фоpмалных паpаметpов>):<тип функции>;
[<pаздел описаний>;]
begin <тело функции> end;
За заголовком идут те же pазделы, что и в основной пpогpамме.
В теле функции хотябы pаз имени функции должно быть пpисвоено значение!.
Подпpогpамма должна быть описана до того, как она будет использоваться в пpогpамме или дpугой подпpогpам. Результат выполнения проц. одно или несколько значений. При вызове проц. формаль. заменяются фактическими. Фактические это параметры которые передаются процедуре при обращении к ним. Формальные параметры - это переменные фиктивно присутствующие в проц. над которыми производиться действие. Формальные делятся на параметры-перемн-е(ПП) и параметры-значения (ПЗ). ПП - со словом var, необходимы для изменения значений фачтических параметров. ПЗ - без var, при вызове передаётся только копия изменение формальных параметров не отражается на фактических.
Все паpаметpы, можно pазбить на две ка тегоpии: локальные паpаметpы, объявленные внутpи подпpогpаммы и доступные только ей самой, и ãëîáàëüíûå, îáúÿâëåííûå â ñàìîé ïpîãpàììå è äîñòóïíûå êàê ïpîãpàììå,òàê è ïîäïpîãp.
Ëîêàëüíûå ïàðàìåòðû ñóù. ïîêà ðàáîòàåò ïîäïðîãðàììà.
Ïpîöåäópà ìîæåò âûçûâàòü ñàìà ñåáÿ (påêópñèÿ), íî ýòî â îñíîâíîì ïpèìåíÿþò ê ôóíêöèÿì.
Передача параметров является важным. При вызове подпрограммы ЭВМ выполняет следующие действия: выделяет память для перемнных описанных в подпрограмме, присваивает формальных значение фактических, выполняет операторы подпрограммы, идет возврат в точку вызова и выполн. след. оператор в программе. При этом пересылка параметров идет по значению (передается значение ) и по ссылке (передается адрес ячейки куда будет записано новое знчение). Локальным переменным выделяется память тольео при обращении, после она освобождается.
12. Алгорнитмы сортировки и их сравнение.
Процесс упорядочивания заданного множества объектов назыв. сортировкой.
Может быть по возрастанию и убыванию.
Постановка задачи. Дан массив элементов нужно расположить их в порядке возр. (убыв.). Существует много методов сорт. отлич. степенью эффективности (кол-во сравнений и кол-во обменов). Виды: простой выбор, простого обмена, прямого включения, слияния, Хоара и т.д.
1.Простой выбор: Применяется для массива без повтор. элементов. Суть: 1) Выбрать мах эл-т 2) Поменять местами с последним 3) Повторить 1) 2) с оставшимися элементами.
begin
for i:=10 downto 2 do begin k:=i; m:=a[i]
for j:=2 to i-1 do
if a[j]>m then begin k:=j m:=a[k] end
if k<>i then begin a[k]:=a[i] a[i]:=m end end
2.Простой обмен (пузырь): Для любого массива. Суть: просмотр от начала к концу и обмен соседних элементов по принципу i<j a[i]>a[j].
3.Прямого включения: Для массива без повтор. элементов. Суть: На к шаге к-1 элемент уже отсортирован, для к ищем место в уже отсортированой части и вставляем его туда.
Сравнение по кол-ву сравнений:
1. С - кол-во сравнений. При первом проходе выполняется n-1 сравнений при втором n-2 и т.д. С(мин) = С(мах) = n(n-1)/2
2. Выполняется n-1 просмотров на каждом i просмотре выполняется n-i сравнений. С(мин) = С(мах) = n(n-1)/2
3. Число сравнений на i шаге С(i) самое меньшее =1 (элемент a[i] на своем месте), самое большее i (элемент a[i] меньше всех предедущих). Среднее (i+1)/2.
С(мин)=n-1 C(max)=(n2+n-2)/2
она работает естественно, тем эффектив. чем ближе массив к отсортиров. В принципе сложность пропрорц. n2
14. Програмное обесапечение. Состав ПО. Назначение различных ПО.
ПО - совокупность программ для ообработки данных и необходимой для их эксплуатации документов. ПО делится на 1.системное 2. прикладное. 3. инструментальное. 1. Совокупность программ для обеспечения работы компа и сетей. Делится на базовое(а)опреционная система (ОС), б)операц. оболочка, в) сетевая операц. система) мин. набор программ обесмпечивающ. работу компа. Сервисное (а) диагностич., б) антивир в) архиваторы г) обслуживание дисков д) обслуживан. сетей), для более удобной работы пользов. со средой. ОС. Программа управляющ. ресурсами компа и кординир. их работу. Бывает одно и многозадачные, одно и много пользовательские, переносимые и непереносимые на др. компы, сетевое и несетевое. ОО. Программы предназначенные для облегчения работы челов. с компом (NC, DN). 2. Включают ТР, ЭТ, СУБД, ГР. 3. Включает языки программирования для создания ППО и СПО.
16. Построение выпуклой оболочки заданного множества точек и многоугольника.
Выпукл. обол. - ломанная линия мин. длины ограничив. фигуру.
Дано тонкая линия, должны получить жирную линию. При обходе ломонной осуществ. поворот по часовой или против часвой стрелке. Поворот по часовой больше нуля. После полного обхода и возврата в начю точку будет 3600. Для выпукл. фигуры все повороты правые или левые. Алг. для правых углов. 1. Просматрив. все тройные точки А(к), А(к+1), А (к+2). 2. Определ. угол поворота, если угол левый то выбрасываем А(к+1) и просматриваем А(к-1), А(к), А(к+2), если правый, то А(к+1), А(к+2), А (к+3). Проверяем пока не замкнется и +1 вершина. Поворот судим по знаку векторного произвед.
Построен. вып. обол. множества точек. Исходной ломонной линии нет, есть массив координ.(точек). Чтобы воспльзов. прежним алгор. нужно построить ломанную линию, которая соеденяет все точки и не имеет самопересечений. Для построения ломанной отсортируем массив по Х. Построение оболочки будем строить из двух частей: верхней и нижней. В первом случае точки рассматрив. от 1 до послед., во втором в обратном порядке. В ходе просмотра будем проверять напралениве поворота для тройных точек. Т.к. первая и последняя точка входит в оболочку, то не требуется действий по замыканию оболочки.
Алг для построен. оболочки связ. фигуры. Х, У - массивы координат, Т - границы, m - число отрезков в границе фигуры. i:=1; j:=3; k:=m+2; while i<=k do begin T[i+2]:=T[j]; y1:=y[T[i]]; x1:=x[T[i]]; y2:=y[T[i+1]]; x2:=x[T[i+1]]; y3:=y[T[i+2]]; x3:=x[T[i+2]]; if (x2-x1)*(y3-y2)>=(x3-x2)*(y2-y1) then begin inc(i); inc (j); end; else if i>1 then dec(i) else begin T[i+1]:=T[i+2]; inc(j) end; if j>m then begin j:=1; k:=i+1; {замыкаем оболочку}end; end; m:=k-j+3{число отрезков в оболочке}for i:=1 to m do T[i]:=T[i+j-1]{сдвиг в начало массива Т}
18. Геометрический поиск. Его виды и меры оценки. Поиск устанавливает связи между образцом, т.е. заданным элементом и набором данных. Поиск сводится к определению позиции соответсв. элемента в наборе данных. Геомет. поиск отличается от обычного: в геометрич. приложениях набор данных достаточно сложная структура. Результатом поиска оказываются не сам элемент, а его положение относительно др. Поисковое сообщение по которому ведется просмотор данных наз-ся запрос. От типа набора данных зависит организация ГП и алгоритм обработки. Если вопрос возникает один раз, то проводить предварительн. обработку для ускорения след. запросов не выгодно. Если запрос массовый, то предварительная обработка. Такую предобработку проводят только затратив какой-то ресурс, по этому анализ алг. сосредат-ся на 4 мерах его оценки. 1. Время запроса (время одного ответа) 2. Память (объем для хранения выбронных структур данн ых, предобработка)3. Сколько времени для организации данных, т.е. сам поиск 4. Время корректировки - сколько времени для включения или удаления заданного элемента. Задачи ГП делятся на задачи локализации и региональн. поиска. Задача локализ(метод полос). Дан плоский связанный грав n вершин. Через них проводим прямые паралельн. оси ОХ (n+1 полоса), отсортируем по координате У и найдем ту полосу где лежит точка. Полоса пересекает некоторые ребра. Отрезки определяют трапеци или прямоугольн. Отрезки ребер внутри полос не пересекаются. Внутри полосы упорядочить отрезки ребер и найти к какой трапеции принадлежит тоочка. Региональный поиск подсчет. Дано n точек на плоскости, подсчитать сколько из них лежит внутри заданного прямоуг. (стороны парал. осям). 1 метод. (в лоб) затрачивается много времени, т.к. анализир все координаты. Метод локусов. Для каждой вершины P прямоуг. вычесляется количество точек лежащих внутри прямоуг. ограничеваемого осями коорд. и прямыми парал. осям проход. ч/з вершину. Количесво таких точек Q(P): N=Q(P1)-Q(P2)-Q(P4)+Q(P3) Т.о. задача регион. поиска сводится к задаче о доминиров. для 4 точек.