Понятие алгоритмов в информатике 10 класса

Информатика Информатика

Теория алгоритмов представляет собой одну часть из целого набора концепций, которые находятся у основания компьютерной науки. С элементами теории можно ознакомиться при помощи учебника в темах об алгоритмах по информатике в 10 классе (автор Семакин И. Г.). Но более глубоко разобраться в этой проблеме можно, лишь поняв принцип работы алгоритмов и особенности их применения в конкретных ситуациях.

Принцип работы

Чтобы заставить компьютер делать что-либо, нужно написать компьютерную программу. Но перед этим важно чётко и пошагово представить, что именно требуется от вычислительной машины. И только в результате правильно прописанных инструкций (алгоритмизации действий) компьютер успешно выполнит заданную программу, достигнув конечной цели. Когда условно говорят компьютеру, что делать, также выбирают способ, как он будет это делать. Вот тут-то и вступает в работу вычислительная машина по тому же принципу, по которому решают алгоритмы по математике в 10 классе.

Алгоритм — это основная техника, используемая для описания выполняемой работы. Понять саму концепцию этой техники поможет презентация следующего примера.

Понятие Алгоритм

Допустим, у кого-нибудь есть друг, прибывающий в аэропорт, и он должен добраться из аэропорта до конкретного места. Вот четыре набора, где перечисляются последовательности действий, которые можно дать этому другу, чтобы добраться до требуемой локации:

Алгоритм «Такси»:

  1. Идти к стоянке такси.
  2. Сесть в такси.
  3. Дать водителю адрес.

Алгоритм «Позвони мне»:

  1. Когда самолёт прибудет, позвонить на мобильный телефон.
  2. Встретиться за пределами места получения багажа.

Алгоритм «Аренды автомобиля»:

  1. Сесть в автобус № 5.
  2. Доехать до места проката автомобилей.
  3. Арендовать автомобиль.
  4. Следовать инструкциям навигатора, чтобы добраться до дома № 10.

Алгоритм «Автобус»:

  1. У входа в аэропорт сесть на автобус № 70.
  2. Пересесть в автобус 14 на главной улице.
  3. Сойти на улице Вязов.
  4. Пройти два квартала на север к дому № 10.

Во всех вариантах достигается одна и та же цель, но делается это совершенно по-разному. Алгоритмы отличаются количеством операций, видом исходной информации, размером денежных затрат и разным временем исполнения. Например, взять такси — это, пожалуй, самый быстрый, но и самый дорогой способ. А поездка на автобусе определённо дешевле, но намного медленнее. Но выбор оптимального способа исходит из конкретных условий и обстоятельств.

Разработка и анализ

Урок информатики

Алгоритм — это особая процедура для решения чётко определённой вычислительной задачи. Разработка и анализ алгоритмов имеет фундаментальное значение для всех аспектов информатики: искусственного интеллекта, баз данных, графики, сетей, операционных систем, безопасности и так далее.

Изначальное представление алгоритма — больше, чем просто программирование. Этот процесс требует понимания альтернатив, доступных для решения конкретной вычислительной задачи, включая аппаратные средства, сети, язык программирования и ограничения производительности, которые сопровождают любое конкретное решение. А также необходимо понимание того, что алгоритм должен быть «правильным» в смысле полного и эффективного решения имеющейся проблемы.

При этом каждому алгоритму должны быть присущи следующие свойства:

  • Алгоритм должен состоять из действий, следующих в определённом порядке (дискретность).
  • Определённость (или однозначность) — в любом случае каждое действие должно быть строго и чётко определено.
  • Один и тот же алгоритм должен иметь возможность завершения (конечность) при работе с разными задачами, отличающимися только исходными данными (массовость).
  • Результативность — обеспечение правильности результатов при разных входных данных.
  • Понятность для исполнителя, то есть предлагаемая последовательность действий должна быть понятна и априори исполняема.

Сопутствующим понятием при разработке является проект конкретной структуры данных, которая позволяет составить алгоритм, способный работать эффективно. Важность структур данных проистекает из того факта, что основная память компьютера является линейной и состоит из последовательности ячеек памяти, которые пронумерованы (0, 1, 2, 3…). Таким образом, самой простой структурой данных является линейный массив, где смежные элементы пронумерованы последовательными целочисленными «индексами», а значение элемента доступно по его уникальному индексу.

Использование массивов

Массив может использоваться при записи и хранения списка имён. Необходимы эффективные методы для эффективного поиска и извлечения конкретного имени из массива. Например, сортировка списка в алфавитном порядке позволяет использовать так называемый метод двоичного поиска, при котором остаток списка, который нужно искать на каждом шаге, обрезается пополам. Этот метод поиска аналогичен поиску в телефонной книге определённого имени. Зная, что книга в алфавитном порядке, можно быстро перейти к странице, которая находится близко к странице, содержащей желаемое имя.

Свойства Алгоритма

Многие алгоритмы были разработаны для обработки, сортировки и поиска списков данных. Хотя элементы хранятся последовательно в памяти, они могут быть связаны друг с другом указателями (по существу, адреса памяти, сохранённые с элементом, чтобы указать, где находится следующий элемент или элементы в структуре), так что данные могут быть организованы способами, подобными тем, в которых они будут доступны.

Самая простая и часто используемая структура называется связанным списком, в котором к непрерывно хранимым элементам можно обращаться в заранее заданном порядке, следуя указателям от одного элемента в списке к следующему.

Список может быть цикличным, причём последний элемент указывает на первый, или каждый элемент может иметь указатели в обоих направлениях для формирования двусвязного списка. Разработки алгоритмов в этом направлении служат для эффективного управления списками с помощью функций поиска, вставки и удаления элементов.

Применение графов

На уроке информатики

Указатели также предоставляют возможность реализовать более сложные структуры данных. Например, граф — это набор узлов (элементов) и ссылок (известных как рёбра), которые соединяют пары элементов. В отличие от словесного алгоритма по информатике, такой график может представлять собой набор городов и соединяющих их автомагистралей, расположение элементов схемы и соединительных проводов на микросхеме памяти или конфигурацию людей, взаимодействующих через социальную сеть.

Типичные алгоритмы графа включают стратегии обхода графа — как переходить по ссылкам от узла к узлу (возможно, поиск узла с определённым свойством) таким образом, что каждый узел посещается только один раз. Смежной проблемой при этом является определение кратчайшего пути между двумя заданными узлами на произвольном графе.

Проблема практического интереса к сетевым алгоритмам состоит в том, чтобы определить и перечислить, сколько «разорванных» ссылок может быть допущено до того, как связь начнёт прерываться. Точно так же при разработке микросхем крупномасштабной интеграции (VLSI) важно знать, является ли график, представляющий схему, плоским, то есть может ли он быть нарисован в двух измерениях без пересечения ссылок (касания проводов).

Вычислительная сложность

Вычислительная сложность алгоритма означает меру количества вычислительных ресурсов (времени и пространства), которое конкретная последовательность выполняемых операций потребляет при запуске. Учёные в этом случае используют в виде теста математические меры сложности, которые позволяют им предсказать, прежде чем писать код, как быстро будет работать алгоритм и сколько памяти ему потребуется. Такие прогнозы считаются важными руководствами для программистов, реализующих и выбирающих алгоритмы для реальных приложений.

Вычислительная сложность Алгоритма

Вычислительная сложность является континуумом. Поскольку одни последовательности действий требуют линейного времени (то есть, затраченное время увеличивается непосредственно с количеством элементов или узлов, которые составляют обрабатываемый список, график или сеть), тогда как для других необходима квадратичная или даже экспоненциальная величина времени для завершения (то есть требуемое время увеличивается с увеличением количества предметов в квадрате или по экспоненте от их числа).

В дальнем конце этого континуума лежат мутные моря неразрешимых проблем — тех, чьи решения не могут быть эффективно реализованы линейными методами. Поэтому специалисты в области компьютерных наук стремятся найти эвристические виды алгоритмов, которые могут решать такие задачи в оптимальные сроки. Ещё дальше находятся те алгоритмические проблемы, которые могут быть поставлены, но не решаемы в принципе; то есть для них можно доказать, что ни одна программа не может быть написана для решения проблемы.

Информатика Алгоритмы

Классическим примером неразрешимой алгоритмической задачи является проблема остановки, которая гласит, что не может быть написана ни одна программа, предсказывающая, остановится ли какая-либо другая программа после конечного числа шагов. Неразрешимость остановки имеет непосредственное практическое значение для разработки программного обеспечения. Например, было бы легкомысленно пытаться разработать программный инструмент, который предсказывает, имеет ли другая разрабатываемая программа бесконечный цикл (хотя наличие такого инструмента — чрезвычайно полезно).

В компьютерном программировании, как и в алгебре, есть много разных способов для решения той или иной задачи. При этом нужно понимать, что любой алгоритм имеет свои преимущества и недостатки в разных ситуациях.

И от выбора оптимального набора последовательностей действий для вычислительной машины напрямую зависит эффективность её работы над конкретной поставленной задачей.

Автор статьи
Алексей Гузанов
Репетитор, закончил Куровскую гимназию, которая входит в топ-100 школ Московской области, с золотой медалью. Являюсь победителем олимпиад по математике и информатике. Успешно сдал ЕГЭ на высокие баллы.
Задать вопрос
Оцените статью
Na5.club
Добавить комментарий

77 − 67 =

Adblock
detector