- •Конспект лекций по курсу «Информатика» для студентов очной и заочной форм обучения.
- •Базовые положения
- •§.1. Физическое устройство и разумная деятельность мозга
- •§2. Самодостаточная эвм
- •2.1. Память (оперативная память)
- •2.2. Процессор
- •2.3. Программа
- •2.4. Жизненный цикл «Самодостаточной эвм»
- •§3. Язык процессора – базовый язык эвм
- •§4. Реальная эвм. Периферийные устройства
- •§5. Язык программирования. Программа транслятор
- •§6. Язык программирования Pascal
- •6.1. Базовые типы числовых информационных объектов
- •6.2. Явные константы
- •6.3. Оператор описания var
- •Var и1, и2, и3, . . . . ,Иn: Итипа;
- •6.5. Операторы консольного ввода информации
- •6.5.1. Стандартные форматы вывода числовой информации.
- •6.6. Логические переменные
- •6.7. Операторы управления программой
- •6.7.1. Условный оператор if then
- •If Условие then Оператор ;
- •6.7.2. Условный оператор выбора if then else
- •6.8. Метки операторов. Оператор безусловного перехода
- •6.9. Циклические вычисления. Операторы зацикливания
- •Организация циклических вычислений операторами if then goto
- •Программа вычисления корня по формуле Герона.
- •6.9.3. Оператор цикла for to
- •6.9.4. Оператор цикла for downto
- •6.9.5. Оператор цикла while
- •6.9.6. Программа вычисления длины дуги кривой
- •7. Массивы переменных
- •7.1. Программа нахождения экстремальных значений
- •7.2. Программа решения системы линейных алгебраических уравнений
- •8. Сортировка информации
- •8.1. Элементы формальной логики, теории множеств и операций
- •8.2. Упорядоченные структуры информационных объектов
- •8.3. Алгоритм сортировки «поплавок»
- •8.3.1. Программа сортировки массива «на месте»
- •8.3.2. Программа сортировки «индексов» массива
- •8.4. Алгоритм быстрого поиска информации в линейно упорядоченном массиве
- •8.4.1. Программа поиска в отсортированных массивах.
- •9. Символьные переменные
- •9.1.Строковые переменные
- •9.1.1. Программа написания чисел прописью
- •10. Клавиатурное управление эвм
- •§.11. Информационные объекты класса – изображение
- •11.1. Устройство функционированиемонитора
- •11.2. Процедурный язык управления графическим экраном
- •11.3. Оцифровка и масштабирование реальных изображений (чертежей) для последующего их вывода на экран
- •11.4. Пример построения фрагмента графика функции
- •11.5. Ввод и обработка информации в форме изображений
- •§12. Информационные объекты класса – подпрограммы
- •12.1. Подпрограммы типа procedure
- •12.1.1. Пример оформления подпрограммы-процедуры
- •12.2. Подпрограммы класса function
- •12.2.1.Пример оформления подпрограммы-функции
- •12.3. Процедурные языки программирования
- •12.4. Библиотечные модули Unit
- •§13. Динамическое распределение оперативной памяти эвм
- •13.1. Программа использующая динамические переменные
- •§14. Переменные типа record
- •§15. Внешняя память эвм. Работа с файлами
- •15.1. Процедурный язык обработки файлов
- •15.2.Программа “ Жизненный путь файла “
- •15.3. Текстовые файлы
- •§16. Элементы объектно-ориентированного программирования
- •Основная рекомендуемая литература.
8. Сортировка информации
8.1. Элементы формальной логики, теории множеств и операций
Опр. Множество – совокупность объектов (частей всеобщности) выделяемых из всеобщности по факту удовлетворения (соответствия) указанному перечню признаков (свойств, характеристик).
Примеры:
1) множество целых чисел (счетное количество),
2) множество действительных чисел на отрезке [2, 5] (несчетное количество – continuum),
3) множество книг в библиотеке или документов в архиве (теоретически конечное),
4) множество разновидностей млекопитающих животных.
Опр. Выборка (массив) – конкретный (частный) набор конечного числа элементов, выбираемых из множества.
Примеры:
1) выборка (массив) из пяти целых чисел {-3, 2, 7, -6, 2}
2) массив из четырех точек плоскости, заданных декартовыми координатами (xi, yi) : { (2.5, 7.3), (-1.4, 0.3), (0. 21, -0.3), (8, 8)}
Опр. Операцией сравнения называется последовательность действий, проводимых над содержимым упорядоченной пары объектов (a, b), если ее результатом является булевская (логическая) переменная.
Математическая запись операции сравнения
либо true (1)
P(a, b) =
либо false (0)
Примеры записи конкретных операций сравнения:
P(a, b) = a<b сравнение чисел a и b «на возрастание их значений»,
P(a, b) = |a| > |b| сравнение векторов a и b «на убывание их модулей»,
P(a, b) = Sin(a) < Cos (b) сравнение чисел a и b «на возрастание значений функций Sin(a) и Cos(b) примененных, соответственно, к числам a и b»,
P(a, b) = (a=b) сравнение чисел a и b «на совпадение их значений».
Терминология: если P(a, b) = true, то говорят, что содержимое объекта a (или сам объект a ) предшествует (находится левее, появляется ранее, является первичным) содержимому объекта b (самому объекту b ).
Важно усвоить:
- если P(a, b) = false, то следует говорить, что объект a не предшествует объекту b, причем это отрицание вовсе не эквивалентно утверждению: объект b предшествует объекту a,
операции сравнения, несмотря на простоту своего результата (да/нет), зачастую очень трудоемки и сложно реализуемы,
операции сравнения присущи, явно или завуалировано, всем операциям обработки информационных объектов: арифметическим действиям, преобразованию данных при вводе-выводе и т.д. и т.п.
На основе введенной операции сравнения и базовых операций формальной логики (and- объединение двух утверждений союзом «И», not – отрицание утверждения) можно построить операцию распознания эквивалентности объектов a, b:
true объекты эквивалентны
Э(a, b) = P(a, b) and P(b, a) =
false объекты разные
Математическая форма записи операции эквивалентности a~b = (a<b) & (b<a) озвучивается утверждением «объект a предшествует объекту b и объект b предшествует объекту a ».
Пример: вектора (3, 4, 7) и (7, 0, 5) будут эквивалентны для операции их сравнения «по модулю».
Интересно, что именно на основе операции сравнения P(a,b), в можно сформулировать операцию N(a,b)-проверки несопоставимости (несравнимости) объектов a и b:
true объекты не сравнимы
N(a, b) = (not P(a, b) ) and (not P(b, a)) =
false объекты сравнимы,
которая может быть озвучена утверждением: «объект a не предшествует объекту b и объект b не предшествует объекту a»
Пример: для операции сравнения двух векторов из R2
true, если ax>by
P( (ax, ay), (bx, by)) =
false, если ax≤by
вектора (3, 7) и (5, 4) являются несопоставимыми, а вектора (3, 7) и (9, 4) будут сопоставимы. Для этой операции сравнения, несопоставимыми будут даже «одинаковые» вектора a=(3, 7) и b=(3, 7)!
Операция проверки строгой упорядоченности пары объектов (a, b), в указанном порядке их следования, также строится на основе операции сравнения P(a, b):
true, есть строгая упорядоченность
S(a, b) = P(a, b) and (not P(b, a)) =
false, нет строгой упорядоченности,
и может быть озвучена утверждением: «объект a предшествует объекту b, но объект b не предшествует объекту a»
Пример: для вышеописанной операции сравнения следует, что вектора
(4, 5) и (7, 3) строго упорядочены.
Опр. Множество {ai} называется условно упорядоченным по операции сравнения Р, если для каждого его элемента ai существует хотя бы один элемент aj, такой что P(ai, aj)=true.
Опр. Множество {ai} называется попарно упорядоченным по операции сравнения Р, если для любых его элементов ai и aj выполняется P(ai, aj) ≠ P(aj, ai), а сама операция сравнения P(a,b) называется антикоммутативной.
Пример: знакомая со школы операция сравнения чисел P(a,b)=a<b антикоммутаnивна!
Опр. Множество {ai} является транзитивным по операции сравнения Р, а сама операция Р – транзитивной, если из условий P(ai,aj)=true и P(aj,ak)=true обязательно следует P(ai, ak) =true.
Опр. Множество {ai} называется линейно упорядоченным по операции сравнения Р, если эта операция транзитивна и антикоммутативна.
Пример: числовые множества (натуральные, целые, рациональные и действительные) транзитивны по антикоммутативной операции сравнения P(a,b)=a<b.
Важно отличать свойство упорядоченности множества, от упорядоченности конечной выборки из некоего множества: из не упорядочиваемого множества иногда можно выбрать линейно упорядоченную совокупность элементов.