Говоря информатика в математике

Question

Я нахожусь в процессе написания довольно длинной монографии на тему информатики.Тем не менее, я обычно нахожусь в состоянии написать какую-то концепцию информатики в математических терминах, и мне это трудно.Например, скажем, я хочу написать цикл for или функцию void.Я чаще всего хожу к Кнуту, Кормену или Седжвику, но их сейчас недостаточно.Есть ли «руководство» или какой-нибудь текст, который я могу взять в качестве примера для перевода информатики в математику?

Редактировать

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

Answer 1

Суммирование или запись продукта, вероятно, могут заменить некоторые циклы for.Другие, вероятно, могут быть выражены как логические квантификаторы («существует i, такой, что a [i] имеет некоторое свойство» или «a [i] имеет некоторое свойство для всех i»).(Извините, я не знаю, как отобразить их в Markdown ... надеюсь, вы поняли идею.)

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

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

Answer 2

Я думаю, вы должны быть более конкретным.Вы говорите о переводе алгоритмов?Написание кода в виде псевдокода?

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

В зависимости от того, что вы пытаетесь сделать, Hoare Logic является хорошим способом представления шагов алгоритмов, ИМХО.

Вы также можете формально указатьнекоторые архитектуры и протоколы, использующие нотацию Z .

Answer 3

Вы можете посмотреть на Элементы программирования . Автор Александр Степанов и Пол МакДжонс:

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

Answer 4

Чтобы ответить на ваш конкретный вопрос: в математике, если он не принимает аргументов и возвращает случайную строку длины n, он, вероятно, вообще не является функцией!То есть, если f () не равно f () (например, с f () = rand ()), то по определению f () не является функцией.Вы можете решить это по-разному, в зависимости от ваших предпочтений: вы можете передать ему параметр состояния и вернуть ему измененный параметр состояния, или вы можете сделать его многозначной функцией и вернуть все возможные значения, или вы можете использовать две функции:f (n, состояние) дает следующую случайную строку длины n, а g (n, состояние) дает новое состояние после генерации f (n, состояние).