Pull to refresh
14
0
Дмитрий @demsp

User

Send message

Планиметрия (прямая и окружность)

Reading time 5 min
Views 6.5K
Задача 1.3
Задача 1.4
Задача 1.5
Задача 1.6
Задача 1.7

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

В данной статье приводятся альтернативные (подсказкам) решения задач из первого раздела приложения Euclidea (геометрические построения с помощью циркуля и линейки).
Читать дальше →
Total votes 9: ↑7 and ↓2 +5
Comments 7

Сравнение алгоритмов сортировки обменами

Reading time 12 min
Views 6.3K

В данной статье рассматриваются различные варианты сортировки обменами, а также даётся описание простого графического приложения (processing.js) с примерами сортировок.

Пузырьковая сортировка


Простейший вариант: перебирать массив от первого элемента к последнему, меняя местами (если потребуется) соседние элементы.

→ Проверить можно здесь

Читать дальше →
Total votes 22: ↑14 and ↓8 +6
Comments 7

К статье о приближениях

Reading time 7 min
Views 7.6K
Часть I
Часть II

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


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

Рассмотрим метод оценок при решении неравенств.
Дать оценку сверху означает определить максимальное значение, которое может принимать искомая величина.

Предположим, что цена за одну единицу товара может колебаться в пределах от 5 до 10 RUB. Для двух единиц товара оценка сверху составляет 10+10=20 RUB, оценка снизу 5+5=10 RUB.

Рассмотрим задачу из задачника профильной направленности М.И. Башмакова
37. Известны оценки для переменных $ x $ и $ y: 0<x<5, 2<y<3.$

Дайте оценки сверху для следующих выражений:
1. $ 2x+3y $
2. $ xy $

5. $ \frac{ 1 }{y} $
6. $ \frac{ x }{y} $

8. $ x-y $
9. $ 3x-2y $

Указание к решению задач
Для оценки этих значений необходимо воспользоваться следующим свойством числовых неравенств:
Если $a<b$ и оба числа положительны, то $ -a>-b $
Если $a<b$ и оба числа положительны, то $ \frac{ 1 }{a}>\frac{ 1 }{b}$
При умножении членов неравенства на одно и то же положительное число смысл неравенства не меняется, при умножении членов неравенства на одно и то же отрицательное число смысл неравенства меняется на противоположный.
Доказательство (Элементарная математика).
Пусть $a>b$, тогда $a-b>0$. Если $m>0$, то $m(a-b)>0$, так как произведение положительных чисел положительно. Раскрыв скобки в левой части последнего неравенства, получим $am-bm>0$, т.е. $am>bm$. Аналогичным образом рассматривается случай $m<0$.
Точно такой же вывод можно сделать и относительно деления частей неравенства на какое-либо отличное от нуля число, так как деление на число $n \neq 0$ равносильно умножению на число $1/n$, а числа $n$ и $1/n$ имеют одинаковые знаки.


Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Comments 1

RAM-машина

Reading time 3 min
Views 12K

Часть I
Часть II
Часть III
Часть IV
Часть V


На Хабре уже была опубликована статья, посвящённая RAM-машине.
Вообще, статья про RAM-машину есть на Википедии.

RAM-машина, которая упоминается в книге «Построение и анализ вычислительных алгоритмов» (авторы: Ахо, Хопкрофт, Ульман) имеет ограниченный набор арифметических команд (сложение, вычитание, умножение, деление), команду безусловного перехода, две команды условных переходов. У нас же из арифметических команд будут только сложение и вычитание, команды ветвления (переходов) будут идентичными командам, приведённым в книге.

Отличием LIttle Man Computer'а (который я описывал в предыдущих частях цикла) от RAM-машины является механизм, обеспечивающий косвенную адресацию (возможность работать с числом, хранящемся в памяти, как с адресом).

Для того, чтобы работать с числом, хранящимся в памяти, как с адресом, подключим к адресному входу Памяти Данных мультиплексор MUX, осуществляющий выборку между, собственно, адресом (поступающим из Памяти Команд) и числом, представляющем адрес и хранящемся в Памяти Данных.


Читать дальше →
Total votes 29: ↑29 and ↓0 +29
Comments 0

Эзотерический язык LMC

Reading time 15 min
Views 7.6K
Часть I
Часть II
Часть III
Часть IV
Часть V

Данная статья посвящена созданию интерпретатора некого эзотерического языка, в основе которого лежит архитектура Little Man Computer.
Фактически, это эмулятор ассемблера для LMC, только здесь вместо ассемблерных команд
INP (загрузить число в аккумулятор из устройства ввода),
STA (сохранить число из аккумулятора в память),
ADD (прибавить к числу в аккумуляторе число из памяти),
SUB (вычесть из числа в аккумуляторе число из памяти),
OUT (вывести число в аккумуляторе устройство вывода)
… используются спец-символы.
Команды переходов от ячейки к ячейке в памяти команд соответствуют командам, сдвигающим считывающую головку машины Тьюринга в языках brainfuck и P′′.
В языке bf команда + (плюс) производит замену текущего символа $ c $ следующим за ним (в ASCII-таблице) символом $ c_{n+1} $. Так, если на ленте Тьюринга изначально находится символ «0», то команда $ c \rightarrow c_{n+1} $ запишет вместо него символ «1».
Читать дальше →
Total votes 18: ↑16 and ↓2 +14
Comments 4

Низкоуровневый эзотерический язык

Reading time 15 min
Views 6.6K
Эта статья о трансляторе эзотерического языка на TurboAssembler'e (TASM).
P′′ — низкоуровневый язык программирования, созданный в 1964 году Коррадо Бёмом.
Этот язык разрабатывался для реализации циклов без использования оператора GOTO и в данной статье демонстрируется создание такого транслятора на низком уровне, в котором обработка текста программы (строки) производится посредством условных и безусловных переходов, т.е. низкоуровневых эквивалентов оператора GOTO.

Команды языка Brainfuck (за исключением ввода и вывода) могут быть переведены на P′′ и обратно.
Вот здесь уже нельзя выполнить отладку bf-программ в пошаговом режиме (а жаль, visualizer был хорош).

Сперва напишем транслятор на каком-нибудь высокоуровневом языке, например, на Паскале.

Пусть массив data_arr представляет память данных (ленту Тьюринга), пусть строка str_arr содержит команды.

Напишем программу, выводящую символ, ascii-код которого соответствует количеству + (поэтому нам нужны будут только команды + и .)

var
 data_arr:array[1..10] of integer;    // массив данных
 str_arr: string;                     // команды  
 i, j: integer;                       // индексы строки и массива
begin
 j:=1;                  // нумерация элементов массива начинается с единицы
 readln(str_arr);       //считываем строку

 for i:=1 to length(str_arr) do begin    // в цикле обрабатываем строку
  if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
  if (str_arr[i]='.') then write(chr(data_arr[j]));
 end;
end.

bf-код +++++++++++++++++++++++++++++++++. выдаст ! (ascii-код символа ! равен 33 ).

Программу можно проверить в online ide ideone.com
Читать дальше →
Total votes 6: ↑6 and ↓0 +6
Comments 6

Решение задачи о приближении иррациональных

Reading time 24 min
Views 17K
В данной статье рассматриваются различные методы приближений иррациональных чисел. Попутно затрагиваются вопросы, косвенно связанные с темой приближений, такие как решение квадратных уравнений и построения геометрических фигур.



В сборнике Арнольда есть следующая задача

38. Вычислить сумму:

$\frac{ 1 }{ 1\cdot2 } + \frac{ 1 }{ 2\cdot3 } + \frac{ 1 }{ 3\cdot4 } + ... + \frac{ 1 }{ 99\cdot100 }$


(с ошибкой не более 1% от ответа)

Ниже представлен алгоритм для вычисления частичных сумм этого ряда на языке Scheme (Lisp), который позволяет производить вычисления в обыкновенных дробях

#lang racket
(define series_sum
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1 (* n (+ n 1))) (series_sum(- n 1)))
  ) ) )
(series_sum 10)
(series_sum 100)
(series_sum 1000)
(series_sum 10000)
(series_sum 100000)
(series_sum 1000000)

(define series_sum_1
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1.0 (* n (+ n 1.0))) (series_sum_1(- n 1.0)))
  ) ) )
(series_sum_1 10)
(series_sum_1 100)
(series_sum_1 1000)
(series_sum_1 10000)
(series_sum_1 100000)
(series_sum_1 1000000)

Читать дальше →
Total votes 24: ↑18 and ↓6 +12
Comments 26

Проектирование процессора ModelSim

Reading time 17 min
Views 15K

Часть I
Часть II
Часть III
Часть IV
Часть V

Это полная версия предыдущей статьи, к которой добавлены тестбенчи.

Спроектируем Little Man Computer на языке Verilog.

Статья про LMC была на Хабре.

Online симулятор этого компьютера здесь.

Напишем модуль оперативной памяти (ОЗУ), состоящий из четырех (ADDR_WIDTH=2) четырёхбитных (DATA_WIDTH=4) слов. Данные загружаются в ОЗУ из data_in по адресу adr при поступлении тактового сигнала clk.

module R0 #(parameter ADDR_WIDTH = 2, DATA_WIDTH = 4)
(
    input clk, //тактовый сигнал
    input [ADDR_WIDTH-1:0] adr, //адрес
    input [DATA_WIDTH-1:0] data_in, //порт ввода данных
    output [DATA_WIDTH-1:0] RAM_out //порт вывода данных
);
    reg [DATA_WIDTH-1:0] mem [2**ADDR_WIDTH-1:0]; //объявляем массив mem
 
    always @(posedge clk) //при поступлении тактового сигнала clk 
        mem [adr] <= data_in; //загружаем данные в ОЗУ из data_in 
    
    assign RAM_out = mem[adr]; //назначаем RAM_out портом вывода данных
endmodule
Читать дальше →
Total votes 43: ↑43 and ↓0 +43
Comments 1

Проектирование процессора Verilog

Reading time 5 min
Views 21K

Часть I
Часть II
Часть III
Часть IV
Часть V

Спроектируем Little Man Computer на языке Verilog.

Статья про LMC была на Хабре.

Online симулятор этого компьютера здесь.

Напишем модуль оперативной памяти RAM/ОЗУ, состоящий из четырех (N=2) четырёхбитных (M=4) слов. Данные загружаются в ОЗУ из data_in по адресу adr при нажатии на кнопку:
module R0 #(parameter N = 2, M = 4)
(
input RAM_button, //кнопка
input [N-1:0] adr, //адрес
input [M-1:0] data_in, //порт ввода данных
output [M-1:0] RAM_out //порт вывода данных
);
reg [M-1:0] mem [2**N-1:0]; //объявляем массив mem
always @(posedge RAM_button) //при нажатии на кнопку
mem [adr] <= data_in; //загружаем данные в ОЗУ из data_in 
assign RAM_out = mem[adr]; //назначаем RAM_out портом вывода данных
endmodule
Читать дальше →
Total votes 27: ↑27 and ↓0 +27
Comments 4

Проектирование процессора (CPU Design) [First ver.]

Reading time 5 min
Views 22K
Это начальный вариант статьи о процессоре, конечный вариант этой же статьи здесь.

Спроектируем в Logisim'е устройство, позволяющие суммировать наборы чисел, хранящихся в памяти. Возьмем набор восьмиразрядных чисел и подключим его к мультиплексору, переход от одного числа к другому будем осуществлять с помощью счетчика, подключенного к выбирающему входу мультиплексора, а к выходу мультиплексора подключим сумматор и аккумулятор. В качестве тактового генератора будем использовать кнопку. Данные будут загружаться в аккумулятор при отпускании кнопки (это осуществляется с помощью элемента НЕ, подключенного к кнопке).


Total votes 38: ↑37 and ↓1 +36
Comments 22

Проектирование процессора Logisim

Reading time 4 min
Views 64K
Часть I
Часть II
Часть III
Часть IV
Часть V

Одна из глав книги «Код» Чарльза Петцольда посвящена проектированию блоков CPU и в начале главы описывается устройство, позволяющие суммировать наборы чисел, хранящихся в памяти. Спроектируем похожую схему в Logisim. Возьмем набор восьмиразрядных чисел и подключим его к мультиплексору, переход от одного числа к другому будем осуществлять с помощью счетчика, подключенного к выбирающему входу мультиплексора, а к выходу мультиплексора подключим сумматор и аккумулятор. В качестве тактового генератора будем использовать кнопку. Данные будут загружаться в аккумулятор при отпускании кнопки. Это осуществляется с помощью элемента НЕ, подключенного к кнопке. Про реализацию этих функциональных блоков в виде отдельных микросхем далее в статье.

Читать дальше →
Total votes 20: ↑20 and ↓0 +20
Comments 7

Игры на Scheme(Lisp) в среде DrRacket

Reading time 4 min
Views 7.4K
Для запуска программ, приведённых в статье, можно использовать DrRacket. Для начала рассмотрим связь конечного автомата и игрового процесса. Объект управления в игре можно представить в виде конечного автомата. Рассмотрим программу, моделирующую светофор. Этот пример был описан в предыдущей статье.

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

image
Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Comments 6

Как проектировать программы (HtDP)

Reading time 6 min
Views 17K
Следующая статья о том, как писать игры на Scheme

Учебник HtDP (How to Design Programs), посвящен программированию на языке Scheme в среде drRacket.
drRacket можно скачать с сайта.
Вводная часть учебника содержит описание функции empty-scene, предназначенной для работы с изображениями. Например, эта программа создает пустую сцену

#lang racket  
(require 2htdp/image)      ;библиотека для работы с изображениями 
(empty-scene 100 60)     ;сцена (канвас) размером 100х60 

Читать дальше →
Total votes 7: ↑7 and ↓0 +7
Comments 5

MASM, TASM, FASM, NASM под Windows и Linux

Reading time 5 min
Views 163K
В данной статье я хочу рассмотреть вопросы, которые могут возникнуть у человека, приступившего к изучению ассемблера, связанные с установкой различных трансляторов и трансляцией программ под Windows и Linux, а также указать ссылки на ресурсы и книги, посвященные изучению данной темы.

MASM


Используется для создания драйверов под Windows.
Читать дальше →
Total votes 33: ↑29 and ↓4 +25
Comments 27

Information

Rating
3,871-st
Registered
Activity