Программирование – это новая грамматика. Но как именно мы пишем хорошие программы? Вот вопросы, на которые нам нужно ответить:

● Как мы получаем алгоритмические решения проблемы?

● Как мы узнаем, что решение действительно работает?

● Даже если мы уверены, что это работает, как мы указываем компьютеру выполнить именно это решение?

Если вы часто размышляете над этими вопросами, то уже философствуете.


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

Первый принцип: вам нужно много думать

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

Но они не могут решить настоящую проблему, например, "как мне добраться до моего офиса из дома?"

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

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

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

Логика программиста

Теперь перейдем к описанию проблемы. Но для ее понимания приведем некоторые примеры ввода-вывода данных:

● Индукция. Нам нужен алгоритм обработки аналогичных примеров. Каким образом осуществляется индукция: на практике путем обобщения принципов.

● Дедукция. Как узнать, работает ли система при вводе нового неизвестного данного? Для этой цели мы используем метод дедукции, чтобы доказать верность нашего алгоритма.

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

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

Процесс

1. Обобщение принципов на основе опыта: алгоритмы

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

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

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

Итак, процедура алгоритма:

1. Вот некоторые настройки: (1) считать, сколько вершин учли: это один набор (visited), (2) запомнить известные кратчайшие расстояния до каждой вершины, которые используются лишь для уже обнаруженных вершин: другой набор distance (u). Прямая от каждой вершины изначально бесконечна, за исключением исходной со значением "0".

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

3. Стоя на вершине u, мы изучаем ребра, которые от нее отходят. Каждое ребро, скажем (u, v), дает нам путь к вершине v, для которого вершина u будет последней. Если какое-либо ребро окажется более коротким к вершине v или самым первым, когда мы обнаружили вершину v, всегда можно обновить набор кратчайших путей. В остальных случаях продолжайте движение.

4. Работа с вершиной u окончена, поэтому мы добавляем ее в наш набор visited.

5. Вернитесь к шагу 2, продолжайте исследовать, пока не пройдете все вершины.

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

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

2. Выявление общих принципов при дедукции

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

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

Вот основная линия доказательства:

1. Для всех учтенных вершин мы найдем кратчайшие пути.

2. Пункт назначения учитывается.

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

Разве это не кажется вам знакомым? Например:

1. Все люди смертны.

2. Сократ – человек.

3. Следовательно, Сократ смертен.

На самом деле это силлогизм, классическая форма дедуктивного рассуждения. В основном это то, чем занимаются логики.

Еще один интересный исторический факт: формально концепция вычисления была впервые разработана логиками в 30-х годах ХХ века. Им нужно было знать, могут ли окончательно быть решены определенные логические задачи (чтобы избежать траты времени на решение чего-то неразрешимого). Для ответа на этот вопрос, они предложили идею вычислимости.

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

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

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

Общая схема следующая. Первое — если алгоритм работает при значении равном 0. Второе — если алгоритм работает при значении равном n, подразумевается, что алгоритм действителен и со значением равным n + 1. Это значит, при входных данных, больших или равных 0, алгоритм работает. На этом этапе можно гарантировать верность алгоритма.

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

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

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

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

Возможно, вы заметили, что в нашем примере алгоритм поиска пути не работает, если вес ребра отрицательный. Причину этого можно найти в этой лекции. Для обработки графика с отрицательным весом вы можете использовать алгоритм Bellman-Ford.

3. Проблема онтологии: структура данных

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

Следующий вопрос: как мы передаем информацию на компьютеры? Людям нравится визуализированная информация, такая как графики или гистограммы. Но сегодняшние компьютеры занимаются только двоичными битами.

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

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

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

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

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

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

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

1. Апостериорное предложение: исправление ошибок

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

Например, ошибки сегментации в программах на C часто происходят из-за ссылок с нулевым показателем. Я узнал об этом после обработки тонны ошибок сегментации C / C ++. Конечно, есть отдельные случаи, которые касаются личных привычек в программировании.

Другой пример – синтаксическая ошибка, сделанная программистом. Условие if должно быть is_float == 1, но программист ошибочно принял за оператора логического равенства == оператора оценки =. В любом случае компилятор оценк будет пройден, так как оба синтаксиса верны.

if (is_float = 1) {

// do something

}

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

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

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

Почему это важно?

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

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

Для практики мы рекомендуем эту статью о том, как думать, как программист, и эту книгу на ту же тему, но с более подробной информацией.