Февраль, 2020

Обработка ошибок и проектирование компилятора

Перевод статьи Error Handling in Compiler Design.

Задача по обработке ошибок (Error Handling) включает в себя: обнаружение ошибок, сообщения об ошибках пользователю, создание стратегии восстановления и реализации обработки ошибок. Кроме того система обработки ошибок должна работать быстро.

Типы источников ошибок

Источники ошибок делятся на два типа: ошибки времени выполнения (run-time error) и ошибки времени компиляции (compile-time error).

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

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

Читать далее Обработка ошибок и проектирование компилятора

Статические и динамические области видимости

Перевод статьи Static and Dynamic Scoping.

Область видимости переменной x это область программы в которой использование имени x ссылается на объявление этой переменной. Одна из причин использование областей видимости — сохранить переменные в разных частях программы отличными друг от друга. Количество коротких имён для переменных ограничено и программисты используют общепринятые имена (например i для индекса массива). В любой программе среднего размера одинаковые названия переменных используются в разных частях программы.

Области видимости делятся на два вида: статические и динамические.

Статические области видимости

Статические области видимости (Static scoping) так же называются лексическими областями видимости (Lexical scoping). В этих областях видимости имена переменных всегда ссылаются на окружение более верхнего уровня. Это свойство текста программы и не связано со стеком вызовов во время выполнения. Статические области видимости упрощают написание модульного кода, так как программист вычисляет область видимости просто смотря на код. В отличии от этого, динамические области видимости требуют от разработчика учитывать все возможные варианты динамического контекста.

Читать далее Статические и динамические области видимости

Python. Структуры данных: список, кортеж, множество, словарь

Перевод параграфа 3.6 Data Structures из книги Intermediate Python.

Python содержит встроенные типы данных: списки, кортежи, словари.

Списки

Чтобы создать список используйте квадратные скобки или функцию list():

my_list1 = [] # Пустой список
my_list2 = list() # Пустой список

1 2	my_list1 = [] # Пустой список my_list2 = list() # Пустой список

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

Первый элемент списка находится под индексом 0, последний — на единицу меньше длины списка.

>>> name = ["obi", "ike", "nwosu"]
>>> name[0]
'obi'
>>> name[1]
'ike'
>>> name[2]
'nwosu'

>>> name = ["obi", "ike", "nwosu"]

>>> name[0]

'obi'

>>> name[1]

'ike'

>>> name[2]

'nwosu'

Метод append() добавляет элемент в список.

>>> name = ["obi", "ike", "nwosu"]
>>> name.append("nkem")
>>> names
["obi", "ike", "nwosu", "nkem"]

>>> name = ["obi", "ike", "nwosu"]

>>> name.append("nkem")

>>> names

["obi", "ike", "nwosu", "nkem"]

Читать далее Python. Структуры данных: список, кортеж, множество, словарь

Отзыв про Стратоплан

Я обучался на Стратоплане с сентября 2018 по май 2019, специальность "Руководитель отдела". Далее я опишу организацию процесса обучения.

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

Занятия

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

У нас занятия проходили в 19 мск. Два раза в неделю, по будням. Одно занятие длилось в среднем час. Занятия проходили по Skype, голосом без видео.

Перед занятием обучающиеся смотрят видео (в среднем 40-60 минут). Кроме видео выдавалась ссылка на страницу с заданием в гуглдоке. На этой же странице ученики пишут ответы на вопросы из задания. Ответы от каждого ученика отдельно, но все видят ответы друг друга. Написание ответа рекомендовалось, но не было обязательным.

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

К конце занятие куратор давал ссылку на страницу с решением от преподавателя и предлагал прочитать и сравнить его с решением группы.

Читать далее Отзыв про Стратоплан

Задача Pythagorean Triplet

Условие

Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).

Решение

Простейшее решение перебором даёт сложность \(O(n^2)\):

for a in range(n):
  for b in range(a + 1, n):
    c = N - a - b
    if is_triplet(a, b, c):
      add_result(a, b, c)

for a in range(n):

for b in range(a + 1, n):

c = N - a - b

if is_triplet(a, b, c):

add_result(a, b, c)

Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.

Эту же задачу можно решить за \(O(n)\). Из условий задачи следуют два уравнения:

\(a + b + c = N\)
\(a^2 + b^2 = c^2\)

\(N\) является константой. Примем так же за константу \(a\). Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

\(c = N - a - b\) (1)
\(c^2 - b^2 = a^2\)
\((c - b)(c + b) = a^2\) (2)
\((n - a - b - b)(n - a - b + b) = a^2\) (подставляем 1 в 2)
\((n - a - 2b)(n - a) = a^2\)
\(n^2 - an - 2nb - an + a^2 + 2ab = a^2\)
\(n^2 - 2an - 2nb + 2ab = 0\)
\((2a - 2n)b = 2an - n^2\)
\(b = \frac{2an - n^2}{2a - 2n}\)
\(c = N - a - b\)

Используя формулы для вычисления \(b\) и \(c\) в цикле по \(a\) находим все пифагоровы тройки.

def triplets_with_sum(number):
    res = []
    n = number
    for a in range(1, number):
        b = (2 * a * n - n ** 2) / (2 * a - 2 * n)
        c = n - b - a

        if round(b) == b and a < b < c:
            res.append([a, b, c])

    return res

def triplets_with_sum(number):

res = []

n = number

for a in range(1, number):

b = (2 * a * n - n ** 2) / (2 * a - 2 * n)

c = n - b - a

if round(b) == b and a < b < c:

res.append([a, b, c])

return res

Курсы на brilliant.org

На brilliant.org находятся курсы по математике и CS (полный список курсов). Курсы построены в полуигровой форме, сначала даётся попытка решить задание, потом краткое объяснение. Задачи направлены на концептуальное понимание тем, теории мало, периодически бывают ссылки на подробное описание.

Большинство задач очень простые, так как темы делятся на маленькие шаги. Например, в теме про наименьшее общее кратное, перед его объяснением проходит более 10 шагов. Часть задач интерактивная, например, связанные с алгоритмами и программированием.

Кроме курсов на brilliant.org есть ежедневные задачи на темы освещенные в курсах и wiki с подробным разъяснением теории.

Курсы платные, примерно 4500р. при годовой подписке.

Задачи на Brilliant.org только на английском, сайт может быть полезен и просто в качестве практики чтения при изучении языка.

Пн	Вт	Ср	Чт	Пт	Сб	Вс
« Янв
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29