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