*Математика и программирование

[mnashe]

А если программа бы не выдала ни одного решения? Где гарантия, что их действительно нет?

Это исключено, поскольку программа перебрала все возможные варианты (больше миллиарда — 1,147,715,240).

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

Дык	задача тривиальная.

У меня действительно очень простая задача и очень простой алгоритм.
Щас объясню алгоритм перебора.
Если не учитывать порядок, то у каждой пары есть только три допустимые соседние пары. Пример я выше уже приводил: для 1-2 это 3-4, 3-5 и 4-5.
Берём и нумеруем допустимых соседей. Для каждой из 10 пар их всего три, а всего есть 19 переходов, стало быть, задача сводится к последовательному перебору всех 19-значных троичных чисел.
Проверки две: одна выполняется на каждом шагу, другая только в конце (после 19-го шага).
Первая проверка: если на очередном преобразовании вышла пара, встречавшаяся ранее уже дважды, то все числа, начинающиеся с этой же последовательности, запрещены и перебирать их нет смысла, так что сразу увеличиваем тот разряд, где мы наткнулись на запрет. Это резко сокращает количество перебираемых вариантов.
Вторая проверка: последняя пара является допустимым соседом первой.

[mnashe]

У меня для тех же целей в ванной песочные часы на 3 минуты.

У меня тоже есть. Для той же цели куплены. Но стоят в спальне про запас.
Преимущества самоделки:
1. Красиво! С детства обожаю цветные лампочки
2. Не бьётся при падении.
3. Может пользоваться одновременно любое количество людей, стартовавших несинхронно. Просто каждый должен отметить в голове свою точку старта.
У наших детей почти всегда ситуация такова. Так что актуально. Песочных часов потребовалось бы 2 штуки.

[mnashe]

Вот это тебе делать нечего, уж прости Если бы я взялся заниматься чем-то подобным на работе, меня бы шеф сразу остановил. Просто потому, что там вопрос звучит так: что дешевле - потратить 100 долларов на готовое устройство и 10 минуты на его программирование или же потратить 100 долларов на час работы программиста.

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

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

Во-о-от!

[mnashe]

Все науки делятся на 4 группы.
1) Естественные науки. Физика там, химия, биология, геология.
2) Неестественные науки. К примеру, шекспироведение. Шекспира читать надо, а не науки вокруг него разводить.
3) Противоестественные науки. Ну это все знают: научный атеизм, история КПСС и т.п. Сегодня я бы добавил "науку каббалу" Лайтмана.
4) Сверхъестественные науки. Это, по сути, одна наука, и это математика.

[_Swetlana]

Меня повалили и дружно пинали ногами 

Интересно, чем пинали аргументировали...

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

[_Swetlana]

Сверхъестественные науки. Это, по сути, одна наука, и это математика.

О, как раз тема всплыла, репутация постов на ЛФ. Там ссылка есть, на поиск репутации по имени. Попутала малость. Вот этот пост:

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

[Lodur]

А могли ведь коньками с ботинками.

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

[_Swetlana]

У вас, небось, и стакан всегда наполовину полон...

На целый стакан у меня уже здоровья нет 

[Ыняша]

Есть изоморфизм Карри-Говарда: программа — это доказательство теоремы. А по hott, есть изоморфизм матлогики, теории множеств, теории гомологий и теории типов. 

[_Swetlana]

Есть изоморфизм Карри-Говарда: программа — это доказательство теоремы. А по hott, есть изоморфизм матлогики, теории множеств, теории гомологий и теории типов. 

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

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

[mnashe]

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

Ага. Даже в моей простенькой задачке пришлось слегка математически подумать, чтобы перебор не растянулся на несколько недель.
Представь, если бы я перебирал не миллиард вариантов (3¹⁹), причём периодически перескакивая сразу через десятки и сотни миллионов, а все 10²º, решая задачу тупо в лоб. Я сначала посчитал, сколько времени займёт такой перебор (ибо зачем оптимизировать, если программа пишется на один раз?), и понял, что так не выйдет. Тогда вот и нашёл этот вариант с перебором связей, а не самих групп.

[Ильич]

Был такой физик Ричард Фейнман. Его "Фейнмановскими лекциями по физике" я просто восхищался в своё время. И там он написал, что математика вообще не наука, потому что она не изучает природу.
Я для себя решил, что математика всё же изучает природу - природу человеческого мозга.

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

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

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

Только ближе к 60-то годам пришлось сменить род занятий. А с этого года вообще чистый пенсионер. Развлекаюсь.

[Ильич]

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

Это уже делают, насколько я слышал. Но не для самых сложных случаев.

[_Swetlana]

Математика - язык. А математическая логика - наука о языке. Логично 
Помню, как С.Б. Стечкин на лекции сказал, что сплайны - это кусок хлеба. Математика кормит (если не брать преподавание) только в каких-то прикладных задачах.

[_Swetlana]

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

[Ильич]

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

[Ильич]

Математика - язык. А математическая логика - наука о языке. Логично 
Помню, как С.Б. Стечкин на лекции сказал, что сплайны - это кусок хлеба. Математика кормит (если не брать преподавание) только в каких-то прикладных задачах.

Нет, совсем не логично.
А про математику, как способ прокормиться это вы в качестве реплики к моему сообщению написали?

[Ыняша]

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

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

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

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

[From_Odessa]

Я для себя решил, что математика всё же изучает природу - природу человеческого мозга.

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

Я тут вот писал в свое время еще свои мысли о математике - О математике

Хотя частично я уже с самим собой не согласен.

[Flos]

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

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

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

[_Swetlana]

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

Ипотеку не брали, проценты не рассчитывали?

[_Swetlana]

Математика - язык. А математическая логика - наука о языке. Логично 
Помню, как С.Б. Стечкин на лекции сказал, что сплайны - это кусок хлеба. Математика кормит (если не брать преподавание) только в каких-то прикладных задачах.

Нет, совсем не логично.
А про математику, как способ прокормиться это вы в качестве реплики к моему сообщению написали?

В качестве реплики.
Что не логично? 

[Flos]

Ипотеку не брали, проценты не рассчитывали?

Ага, смешно.
У меня жена деньги считает, мне не доверяет.

[_Swetlana]

Сыну задачки не решали? 

Низшая математика

Пап, а пап, у меня тут по математике задали...- Гоша неловко переминался с ноги на ногу.
- У мамы спроси. – отбил подачу Иван Иванович.
- Мама сказала, что в ее жизни слишком много вычитания и деления и отправила к тебе.
- И умножения. Местами. – хихикнул Иван Иванович. – Что там за задача?
- Гражданин взял в банке десять тысяч и через полгода вернул шестнадцать. Под какой процент брал кредит гражданин? – прочитал Гоша.
- И что тебе тут непонятно? – укоризненно спросил Иван Иванович.
- Пап, мне надо задачу решить. – сказал Гоша. – Мне не надо вот это «У нас есть десять и шестнадцать. А еще у нас есть шесть месяцев. Что надо сначала сделать?». Мне ответ нужен. И решение.
- А самому...
- А самому мне мозгами раскинуть слабо. – перебил Гоша и умело имитировал интонации отца: - Я способный, но лень меня погубит. И вот сейчас я пришел не потому, что не умею решать, а потому что мне лень самому напрягаться. Мне легче прийти, ты решишь, я запишу решение и ответ. И поскорее сяду играть в компьютер. А знаний по математике у меня останется ноль. Я бестолковый и позорю отца.
- Хахаха. – не удержался Иван Иванович. – Я так говорю? А.. Ну да... Я так говорю. В общем, надо от шестнадцати отнять десять – получится шесть. Это интерес банка. Шесть поделить на десять и умножить на сто. Получается шестьдесят процентов.
- Значит ответ – шестьдесят? – переспросил Гоша.
- Значит ответ – девяносто процентов годовых. – выдал Иван Иванович.
- Не понял. Откуда девяносто? – удивился Гоша.
- Оттуда. Рассмотрение заявки, заключение договора залога и заключение кредитного договора составит процентов пятнадцать. Остается сорок пять на полгода. Годовых – девяносто. Так и пишут в рекламе. – пояснил Иван Иванович.
- Здорово живешь! – появилась в дверях мать Гоши, Софья Александровна. – А вдруг он на три месяца брал и ему просрочку с пеней вклеили?
- Пеню брать с физических лиц запрещено. – возразил Иван Иванович. – Не слушай ее, Гоша. Пиши – девяносто годовых.
- Да нет таких процентов сейчас! Нету! – начала горячиться Софья Александровна.
- Дай-ка, Гоша, учебник сюда. – попросил Иван Иванович. – Что и требовалось доказать! Учебник девяносто четвертого года. Тогда такие проценты были. Съела?
- Тогда и пеня и просрочка брались. – ответила Софья Александровна. – Съел?
- Тогда физическим лицам вообще не давали! – ляпнул Иван Иванович.
- Под одну пятую от залога – давали! – сказала Софья Александровна. – Грамотей. Взял десять. С ежемесячным погашением процентов и погашением кредита по концу срока. Человек не платил проценты. После первого месяца по первой сумме включается двойная ставка с пеней на сумму задолженности в размере одного процента от суммы задолженности в день. После второго – на вторую сумму. После третьего – на третью сумму процентов, на основной кредит и задолженность за первые два месяца.
- Да там было бы за сто тысяч! – взвыл Иван Иванович.
- Это если по девяносто годовых. А если под меньше – то нет. – спокойно возразила Софья Александровна. – А под сколько – тебе и надо посчитать.
- Фигня вопрос. – сказал Иван Иванович. – Гоша дай лист бумаги и ручку. За икс принимаем месячную процентную ставку. Считаем проценты – икс на сумму кредита. Считаем пеню – перемножаем задолженность на сто пятьдесят, сто двадцать и девяносто дней. Считаем просрочку в два раза. И проценты. Складываем. Все равно шести тысячам. Уравнение.... Итого... получается пятьдесят семь процентов годовых! Или четыре и семь в месяц. Ну, приблизительно.
- А давайте я лучше шестьдесят напишу, а? – тоскливо спросил Гоша. – Я ж этого всего никогда не пойму..
- Трус! – сурово ответили родители. – Вот решение. Пиши.
- Двойку же получу. – заныл Гоша.
- Пиши, тебе говорят! – сказал отец. – И ответ – в случае трехмесячного кредита с просрочкой и пеней, при отсутствии банковской комиссии за выдачу и оформление кредита...
- И отсутствия дисконтирования процентов. – добавила мама. – Тогда модно было дисконтировать. Но тогда и просрочка... А ты посчитал просрочку и пеню по основному долгу?
- Охтыж, йоо. – протянул Иван Иванович. – Забыл совсем.
- Растяпа. – ласково сказала Софья Александровна.
- А нет! Посчитал. Вот же – шестьдесят икс! Это просрочка по основному долгу. Не путай меня!
- А пеню? – ехидно спросила супруга.
- Черт! – ругнулся Иван Иванович и пересчитал все. – Не путай меня, я сказал! Не бралась пеня на основную сумму.
- Это почему это? – поинтересовалась супруга.
- Потому как пеня на десять тысяч за девяносто дней в любом случае больше шести тысяч. – победно пропел Иван Иванович.
- Так и пиши, Гошенька. – сказала мама. – При отсутствии дисконтирования процентов и взымания пени только за просроченные проценты, а не за задолженность по основной сумме – человек брал кредит приблизительно под пятьдесят семь процентов годовых. Приблизительно – из-за округлений.
- За двойку чтоб не ругались! – предупредил Гоша.
...
- Пап, а пап. – переминался Гоша с ноги на ногу на следующий день. – Тут математичка опять задачу задала....

Под домашним заданием, красной пастой было выведено:
«Отлично!!! Гоша, реши, пожалуйста следующую задачу:
Семья учителя математики получает пятьдесят тысяч рублей совокупного дохода в месяц. Какие условия кредита были бы приемлемыми для этой семьи, так чтобы ежемесячный платеж не превышал десять тысяч рублей? Какую максимальную сумму может взять эта семья на пятнадцать лет? В какой валюте лучше брать кредит и в каком банке?»
- Ну это просто, Гоша. – хмыкнул Иван Иванович. – Пусть в сбербанке берет. Миллиона три-четыре. С отсрочкой платежей на пять лет. Под тридцать процентов.
- А это правильный ответ? – засомневался Гоша.
- Неа. – радостно сказал Иван Иванович. – Но твоя математичка узнает об этом только через пять лет. А ты уже в шестом.

[zwh]

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

Вирт -- швейцарский программист, если чё.