Developers Club geek daily blog

Soviet school: address programming language

1 year, 7 months ago
The address programming language is considered one of the first programming languages of the high level. It was created by the Soviet developer Ekaterina Logvinovna Yushchenko together with the mathematician Vladimir Semenovich Korolyuk in 1955. Constructions of this algorithmic language were included into a basis of the modern languages of programming.

Developments of the member of the correspondent of Academy of Sciences of the USSR Alexey Andreevich Lyapunov became a peculiar base for address language. This outstanding mathematician created the operator programming method which was widely adopted in practice and exerted strong impact on all subsequent development of theoretical programming.


Ekaterina Logvinovna Yushchenko and Vladimir Semenovich Korolyuk

Read more »


Chaos generators on COTTON VELVET

1 year, 7 months ago
Hi everyone!

This article is devoted to surprising features in the world of chaos. I will try to tell about how to bridle such strange and difficult thing as chaotic process and to learn to create own elementary generators of chaos. Together with you we will pass a way from the dry theory before fine visualization of chaotic processes in space. In particular, on the example of the known chaotic attractors, I will show how to create dynamic systems and to use them in the tasks connected with the programmable logic integrated circuits (PLIC).


Read more »


John Horton Conway: Life as game — the termination

1 year, 7 months ago
first part

Having arrived home, Gardner immediately showed to Conway more than 20 articles devoted to calculation of a day of the week for any date. Lewis Carroll's rule looked better than the others. Gardner turned to Conway and told: "John, you need to develop simpler rule which I will be able to share with readers". And, as Conway, long winter nights when Mr. and Mrs. Gardner went to sleep at home (though on a visit he came to them only in the summer) tells, Conway reflected how to make such calculation rather simple that it could be explained to the average any passer-by.

He thought over it all way home, and in the general room of university, and at last guessed "the rule of the Doomsday". For work only addition, subtraction and storing were required for algorithm. Also Conway thought up the mnemonic rule helping to store intermediate calculations on hand fingers. And for the best storing of information on date, Conway bites the thumb.

Traces from teeth have to be visible! Only this way it is possible to remember it. When I tell students about this method, I always ask someone from the first row to confirm existence of marks from teeth in a finger. Serious people so you will not force to do – they will decide that it is kindergarten. But sense that all this business usually is not delayed at you in a brain and you forget the date of birthday designated to you by the person. But the thumb is capable to remember for you how far this date will be spaced from next "Doomsday".


Over the years Conway taught this algorithm thousands of people. Sometimes in a conference room the person on 600, calculating birthdays of each other and biting the thumbs is taken. And Conway, as always, tries to be unreasonable – he is not satisfied with the simple algorithm any more. Since the moment of development he tries to improve it.

Read more »


Simple algebraic data types

1 year, 7 months ago
It is the sixth article from the cycle "The Category Theory for Programmers". The previous articles were already published on Habré:
0. The category theory for programmers: preface
1. Category: composition essence
2. Types and functions
3. Categories, big and small
4. Kleysli's categories
5. Works and koproizvedeniye

In the previous article basic operations over types were considered: work and koproizvedeniye. Now we will show that the combination of these mechanisms allows to construct many of daily data structures. Such creation has essential applied relevance. For example, if we are able to check base data types for equality, and also we know how to reduce equality of work and a koproizvedeniye to equality a component, then operators of equality for composite types it is possible to display automatically. In Haskell for an extensive subset of composite types operators of equality and comparison, converting at line and back and many other operations are automatically brought.

Let's consider in more detail the place of work and a koproizvedeniye of types in programming.

Work of types


Canonical implementation of work of types in programming languages is a couple. In Haskell of steam is a primitive designer of types, and in C ++ it is rather difficult template from standard library.
Pair
Strictly speaking, work of types is not commutative: it is impossible to substitute couple of type (Int, Bool) instead of (Bool, Int), though they also contain the same data. However work is commutative to within the isomorphism set by function swap, which back to:
swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

It is possible to consider such couples as different formats of storage of the same information as big endian and little endian.

Read more »


John Horton Conway: Life as game

1 year, 7 months ago
John Horton Conway claims that he did not work day in the life. This fragment from the biography "The Genius behind Game" shows what serious mathematical theories, like syurrealny numbers, can appear from entertainments and games.

image

Gnawing a forefinger of the left hand the old broken-off British teeth, with the bulked-up senile veins, with the eyebrow which is thoughtfully frowned under long ago unbarbered hair, the mathematician John Horton Conway without regret spends the time for thoughts and theoretical researches. Though he will claim that he is engaged, lazy nothing, and plays toys.

It works in Princeton though it found glory in Cambridge (being at first a student, and then professor from 1957 to 1987). Conway, 77, claims that he did not work day in the life. He means that he spends almost all the time for games. And at the same time, he is professor of Princeton of applied and calculus mathematics (already honourable). Member of Royal community. And recognized genius. "The title "genius" is often incorrectly used", - Percy Dyakonis, the mathematician from Stanford says. – John Conway is the genius. At the same time it can work in any area. And it has an intuition for any unusual things. It cannot be put in any mathematical framework".

Read more »


Stephen's book of Elementary Introduction to the Wolfram Language Language Tungsten

1 year, 7 months ago

Transfer of a post of Stephen Wolfram "I Wrote a Book — To Teach the Wolfram Language".
I express huge gratitude to Kirill Guzenko of KirillGuzenko for the help in transfer and preparation of the publication

The book "Elementary Introduction to the Wolfram Language Language" is available to you in printed form, is free on the Internet, and also in other forms.



I was not sure that I will sometime write one more book. My latest book — the New type of science — took me more than ten years of the hard concentrated work and is my largest project from all that I ever did.

But some time ago I understood that I should write one more book — such which would acquaint the people not familiar with programming, with the Wolfram Language language and methods of thinking in the computing sphere which are presented by this language.

Result — the book Elementary introduction to the Wolfram Language language which was published today. It is also freely available on the Internet, and in other forms.


Read more »


Multiplication by a method of the Russian peasants

1 year, 8 months ago
Sometimes this method call "country multiplication", sometimes "Ancient Egyptian", sometimes "Ethiopian", sometimes "multiplication through doubling and halving". Some it is well-known, some – is unclear, but at the same time it is rather useful and can be used not only for multiplication, but also for exponentiation and calculations of matrixes.

Algorithm


  13  x  19 ->     0
   6     38       19
   3     76 ->
   1    152 ->    95
   0    304      247
                 ^^^

Let's write two multiplied numbers nearby – they will become headings of two columns. The third column will contain the increasing sum.

If number in the left column odd, we add number from the right column to the increasing sum. Initially it will be equal to zero.

Then in the left column below we write number from heading, divided in half (with discarding of a remaining balance). 13 / 2 = 6. And in the second column we write the number equal to doubling of column heading, 19*2 = 38.

As number in the left column even, we do not increase the increasing sum.

Read more »


Open lecture: problem of feasibility of Boolean formulas

1 year, 8 months ago
image
(A screenshot from the presentation: slideplayer.com/slide/3238789)


We invite all to the open lecture Computer Science of the center devoted to a problem of feasibility of Boolean formulas — one of the most known and important algorithmic tasks. Lecture will take place within a meeting with listeners of an online course "Algorithms: theory and practice. Methods". Time and venue: On December 25, 19:00, BTs of Tayms (St. Petersburg, Kantemirovskaya St. 2A, 4 floor). Participation is free, but registration is required: goo.gl/IiNvV8

Problem of feasibility — a canonical difficult task on which the huge number of researches is carried out: both practical, and theoretical. In particular, annual international conference is devoted to this task. Every year there take place competitions of programs for this task (so-called sat-solver). Such programs are actively used in many application areas. Just several months ago Donald Cnut added volume 4B of the monograph "Programming Art" which third is devoted to a problem of feasibility.

Read more »


Forward, on searches of palindromes 3

1 year, 8 months ago
After seemingly quite good result received in the previous part was only "a local maximum", I for some time threw a problem. I will remind a condition:
"The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number". Or, in Russian: "The decimal number 585 in binary numeral system looks as 1001001001. It is a palindrome in both numeration systems. Find n-y a similar palindrome".

But existence is considerable faster, with essentially other computing complexity, algorithm haunted me, and eventually I returned to its analysis.

Eventually, the algorithm was not such and difficult, but, in my opinion, very beautiful.

Read more »


The fast algorithm for a problem of graph isomorphism is published

1 year, 8 months ago

These two graphs are isomorphic

The mathematician László Babay (László Babai) from faculty of computer sciences and mathematics of the Chicago university provided fast new algorithm for a solution of a problem of graph isomorphism — one of fundamental problems of the theory of complexity of calculations. The algorithm leads a problem very close to a class P. According to some specialists, it is one of the most considerable results in theoretical information science in a decade if not for several decades.

Read more »