Можно написать программу которая не будет алгоритмом верно ли

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.

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

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

Прекрати задрачивать алгоритмы

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

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

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

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

Не могу написать программу! Что делать! Как начать писать код!

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

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

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

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

Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого?

Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary?

Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map.

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

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

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

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

Со мной работал один программист со стажем больше десяти лет. Однажды нам понадобилась функция, которую использованная нами библиотека на тот момент не поддерживала: примитивный text-wrap в одном из визуальных компонентов. Этот «программист» посмотрел, что стандартными средствами это сделать нельзя, и сразу заявил, что реализация такой функции невозможна.

Задачу решил интерн-третьекурсник с аналитическим мозгом, который за два часа написал простой алгоритм и внедрил его в нужный компонент. Другой проект в виде сайта на .net мне достался по наследству. Главная страничка представляла собой несколько маленьких графиков, и загружалась почти 10 секунд. Оказалось, что человек, который изначально делал этот проект, нагородил кучу ужасных конструкций из тройных вложенных циклов, которые долго и печально забирали данные из БД, и потом привязывали их к графикам. После небольшого рефакторинга страница стала грузится почти мгновенно.

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

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

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

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

• программирование
• алгоритмы
• размышления вслух

• Программирование
• Алгоритмы

Источник: habr.com

Урок 61
Алгоритмически неразрешимые задачи
(§35. Алгоритмически неразрешимые задачи)

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

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

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

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

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

В 1900 г. на Международном математическом конгрессе в Париже известный математик Давид Гильберт сформулировал 23 нерешённые математические проблемы 1 .

1 Сейчас большинство из них решено полностью или частично.

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

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

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

Немецкий математик Г. В. Лейбниц в XVII веке безуспешно пытался найти метод проверки правильности любых математических утверждений. Как вы знаете, почти все математические теории основаны на использовании аксиом (положений, принимаемых без доказательства), из которых выводятся все остальные утверждения (теоремы). Задача заключалась в том, чтобы разработать алгоритм, позволяющий установить, можно ли вывести формулу Б из формулы А в рамках заданной системы аксиом («проблема распознавания выводимости»).

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

2 Тем не менее отдельные классы теорем можно доказывать на компьютере.

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

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

3 Допустим, что (1) задача А неразрешима и (2) если мы можем построить алгоритм для решения задачи Б, то с его помощью можно построить алгоритм решения задачи А. Тогда задача Б тоже неразрешима.

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

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

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

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

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

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

Следующая страница Вопросы и задания

Cкачать материалы урока

Источник: xn—-7sbbfb7a7aej.xn--p1ai

Понятие алгоритма. Исполнитель алгоритма

Будьте внимательны! У Вас есть 10 минут на прохождение теста. Система оценивания — 5 балльная. Разбалловка теста — 3,4,5 баллов, в зависимости от сложности вопроса. Порядок заданий и вариантов ответов в тесте случайный.

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

Система оценки: 5 балльная

Список вопросов теста

Вопрос 1

Варианты ответов

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

Вопрос 2

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

Варианты ответов

• Технические устройства.
• Человек.
• Робот.

Вопрос 3

Создание рисунка в графическом редакторе Paint.

Варианты ответов

• Открыть стандартное приложение Windows Paint.
• Создать изображение с помощью панели рисования.
• Закрасить рисунок.
• Сохранить созданный рисунок.
• Закрыть приложение Windows Paint.

Вопрос 4

Исправьте алгоритм «Поездка в гости»

Варианты ответов

• Выйти из дома.
• Дойти до автобусной остановки.
• Сесть в автобус №10.
• Проехать 3 остановки.
• Выйти из автобуса.
• Дойти до дома, в котором живет друг.

Вопрос 5

Можно ли считать следующие команды алгоритмом?
а) Пойди туда — не знаю куда;
б) принеси то — не знаю, что.

Варианты ответов

Вопрос 6

Что из ниже перечисленного является алгоритмом?

Варианты ответов

• Каталог книг в библиотеке;
• инструкция по сборке шкафа;
• программа телепередач;
• рецепт приготовления клея;
• настенный календарь на текущий год.

Вопрос 7

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

Варианты ответов

• взять тряпку;
• намочить тряпку.
• отжать тряпку;
• Вытереть доску;

Вопрос 8

Выполните следующий алгоритм и введите
в прямоугольник результат:
1) написать слово ПАСТОРАЛЬ;
2) удалить ТОРА;
3) поменять местами буквы П и С;
4) вставить после буквы П слово ЛАНИТА;
5) удалить все буквы А;
6) дописать букву О после буквы П;
7) дописать букву Е после буквы Т;
8) дописать в начало слова букву И.

Вопрос 9

Составьте алгоритм, позволяющий добраться до сердца Кощея.
» — Выйдешь за меня замуж, — сказал Кощей Марье Моревне, — озолочу.
— Как же за тебя замуж идти, когда у тебя сердца нет?!
— Есть у меня сердце! Есть! Спрятано оно в черном яблоке, что на черном дереве. А черное дерево растет на черной горе.»

Варианты ответов

• Идти на черную гору
• Найти черное дерево
• Сорвать черное яблоко
• Найти сердце Кощея

Вопрос 10

Установите взаимно-однозначное соответствие между понятиями в левом столбце и определениями в правом столбце таблицы.

Указание исполнителю выполнить конкретное действие

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

Конечная последовательность команд

Объект, способный выполнять команды

Варианты ответов

• Алгоритм
• Команда
• Исполнитель
• Система команд исполнителя

Источник: videouroki.net