Теоретический минимум по Computer Science

Этого достаточно, чтобы переводить мысли в вычислимые решения.

1.1. Идеи

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

Блок-схемы

Когда разработчики «Википедии» обсуждали организацию коллективной работы, они создали блок-схему дискуссии. Договариваться проще, если все инициативы перед глазами и объединены в общую картину (рис. 1.1).

Компьютерный код, как и изображенный выше процесс редактирования вики-страницы, по существу является процессом. Программисты часто пользуются блок-схемами для изображения вычислительных процессов на бумаге. Чтобы другие могли понимать ваши блок-схемы, вы должны соблюдать следующие рекомендации[3]:

• записывайте состояния и инструкции внутри прямоугольников;

• записывайте принятие решений, когда процесс может пойти различными путями, внутри ромбов;

• никогда не объединяйте инструкции с принятием решений;

• соединяйте стрелкой каждый последующий шаг с предыдущим;

• отмечайте начало и конец процесса.

Рис. 1.1. Редакционный процесс в «Википедии»[4]

Рассмотрим составление блок-схемы на примере задачи поиска наибольшего из трех чисел (рис. 1.2).

Рис. 1.2. Поиск наибольшего из трех чисел

Псевдокод

Так же, как блок-схемы, псевдокод выражает вычислительные процессы. Псевдокод — это код, удобный для нашего восприятия, но непонятный для машины. Следующий пример передает тот же процесс, что был изображен на рис. 1.2. Задержитесь на минуту и проверьте, как он работает с разными значениями A, B и C[5].

function maximum(A, B, C)

····if A > B

·········if A > C

··············max ← A

·········else

··············max ← C

····else

·········if B > C

··············max ← B

·········else

··············max ← C

····print max

Заметили, что этот пример полностью игнорирует синтаксические правила языков программирования? В псевдокод можно вставлять даже разговорные фразы! Когда вы пишете псевдокод, дайте своей творческой мысли течь свободно — как при составлении блок-схем (рис. 1.3 ).

Рис. 1.3. Псевдокод в реальной жизни[6]

Математические модели

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

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

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

Начнем с того, что именно требуется определить; w и l — это размеры пастбища; w × l — его площадь. Сделать площадь максимальной означает использовать всю проволоку, потому мы устанавливаем связь между w и l, с одной стороны, и 100 мотками, с другой:

l

w

A = w × l

100 = 2w + 3l

Подберем w и l, при которых площадь A будет максимальной.

Подставив l из второго уравнения в первое, получаем:

Да это же квадратное уравнение! Его максимум легко найти при помощи формулы корней квадратного уравнения, которую проходят в средней школе. Квадратные уравнения так же важны для программиста, как мультиварка — для повара. Они экономят время. Квадратные уравнения помогают быстрее решать множество задач, а это для вас самое главное. Повар знает свои инструменты, вы должны знать свои. Математическое моделирование вам просто необходимо. А еще вам потребуется логика.

1.2. Логика