Інформатика:загальні питання
Матеріал з USIC Wiki
|
Ця стаття відноситься до групи довідкових статей для студентів ФІН. |
Зміст |
Поняття алгоритму.
Означення алгоритму
Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович)
«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio)
«Алгоритм — это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич)
«Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм». ([grey_olli])
«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».
«Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:
- 1. дискретны;
- 2. детерминированы;
- 3. потенциально конечны;
- 4. преобразовывают некоторые конструктивные объекты.
Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев)
Формальні ознаки алгоритмів
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
- Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа.
- Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
- Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
- Массовость — алгоритм должен быть применим к разным наборам исходных данных.
Важную роль играют рекурсивные алгоритмы (алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения). В последнее время активно разрабатываются параллельные алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одноврем
- Часова складність-
Основні поняття об’єктно орієнтованого програмування.
- Абстракция данных
Объекты представляют собою упрощенное, идеализированное описание реальных сущностей предметной области. Если соответствующие модели адекватны решаемой задаче, то работать с ними оказывается намного удобнее, чем с низкоуровневым описанием всех возможных свойств и реакций объекта.
Инкапсуляция
- Инкапсуляция — это принцип, согласно которому любой класс должен рассматриваться как чёрный ящик — пользователь класса должен видеть и использовать только интерфейсную часть класса (т. е. список декларируемых свойств и методов класса) и не вникать в его внутреннюю реализацию. Поэтому данные принято инкапсулировать в классе таким образом, чтобы доступ к ним по чтению или записи осуществлялся не напрямую, а с помощью методов. Принцип инкапсуляции (теоретически) позволяет минимизировать число связей между классами и, соответственно, упростить независимую реализацию и модификацию классов.
Наследование
- Наследованием называется возможность порождать один класс от другого с сохранением всех свойств и методов класса-предка (прародителя, иногда его называют суперклассом) и добавляя, при необходимости, новые свойства и методы. Набор классов, связанных отношением наследования, называют иерархией. Наследование призвано отобразить такое свойство реального мира, как иерархичность.
Полиморфизмом
- Полиморфизмом называют явление, при котором один и тот же программный код (полиморфный код) выполняется по-разному в зависимости от того, объект какого класса используется при вызове данного кода. Полиморфизм обеспечивается тем, что в классе-потомке изменяют реализацию метода класса-предка с обязательным сохранением сигнатуры метода. Это обеспечивает сохранение неизменным интерфейса класса-предка и позволяет осуществить связывание имени метода в коде с разными классами — из объекта какого класса осуществляется вызов, из того класса и берётся метод с данным именем. Такой механизм называется динамическим (или поздним) связыванием — в отличие от статического (раннего) связывания, осуществляемого на этапе компиляции программы.
Принципи криптографічного захисту інформації.
М - простір повідомлень.
m - повідомлення з М
Якщо існує певна процедура E(_k,k')(m), яка ствавить у відповідність кожному повідомленню певний код с, то цей код і називається шифром, або криптотекстом.
k і k'(ключі) - це елементи криптосистеми, які є основою кожної системи і, змінюючи їх, повинно змінюватись все кодування.
k - ключ, за допомогою якого закодовують.
k' - ключ, за допомогою якого розкодовують.
Процедура E(_k,k')(m), разом з ключами називається криптосистемою.
Симетричні криптосистеми - це криптосистеми, у яких k = k'.
Асиметричні криптосистеми - це криптосистеми, у яких k != k'.
Блочні шифри:
Вхідне повідомлення ділиться на певні однакові частини(блоки) і кожна з цих частин по черзі і НЕЗАЛЕЖНО обробляється криптосистемою. Результуючим шифром буде об'єднання результатів роботи криптосистеми.
Потокові шифри:
Вхідне повідомлення обробляється таким чином, що на закодовування кожного наступного блоку впливає результат попередньої роботи.
Шифри заміни - це шифри, в яких кожній букві(слову,символу, біту...) ставиться у відповідність якийсь інший символ, або комбінація символів.
Шифри перестановок - це шифри, в яких у вхідному повідомленні за певним алгоритмом і залежно від ключа робиться перестановка символів(слів, бітів ...) у вхідному повідомленні.
Шифр Цезаря.
Ототожнюємо алфавіт, з якого побудоване вхідне повідомлення, з кільцем лишків Z(_n), де n - кількість літер в алфавіті. Вибираємо k, яке належить Z(_n).
Кожна літера x вхідного повідомлення кодується, як c = x+k mod n.
Ключем даної криптосистеми є k.
Частотний аналіз - ідеологія криптоатак, яка базується на визначенні частоти появи символів у зашифрованому тексті.
Ідея К.Гауса, що унеможливлює частотний аналіз:
Спочатку кожній літері алфавіту ставиться у відповідність певна множина можливих кодів цієї літери. При чому чим частіше ця літера зустрічається в мові, тим більша множина їй ставиться у відповідність. Крім того такі множини не повинні перетинатись. А далі при закодуванні з такої множини рендомом обирається код для відповідної літери.
Оскільки одна і та ж літера може бути закодована різними кодами, то за допомогою частотного аналізу стає практично неможливо атакувати криптосистему.
Базові принципи фон Нейманівської архитектури.
Более чем за полвека развития вычислительных средств прогресс в аппаратной реализации ЭВМ и их технических характеристик превзошел все прогнозы, и пока не заметно снижение его темпов. Несмотря на то, что современные ЭВМ внешне не имеют ничего общего с первыми моделями, основополагающие идеи, заложенные в них и связанные с понятием алгоритма, разработанным Аланом Тьюрингом, а также архитектурной реализацией, предложенной Джоном фон Нейманом, пока не претерпели коренных изменений (за исключением систем параллельной обработки информации).
Любая ЭВМ неймановской архитектуры содержит следующие основные устройства:
- арифметико-логическое устройство (АЛУ);
- устройство управления (УУ)
- запоминающее устройство (ЗУ);
- устройства ввода-вывода (УВВ);
- пульт управления (ПУ).
В современных ЭВМ АЛУ и УУ объединены в общее устройство, называемое центральным процессором. Обобщенная логическая структура ЭВМ представлена на рис. 1.3.
Процессор, или микропроцессор, является основным устройством ЭВМ. Он предназначен для выполнения вычислении по хранящейся в запоминающем устройстве программе и обеспечения общего управления ЭВМ. Быстродействие ЭВМ в значительной мере определяется скоростью работы процессора. Для ее увеличения процессор использует собственную намять небольшого объема, именуемую местной или сверхоперативной, что в некоторых случаях исключает необходимость обращения к запоминающему устройству ЭВМ.
Вычислительный процесс должен быть предварительно представлен для ЭВМ в виде программы — последовательности инструкций (команд), записанных в порядке выполнения. В процессе выполнения программы ЭВМ выбирает очередную команду, расшифровывает ее, определяет, какие действия и над какими операндами следует выполнить. Эту функцию осуществляет УУ. Оно же помещает выбранные из ЗУ операнды в АЛУ, где они и обрабатываются. Само АЛУ работает под управлением УУ.
Обрабатываемые данные и выполняемая программа должны находиться в запоминающем устройстве — памяти ЭВМ, куда они вводятся через устройство ввода. Емкость памяти измеряется в величинах, кратных байту. Память представляет собой сложную структуру, построенную по иерархическому принципу, и включает в себя запоминающие устройства различных типов. Функционально она делится на две части: внутреннюю и внешнюю.
Внутренняя, или основная память — это запоминающее устройство, напрямую связанное с процессором и предназначенное для хранения выполняемых программ и данных, непосредственно участвующих в вычислениях. Обращение к внутренней памяти ЭВМ осуществляется с высоким быстродействием, но она имеет ограниченный объем, определяемый системой адресации машины.
Внутренняя память, в свою очередь, делится на оперативную (ОЗУ) и постоянную (ПЗУ) память. Оперативная память, по объему составляющая" большую часть внутренней памяти, служит для приема, хранения и выдачи информации. При выключении питания ЭВМ содержимое оперативной памяти в большинстве случаев теряется. Постоянная память обеспечивает хранение и выдачу информации. В отличие от содержимого оперативной памяти, содержимое постоянной заполняется при изготовлении ЭВМ и не может быть изменено в обычных условиях эксплуатации. В постоянной памяти хранятся часто используемые (универсальные) программы, и данные, к примеру, некоторые программы операционной системы, программы тестирования оборудования ЭВМ и др. При выключении питания содержимое постоянной памяти сохраняется.
Внешняя память (ВЗУ) предназначена для размещения больших объемов информации и обмена ею с оперативной памятью. Для построения внешней памяти используют энергонезависимые носители информации (диски и ленты), которые к тому же являются переносимыми. Емкость этой памяти практически не имеет ограничений, а для обращения к ней требуется больше времени, чем ко внутренней.
Внешние запоминающие устройства конструктивно отделены от центральных устройств ЭВМ (процессора и внутренней памяти), имеют собственное управление и выполняют запросы процессора без его непосредственного вмешательства. В качестве ВЗУ используют накопители на магнитных и оптических дисках, а также накопители на магнитных лентах.
ВЗУ по принципам функционирования разделяются на устройства прямого доступа (накопители на магнитных и оптических дисках) и устройства последовательного доступа (накопители на магнитных лентах). Устройства прямого доступа обладают большим быстродействием, поэтому они являются основными внешними запоминающими устройствами, постоянно используемыми в процессе функционирования ЭВМ. Устройства последовательного доступа используются в основном для резервирования информации.
Устройства ввода-вывода служат соответственно для ввода информации в ЭВМ и вывода из нее, а также для обеспечения общения пользователя с машиной. Процессы ввода-вывода протекают с использованием внутренней памяти ЭВМ. Иногда устройства ввода-вывода называют периферийными или внешними устройствами ЭВМ. К ним относятся, в частности, дисплеи (мониторы), клавиатура, манипуляторы типа «мышь», алфавитно-цифровые печатающие устройства (принтеры), графопостроители, сканеры и др. Для управления внешними устройствами (в том числе и ВЗУ) и согласования их с системным интерфейсом служат групповые устройства управления внешними устройствами, адаптеры или контроллеры.
Системный интерфейс — это конструктивная часть ЭВМ, предназначенная для взаимодействия ее устройств и обмена информацией между ними.
В больших, средних и супер-ЭВМ в качестве системного интерфейса используются сложные устройства, имеющие встроенные процессоры ввода-вывода, именуемые каналами. Такие устройства обеспечивают высокую скорость обмена данными между компонентами ЭВМ.
Отличительной особенностью малых ЭВМ является использование в качестве системного интерфейса системных шин. Различают ЭВМ с многошинной структурой и с общей шиной. В первых для обмена информацией между устройствами используются отдельные группы шин, во втором случае все устройства ЭВМ объединяются с помощью одной группы шин, в которую входят подмножества шин для передачи данных, адреса и управляющих сигналов. При такой организации системы шин обмен информацией между процессором, памятью и периферийными устройствами выполняется по единому правилу, что упрощает взаимодействие устройств машины.
Пульт управления служит для выполнения оператором ЭВМ или системным программистом системных операций в ходе управления вычислительным процессом. Кроме того, при техническом обслуживании ЭВМ за пультом управления работает инженерно-технический персонал. Пульт управления конструктивно часто выполняется вместе с центральным процессором.
Основні принципи побудови і функціонування компіляторів.
- Синтаксический анализатор (парсер) - компонент компилятора, проверяющий исходные операторы на соответствие синтаксическим правилам и строящий дерево грамматического разбора, отображающее конкретные семантические связи языковых конструктов программы. Для упрощения выделения и опознания языковых конструктов используется лексический анализатор (сканер).
- Синтаксический анализатор проверяет правильность входной программы по грамматике языка, реализуя принцип синтаксической управляемости языкового процессора.
- Лексический анализатор (сканер) - не только перекодирует входную программу, но и собирает (агрегирует) информацию в специальных сводных таблицах.
- Семантичний або контекстний аналізатор як компонент мовного процесора перевіряє семантичну узгодженість вживання у програмі мовних конструктів. Це найбільш залежна від мови програмування частина транслятора, проте для кожної мови реалізуються наступні функції:
- - виконати перевірку контекстних умов в програмі;
- - провести розподіл пам’яті;
- - провести синтез програмного коду у єдиний модуль.
- Генератор коду – компонент компілятора, який збирає скомпільований код у єдиний модуль. При цьому обов’язково проводиться оптимізація.
- Потім цей модуль компонується (лінкується) з іншими, чим підтримується модульний принцип програмування. Проте компонувальним складає частину не транслятора, а інструментального середовища розробки програм. Сюди входить і Debuger, за допомогою якого модуль тестується і налагоджується, тобто в ньому шукаються і виправляються помилки. Головна функція Debuger’а – емуляція злінкованого модуля для отримання траси його виконання і перевірки проміжних і підсумкових результатів виконання.
Розглянемо схему компілятора, в якому:
- 1 - исходный текст программы;
- 2 - таблица терминальных символов языка (ключевые слова if, then и т.д.);
- 3 - лексическая свертка программы (промежуточная программа, удобная для работы парсера);
- 4 - правила грамматики (правила и аксиомы грамматики);
- 5 - дерево вывода (дерево грамматического разбора программы);
- 6 - абстрактная программа (атрибутное дерево программы) Отличия атрибутного дерева от дерева вывода: узлы снабжаются атрибутами (со ссылками на таблицу имен или к другим узлам атрибутного дерева, конкретными вычисленными значениями);
- 7 - некоторая промежуточная программа после машинно-независимой оптимизации. Может быть несколько этапов такой оптимизации и несколько форм представления машинного кода;
- 8 - таблица содержит кодовые продукции или заготовки, шаблоны по которым строится следующая версия промежуточной формы 9;
- 9 - код ассемблера или команды, напоминающие ассемблер. Возможно, для кода 9 еще не было распределения регистров.
Класифікація сучасного апаратного забезпечення.
- Прикладні – текс.ред, ігри, …
- Системні(с HardWare) – для підтримки ф-ня комп-ра,
- ОССАПР – компілятори, інструментальне середовище розробки, …
