Алгоритм
Решение любой сложной задачи проводится в несколько этапов. Все этапы, выполненные последовательно друг за другом и приводящие в итоге к достижению поставленной цели составляют алгоритм. Например, чтобы снять деньги в банкомате, нужно выполнить последовательность действий: вставить карту, ввести пин-код, выбрать в меню программного обеспечения команду «Снятие наличных», ввести требуемую сумму, распечатать чек, вернуться в главное меню или закончить обслуживание карты.
Алгоритм – это базовое понятие в информатике. Он представляет собой набор инструкций, выполнение которых приведет к решению поставленной задачи за конечное число шагов.
термин «Алгоритм» получил свое название от имени знаменитого восточного ученого математика Мухаммеда аль-Хорезми, жившего в восьмом веке в Багдаде. Трактаты аль-Хорезми внесли большой вклад в развитие средневековой науки.
Рис. 1. Мухаммед аль-Хорезми.
Вычислительная сложность
Вычислительная сложность алгоритма означает меру количества вычислительных ресурсов (времени и пространства), которое конкретная последовательность выполняемых операций потребляет при запуске. Учёные в этом случае используют в виде теста математические меры сложности, которые позволяют им предсказать, прежде чем писать код, как быстро будет работать алгоритм и сколько памяти ему потребуется. Такие прогнозы считаются важными руководствами для программистов, реализующих и выбирающих алгоритмы для реальных приложений.
Вычислительная сложность является континуумом. Поскольку одни последовательности действий требуют линейного времени (то есть, затраченное время увеличивается непосредственно с количеством элементов или узлов, которые составляют обрабатываемый список, график или сеть), тогда как для других необходима квадратичная или даже экспоненциальная величина времени для завершения (то есть требуемое время увеличивается с увеличением количества предметов в квадрате или по экспоненте от их числа).
В дальнем конце этого континуума лежат мутные моря неразрешимых проблем — тех, чьи решения не могут быть эффективно реализованы линейными методами. Поэтому специалисты в области компьютерных наук стремятся найти эвристические виды алгоритмов, которые могут решать такие задачи в оптимальные сроки. Ещё дальше находятся те алгоритмические проблемы, которые могут быть поставлены, но не решаемы в принципе; то есть для них можно доказать, что ни одна программа не может быть написана для решения проблемы.
Классическим примером неразрешимой алгоритмической задачи является проблема остановки, которая гласит, что не может быть написана ни одна программа, предсказывающая, остановится ли какая-либо другая программа после конечного числа шагов. Неразрешимость остановки имеет непосредственное практическое значение для разработки программного обеспечения. Например, было бы легкомысленно пытаться разработать программный инструмент, который предсказывает, имеет ли другая разрабатываемая программа бесконечный цикл (хотя наличие такого инструмента — чрезвычайно полезно).
В компьютерном программировании, как и в алгебре, есть много разных способов для решения той или иной задачи. При этом нужно понимать, что любой алгоритм имеет свои преимущества и недостатки в разных ситуациях.
И от выбора оптимального набора последовательностей действий для вычислительной машины напрямую зависит эффективность её работы над конкретной поставленной задачей.
Свойства алгоритма
Алгоритм, как базовое понятие информатики, обладает рядом свойств:
- Массовость предполагает пригодность алгоритма для различных исходных данных.
- Дискретность означает, что каждый этап алгоритма представляет собой законченное действие.
- Однозначность означает, что очередность выполнения этапов алгоритма должна быть одинакова при всех возможных наборах данных.
- Конечность означает, что алгоритм состоит из строго определенного числа шагов.
Конспект урока и презентация по информатике «Обработка информации» (с дополнительным материалом)
Цели урока:
дать учащимся представление о процессе обработки информации,
познакомить с двумя типами обработки информации.
Задачи урока:
Образовательные:
закрепление представления учащихся о видах информации и информационных процессах;
расширение представления о компьютере как инструменте обработки числовой информации.
Развивающие:
развитие логического мышления, памяти, внимания, познавательного интереса, исследовательских умений;
формирование информационной культуры
Воспитательные:
воспитание стремления к организации самостоятельной работы, умения работать в группе, культуры общения.
Ход урока.
1. Организационная часть.
Учитель проверяет готовность класса к уроку.
Здравствуйте, ребята, садитесь.
2. Актуализация опорных знаний. Постановка проблемы.
Урок мы начнем с повторения теоретического материала
Скажите мне, пожалуйста,
1) Что такое информация?
2) Как человек получает информацию?
3) Какие виды информации по форме представления вы знаете?
4) Как человек получает информацию?
Хорошо! Что вы делали для того чтобы ответить на поставленные мною вопросы? (Думали, рассуждали). А как назвать то, что происходит с информацией в голове человека во время рассуждений? Вы сейчас узнаете отгадав ребус (Обработка информации).
— «Обработка информации»
И сегодня на уроке как вы думаете что мы будем делать?
(Дети выражают свои мнения)
Правильно.
Теперь сформулируем цель урока:
На доске вы видите картинки что вы можете о них сказать
Цель урока: Мы должны сегодня на уроке получить представление как обрабатывается информация, узнать какими способами обрабатывается информация.
Познакомится на практической работе с различными способами обработки информации.
Кроме того, мы будем анализировать, сравнивать, делать выводы.
Знакомство с процессом обработки информации.
Мозг человека постоянно занят обработкой информации, даже во сне.
1. Слышим звонок будильника – понимаем, что пора вставать.
2. Перед выходом на улицу выглядываем в окно, видим, что идет дождь – делаем вывод, что надо взять зонт.
3. Пробуем суп – понимаем, что недостаточно соли.
4. Смотрим фильм – и сопереживаем героям.
Приведите свои примеры обработки информации человеком.
5. Информацию обрабатывают и технические устройства, например, телевизор получает сигналы с помощью антенны, а мы видим изображение и слышим звук. Приведите свои примеры обработки информации техническими устройствами.
Вы хорошо знакомы с задачами по математике. Рассмотрим одну из них.
Пример 1. Ученики 5 класса посадили 20 деревьев, а ученики 6 класса на 5 деревьев больше. Сколько деревьев посадили дети? Показать задачу
При решении данной задачи особое внимание следует уделить нахождению исходных данных, принципу решения и результату. Отмечаем, что в условии была задана числовая информация. И в результате получилось число.
А теперь рассмотрим еще один пример.
Пример 2. Есть текст: Москвичи любят домашних животных. Согласно опросам, собак содержат 57 % жителей города, 38 % имеют кошек, 25 % заботятся о попугаях. Нередки в последнее время экзотические животные: игуаны (5 %) и пауки (3 %).
Изменим способ представления информации, представим текст в табличном и графическом виде.
Смотрите как интересно, во втором примере: исходным данным был текст, а результатом – диаграмма. Показать диаграмму
Что произошло?
Произошла обработка информации, точнее произошло изменение формы представления информации. Содержание информации осталось прежним.
А что можно сказать о первом примере?
(Важно, чтобы дети сами сделали вывод о том, что в первом примере мы просто получили результат – новую информацию, без изменения ее содержания).
Таким образом, существуют два способа обработки информации:
Обработка информации, связанная с получением новой информации
Обработка информации, связанная с преобразованием информации к новой форме.
Вопрос: приведите примеры различных способов обработки информации. Укажите исходные данные и результат. (Слушаем и обсуждаем 2-3 примера).
Весь материал — в архиве.
Способы записи алгоритмов
Алгоритмы можно представлять по-разному. Существую следующие способы записи алгоритмов:
- формульно-словесный – алгоритм задается с помощью естественного разговорного языка с использованием специальных знаков и формул;
- графический – алгоритм воспроизводится с применением графических объектов, выстроенных в виде блок-схемы;
- алгоритмический язык – алгоритм реализован посредством ключевых слов специального алгоритмического языка.
Рис. 2. Алгоритм, записанный на алгоритмическом языке.
Самым наглядным алгоритмом, является алгоритм, заданный в виде блок-схемы, где каждый шаг представлен определенной геометрической фигурой: прямоугольник заменяет вычислительный процесс, ромбом изображается условие, шестигранник используется для обозначения цикла с известным числом повторов.
Рис. 3. Блок-схема алгоритма.
при разработке блок-схем алгоритмов следует пользоваться правилами, регламентированными в специальном стандарте. На территории РФ функционирует Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем».
Использование массивов
Массив может использоваться при записи и хранения списка имён. Необходимы эффективные методы для эффективного поиска и извлечения конкретного имени из массива. Например, сортировка списка в алфавитном порядке позволяет использовать так называемый метод двоичного поиска, при котором остаток списка, который нужно искать на каждом шаге, обрезается пополам. Этот метод поиска аналогичен поиску в телефонной книге определённого имени. Зная, что книга в алфавитном порядке, можно быстро перейти к странице, которая находится близко к странице, содержащей желаемое имя.
Многие алгоритмы были разработаны для обработки, сортировки и поиска списков данных. Хотя элементы хранятся последовательно в памяти, они могут быть связаны друг с другом указателями (по существу, адреса памяти, сохранённые с элементом, чтобы указать, где находится следующий элемент или элементы в структуре), так что данные могут быть организованы способами, подобными тем, в которых они будут доступны.
Самая простая и часто используемая структура называется связанным списком, в котором к непрерывно хранимым элементам можно обращаться в заранее заданном порядке, следуя указателям от одного элемента в списке к следующему.
Список может быть цикличным, причём последний элемент указывает на первый, или каждый элемент может иметь указатели в обоих направлениях для формирования двусвязного списка. Разработки алгоритмов в этом направлении служат для эффективного управления списками с помощью функций поиска, вставки и удаления элементов.
