Структуры данных и алгоритмы для чего их изучать


Оглавление (нажмите, чтобы открыть):

Study & Dev О программировании и не только

Структуры данных и алгоритмы. Теория. Введение

Введение. Классической формулой успеха для программиста является утверждение Н.Вирта «Хорошая программа – это единство продуманного алгоритма и эффективных структур данных». Данный учебный курс посвящен формированию научной системы мышления, умению проектировать алгоритмы и структуры данных. Перед изучением данного учебного курса предполагается, что студенты обладают знаниями в области простейших алгоритмов, владеют языком программирования высокого уровня, владеют основами объектно-ориентированного подхода в анализе и проектировании систем.

Анализ алгоритмов

Понятия “алгоритма и структур данных” являются центральными в сфере компьютерных технологий, однако, чтобы называть некоторые структуры данных и алгоритмы «качественными и эффективными», следует использовать точные приемы их анализа. В качестве естественного критерия качества естественно выделить, во-первых, время исполнения. Также важным является объем затрачиваемых ресурсов памяти и дискового пространства. Внимание также следует уделить надежности и достоверности решений, их стабильности. Прежде всего давайте рассмотрим понятие затрат времени и того как его оценивать для произвольного алгоритма.

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

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

x y
1 0,012753
10 46,3401
19 183,8774
28 259,4942
37 925,4948
46 17,15173

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

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

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

1) эксперименты могут проводиться лишь с использованием ограниченного набора исходных данных; результаты, полученные с использованием другого набора, не учитываются.

В качестве демонстрации можно привести алгоритм подсчета суммы некоторого ряда с точностью до указанной дельта.

То алгоритм выдаст неправильное решение (равное конечному числу, хотя и очень большому) в виду того, что данный ряд является расходящимся и его суммой является бесконечность.

2) для сравнения эффективности двух алгоритмов необходимо, чтобы эксперименты по определению времени их выполнения проводились на одинаковом аппаратном и программном обеспечении;

3) для экспериментального изучения времени выполнения алгоритма необходимо провести его реализацию и выполнение.

Таким образом, мы приходим к необходимости использования для анализа алгоритмов методов общего анализа, который позволяет:

1) учитывает различные типы входных данных;

2) позволяет производить оценку относительной эффективности любых двух алгоритмов независимо от аппаратного и программного обеспечения;

3) может проводиться по описанию алгоритма без его непосредственной реализации или экспериментов.

Суть общего анализа заключается в том, что некоторому алгоритму ставится в соответствие функция F=F(n1, . nm). В простейшем варианте это функция одной переменной n1 – количества исходных данных. Однако могут быть и другие переменные – например точность расчета или его достоверность. Так для определения того является ли некоторое число простым в случае больших чисел (длина двоичного представления более чем 200 бит) используют вероятностный метод, достоверность которого можно варьировать. Наиболее известные функции это линейные, степенные, логарифмические. Поэтому следует потратить время и вспомнить основы работы с ними.

При построении алгоритмов первая стадия идет с использованием не языка программирования, а описания на человеческом языке. Подобные описания не являются программами, но вместе с тем они более структурированы, чем обычный текст. В частности, «высокоуровневые» описания сочетают естественный язык и распространенные структуры языка программирования, что делает их доступными и вместе с тем информативными. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. Подобные описания принято называть псевдокодом. Следует также отметить, что для проведения анализа псевдокод является зачастую более полезным, чем код на конкретном языке программирования.

Пример псевдокода:

Название: Алгоритм подсчета количества элементов массива равных нулю.

Исходные данные: массив A

Требуется: количество элементов равных нулю

Начало алгоритма:

Конец алгоритма.

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

При анализе структур данных и алгоритмов зачастую используется понятие рада, которое можно определить следующим образом:
Утверждение: если целое число N>=0 и действительно число 0 1, то

Это пример геометрического ряда. Значение каждого элемента данного ряда увеличивается в геометрической прогрессии, если, конечно, a > 1. Таким образом, элементы данного ряда возрастают по экспоненте. Если вы вспомните начала нашего учебного курса и то, как вы работали с двоичной системой счисления, то также узнаете следующее равенство:
В случае арифметического ряда, в котором значение каждого элемента увеличивается на величину D = A(i) –A(i-1).

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

Простые приемы доказательства

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

Прием «Пример»

Иногда утверждения записываются в обобщенной форме: «Множество S содержит элемент х, обладающий свойством V. Для доказательства данного утверждения достаточно привести пример х «принадлежит» S, который обладает данным свойством. В подобной обобщенной форме записываются, как правило, и маловероятные утверждения, например: «Каждый элемент х множества S обладает свойством Р». Чтобы доказать ошибочность данного утверждения, достаточно просто привести пример: х «принадлежит» S, который не обладает свойством Р. В данном случае элемент х будет выступать в качестве контр-примера.

ПРИМЕР: Профессор Амонгус утверждает, что любое число вида 2^n — 1 является простым, если n — целое число, большее 1. Утверждение профессора Амонгуса ошибочно.

ДОКАЗАТЕЛЬСТВО: чтобы доказать неправоту профессора Амонгуса, обходимо найти контр-пример. К счастью, для этого не потребуется много времени: 2^4 — 1 = 15 = 3 * 5. (Я надеюсь, вы помните, что простое число не имеет делителей отличных от 1 и самого себя).

Прием «Контратака»

Существует и другой способ, основанный на доказательстве от противного (использовании отрицания). Основными методами в данном случае являются контрапозиция и контрадикция. Использование методов противопоставления подобно зеркальному отражению: чтобы доказать, что «если X — истинно, то и Y — истинно», будем утверждать обратное «если Y — ложно, то и X — ложно». С точки зрения логики, данные утверждения идентичны, однако второе выражение, которое является котропозицией первого, более удобно.

ПРИМЕР: Если a*b — нечетное число, то а — нечетное или b – нечетное.

ДОКАЗАТЕЛЬСТВО: для доказательства данного утверждения рассмотрим контрапозицию: «Если а — четное число и b — нечетное, то a*b – четное. Пусть, а = 2*X, для некоторого целого числа X. Тогда a*b = 2*i*b, а следовательно произведение a*b — четное.

При использовании методов доказательства от противного полезным является использование законов логики.
В приведенном выше примере используется закон Де-Моргана, который в вышепринятых обозначениях будет записана так:
При использовании метода контрадикции для доказательства того, что утверждение q — верно, вначале предполагается, что q — ложно, а затем показывается, что такое предположение приводит к противоречию (например, 2 * 2 <> 4). Придя к подобному противоречию, можно утверждать, что ситуации, при которой q — ложно, не существует, и, следовательно, q – истинно.

Индукция и инварианты цикла

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

Метод индукции основан на том; что для любого n > 1. Существует конечная последовательность действий, которая начинается чего-то заведомо истинного и, в конечном итоге, приводит к доказательству того, что q(n) истинно. Таким образом, доказательство с помощью индукции начинается с утверждения, что q(n) истинно при n=1,2,3 и т.д. до некоторой константы k. Далее доказывается, что следующий «шаг» индукций q(n+1), q(n+2) также является истинным для n > k.

ПРИМЕР: Рассмотрим последовательность Фибоначчи.
Докажем, что F(n) 2). Предположим, что приведенное утверждение истинно для n’ n0

3) Выполните предыдущее задание, если алгоритм В выполняет n*sqrt(n) операций.

4) Докажите, что следующие два утверждения равнозначны:
5) Существует алгоритм find2D, который находит элемент х в массиве A размером n х n элементов (квадратная матрица). При каждой итерации алгоритм find2D просматривает строки массива А и вызывает алгоритм arrayFind фрагмент кода которого приводится ниже, до тех пор пока не будет найден элемент х или будут просмотрены все строки массива А. Каково худшее время выполнения алгоритма find2D, выраженное с помощью переменной n. Является ли время выполнения алгоритма линейной функцией? Почему?

Алгоритм arrayFind в виде псевдокода:

Входные данные: элемент X и массив A содержащий N элементов.

Требуется: Индекс “i” элемента массива A(i) = X или же, если такого элемента нет, то -1.

6) Эл и Билл спорят об эффективности своих алгоритмов, которые выполняют сортировку данных. Эл утверждает, что его алгоритм, выполнения которого равно O(n logn), всегда быстрее алгоритма Эла со временем выполнения О(n^2). Для того чтобы разрешить спор они многократно выполняют алгоритмы на произвольных блоках данных. К ужасу Эла, эксперименты показали, что при n 100 алгоритм со временем О(n log n) лучше. Объясните причину подобной закономерности.

Структуры и алгоритмы обработки данных

4й семестр – лекции 34 часа, лабораторные работы 32 часа – экзамен;

5й семестр – лекции 34 часа, лабораторные работы 16 час – зачёт.

1. Хусаинов Б.С. «Структуры и алгоритмы обработки данных. Примеры на языке Си» М: Финансы и статистика, 2004.

2. Вирт Н. «Алгоритмы и структуры данных», СПб: Невский диалект, 2001.

3. Ахо А., Хопкрофт Джон, Ульман Джеффри «Структуры данных и алгоритмы», М: Издательский дом «Вильямс», 2000.

4. Кнут Д. Искусство программирования. В трёх томах. М.: Издательский дом «Вильямс», 2001.

5. Кормен Т. и др. Алгоритмы: Построение и анализ, 2-е издание. М.: Издат. Дом «Вильямс». 2005.

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

Алгоритм должен обладать следующими свойствами:

1. Конечность – работа алгоритма должна заканчиваться за конечное число шагов, причём некоторые из шагов могут повторяться многократно.

2. Определённость (детерминированность) – все шаги алгоритма должны иметь однозначную трактовку и должны быть понятны исполнителю алгоритма, при одних и тех же исходных данных должны быть получены одни и те же результаты.

3. Массовость – алгоритм должен быть направлен на решение целого класса задач, отличающихся исходными данными.

4. Результативность – алгоритм должен приводить к достижению поставленной цели за конечное число шагов.

5. Эффективность – все шаги алгоритма должны выполняться за конечное время, а общее время решения задачи должно лежать в допустимых пределах.

Основными этапами подготовки задачи к решению на компьютере являются:

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

2. Построение модели задачи – предполагает подбор или разработку формального описания (модели) задачи, привлекая достижения современной науки.

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

4. Реализация алгоритма в виде программы – сначала выбирается язык программирования.

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

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

Каждая программа определяется правилами её представления (синтаксисом языка программирования) и правилами интерпретации её содержательного значения (семантикой). Корректная программа может быть создана только при строгом соотношении этих правил. Задача определения синтаксической правильности решается транслятором автоматически в ходе трансляции программы. Проблема доказательства семантической правильности оказывается значительно сложнее, так как процедура доказательства существенно зависит от решаемой задачи и исходных данных. Формализованное описание поставленной задачи называют спецификацией задачи. Область науки, занимающаяся доказательством соответствия между программной реализацией и спецификацией задачи, получила название верификации программ. Цель верификации программ – демонстрация их корректности.

Семантическая правильность программы проверяется путём её тестирования, то есть выполнения программы при определённых исходных данных (тестах) с целью нахождения ошибок.

6. Анализ сложности алгоритма: алгоритму решения задачи предъявляют два противоречивых требования:

а) быть простым для понимания, отладки и сопровождения;

б) быть эффективным в смысле затрат времени и памяти компьютера.

Какому из этих требований отдать предпочтение, определяется характером решаемой задачи.

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

Данные характеризуются тремя качествами: семантикой, синтаксисом и прагматикой.

Семантика – это содержательная (смысловая) характеристика данных. Она определяет множество возможных значений данных и множество операций, которые можно выполнять над этими данными.

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

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

Комбинацию семантической и синтаксической характеристик данных в программировании называют типом данных. В современных языках программирования типы данных делятся на простые (скалярные) и структурированные.

Данные простых (скалярных) типов рассматриваются как цельные простые неделимые объекты. Например: целые, вещественные, символьный, логический и другие.

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

Число различных значений, входящих в тип, называется мощностью этого типа.

Если для значений некоторого типа существует отношение порядка следования, то такой тип называется порядковым.

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

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

Рис. 1. Структура данных.

На основе фундаментальных структур в программе могут строиться более сложные структуры.

Таким образом, структура данных – это организованная некоторым образом информация, которая может быть описана, создана и обработана программами.

Структура данных используется для представления абстрактного типа данных.

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

Структуры хранения данных

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

Большинство современных вычислительных машин имеет линейную оперативную память, состоящую из последовательности ячеек памяти. Ячейка – это наименьшая адресуемая часть памяти. Возможные значения адресов образуют адресное пространство модели вычислительной машины (0,1,2,…,n). По содержимому ячейки невозможно определить, какого типа данные в ней хранятся.

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

Рассмотрим возможности представления структур данных в линейной оперативной памяти.

Первая возможность связана с получением памяти. Данные могут размещаться либо в статической, либо в динамической памяти. Память под данные в программе может быть получена двумя способами. Первый способ – это когда для отдельных данных, которые описаны в программе, при её выполнении выделяется память, определяемая типом данных. Такая память является статической и сохраняется на время выполнения программы или её частей. (Не путать со статическими данными в языке Си и других языках программирования.) Второй способ – это получение памяти по явному запросу в программе. В запросе указывается объём требуемой памяти. В случае наличия памяти операционная система выделяет одну сплошную область памяти и возвращает адрес начала этой области. Такую память будем называть динамической памятью. За её правильное использование отвечает программист. После того как потребность в динамической памяти отпала, она может быть освобождена также по явному запросу. Динамическая память может быть получена для структуры данных в целом по одному запросу. Тогда размеры структуры данных могут изменяться только в пределах фиксированной длины полученной памяти, а число элементов в структуре будет ограничено. Если же получать память для каждого элемента по отдельному запросу, число элементов не ограничивается, пока есть доступная память вычислительной машины.

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

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

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

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

Рассмотрим три вида структур хранения данных: вектор, список и сеть, на основе которых строятся многие другие структуры хранения.

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

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

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

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

Рис. 2. Структура вектора.

Дескриптор вектора содержит: адрес Am начала вектора, тип элементов структуры данных или их длину L, число элементов или их начальный m и конечный n индексы. Адрес Ai элемента Ei с индексом i определяется выражением Ai = Am + (i — m) * L.

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

В прикладной программе можно организовать хранение данных в динамическом векторе. Для этого нужно выполнить ряд операций: 1) определить структуру дескриптора; 2) получить динамическую память под дескриптор и заполнить дескриптор управляющей информацией; 3) используя данные из дескриптора, определить размер памяти для вектора и получить динамическую память; 4) при необходимости инициализировать элементы структуры данных в векторе. Адреса элементов к ним вычисляются с использованием управляющей информации из дескриптора. В программе доступ к структуре данных, хранимой в виде вектора, осуществляется посредством указателя на дескриптор (рис. 3).

Рис. 3. Доступ к вектору через дескриптор.

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

Список является более сложной структурой хранения, в которой элементы имеют явные связи. В списке элементы структур данных размещаются не обязательно в смежных областях памяти. Каждый элемент структуры данных содержит, по крайней мере, два поля. Одно поле – основное содержит данные этого элемента или указатель на данные, а другое поле предназначено для размещения указателя на следующий элемент. Оконечный элемент структуры данных в поле указателя содержит признак конца списка (NULL – в Си, в Паскале — Nil). Элемент структуры данных, в свою очередь, тоже может быть структурой, хранимой в виде списка. Различают списки однонаправленные, двунаправленные и циклические. Число элементов списка может изменяться. Учитывая наличие явных связей между элементами списка, иногда используют термины цепной список или связной список. Список, отражающий отношение соседства между элементами (у каждого элемента списка могут быть только один предыдущий и один последующий элементы), называется линейным. Любой другой список называется нелинейным.

Однонаправленный список (рис. 4) является простейшей формой списка.

Рис. 4. Однонаправленный список.

Достоинства однонаправленного списка – простота создания, включения и удаления элементов. Недостаток – просмотр элементов осуществляется всегда с начала списка. Правда, программа обработки ожжет запоминать указатель на текущий элемент, тогда обработку можно продолжать с него.

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

Рис. 5. Циклический список.

Мастер Йода рекомендует:  Обзор Интернет - магазинов для Joomla CMS

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

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

· указатель (адрес) начала списка;

· текущее число элементов;

· описание элемента (длина, тип и т.п.).

Вместо дескриптора можно использовать только указатель.

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

Элементы структуры данных в списке могут быть упорядочены по возрастанию или убыванию значения некоторого поля данных (по ключу). Обработка упорядоченных списков во многих случаях проще обработки неупорядоченных списков.

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

Возможна организация списка и в смежной области памяти. В этом случае все элементы структуры данных имеют один и тот же тип, а число возможных элементов ограничено размерами области памяти. На рис. 1.7 приведён пример цепного списка, размещённого в одной сплошной области памяти (указатель списка размещён в другой области и содержит адрес списка). Элементами данных являются буквы. Последовательность букв, размещённых в списке, образует слово АЗБУКА.

Рис. 1.7. Цепной список в смежной области памяти.

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

Сеть как структура хранения является дальнейшим развитием списковой структуры хранения. Каждый элемент структуры данных в сети, кроме данных, может содержать несколько указателей на другие элементы. На один и тот же элемент могут ссылаться несколько других элементов, образуя, таким образом, сложные переплетения по связи (рис. 1.8).

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

Сети используются для представления в памяти ЭВМ сложных структур данных, таких как графы, деревья, многоуровневые и многосвязные таблицы, структуры сложных программных изделий, организационные структуры предприятий и связи между ними и т.п.

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

1. Структуры данных «массив»

Массивы являются наиболее широко используемыми структурами данных и предусмотрены во всех языках программирования. Массив состоит из элементов одного типа, называемого базовым, поэтому структура массива однородна. Базовый тип может быть как скалярным, так и структурированным, т.е. элементами массива могут быть числа, символы, строки, структуры, в том числе и массивы. Число элементов массива фиксировано, поэтому объём занимаемой массивом памяти остаётся неизменным. С каждым элементом массива связан один или несколько индексов. Они однозначно определяют место элемента в массиве и обеспечивают прямой доступ к нему. Индексы массива относятся к определённому порядковому типу, поэтому индексы можно вычислять. Это обеспечивает, с одной стороны, гибкость обработки элементов массива, с другой стороны, создаёт опасность выхода за пределы массива, если не предусмотрены соответствующие средства контроля.

В зависимости от числа индексов различают одномерные и многомерные массивы. Допустимое число индексов массива (размерность массива) и диапазоны изменения их значений устанавливаются языком программирования. Трансляторы с языка программирования могут уточнить эти значения. По стандарту языка Си размерность массива не может превышать 31, а нумерация индексов начинается всегда с нуля, т.е. индекс изменяется от 0 до n-1, где n – количество значений индекса (мощность индекса).

Областями применения массивов являются:

· числовые массивы в вычислительных задачах;

· матричная алгебра, экстраполяция, интерполяция;

· таблицы – массивы с элементами типа «запись»;

· управляющие и информационные таблицы в операционных системах, трансляторах, системах управления базами данных (СУБД);

· представление других структур: графов, деревьев.

2. Структуры хранения массивов

Массив в памяти хранится в виде вектора, т.е. все элементы размещаются в смежных участках памяти подряд, начиная с адреса, соответствующего началу массива. Элементы одномерного массива размещаются последовательно друг за другом a, a1,…, an-1. Элементы двухмерного массива размещаются по строкам, т.е. наиболее быстро меняется последний индекс b0,0, b0,1,…, b0,n-1, b1,0, b1,1,…, b1,n-1,…, bm-1,n-1 (в Си, Паскале, ПЛ/1).

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

· адрес начала массива Aн;

· тип элемента (длина элемента массива L);

· нижняя граница индекса iн;

· верхняя граница индекса iв.

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

Этой информации достаточно как для доступа к элементам массива, так и для контроля над тем, чтобы значения индексов не выходили за установленные диапазоны. Доступ к любому i-тому элементу в одномерном массиве осуществляется по адресу:

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 8981 — | 7233 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Структуры данных и алгоритмы: для чего их изучать

Чему научит этот курс?

Зачем нужны алгоритмы и структуры данных?

Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живёте.

Мартин Голдинг

1.1 Введение в курс

Компьютеры прочно вошли в нашу жизнь и стали её частицей. Хорошо это или нет – жизнь покажет. Но нам с ними, как говорится, теперь, надо переспать.

Науки, имеющие непосредственное отношение к налаживанию отношений с компьютерами, обобщающе названы Computer Science. Огромнейший объем информации, содержащийся в Computer Science, имеет под собой концептуальные основания, без изучения которых немыслимо не только налаживание, но и сами отношения.

«Алгоритмы» и «структуры данных» являются одними из основополагающих понятий, рассматриваемых в Computer Science. Классической формулой успеха для программиста является утверждение Н.Вирта «Хорошая программа – это единство продуманного алгоритма и эффективных структур данных». Добавим к его утверждению, что для написания и реализации программы необходим алгоритмический язык и получим формулу:

  • (1.1) ​Программа = Алгоритм + Структуры данных + Алгоритмический язык,

представленную рисунком 1.1.

Рисунок 1.1 – Составляющие программы

Исследование алгоритмов и структур данных является одной из основ программирования, а также богатым полем элегантных технологий и сложных математических изысканий. И это — что-то большее, чем развлечение для теоретически подготовленных: хороший алгоритм или структура данных могут позволить решить в течение нескольких секунд проблему, которая без них решалась бы годами.

Возможность решения задачи целиком и полностью зависит от наличия специальных алгоритмов и структур данных. Если вы разрабатываете программы в новых для вас областях программирования, то вы должны выяснить, какие наработки уже существуют, иначе вы потратите свое время впустую в попытках плохо сделать то, что уже кем-то было сделано хорошо. Каждая программа зависит от алгоритмов и структур данных, но редко бывает нужно изобретать новые алгоритмы. Даже в сложной программе, например в компиляторе или Web-браузере, структуры данных по большей части являются массивами, списками, деревьями и хэш-таблицами. Когда программе нужна более изощренная структура, она, скорее всего, будет основываться на этих более простых структурах. Соответственно, задача программиста – знать, какие алгоритмы и структуры доступны, а также понимать, как выбрать среди них наиболее эффективные.

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

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

Несколько слов о литературе. При написании курса использованы 8 основных книг, но, разумеется, время не стоит на месте – появляются публикации «новых» ученых, да и у неприведенных в списке «старичков» можно наверняка найти что-нибудь полезное.

1.2 Понятие «алгоритм»

Наша жизнь сплошь и рядом напичкана алгоритмами. И мы порой не задумываемся, что применяем в какой-то момент жизни тот или иной алгоритм. Авторы обзора основных достижений теории алгоритмов [4] утверждают: «Алгоритмические концепции играют в процессе обучения и воспитания современного человека фундаментальную роль, сравнимую лишь с ролью письменности».

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

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

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

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

На одной из научных конференций ( 1984 г.) по информатике академик Самарский изобразил на слайде информатику в виде красавицы, несущейся на трех китах по научному океану. Имена тех китов: Модель, Алгоритм, Программа.

Мы займемся как раз вторым китом имя которого – Алгоритм! Тем более, что агитировать Вас им заняться не вызывает я думаю возражений. Ибо алгоритм, бесспорно, центральное понятие для программирования! С него начинается по сути робота над программой,

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

Рисунок 1.2 – Изображение «Информатики» в докладе А. Самарского

История у его величества «Алгоритма» очень длинная, а вот у теории алгоритмов сравнительно короткая. Теория алгоритмов , пожалуй, как раздел научных знаний начал оформляться лишь с конца 30-х годов 20 века и продолжается оформляться до наших дней.

Слово алгоритм, как утверждают историки, математики, появилось 12 веков назад и означало не термин, а имя. Узбекский математик Аль-Хорезми , ученый, которому математика обязана многими открытиями, — был известен европейским математикам как Алгоризми. А полное его имя Абу Абд Аллах Мухаммед ибн Мусса аль-Хорезми ( около 825 г. ) – в переводе буквально – Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезми. Его книга – «Китаб аль-джебр Валь-мукабала». Именно с трактата Аль-Хорезми по арифметике началось знакомство Европы с алгоритмами – строгими процедурами для выполнения арифметических операций. Т.е. алгоритм, вернее как алгорисм, – понимался как руководство к действию для решения задач.

Дальнейшее развитие математики утвердило ту мысль, что решение любой проблемы должно быть алгоритмическим. Декарт, Лейбниц, Гильберт, особенно последний стимулировал алгоритмические исследования, предложив в 1900 году на международном математическом конгрессе свои знаменитые 23 проблемы.

Рисунок 1.3 – Марка с изображением Мухаммеда аль-Хорезми.

Для уточнения понятия алгоритм были распространены 2 точки зрения :

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

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

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

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годом Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем.

В 1950 годы существенный вклад в теорию алгоритмов внесли работы А. Колмогорова и

А. Маркова. К 1960-70 годам оформились следующие направления в теории алгоритмов:

классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, формулировка в 1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его исследование)[1];

теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения), в развитие которой внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп[2,4];

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

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

Современное определение алгоритма – это что-то близкое к этому : Алгоритм — способ преобразования информации по правилам, сформулированными на определенном языке.

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

Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм А осуществляет отображение D в R:

Вот еще два определения алгоритма известных ученых:

Определение 1 (Колмогоров): Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение 2 (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Пример 1.1. Рассмотрим алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел a и в (НСД (а, в)).

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

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

Детерминированность ( определенность) – однозначность результата процесса при заданных исходных данных.

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

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

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

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

Рисунок 1.4 – Свойства алгоритмов

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

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

Обобщая результаты различных разделов теории алгоритмов можно выделить следующие цели и соотнесенные с ними задачи , решаемые в теории алгоритмов [1-7]:

формализация понятия «алгоритм» и исследование формальных алгоритмических систем;

формальное доказательство алгоритмической неразрешимости ряда задач;

классификация задач, определение и исследование сложностных классов;

асимптотический анализ сложности алгоритмов;

исследование и анализ рекурсивных алгоритмов;

получение явных функций трудоемкости в целях сравнительного анализа алгоритмов;

разработка критериев сравнительной оценки качества алгоритмов.

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

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

Практический аспект: методы и методики теории алгоритмов (в основном разделов асимптотического и практического анализа) позволяют осуществить:

рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);

получение временных оценок решения сложных задач;

получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно для криптографических методов;

разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.

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

Немного о способах представления алгоритмов.

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

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

Среди множества известных способов представления алгоритмов, как-то: словесно-формульное представление — описание алгоритма в словесной форме с использованием математических или других формул; подача алгоритма в виде блок- схем, таблиц, формул, схем, рисунков и тому подобное; запись алгоритма на специализированном языке программирования, мы выбрали способ представления алгоритмов псевдокодом.

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

Пример 1.2. Записать на псевдокоде алгоритм Евклида — нахождение наибольшего общего делителя двух чисел.

1.3 Понятие «структура данных»

Обратимся к другому основополагающему понятию Computer Science – «структура данных». Концептуально, понятие «данные» связаны с понятиями «информация» и «знания». Эту триаду представляет рис. 1.5 ( http://socinform4.narod.ru/slovo.html ).

Рисунок 1.5 – Триада «Данные-информация-знания»

Рисунок 1.6 — Схема взаимосвязи понятий «данные», «информация», «знания»

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

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

Данные — сведения, представленные в определенной знаковой системе и на определенном материальном носителе для обеспечения возможностей хранения, передачи, приема и обработки.

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

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

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

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

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

Структуры данных, алгоритмы и умение решать проблемы: улучшаем свои навыки

Перевод статьи «How to improve your data structures, algorithms, and problem-solving skills».

В этом посте отражен мой собственный опыт. Я приступил к своему последнему семестру, не имея практически никаких знаний по структурам данных и алгоритмам, а также не умея решать задачи. Как программисту-самоучке мне были более знакомы такие идеи как объектно-ориентированное программирование. Однако для решения задач по структурам данных и алгоритмам требовались навыки решения проблем.

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

Проблема: вы знаете теорию, однако не умеете применять ее на практике

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

Я довольно хорошо понимал теорию. Например, я знал, что такое связный список, как он работает, какие списки бывают и какова их временная сложность, какие абстрактные типы данных они поддерживают и как реализовываются операции с ними.

Мастер Йода рекомендует:  Пример использования в PHP библиотеки Curl для создания запросов GetPost PHP

Но поскольку я не знал, чего именно я не знаю, я не мог научиться применять все эти знания для решения проблем.

Различные типы вопросов

Вот пример вопроса по структурам данных:

«Опишите, как бы вы вставили узел в связный список, и укажите временную сложность».

А вот по алгоритмам:

«Поиск элемента в перевернутом отсортированном массиве с указанием временной сложности».

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

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

Как улучшить навыки применения структур данных, алгоритмов, а также навыки решения проблем?

Для практики я пользовался главным образом тремя сайтами: HackerRank, LeetCode и Kattis. Они имеют много общего, особенно первые два, однако не совсем идентичны. Я обнаружил, что у каждого сайта немного отличается фокус, и все они очень полезны, но каждый по-своему.

Навыки, необходимые для нахождения ответов на указанные выше вопросы, я бы разбил на три категории:

  1. Знание структур данных.
  2. Знание алгоритмов.
  3. Умение применять структуры данных и алгоритмы.

Первые две группы можно считать «примитивами» или строительными блоками, нужными для успеха в третьей категории.

Знание структур данных

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

Вопросы на знание структур данных касаются не столько решения проблем, сколько умения работать со структурами данных. Например:

  • Массивы: поворот массива (array rotation), манипуляции с массивами (array manipulation)
  • Связные списки: разворот связного списка (reversing a linked list), определение зацикленности (cycle detection)
  • Деревья: замена узлов (node swapping), проверка двоичного дерева поиска (BST validation)

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

На HackerRank нет «моделей решения» в свободном доступе, однако в разделе обсуждения обычно полно подсказок, зацепок и даже отрывков рабочего кода. Я до сих пор находил эти отрывки полезными, хотя поначалу вам, возможно, придется разбирать их построчно в своей IDE.

Знание алгоритмов

На HackerRank есть также и раздел с алгоритмами, но по этой теме я предпочитаю пользоваться LeetCode. Я считаю, что на этом сайте куда шире набор проблем. Кроме того, мне очень нравится, что многие проблемы имеют решение с объяснением и даже временными сложностями.

Хорошим стартом будет раздел top 100 liked questions на LeetCode. Вот некоторые из вопросов, которые мне особенно понравились:

В отличие от вопросов по структурам данных, здесь фокус скорее не на том, как это работает, и не на манипуляциях со структурами данных, а на том, как что-то сделать.

Например, задача со слиянием аккаунтов это прежде всего применение стандартных алгоритмов UFDS (union–find data structure, русск. «система непересекающихся множеств»). «Поиск в повернутом отсортированном массиве» представляет собой измененный двоичный поиск.

Порой случается изучить и совершенно новую технику решения проблем. Например, решение «раздвижное окно» («sliding window») для задачи «Самая длинная непрерывно возрастающая подпоследовательность».

Умение применять структуры данных и алгоритмы

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

Kattis может порой разочаровывать, поскольку там нет официальных решений или форума для обсуждений (в отличие от HackerRank и LeetCode). Кроме того, там скрыты test cases. У меня есть несколько проблем с Kattis, которые я никак не могу решить не потому, что не знаю решения, а потому что не могу найти баг.

Этот сайт мне нравится меньше других, так что я там провожу меньше всего времени.

Другие ресурсы

Еще одним очень ценным ресурсом для изучения структур данных и алгоритмов является Geeksforgeeks. Мне он нравится тем, что там даются отрывки кода на разных языках, обычно на C++, Java и Python. Их можно скопировать и вставить в своей IDE, чтобы проследить решение построчно.

Наконец, есть старый добрый Google, который чаще всего приводит вас к GeeksForGeeks, и Youtube для визуальных объяснений.

Заключение

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

Скачай курс
в приложении

О курсе

Данный курс — это модификация первой части базового курса «Алгоритмы и структуры данных», читающегося в Computer Science Center.

Раз вы уже здесь, нет смысла подробно объяснять, почему важно знать алгоритмы. И всё же в двух словах: без алгоритмов был бы невозможен технологический прогресс; алгоритмы используются практически во всех областях computer science (например, в криптографии, анализе текстов, изображений и видео, биоинформатике); каждый уважающий себя программист должен знать базовые алгоритмы и структуры данных, чтобы писать эффективные программы.

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

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

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

Мы благодарны компании JetBrains, при поддержке которой подготовлен данный курс, а также команде Стэпика и Сергею Аганезову за помощь в подготовке.

Для кого этот курс

Студенты младших курсов и школьники.

Часть задач курса состоит в реализации изученных алгоритмов. Для этого можно использовать один их следующих языков программирования: C++, Java, Python, Octave, Haskell.

Структуры данных и алгоритмы: часть 1

Data Structures & Algorithms: Part 1

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

Структуры данных и алгоритмы являются шаблонами для решения проблем. Разработчики, которые знают больше о структурах данных и алгоритмах, лучше решают проблемы. Вот почему такие компании, как Google, Microsoft и Amazon, всегда задают вопросы о структуре данных и алгоритмах интервью. Они хотят оценить ваши навыки решения проблем. Их не волнует, сколько языков программирования и фреймворков вы знаете.

Сложная тема, сделанная простой

Вот почему я сделал этот курс. Я хочу раз и навсегда демистифицировать структуры данных и алгоритмы.

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

К концу этого курса .

Вы сможете:

  • Писать лучше и быстрее код
  • Стать лучшим разработчиком
  • Повысить свои навыки решения проблем
  • Реализовать все необходимые структуры данных с нуля
  • Использовать десятки популярных алгоритмов

Что вы собираетесь изучать

Этот курс является первым из серии. В этой части мы сосредоточимся на линейных структурах данных. Часть 2 посвящена деревьям и графикам. Часть 3 о алгоритмах поиска и сортировки.

Вот что вы собираетесь выучить в первой части:

  • Big O
  • Массивы
  • Связанные списки
  • Стеки
  • Очереди
  • Хеш-таблицы

Требования

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

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

Вам не нужен опыт работы со структурами данных или алгоритмами для прохождения курса.

Для чего нужны алгоритмы? Основные алгоритмы программирования

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

Алгоритм — что это?

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

Также нужно понимать, что алгоритм как последовательность шагов позволяет решать конкретную задачу и должен: 1. Работать за конечный объём времени. Если алгоритм не способен разобраться с проблемой за конечное количество времени, можно сказать, что этот алгоритм бесполезен. 2. Иметь чётко определённые инструкции. Любой шаг алгоритма должен точно определяться. При этом его инструкции должны быть однозначны для любого случая. 3. Быть пригоден к использованию. Речь идёт о том, что алгоритм должен быть способен решить проблему, для устранения которой его создавали.

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

Алгоритмы сортировки (пирамидальная, быстрая, слиянием)

Какой алгоритм сортировки считают лучшим? Здесь нет однозначного ответа, ведь всё зависит от ваших предпочтений и поставленных перед вами задач. Рассмотрим каждый из алгоритмов: 1. Сортировка слиянием. Важнейший на сегодня алгоритм. Базируется на принципе сравнения элементов и задействует подход «разделяй и властвуй», позволяя более эффективно решать проблемы, которые когда-то решались за время O (n^2). Сортировка слиянием была изобретена математиком Джоном фон Нейманом в далёком 1945 году. 2. Быстрая сортировка. Это уже другой подход к сортировке. Тут алгоритм базируется, как на in-place разделении, так и на принципе «разделяй и властвуй». Однако эта сортировка нестабильна, что и является её проблемой. Зато алгоритм эффективен при сортировке массивов в оперативной памяти. 3. Пирамидальная сортировка. Алгоритм in-place который использует приоритетную очередь (за счёт этой очереди сокращается время поиска данных).

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

Преобразование Фурье. Быстрое преобразование Фурье

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

Алгоритм Дейкстры

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

Алгоритм RSA

Это алгоритм пришёл к нам из криптографии. Он сделал криптографию доступной всем, предопределив её будущее. Вообще, RSA-алгоритм сделан для решения простой задачи с неочевидным решением. Он позволяет делиться открытыми ключами между конечными пользователями и независимыми платформами таким образом, чтобы можно было применять шифрование.

Алгоритм безопасного хэширования

Ну, это не совсем алгоритм. Скорее, его можно назвать семейством криптографических хэш-функций (SHA-1, SHA-2 и т.д.), которые разработаны в США и имеют важнейшее значение для всего мира. Антивирусы, электронная почта, магазины приложений, браузеры и т. п. — во всём этом используются алгоритмы безопасного хэширования (на деле хэш является результатом их работы). Алгоритм нужен для определения, удалось ли вам загрузить то, что хотели, а также не подверглись ли вы фишингу или атаке «человек посередине».

Анализ связей

Идея алгоритма анализа связей проста. Например, вы легко сможете представить график в виде матрицы, что сведёт задачу к проблеме уровня собственной значимости каждого узла. Данный подход к структуре графа позволит оценить относительную важность каждого объекта, который включён в систему.

Алгоритм был создан в далёком 1976 году и используется сегодня при ранжировании страниц в процессе поиска в Google, при генерации ленты новостей, при составлении списка возможных друзей на Facebook, при работе с контактами в LinkedIn и во многих других случаях. Любой из перечисленных сервисов работает с различными объектами и параметрами и объектами, однако сама математика по сути не меняется.

Пропорционально-интегрально-дифференцирующий алгоритм

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

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

Алгоритмы сжатия данных

Сложно сказать, какой алгоритм для сжатия наиболее важен, ведь в зависимости от поставленных задач он может меняться от zip до mp3 либо от JPEG до MPEG-2. Но эти алгоритмы важны почти для всех сфер деятельности.

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

Алгоритм генерации случайных чисел

На самом деле не существует «настоящего» генератора случайных чисел, и мы уже об этом говорили. Зато у нас существуют генераторы псевдослучайных чисел, которые прекрасно с этим справляются. Они имеют расширенную вариативность использования: программные приложения в программировании, криптография, алгоритмы хэширования, видеоигры, искусственный интеллект, тесты при разработке программ и т. д.

Уроки 31 — 32
Алгоритмы, структуры алгоритмов, структурное программирование

Алгоритмы и величины

Этапы решения задачи на компьютере

Работа по решению любой задачи с использованием компьютера делится на следующие этапы:

Часто эту последовательность называют технологической цепочкой решения задачи на компьютере. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.

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

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

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

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

Таким образом, программист должен обладать следующими знаниями и навыками:

• уметь строить алгоритмы;
• знать языки программирования;
• уметь работать в соответствующей системе программирования.

Основой программистской грамотности является развитое алгоритмическое мышление.

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

Одним из фундаментальных понятий в информатике является понятие алгоритма. Сам термин «алгоритм» пришел из математики. Это слово происходит от «Algorithmi» — латинского написания имени Мухамеда аль-Хорезми (787-850 гг.), выдающегося математика средневекового Востока. В XII веке был осуществлен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел — вот первые алгоритмы в математике. Правила алгебраических преобразований, вычисление корней уравнений также можно отнести к математическим алгоритмам.

В наше время понятие алгоритма трактуется шире.

Алгоритм — это последовательность команд управления каким-либо исполнителем.

В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики впервые знакомятся на примерах учебных исполнителей: Робота, Черепашки, Чертежника и др. В учебнике для 9 класса описан графический исполнитель — ГРИС. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.

В разделе информатики под названием «Программирование» изучаются методы программного управления работой компьютера. Следовательно, в качестве исполнителя выступает компьютер. Он работает с величинами — различными информационными объектами: числами, символами, кодами и пр. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.

Данные и величины

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

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

Например, при решении квадратного уравнения: ах 2 + bх + с = 0 исходными данными являются коэффициенты а, b, с; результатами — корни уравнения х1, х2; промежуточными данными — дискриминант уравнения: D = b 2 — 4ас.

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

У всякой величины имеются три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется адресом ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, ‘k’, true. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа или переменная занимают ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

Типы констант определяются по контексту (т. е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных.

Есть еще один вариант классификации данных: классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение. Для структурированных: одна величина — множество значений.

К структурированным величинам относятся массивы, строки, множества и др.

Компьютер — исполнитель алгоритмов.

Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет речь в теме «Программирование обработки информации»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс: компьютер + система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП. Схематически это изображено на рис. 3.2, где входным языком исполнителя является язык программирования Паскаль.

Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на компьютере может быть составлен из команд:

• присваивания;
• ввода;
• вывода;
• обращения к вспомогательному алгоритму (подпрограмме);
• цикла;
• ветвления.

Для описания алгоритмов в дальнейшем мы будем использовать блок-схемы и учебный Алгоритмический язык, применяемый в школьном курсе информатики.

Вопросы и задания

1. Перечислите и охарактеризуйте этапы решения задач на компьютере.

2. Дайте определение алгоритма.

3. Что такое «система команд исполнителя алгоритмов» (СКИ)?

4. Какими возможностями обладает компьютер как исполнитель алгоритмов?

5. Назовите команды, входящие в СКИ компьютера, из которых составляется любая программа обработки данных.

6. Перечислите различные варианты классификации данных.

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

Структура алгоритмов

Базовые алгоритмические структуры

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

С базовыми алгоритмическими структурами вы познакомились, изучая информатику в 9 классе. Там же для описания структур алгоритмов были использованы два способа: блок-схемы и учебный Алгоритмический язык (АЯ). Еще раз покажем, как изображаются базовые структуры в схемах алгоритмов и как они описываются на АЯ.

Следование — это линейная последовательность действий (рис. 3.3).

В программе на Паскале серия — это либо один отдельный оператор, либо составной оператор: последовательность операторов, заключенная в операторные скобки. Например, в языке Паскаль операторными скобками являются служебные слова Begin и End.

Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение. Вот как изображается ветвление на блок-схеме и АЯ (рис. 3.4).

Условие представляет собой утверждение, которое может быть либо истинным, либо ложным. Такое утверждение называется логическим выражением.

Неполная форма ветвления имеет место, когда на ветви «нет» пусто (рис. 3.5).

Цикл — повторение некоторой группы действий по условию. Различают два типа цикла. Первый — цикл с предусловием: цикл-пока (рис. 3.6).

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры — цикл с постусловием: цикл-до (рис. 3.7).

Здесь тело цикла предшествует условию цикла. Тело цикла повторяет свое выполнение, если условие ложно. Повторение прекращается, когда условие становится истинным.

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

Иногда в литературе структурное программирование называют программированием без GOTO — оператора безусловного перехода. Действительно, при таком подходе нет места безусловному переходу. Неоправданное использование в программе оператора GOTO лишает ее структурности, а значит, всех связанных с этим положительных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, с точки зрения структурного подхода, его употребления следует избегать.

Комбинации базовых структур

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

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

Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма. Несколько примеров структурных блок-схем алгоритмов приведены на рис. 3.8 (вместо «да», «нет» здесь использованы знаки « + » и «-», У — , С — ).

Такие блок-схемы легко читаются. Их структура хорошо воспринимается визуально. Структуре каждого алгоритма можно дать название. Приведенные блок-схемы можно охарактеризовать следующим образом (в порядке номеров).

1. Вложенные ветвления. Глубина вложенности равна единице.
2. Цикл с вложенным ветвлением.
3. Вложенные циклы-пока. Глубина вложенности — 1.
4. Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.
5. Следование ветвления и цикла-до.
6. Вложенные циклы. Внешний — цикл-пока, внутренний — цикл-до.

Наглядность структуре описания алгоритма на АЯ придает структуризация внешнего вида текста.

Основной используемый для этого прием — сдвиги строк, которые должны подчиняться следующим правилам:

• конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);
• вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.

Для приведенных на рис. 3.8 блок-схем структура текста на АЯ должна быть следующей:

Такой же способ структуризации используется и в текстах программ (например, на Паскале).

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

Вопросы и задания

1. Перечислите основные базовые алгоритмические структуры и покажите способы их отображения на блок-схемах и в АЯ.

2. Какой алгоритм называется структурным?

3. Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из двух числовых величин наибольшее значение. Первый вариант — с полным ветвлением, второй вариант — с неполным ветвлением.

Мастер Йода рекомендует:  Онлайн-курс «iOS-разработчик»

4. Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из трех числовых величин наименьшее значение. Первый вариант — с вложенными ветвлениями, второй вариант — с последовательными ветвлениями.

5. Для данного натурального числа N требуется вычислить сумму: 1 + 1/2 + 1/3 + . + 1/N. Постройте блок-схемы и напишите на АЯ два варианта алгоритма: с циклом-до и с циклом-пока.

6. Какую структуру будет иметь алгоритм решения следующей задачи? Дано целое положительное число N. Если N — четное, то вычислить N! = 1 • 2 • . • N. Если N — нечетное, то вычислить сумму: 1 + 2 + . + N.

Составьте блок-схему алгоритма решения и опишите его на АЯ.

Паскаль — язык структурного программирования

Программирование для ЭВМ — процесс создания программ управления работой компьютера.

Эволюция программирования

С изобретением программно управляемых вычислительных машин появилась новая профессия — программист. На ламповых ЭВМ первого поколения программисты составляли свои программы, используя непосредственно команды процессора. При этом программисту приходилось самому распределять ячейки памяти под данные и под команды программы. Нужно было знать систему команд процессора и коды всех команд. Исходные данные и команды представлялись в форме двоичного кода, т. е. непосредственно в том виде, в котором они хранились в памяти ЭВМ. Для сокращения записи программ на специальных бланках обычно использовали двоично-восьмеричный или двоично-шестнадцатеричный код. Вот пример команды программы для одного из компьютеров первого поколения:

Такая команда называется трехадресной. Код 0216 относится к команде сложения. 1-й и 2-й адреса — это адреса ячеек ОЗУ, в которых хранятся слагаемые, 3-й адрес — адрес ячейки, куда заносится сумма. Сама команда хранится в ячейке ОЗУ с адресом 2816.

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

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

ADD а, Ь, с

Слово ADD обозначает команду «сложить», а и b — имена переменных-слагаемых, с — переменная, куда помещается результат.

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

Составление программы на ассемблере проще, чем на языке команд процессора. Работу по распределению памяти под данные и команды, перевод команд ассемблера в машинные команды берет на себя специальная системная программа — транслятор.

Из машинной ориентированности программ на ассемблере следует, что такие программы нельзя переносить для исполнения на другие типы ЭВМ с другой системой команд процессора. Эта проблема создавала серьезные ограничения для прикладных программистов. Кроме того, само программирование на ассемблере является достаточно сложным для массового освоения, что ограничивало использование ЭВМ в прикладных областях.

Языки программирования высокого уровня

Следующим этапом развития программирования стало создание языков программирования высокого уровня — ЯПВУ. Примеры ЯПВУ: Паскаль, Бейсик, Фортран, Си, Java и др. Все названные ЯПВУ относятся к так называемой процедурной парадигме программирования. Поэтому их называют процедурными языками программирования. Программы на таких языках представляют собой последовательности команд, описывающих действия (процедуры) компьютера по обработке информации. Существуют другие парадигмы программирования. Относящиеся к ним языки называют декларативными языками программирования (Пролог, Лисп и др.). Однако мы их рассматривать не будем.

Для каждого языка существует машинно-независимый стандарт. Возможность программирования на данном ЯПВУ зависит от наличия на вашем компьютере транслятора с этого языка. Трансляторы для каждого типа компьютера создают системные программисты.

Текст программы на ЯПВУ по своей форме ближе к естественным языкам (чаще всего — английскому), к языку математики. Та же команда сложения двух величин на ЯПВУ похожа на привычную форму математического равенства:

с=а+Ь (на Фортране, Бейсике, Си).

Освоить программирование на языке высокого уровня гораздо проще, чем на ассемблере. Поэтому с появлением ЯПВУ значительно возросло число прикладных программистов, расширилось применение ЭВМ во многих областях.

Большое количество языков программирования появилось в 1960-1970-х годах. В 1965 году в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой, легко изучаемый язык, предназначенный для программирования несложных расчетных задач. Наибольшее распространение Бейсик получил с появлением микроЭВМ и персональных компьютеров.

История Паскаля

Язык программирования Паскаль был создан швейцарским профессором Никлаусом Виртом в 1969 году как язык для обучения студентов структурной методике программирования. Язык получил свое название в честь Блеза Паскаля, изобретателя первого вычислительного механического устройства. Позднее фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для персональных компьютеров, которая вышла за рамки учебного применения и стала использоваться для научных и производственных целей. В Турбо Паскаль были внесены некоторые дополнения к базовому стандарту Паскаля, описанному Н. Виртом.

Со временем язык развивался. Начиная с версии 5.5, в Турбо Паскаль вводятся средства поддержки объектно- ориентированного программирования (ООП). В дальнейшем это привело к созданию Object Pascal — языка с возможностями объектно-ориентированного программирования. В начале 1990-х годов объединение элементов ООП в Паскале с визуальной технологией программирования привело к созданию системы программирования Delphi.

Структура процедурных языков программирования высокого уровня

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

Всякий язык программирования образуют три его основные составляющие: алфавит, синтаксис и семантика.

Алфавит — это множество символов, допустимых в записи текстов программ.

Синтаксис — это правописание языковых конструкций (имен, констант, выражений, операторов и пр.).

Семантика — это смысловое содержание языковой конструкции.

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

Структура программы на Паскале

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

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

В Турбо Паскале, в отличие от базового стандарта Паскаля, возможно:
• отсутствие заголовка программы;
• разделы Const, Type, Var, Label могут следовать друг за другом в любом порядке и повторяться в разделе описаний сколько угодно раз.

Вопросы и задания

1. В каком виде составлялись программы для первых компьютеров?

2. Чем отличались программы на автокодах (ассемблерах) от программ в машинных кодах?

3. Почему ЯПВУ являются машинно-независимыми языками программирования?

4. Что такое трансляция?

5. В какой парадигме программирования реализован язык Паскаль?

6. Что входит в структуру любого процедурного ЯПВУ?

7. Из каких основных разделов состоит программа на Паскале?

Выбор языка программирования для изучения структур данных и алгоритмов [закрыто]

Какой язык программирования вы бы порекомендовали узнать о структурах данных и алгоритмах в?

  • Личный опыт
  • Языковые функции (указатели, OO и т. д.)
  • Пригодность для обучения DS & Концепции

Я спрашиваю, потому что есть некоторые книги, которые не зависят от языка программирования (написаны с математической точки зрения и используют псевдокод). Если я учусь на одном из них, я бы хотел выбрать язык программирования для кодирования и запуска алгоритмов.

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

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

14 ответов

Ответ на этот вопрос зависит от того, что именно вы хотите выучить.

Python и Ruby

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

Кроме того, Ruby и Python являются динамически типизированными языками. Это может быть хорошо, но это также может сбивать с толку новичка, и может быть труднее (на начальном этапе) отлавливать ошибки, поскольку они обычно не будут видны до времени выполнения.

С на другом краю. Хорошо, если вы хотите узнать действительно низкоуровневые подробности, такие как управление памятью, но управление памятью внезапно становится важным фактором, как при правильном использовании malloc () /free (). Это может отвлекать. Кроме того, C не является объектно-ориентированным. Это не плохо, но просто стоит отметить.

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

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

C # язык похож на более современную версию Java. Как и Java, это управляемый (сборщик мусора) промежуточный скомпилированный язык, который работает на виртуальной машине. Любой другой язык, перечисленный здесь, кроме C /C ++, также работает на виртуальной машине, но Python, Ruby и т. Д. Интерпретируются напрямую, а не компилируются в байт-код.

C # имеет те же плюсы и минусы, что и Java, в основном.

Haskell (и т. д.)

Наконец, у вас есть функциональные языки: Haskell, OCaml, Scheme /Lisp, Clojure, F # и т. д. Они думают обо всех проблемах совершенно по-другому и в какой-то момент их стоит изучить, но опять же все сводится к тому, что вы хотите выучить: функциональное программирование или структуры данных? Я придерживаюсь изучения одной вещи за один раз, а не путаю проблему. Если вы в какой-то момент выучите функциональный язык (что я бы порекомендовал), Haskell — безопасный и хороший выбор.

Мои советы

Выберите Java или C #. Оба имеют бесплатные отличные IDE (Eclipse, Netbeans и IntelliJ Community Edition для Java, Visual Studio Express для C #, Visual Studio Community Edition), которые делают написание и запуск кода проще простого. Если вы не используете собственную структуру данных, более сложную, чем массив, и любой объект, который вы пишете сами, вы узнаете в основном то же самое, что и в C /C ++, но без необходимости фактически управлять памятью.

Позвольте мне объяснить: размер расширяемой хеш-таблицы необходимо изменить, если добавлено достаточное количество элементов. В любой реализации это будет означать выполнение чего-то вроде удвоения размера структуры вспомогательных данных (обычно массива) и копирования в существующие элементы. Реализация в основном одинакова во всех императивных языках, но в C /C ++ вам приходится иметь дело с ошибками сегментации, когда вы не распределяете или не освобождаете что-то правильно.

Python или Ruby (не важно, какой именно) будет моим следующим выбором (и очень близким к другому)два) только потому, что динамическая типизация может быть проблематичной на первый взгляд.

Я бы порекомендовал Java в основном потому, что:

  • сборка мусора
  • ссылки
  • богатые коллекции

РЕДАКТИРОВАТЬ: Извините избирателей, пожалуйста, объясните.

По моему мнению, C был бы лучшим языком для изучения структур данных и алгоритмов, потому что он заставит вас писать свои собственные. Это заставит вас понять указатели, динамическое выделение памяти и реализации, стоящие за популярными структурами данных, такими как связанные списки, хеш-таблицы и т. Д. Многие из этих вещей можно воспринимать как должное в языках более высокого уровня (Java, C # и т. Д. ).

Python отлично. Легко читается, полнофункциональный. Если вы собираетесь работать с псевдокодом, Python будет выглядеть довольно знакомо.

Python уже является предпочтительным языком алгоритмов в Калифорнийском университете в Ирвине где это описано так:
« Python представляет собой ориентированный на алгоритмы язык, который крайне необходим в образовании. Преимущества Python включают синтаксис и интерактивность, подобные учебникам, которые стимулируют эксперименты. »

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

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

Преимуществом также является то, что вы можете легко визуализировать различные структуры данных, используя браузер для визуализации графиков и деревьев, используя DOM и Canvas.

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

Оберон-2 или Pascal для компонентов . Последний является надмножеством первого.

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

Когда дело доходит до совершенства языка программирования, я хотел бы процитировать Антуана де Сент-Экзюпери: «Дизайнер знает, что он достиг совершенства не тогда, когда больше нечего добавить, но когда уже нечего брать далеко.». Вирт, даже если этого не достигнуто, идет по правильному пути. В «Виртской строке языков программирования» (Algol -> Pascal -> Modula-2 -> Oberon -> Oberon-2) каждый последующий язык проще и в то же время более мощный, чем предыдущий.

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

Когда вы хотите изучить алгоритмы и структуры данных, вы это имеете в виду. Но если ваш язык «мощный» (имеет много функций, таких как C ++, C #, Java, Python, . ), вы потратите много времени на изучение языка, а не алгоритмов и структур данных. Вы не увидите лес за деревьями. =) Вы можете рассматривать деревья как элементы синтаксиса (и любые другие функции), а лес как важную концепцию (любой алгоритм, структура данных, может быть ООП, как угодно). Чем больше функций (деревьев) у вас есть в вашем языке, тем сложнее становится сделать шаг назад и понять концепции (чтобы увидеть лес).

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

Кроме того, многие книги об алгоритмах и структурах данных используют псевдокод, подобный Algol /Pascal, , и примеры на этих языках будет легко преобразовать. И вы можете непосредственно использовать примеры из книги «Алгоритмы и структуры данных» Вирта. Издание Oberon (2004), PDF (1,2 МБ).

Некоторые дополнительные ссылки:

  • компилятор Oxford Oberon-2 для Linux, Windows, Mac OS X.
  • Компоновщик компонентов BlackBox — среда разработки для Компонента Паскаль. Окна-только. Хорошо работает в Wine.
  • Введение в разработку и анализ алгоритмов Ананы В. Левитина — моя любимая книга о алгоритмы.

Я бы предложил Аду. Он имеет функции для конструкций данных, которых нет в других языках, таких как проверки диапазона type Day is range 1 .. 31; Кроме того, он имеет очень строгие время компиляции и выполнения проверка (если вы не решите ее отключить), упрощая поиск ошибок в вашей реализации.

Если вы хотите пойти по пути наименьшего сопротивления, тогда Python. В нем будет минимальное количество ненужной котельной плиты и тому подобное.

В идеале, я бы хотел изучить алгоритмы на C, чтобы вы могли узнать, что происходит на уровне памяти; Я также хотел бы изучить алгоритмы на функциональном языке, чтобы вы могли видеть, как сходные алгоритмы работают с постоянными структурами данных.

Знаменитые книги Кнута содержат большое количество (придуманной платформы код ассемблера. Это рекомендуется, если вы хотите быть супер хардкорным. Лично я работал в C, когда прорабатывал свой класс алгоритмов (раскрытие: это было всего пару лет назад). Иногда я работаю над некоторыми проблемами в Кнуте, но я не знаю, пойду ли я с MMIX полностью в качестве моего предпочтительного языка для изучения алгоритмов. Я чувствую, что это немного излишне.

ИЗМЕНИТЬ : Это также зависит от того, с чем вы знакомы. Если вы хотите начать работать с текстом алгоритма прямо сейчас, и вы никогда не много работали с C, тогда Python — правильный ответ. Вы хотите, чтобы язык не был огромным препятствием для преодоления, потому что вы хотите наслаждаться этим. Я знаю, что сделал.

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

Я думаю, что Lisp стоит изучить.

Мой первый университетский курс программирования был в Лиспе. До этого я писал программы на нескольких языках в течение 10 лет. Я думал, что первый курс программирования будет скучным, но я ошибся.

Лисп — очень интересный язык, потому что у него очень простой синтаксис. Фокус смещается от синтаксиса к функциональности. Функциональный стиль программирования также чрезвычайно полезен для изучения. После моего курса по Лиспу я обнаружил, что пишу программы на С ++ совершенно новым, лучшим способом, благодаря новым концепциям, которым меня научил Лисп.

Lisp также использует то же представление для кода и данных, что открывает интересный дизайн алгоритма с кодом, сгенерированным на лету, а затем выполненным.

«Если ваш единственный инструмент — молоток, то все ваши проблемы будут выглядеть как гвозди»

Изучите хотя бы несколько языков.

Кроме того, ваш выбор зависит от вашей цели.

Hobby? Работа в мире Windows? Семейство Linux /UNIX?

Тип приложений: бизнес против научных; аппаратные драйверы или приложения?

Настольные приложения или веб-приложения?

У меня есть несколько предложений для вас.

(a) определенно выучите немного J (бесплатно от jsoftware.com; преемник APL; оба J и APL являются творениями Кена Айверсона, победителя Тьюринга . Награда Тьюринга похожа на Нобелевскую премию в области вычислительной техники).

(b) если вы находитесь в мире Windows, начните с c #, потому что в .NET так много работает на c #. Если вы можете, получите копию Тома Арчера «Inside c #» из Microsoft Press. Вы можете получить бесплатную систему разработки для c #, загрузив экспресс-версию Microsoft.

(c) научитесь использовать TDD /BDD . независимо от языка, сначала вы пишете небольшой тест, называемый модульным тестом; затем вы пишете производственный код для прохождения модульного теста; один маленький шаг за раз . это не только язык, который вы используете, это также методология.

(d) выучить некоторый язык ассемблера . ассемблер низкого уровня, почти машинный язык, он даст вам хорошее понимание того, что происходит за кулисами.

(e) за пределами мира Windows, я бы порекомендовал c ++.

Нет лучшего языка.

Если бы речь шла только о языке, программирование было бы проще.

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

Одно можно сказать наверняка: у вас, скорее всего, никогда не останется ничего, чему можно научиться, если вы собираетесь стать программистом.

Вы можете оценить язык с алгебраическими типами данных и сопоставлением с образцом, таким как Standard ML, OCaml, F # или Haskell. Например, вот функция перебалансировки красно-черного дерева двоичного поиска, написанного на OCaml /F #:

Я могу ошибаться, но разве структуры данных и алгоритмы не зависят от языков программирования?

В конце концов, структуры данных — это просто способ организации данных; любой язык высокого уровня будет поддерживать это. Конечно, некоторые языки будут иметь механизмы, реализующие базовые структуры данных (такие как Collections Framework в Java или C ++ STL), но это не мешает вам программировать структуру данных на выбранном вами языке программирования. Более того, алгоритмы написаны в псевдокоде, что делает их независимыми от языка.

Я понимаю, что на самом деле он не отвечает на ваш вопрос, но мне трудно понять, что вы ищете; изучение структур данных /алгоритмов или изучение нового языка.

Новый курс «Алгоритмы и структуры данных»

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

Пользуетесь ли вы списком или стеком? Знаете ли вы, как они работают? Если нет, то как вы можете быть уверены в правильности выбранного вами алгоритма? Умение определять и сравнивать их сложность — первый шаг к пониманию алгоритмов и структур данных.

Измерение сложности алгоритмов — что это такое?

Начнём с другого вопроса: сколько времени уходит на обработку массива из десяти элементов? А сколько уйдёт на обработку тысячи, миллионов элементов? Измерение сложности алгоритма — это анализ времени, которое требуется для обработки очень большого количества данных. Такой процесс называется «асимптотический анализ».

Задача: алгоритм обрабатывает пятьсот элементов за 10 миллисекунд. Что будет, если загрузить в него ещё тысячу? Сколько времени уйдёт на обработку данных: десять минут, три года? Стоит ли задумываться об этом перед тем, как сдавать проект заказчику?

Новый курс GeekBrains «Алгоритмы и структуры данных»

На курсе мы подробно исследуем язык C — это превосходная возможность “пощупать” механизмы, которые лежат в основе современных фреймворков.

Чему вы научитесь:

  • Основам программирования на языке C;
  • Структурам данных и алгоритмам, которые лежат в основе их работы;
  • Общим подходам и полезным методикам для решения сложных задач;
  • Инструментам оценки сложности решаемых задач;
  • Создавать консольные программы на языке C в среде разработки QT;
  • Создавать программы, используя собственные алгоритмы;
  • Создавать собственные структуры данных: стеки, списки, деревья и др.;
  • Оценивать производительность программ;
  • Использовать “незащищённый” режим работы с памятью, основанный на указателях;
  • Динамически выделять и освобождать память;
  • Использовать рекурсию.

Мы добавили новый курс в профессии:

Посмотреть описание уроков и дату начала обучения можно здесь:

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

Пользуетесь ли вы списком или стеком? Знаете ли вы, как они работают? Если нет, то как вы можете быть уверены в правильности выбранного вами алгоритма? Умение определять и сравнивать их сложность — первый шаг к пониманию алгоритмов и структур данных.

Измерение сложности алгоритмов — что это такое?

Начнём с другого вопроса: сколько времени уходит на обработку массива из десяти элементов? А сколько уйдёт на обработку тысячи, миллионов элементов? Измерение сложности алгоритма — это анализ времени, которое требуется для обработки очень большого количества данных. Такой процесс называется «асимптотический анализ».

Задача: алгоритм обрабатывает пятьсот элементов за 10 миллисекунд. Что будет, если загрузить в него ещё тысячу? Сколько времени уйдёт на обработку данных: десять минут, три года? Стоит ли задумываться об этом перед тем, как сдавать проект заказчику?

Новый курс GeekBrains «Алгоритмы и структуры данных»

На курсе мы подробно исследуем язык C — это превосходная возможность “пощупать” механизмы, которые лежат в основе современных фреймворков.

Чему вы научитесь:

  • Основам программирования на языке C;
  • Структурам данных и алгоритмам, которые лежат в основе их работы;
  • Общим подходам и полезным методикам для решения сложных задач;
  • Инструментам оценки сложности решаемых задач;
  • Создавать консольные программы на языке C в среде разработки QT;
  • Создавать программы, используя собственные алгоритмы;
  • Создавать собственные структуры данных: стеки, списки, деревья и др.;
  • Оценивать производительность программ;
  • Использовать “незащищённый” режим работы с памятью, основанный на указателях;
  • Динамически выделять и освобождать память;
  • Использовать рекурсию.

Мы добавили новый курс в профессии:

Посмотреть описание уроков и дату начала обучения можно здесь:

Добавить комментарий