Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 9 лет назад пользователемВиктор Якушов
1 Основы информатики Лекция 1. Алгоритм Заикин Олег Сергеевич
2 Заикин Олег Сергеевич к.т.н. н.с. Института динамики систем и теории управления СО РАН ст. преп. кафедры Информационных технологий ИМЭИ ИГУ Научные интересы: параллельное программирование, криптография О себе
3 Структура курса базовые алгоритмы и структуры данных введение в программирование на языке C++
4 Рекомендуемая литература Алгоритмы и структуры данных 1. Левитин А. В. Алгоритмы: введение в разработку и анализ 2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е издание Программирование на C++ 1. Герберт Шилдт. Базовый курс C++, 3-е издание Бьерн Страуструп. Язык программирования С++ (в качестве справочника)
5 Информатика – наука о способах получения, накопления, хранения, преобразования, передачи и использования информации. Информация – совокупность сведений о людях, предметах, процессах независимо от способа их представления. Данные – информация, представленная в формализованном виде. Данные допускают обработку с помощью технических средств.
6 Информатика Термин возник в 60-х годах во Франции для названия области, занимающейся автоматизированной переработкой информации, как слияние французских слов information и automatique Отдельной наукой была признана лишь в 1970-х Высшая награда – премия Тьюринга (с 1966 г.)
7 Информатика Разделы: Общие сведения об информации Аппаратное и программное обеспечение Обработка информации (текстовой, графической, мультимедийной) Базы данных Алгоритмизация и программирование Локальные и глобальные компьютерные сети
8 8 Определение алгоритма Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность. (Д. Кнут). Алгоритм последовательность четко определенных инструкция, позволяющих получить из корректных входных данных требующиеся выходные данные за ограниченный промежуток времени. (А. Левитин). Обычно в качестве исполнителя выступает некоторый механизм (компьютер, человек, т.п.)
9 9 Определение алгоритма Формальное определение: Тезис Черча-Тьюринга: Для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга т. е. некоторый алгоритм для нахождения значений функции существует тогда и только тогда, когда функцию можно вычислить на машине Тьюринга. « вычислить на машине Тьюринга » – значит можно написать соответствующую программу для машины Тьюринга.
10 10 Определение алгоритма Проблема в требовании конечности алгоритма. Из формального математического определения алгоритма ( через тезис Черча - Тьюринга ) не следует конечность шагов. Ведь можно написать программу для машины Тьюринга, которая никогда не остановится. В информатике требование конечности алгоритма означает, что алгоритм находит решение задачи ( требуемый выход ) если он j существует, за конечное число шагов. Если искомого результата не существует, алгоритм или никогда не завершает работу, либо заходит в тупик.
11 11 Определение алгоритма Например, Д. Кнут определяет алгоритм, с нарушенным условием конечности, как « метод вычислений ». Пример алгоритма, который никогда не остановится ?
12 12 Входные и выходные данные Для каждого алгоритма есть некоторые множества объектов, допустимых в качестве входных и выходных данных. Например, в алгоритме деления вещественных чисел есть ограничение на вход - делитель не может быть равен нулю (делимое может быть любым). Алгоритмизация процесс систематического составления алгоритмов для решения поставленных прикладных задач.
13 13 Формальные признаки алгоритмов 1. Дискретность - алгоритм разбивается на конечное число элементарных шагов (действий) 2. Понятность - каждое из этих элементарных действий является понятным исполнителю 3. Детерминированность - каждое действие должно пониматься в строго определённом смысле, чтобы не оставалось места произвольному толкованию.
14 14 Формальные признаки алгоритмов 4. Массовость – по данному алгоритму должна решаться не одна, а целый класс подобных задач, т.е. алгоритм должен быть применим к разным наборам исходных данных. 5. Корректность – алгоритм содержит ошибки, если приводит к получению неправильных результатов. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
15 Пример : суммирование элементов одномерного массива Вход Выход S:=a(1) S:=S+a(2)... S:=S+a(n) 1. Введем переменную S – сумма всех элементов и присвоим значение первого элемента 2. Прибавим к S значение второго элемента 3. Прибавим к S значение третьего элемента 4.… 5. Прибавим к S значение n-ого элемента
16 Свойства алгоритма Вход – массив вещественных чисел. Выход – вещественное число. 1. Дискретность – есть, n шагов 2. Понятность – на каждом шаге выполняется одно действие 3. Детерминированность – каждый шаг алгоритма заканчивается определенным результатом. Шаги проходят в определенной последовательности 4. Массовость – алгоритм может применяться для массивов входных данных различной длины 5. Корректность – очевидна
17 Проверка свойств 1. Дискретность 2. Понятность 3. Детерминированность 4. Массовость 5. Корректность а ) рецепт приготовления блюда б ) схема эвакуации из здания в ) вычисление числа Пи
18 18 Блок - схема Начало и конец алгоритма Блок ввода/вывода данных Блок присвоения Альтернативный блок Современный способ представления алгоритма – псевдокод.
19 19 Алгоритм и программа Компьютерная программа - последовательность инструкций, предназначенных для исполнения вычислительной машиной. Компьютерная программа данные, предназначенные для управления кон кретными компонентами системы обработки данных в целях реализации определённого алгоритма. Иногда сопоставляется с исходным кодом.
20 20 Алгоритм и программа Алгоритм является математической абстракцией компьютерной программы. Метод абстракции применяется для исследования свойств сложных объектов. При этом какие-либо малозначительные свойства опускаются.
21 21 Язык программирования Язык программирования формальная знаковая система, предназначенная для записи программ. Программа обычно представляет собой некоторый алгоритм в форме, понятной компьютеру. Язык программирования определяется синтаксисом ( построение языковых конструкций ) и семантикой ( приписывание действий языковым конструкциям ).
22 22Определения Константа фиксированное значение, для которого определено имя Переменная контейнер, в котором может храниться одно значение в каждый момент выполнения программы. Каждая переменная имеет тип, определяющий, какого рода данные в ней хранятся Тип данных ( тип ) множество значений вместе с набором операций над этими значениями Оператор – законченное действие
23 23 Декларативное программирование Программа описывает нечто, а не реализует алгоритм ( в отличии от процедурного программирования ) Пример Веб - страницы на HTML декларативны, так как они описывают что должна содержать страница, а не как отображать страницу на экране
24 24 Процедурное ( императивное ) программирование Описывается не задача, а процесс её решения На каждом шаге решения состояние характеризуется набором значений переменных Каждое утверждение программы содержит указания на то, какие изменения в состоянии необходимо выполнить на данном шаге решения Примеры Pascal, Basic,C, Fortran
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.