- •Конспект лекций по курсу «Информатика» для студентов очной и заочной форм обучения.
- •Базовые положения
- •§.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.2. Упорядоченные структуры информационных объектов
Напоминание:
информация (для автомата ЭВМ) это-состояние (битовое содержимое) информационного объекта (носителя информации),
каждый информационный объект имеет уникальное имя (имя собственное, название, адрес в памяти ЭВМ).
Опр. Индексное имя информационного объекта это - название составленное из последовательности символов и натурального числа – собственно индекса.
Пример:
математическая запись индексных имен: а5, Тi
и, аналогичные им, записи на языке Pascal: a[5], T[i].
Системы индексных имен характеризуются «естественной упорядоченностью», т.к. это свойство присуще натуральным числам – обязательной составляющей индексированного имени. Например, имя w5 предшествует имени w7, поскольку индекс (число) 5 меньше индекса (числа) 7.
Опр. Сортировка информации – процесс согласования (установления взаимосвязи) содержимого информационных объектов с их индексными номерами.
Опр. Выборка {ai}, i=1, 2, ...n, называется попарно упорядоченной по операции сравнения P, если для любых двух последовательных объектов ai и ai+1 i=1,2,..,(n-1) выполняется P(ai,ai+1)=true.
Пример: четыре информационных объекта {a1, a2, a3, a4} , содержащие числа {3.5, -2.7, -2.0, 1.1} упорядочены «по убыванию абсолютной величины их значений», т.е. по операции сравнения P(a, b) = |a| > |b|.
8.3. Алгоритм сортировки «поплавок»
Проводим последовательное (слева направо) попарное сравнение элементов массива, т.е. вычисляем P(ai,ai+1) для i=1, 2, ...n-1,
Если P(ai,ai+1)=false, то меняем содержимое информационных объектов ai и ai+1 местами.
В результате разового просмотра всех пар объектов, что требует выполнения (n-1)-ой операции сравнения, самая «правая» («самая последняя в данной выборке») информация, действительно окажется в самом последнем элементе массива, т.е. в элементе an.
Для упорядочения всей информации выборки, следует повторить пункты (1) и (2) (n-1) раз, причем при каждом очередном повторении количество просматриваемых и сравниваемых объектов сокращается на единицу.
На вопрос о возможном упорядочении информации массива {ai}, i=1, 2, ...n сообразно операции сравнения P(ai, aj) отвечает следующая теорема.
Теорема 1. Выборка {ai}, i=1, 2, ...n может быть попарно отсортирована, если используемая операция сравнения P(ai,aj) антикоммутативна, однако результат сортировки может оказаться неоднозначным.
Теорема 2: Выборка {ai}, i=1, 2, ...n может быть однозначно отсортирована, если используемая операция сравнения P(ai,aj) антикоммутативна и дистрибутивна.
Поскольку алгоритм сортировки «поплавок» основан на попарном сравнении элементов, он гарантирует линейную упорядочиваемость информации только в том случае, если используемая операция сравнения действительно антикоммутативна и транзитивна.
Сортировка это–процесс получения (создания) новой информации, которая описывает взаимосвязь содержимого совокупности объектов с их именами (индексами). Для размещения этой информации необходимы соответствующие материальные носители, т.е. ячейки памяти ЭВМ.